Hashing or Hash function is a function which will give you a fixed length of output every time, no matter what length of data you give as an input to the function. The values returned by a hash function are called digests, hash values, hash codes, or simply hashes. The benefit of this fixed length output is obvious.
Suppose, you have a hash function that always produces 32-bit output. So instead of dealing with inputs of various lengths (say 8 bit or 128 bit), which can be huge, you only have to deal with 32-bit output every time. This makes computation and keeping tab easy.
Now do not think that this is the hashing blockchain uses. Though the Cryptographic hash is referred to as hash, it is not technically correct. The Cryptographic Hash is different rather it is a specialized case of the general hash function. For example, Cyclic Redundancy Check (CRC) is a hash function but not a cryptographic one.
The cryptographic hash function needs to have mainly five properties that make it a secure and therefore can be considered for cryptographic use.
The Properties of Cryptographic Hash Function
Property 1: Deterministic
What this means is for a particular hash function, the hash or result of a particular input message is always same, no matter how many times you run it through.
Property 2: Quick Computation
The hash function needs to procure output fast enough i.e. process quickly. This is definitely a desired property since it needs to process multiple messages or data, and this allows the system to be efficient.
Property 3: The Avalanche Effect
What happens to the hash if you change a letter of your message or a digit of your data? For a hash function to be a cryptographic hash this slight change should result in a huge change in the output hash.
What happens here is simple. We know that any message, text or numerical, is represented in bits (1 or 0). So, a single character or number change alter the bitstream altogether. The cryptographic hash function now gives an output that is distinctively different than before – a single bit change reflects in more than half the output bits getting flipped. This is also mathematically called the Butterfly Effect.
Check the below image for example:
Property 4: Preimage Resistance
Let us first state what Preimage Resistance is, then we will break it down for you further.
If you know the hash value H(M) it is infeasible to determine the input M. This is what we mentioned earlier make the cryptographic hash function ‘one-way’. Functions that don’t have this property are open to First PreImage Attacks.
On a broader perspective, we should also mention that if H(M1) = H(M2) i.e. the hash value of two different message is the same (will discuss this next), it should be infeasible to find out M2 though you know M1. Lacking this property, such hash functions are vulnerable to the Second Preimage Attacks.
Now we would like to draw your attention to the word ‘infeasible’, not impossible but simply means very difficult. So why do we say it is not impossible?
Well, take the example of rolling a die. For each of the 6 outcomes, we have 6 different hash values. Though in general there is no way to find out the actual outcome from the hashes, if we find out or create a table of hashes for each number (1 – 6), we can consult the table and find out for sure the actual input.
Now, what if this number of input increases say a 32 bit or 128 bit or 256-bit data stream? As you can easily guess, it gets exponentially difficult to create the table, called Rainbow Table, for so many input data. The only option you have now is, take a random input, hash it, and hope that it is the one you are looking for. This is called the “brute-force method.”
In the best case, you will select the input on your first attempt. If this is a 32-bit input data, then the probability of this happening is 1/(2^32) = 2.33 x 10^-10 = 0.000000000233%; now if this is a 128-bit data then chances of the best case scenario is 1/(2^128) = 2.99 x 10^-39% !! See our point, the chances get astronomically slimmer as the range of input increases.
For the worst case scenario, you will only find the hash you need at your last selection. So, for 32-bit data it means after 2^32 – 1 = 4.2949 x 10^9 attempts, and for 128-bit data your luck smiles after you have exhausted 2^128 – 1 = 3.403 x 10^38 options.
Even we consider the average scenario, you find what you need after (2^32)/2 = 2^31 = 2.147 x 10^9 attempts for 32-bit and (2^128)/2 = 2^127 = 1.7 x 10^38 attempts for 128-bit data.
To summarize, though academically not impossible to break the pre-image resistance by using use brute-force method, the number of attempts and therefore time (yes, even with huge computing power) needed makes someone cracking it nearly impossible.
Property 5: Collision Resistant
This is where we address the issue of second pre-image resistance as promised.
The cryptographic hash function demands that for any two given input M1 and M2, their hashes shouldn’t be equal i.e. H(M1) ≠ H(M2) or should be very difficult to find such pair, which is called cryptographic hash collision. Note here that a hash function having collision resistance ensures second pre-image resistance, but not the first.
Now since there is a chance of finding such pair, and hackers can do that with what is known as “the birthday attack.” So how do we avoid this?
The birthday attack exploits what is known in probability theory as birthday paradox or birthday problem. Let us explain as simply as possible.
The chance of two people in a group of 367 people sharing the same birthday is 100%. Astonishingly, the probability of two people sharing their birthdays in a group of 70 people is 99.9%. And the chance of 50% probability of same birthday occurring happens for just about 23 people!
According to the probability theory, for a 50% chance of collision to happen, you need √N (square root) number of items, where N is the total number of possibilities.
For birthday problem, out of 365 different possibilities, you need √365 i.e. about 23 people to have a 50% chance of having the same birthday.
So, let us check what this means in the context for Cryptographic Hash function.
For 128-bit hash, there are 2^128 possibilities, and as per our probability rule, the 50% chance of breaking the collision resistance happens at √(2^128) = 2^64-h instance.
Therefore it is evident that it is much much easier to break the collision resistance of a hash function than to break its preimage resistance. But since even the time needed to do that is so long, we can safely assume that if two hashes match they refer to the same input i.e. if H(M1)=H(M2), then M1=M2.
In order to achieve this collision resistance, hash functions use a paradigm called Merkle–Damgård construction.
The Merkle–Damgård construction or paradigm works on a very simple philosophy – if we have a collision-resistant hash function for short messages, then we can construct a collision-resistant hash function for long messages as well.
Keeping in mind the diagram above, take note of the following points:
- A larger message M can be broken down into smaller blocks of messages, m[i].
- The hash function H consists of lots of smaller hash functions “h”.
- “h” is a smaller hash function which is called compression function. It takes in a small block of the message and returns a hash.
- The first hash function “h” (circled in the diagram above) takes in the first block of the message (m) and adds to it a fixed value IV and returns the hash.
- The hash now gets added to the second block of the message and goes through another hash function h
- This goes on till the last message block where a padding block PB is also added to the message.
- The output of each compression function h is called a chaining variable.
- The padding block (PB) is a string of 1s and 0s. In the SHA-256 algorithm, the PB is 64-bits long.
- The output of the last (rightmost) hash compression function “h” is the output of the large message M.
We will now discuss how does this follow collision resistance.
Now, if “h” is collision-resistant, then “H” should be collision resistant as well.
In order to prove this theorem, we will go in the reverse direction, i.e. if we can prove that collision happens for H, then h also should have a collision.
If there are two messages M and M’, and we are having collisions on both of their hashes that means
H(M) = H(M’)
Therefore we can use it to find out the collision in h. For now, let us find out the chaining variables for both H(M) and H(M’) messages.
For H(M), IV= H(0), H(1),….., H(t), H(t+1) = H(M) : t is any arbritrary number
Now for H(M’), IV= H’(0), H’(1),..…, H’(r), H’(r+1) = H(M’) : r is any arbritrary number which may
or may not be equal to t
Though both hash functions may not have equal number of chaining variables, in both the cases – H(t+1) = H(M) And H’(r+1) = H(M’)
As we know that H(M) = H(M’), and since collision exists, therefore H’(r+1) = H(t+1).
Now let’s refer back to the above diagram again –
Now, let’s check if H(t+1) and H’(r+1) are the last hash values or digests of their respective hash functions then what would be the input message for the last compression function for each
For H(t+1) it would be h(H(t), M(t)||PB)
Similarly, for H’(r+1) that would be h(H’(r), M’(r)||PB’)
So, now the question is under what conditions the compression function “h” will be non-collision resistant. The answer is if and only if it gives the same output to inputs which are not similar i.e. –
- H(t) ≠ H’(r)
- M(t) ≠ M’(r)
- PB ≠ PB’
Now if these outputs are same then we have to dig deeper.
If PB = PB’ then we know for sure that both have the same number of message blocks i.e. t = r which means:
M(t) = M’(r) And H(t) = H’(r)
In this case, since the value of t and r are the same, we can rewrite H(t) and H’(r) as H’(t)
So let’s see what would be the value of H(t) and H’(t) –
H(t) = h(H(t-1), M(t-1)) and H’(t) = h(H’(t-1), M’(t-1))
Since H(t) = H’(t), therefore h(H(t-1), M(t-1)) = h(H’(t-1), M’(t-1))
For a collision to occur, the following conditions must be met:
H(t-1) ≠ H’(t-1)
M(t-1) ≠ M’(t-1)
Now, if these conditions are held true, then we know for sure that we have fianlly found a collision on ‘h’
Let’s see what happens if those conditions are true.
Here H(t-1) = H’(t-1), and since we already know that M(t) = M’(t),
Therefore M(t-1) = M’(t-1).
We can now continue the calculations for H(t-1) and H’(t-1) all the way back until we reach the very first input message. In that case any one of the following two conditions must hold:
- Find collision for ‘h’.
- All message blocks of M and M’ have to be the same.
Now, since we already know that the prime condition for a collision to happen is that the input message M and M’ cannot be the same, the only way the collision of H happens is if the compression function h also has a collision.
Therefore, it is proven that for every hash function H with a collision, we have a compression function h that has a collision, and thus the Merkle-Damgard holds true.
All these are the main five properties of cryptographic hash functions, but this last one is also has a very high value.
Property 6. Puzzle-friendly
This property states that if you take any random value (message or number) k from a distribution of high min-entropy, for every output Y, it is infeasible to find another message x so that H(k|x) = Y.
Let us explain what min-entropy is then we will elaborate on this property.
A distribution or set of message or data is said to have min-entropy if the distribution is so large that the probability of us picking up a certain message or number while choosing randomly can be considered very very low or negligible.
What this means is, the distribution of selecting a random number from a dice (1 -6) has low min-entropy. But the distribution of selecting a lottery number from say 6-digit string has high min-entropy.
Now, the I sign denotes concatenation. This simply means joining the two strings together, i.e. in this case when ‘k’ is concatenation with ‘x’ it becomes ‘xk’. A better example would be (Crypto | Currency) = CryptoCurrency.
So what the property means is a hash function will be called cryptographic if, for its any output Y, it is infeasible to find a string x such that there is no string k when concatenated with x and then hashed will produce Y.
Length Extension Attack
As mentioned earlier to avoid collision resistance, Merkle–Damgård construction is used, but using it purely also exposes such hash functions to the Length Extension attack.
In simplest terms, if an attacker knows a message M2 and only the length of another message M1, then he or she can use the hash of M1 i.e. H(M1) to find out H(M1|M2) i.e. the hash value of M1 and M1 concatenated.
What the attacker can do now is he or she can alter the internal state of the message. This attacker now adds extra information (bit string) at the end of the message and create a valid hash.
Popular cryptographic hash functions like the SHA-256, SHA-512 or other functions like MD5, SHA-1, RIPEMD-160, Whirlpool all use the Merkle–Damgård paradigm and therefore are vulnerable to the Length Extension Attack.
However hash functions like SHA-3, truncated SHA-2, HMAC and BLAKE-2 are not at all vulnerable to the length extension attack, making them heavy security.
That is why the Merkle–Damgård construction are tweaked a bit to safeguard against such attacks.
Narrow Pipe to Wide Pipe Construction
In Merkle–Damgård construction’s straightforward usage, the size of the hash output is equal to the internal state size (between each compression step), resulting in a what is called narrow-pipe hash design. This invites for the discussed length-extension attacks, as well as multiple security issues such as multi-collisions, long message attacks, generate-and-paste attacks etc.
This is where the Wide Pipe construction of Merkle–Damgård comes in. In this case, it has a larger internal state size i.e. the bit-length that is internally used is larger than the output bit-length.
Apart from the tweak t of the Merkle–Damgård construction, the Wide Pipe construction also includes new constructions like the sponge construction and HAIFA construction.
Some Examples of Cryptographic Hash Functions
Before we delve in details about a few of the popular cryptographic hash functions currently in use, let us give you near-exhaustive examples of cryptographic hash functions –
All of these are unkeyed cryptographic hash examples –
- BLAKE-256 – This is a 256 bits hash function based on HAIFA structure.
- BLAKE-512 – This is a 512 bits hash function based on HAIFA structure.
- BLAKE2s – This is a type of cryptographic hash function that goes up to 256 bits and it’s based on HAIFA structure.
- BLAKE2b – This is a type of cryptographic hash function that goes up to 512 bits and it’s based on HAIFA structure. It is used by ZCash and faster than the recent SHA-3.
- GOST – This is a 256 bits hash.
- HAS-160 – This is a 160 bits hash.
- HAVAL – This is a type of hash that has a range of 128 to 256 bits.
- JH – This is a type of hash that has a range of 224 to 512 bits.
- MD2 – This is a 128 bits hash.
- MD4 – This is a 128 bits hash.
- MD6 – This is a type of cryptographic hash function that goes up to 512 bits and it’s based on Merkle tree NLFSR.
- MD5 –This is a 128 bits hash function based on Merkle–Damgård construction. It’s complex hence slower than MD-4.
- RIPEMD – This is a 128 bits hash.
- RIPEMD-128 – This is also a 128 bits hash.
- RIPEMD-160 – This is a 160 bits hash. This is used by Bitcoin Script.
- RIPEMD-320 – This is a 320 bits hash.
- SWIFFT – This is a 512 bits hash.
- Whirlpool – This is a 512 bits hash as well.
- SHA-1 – This is a 160 bits hash function based on Merkle–Damgård construction.
- SHA-224 – This is a 224 bits hash function also based on Merkle–Damgård construction.
- SHA-256 – This is a 256 bits hash function based on Merkle–Damgård construction. Both Bitcoin and Bitcoin Script also uses this hash function.
- SHA-384 – This is a 384 bits hash function based on Merkle–Damgård construction.
- SHA-512 – This is a 512 bits hash function based on Merkle–Damgård construction.
- SHA-3 (a.k.a Keccak) – This is a hash function based on Sponge function and has an arbitrary bits length. Ethereum uses this one.
- Streebog – Another Merkle–Damgård construction-based cryptographic hash function with a range from 256 to 512 bits.
- Tiger – This is a 192 bits hash function based on Merkle–Damgård construction.
- Skein – This is a cryptographic hash function based on Unique Block Iteration and has an arbitrary bits length.
- Spectral Hash – This is a 512 bits hash function based on Wide pipe Merkle–Damgård construction.
You can easily figure out after how many hashes or instances you can break collision resistance for each of them. For example, we would like to mention that though falls under the family of very popular hash functions, MD4, MD5, and SHA-1 are not recommended anymore as their collision resistances are already broken.
Hashing and Data Structures
A data structure is a specialized way of storing data. There are two data structure properties that are critical if you want to understand how a blockchain works. They are as follows:
- Linked Lists.
Variables are used in programming to store data. So, if we have something like this in programming:
int a = 1;
What this means is that we are declaring an integer variable a and are storing the value 1 in it.
Pointers are variables in programming which stores the address of another variable. This is why they are called pointers because they are literally pointing towards the location of other variables.
Also, a hash pointer is a variable that saves the address of another variable along with the hash of the data stored in the variable.
You see the data structure above, that’s called a linked list. It is a sequence of blocks, each containing data which is linked to the next block via a pointer. The pointer variable, in this case, contains the address of the next node in it and hence the connection is made. The last node, as you can see, has a null pointer which means that it has no value.
There is one important thing to note here.
There is a pointer in each block which contains the address of the next block. That is how the pointing is achieved and the blocks are linked to one another.
So, you might be thinking that the structure looks pretty familiar right?
Turns out, that a blockchain is basically a linked list where each block is pointing to the next one with a hash pointer. Each block in the chain stores the hash of the data of the previous block.
This is how the blockchain gains its immutability.
- Suppose a hacker tries to tamper with the data in the 3rd block of the blockchain
- Because of the snowball property, it drastically changes the hash of the block which is stored in block 4
- This goes on until the end of the chain until it freezes the whole chain
- Since that is a theoretical impossibility, the blockchain is immutable.
Alright, so that’s what hashing does and how cryptographic hashing algorithm works.
Hashing Application: Digital Fingerprints
Let’s explore the most important application of hashing in the blockchain, digital fingerprints aka digital signatures. To understand what digital signatures do, let’s think about what an actual signature does.
What are the “properties” of a typical signature? When you put your signature on a piece of paper, what should it be able to do?
- It should be able to provide proper verification. So, the signature should basically be able to verify that it is you who actually signed the paper.
- A good signature should be impossible, or at least very hard to forge. This maintains the uniqueness of the signature
- The final property is non-repudiation. In simpler terms, it means that If you have signed something with your signature, then you should not be able to take it back or claim that someone else has done it instead of you.
Now, we know that this is what a signature SHOULD do, but having said that, the reality is that in the real world, no matter how intricate the signature, there are always chances of forgery, and you cannot really verify signatures using simple visual aids, it is very inefficient and non-reliable.
And this is exactly where digital signature/fingerprint comes in. Digital fingerprints are extremely important for message integrity.
Remember the determinism property of the hash functions? So, suppose you and your friend have a message and both of them produce the same hash, then, needless to say, both of you have the same message.
In fact, let’s look at another property of hash functions to see how message integrity can be achieved.
Suppose we want to test 4 of our friends for their honesty. How exactly are we going to do that with hash functions?
- We will create a random message M and create its hash H(M).
- We will send the message to a friend and tell them to send it to the next.
- Finally, when everyone has checked the message, you will get the message back at the end.
At this point, you are going to check the hash of your final message again. If the hash is any different, then you know that someone has tampered with it. This happens because of the snowball property of the hash functions. If your friends have tampered with it even a little bit, your hash is going to change significantly.
There is another useful hash function which lends itself to better digital signatures.
Hash functions have preimage resistance. So, whenever a message has been hashed, it is impossible to obtain the original message from the hash. Think about it like this:
The tree is the original message and the book is the hash. It is impossible to know which trees were used to make this book.
Ok, so how is that useful in digital signatures? How about password storage?
Think of the last time that you created an account, let’s say your Netflix account. For creating these accounts you need to submit your email ID (a unique identifier since no two people can have the same email ID) and a password. Now, this is where we encounter a problem.
80% of the password that we use are one and the same. Most of the time, we use the same password for Facebook, email, Netflix, and maybe even Paypal!
So, if someone does hack the database of these servers, they can basically gain access to our entire life and, in the process, compromise our privacy.
This is the reason why these servers don’t save the actual password, they save the hash of the passwords. So, this way if someone gets their hands on the hash, it will still be impossible for them to get the original password, thanks to the preimage resistance. However, that’s not the only layer of protection that’s used.
These websites sometimes also add a random string in front of the password to add even more randomness to the hash. This makes it even harder for attackers to guess the password.
Up next, we are going to take a look at one of the most important implementations of hashing, the Merkle Tree.
What is Merkle Tree?
If you take a look at Bitcoin’s block header, then this is what you will see:
A block header contains:
- Version: The block version number.
- Time: the current timestamp.
- The current difficult target. (More on this later).
- Hash of the previous block.
- Nonce (more on this later).
- Hash of the Merkle Root.
Alright, so you see the term “Merkle Root”? It is actually the core of the Merkle Tree.
This right here, is the Merkle Tree:
You see that diagram above? That is the Merkle Tree.
In a Merkle tree, each non-leaf node is the hash of the values of their child nodes. Leaf Node: The leaf nodes are the nodes in the lowest tier of the tree. So wrt the diagram above, the leaf nodes will be L1, L2, L3, and L4.
So, what do Child Nodes and Merkle Root (aka Root Node) mean?
Child Nodes: For a node, the nodes below its tier which are feeding into it are its child nodes. Wrt the diagram, the nodes labeled “Hash 0-0” and “Hash 0-1” are the child nodes of the node labeled “Hash 0”.
Root Node: The single node on the highest tier labeled “Top Hash” is the root node.
Alright, so that’s pretty cool, but what exactly does that have to do with blockchains? Well, let’s check it out.
Each and every block in the blockchain contains thousands of transaction. As a result, it is really inefficient to store them in their entirety inside the block. Plus, it makes auditing an absolute nightmare. However, what happens if you use a Merkle Tree here?
Now, what happens if you want to access this particular data:
If a Merkle tree wasn’t put in place, you would have had to go through each and every single ounce of data to get to your desired goal. However, what happens if we implement a a merkle tree? Now you can simply track down the data by following a trail of hashes?
As you can imagine, this significantly cuts down the time taken.
Up next, we are going to check out how hashing is used in the proof-of-work mining in bitcoin.
What is Proof-of-Work?
When we say “mining”, it basically means searching for a new block to be added in the blockchain. Miners from around the world are constantly working to make sure that the chain keeps on growing. Earlier it used to be easy for people to mine using just their laptops, but over time, people started forming mining pools to pool in their computer powers and mine more efficiently.
This, however, could have been a problem. There is a cap for each cryptocurrency, eg. for bitcoin, it is just 21 million. There are only 21 million bitcoins out there. If the miners are allowed to carry on, at this rate, they will fish out all the bitcoins in existence. On top of that, there needs to be a specific time limit in between the creation of each blocks. For bitcoin, the time limit in between block creation is 10 mins. If the blocks were allowed to be created faster, it would result in:
- More collisions: More hash functions will be generated which will inevitably cause more collisions.
- More orphaned blocks: If a lot of miners are over mining they will come up with new blocks simultaneously. This will result in or more blocks not getting to be part of the main chain and becoming orphan blocks.
So, in order to restrict block creation, a specific difficulty level is set. Mining is like a game, you solve the puzzle and you get rewards. Setting difficulty makes that puzzle much harder to solve and hence more time-consuming. WRT bitcoins the difficulty target is a 64-character string (which is the same as a SHA-256 output) which begins with a bunch of zeroes. A number of zeroes increases as the difficulty level increases. The difficulty level changes after every 2016th block.
So, now that we have established that, let’s check how POW works with context to our example given above. Suppose a general wants to communicate with another general. How do you think it will go down?
The steps will be:
- The miners try to solve cryptographic puzzles to add a block to the blockchain.
- The process requires a lot of effort and computational power.
- The miners then present their block to the bitcoin network.
- The network then checks the authenticity of the block by simply checking the hash, if it is correct then it gets appended to the blockchain.
- So, discovering the required nonce and hash should be difficult, however checking whether it is valid or not should be simple. That is the essence of proof-of-work.
So, with that out of the way, let’s discuss in detail the popular cryptographic hash functions that are in use.
Secure Hashing Algorithm (SHA)
As per Wikipedia, the Secure Hash Algorithms are a family of cryptographic hash functions published by the National Institute of Standards and Technology (NIST) as a U.S. Federal Information Processing Standard (FIPS). SHA is modeled after MD4. This family includes the following hash functions:
- SHA-0: Named SHA, it is the original version of the 160-bit hash function published in the year 1993. But due to an undisclosed “significant flaw”, SHA was withdrawn shortly after publication and replaced by the slightly revised version SHA-1.
- SHA-1: SHA-1 replaced the SHA-0. So this is also a 160-bit hash function that resembles the earlier MD5 algorithm. This was designed by the National Security Agency (NSA) to be part of the Digital Signature Algorithm. But as soon as cryptographic weaknesses were discovered, the standard was discarded for most cryptographic uses after 2010. So this is no longer in use.
- SHA-2: Designed by the NSA using the Merkle-Damgard paradigm, SHA-2 is basically a family of two similar hash functions but with different block sizes – SHA-256 and SHA-512. While the SHA-256 uses 32-bit words, the SHA-512 uses 64-bit words. There are also truncated versions of each standard, known as SHA-224, SHA-384, SHA-512/224, and SHA-512/256.
- SHA-3: Formerly known as Keccak, SHA-3 was chosen in 2012 after a public competition among non-NSA designers. The latest of the SHA family was released in 2015. It supports the same hash lengths as SHA-2, and its internal structure differs significantly from the rest of the SHA family. SHA-3 provides the same output sizes as SHA-2, i.e. 224, 256, 384 and 512 bits. Ethereum uses this popular hash function.
Check the below image for comparison between different hash functions of SHA family. Courtesy Wikipedia.
Now, let us discuss SHA-256 of SHA-2 and the SHA-3 hash functions in detail.
As explained earlier, the SHA-256 function uses 32-bit words which makes the output 32 x 8 = 256-bit long. Bitcoin and many other cryptocurrencies use SHA-256 algorithm. For example, Bitcoin make use of it in two ways –
Mining – Mining means when blocks are created by miners by solving complex computational puzzles, it gets added to the blockchain. This is called proof of work and this mining process of Bitcoin uses SHA-256 hashing.
Address Creation – The Bitcoin public key is also hashed using the SHA-256 to generate the public address since it adds an extra layer of protection to the key holder’s identity. Additionally, this also makes the hashed address shorter in length than a Bitcoin public key thus helping in storage.
SHA-256 is also used in Proof of Stake algorithm. Today the hash functions are also used in other areas as security measure including TLS and SSL, PGP, SSH, S/MIME, and IPsec.
Currently, the best public attacks break preimage resistance for 52 out of 64 rounds and collision resistance for 46 out of 64 rounds of SHA-256 hash function. It is vulnerable to length extension attack though.
SHA-3 hash function is a subset of the broader cryptographic primitive family known as Keccak. The SHA-3 hash function, the winner of the NIST hash function competition, was not meant as an SHA-2 successor, rather it is an alternative. Since there is no threat to the existing SHA-2 as perceived earlier, there is no need to replace it with SHA-3.
It is used when required in certain applications. Some cryptocurrencies like Ethereum uses the SHA-3 hashing. The SHA-3 is faster than SHA-2 though, and that is due to SHA-3 uses a structure called Sponge Construction.
A sponge construction or sponge function is a class of algorithms with finite internal states that take an input bit stream of any length and produce an output bit stream of any length you want.
In this mechanism, data is absorbed into the sponge, and then the result is squeezed out of it.
In this absorbing phase, those message blocks are XOR-ed into a subset of the state, which is then transformed as a whole using a permutation function f.
Now in the squeeze phase, the output blocks are read from that same subset of the state, alternated with the state transformation function f. The size of the part of the state that is written and read is called the “rate” (denoted as r), and the size of the part that is untouched by input/output is called the “capacity” (denoted as c). The capacity determines the security of the scheme. The maximum security level is half the capacity.
The sponge construction function is stated as Z = sponge[f,pad,r](N,d),
Where N = input bit string
pad = a padding function
f = a permutation function
b = blocks of width, f operates on bit b
r = a rate
d = output length
Z = a bit string of length d
The capacity c is determined as c = b − r
The sponge function works as follows:
- Pad the input N using the pad function, yielding a padded bit string P with a length divisible by r (such that n = len(P)/r is an integer),
- Break P into n consecutive r-bit pieces P0, …., Pn-1
- Next initialize the state S to a string of b number of 0 bits.
- Then absorb the input into the state: For each block Pi,
- extend Pi at the end by a string of c 0 bits, thus yielding one of length b,
- XOR that data with S
- apply the block permutation f to the result, yielding a new state S
- Initialize the Z to be the empty string
- If the length of Z is less than d, then
- append the first r-bits of S to Z
- if Z is still less than d-bits long, then apply f to S, yielding a new state S.
- Otherwise, Z is truncated to a length of d bits
SHA-3 is not vulnerable to length extension attacks like SHA-2 or SHA-1. It is because the internal state S contains c additional bits of information in addition to what is output to Z.
One thing to note here is that SHA-3 is much slower than the other especially the SHA-512 in software implementations, but very much faster than the rest in hardware implementation. Check the image below for collision resistance and preimage resistance scores for various SHA-3 functions.
RIPEMD-160 Hash Function
First published in 1996, RIPEMD is a family of cryptographic hash functions developed in Leuven, Belgium, by Hans Dobbertin, Antoon Bosselaers, and Bart Preneel at the COSIC research group at the Katholieke Universiteit Leuven. This is based on the Merkle–Damgård construction.
RIPEMD hash is based on the design principles of MD4 hash and its performance is very much similar to the SHA-1 hash function. RIPEMD-160 is the 160-bit version of this hash function and commonly used in generating Bitcoin addresses. RIPEMD-160 is tuned for 32-bit processors.
Bitcoin uses both SHA-256 and RIPEMD-160 hash functions for address generation – the bitcoin public key first runs through the SHA-256 and then through RIPEMD-160. The reason why we do that is that the output of 160 bits is a lot smaller than 256 bits which helps in saving up space.
One thing to mention here is that RIPEMD-160 is the only hash function that produces the shortest hashes whose uniqueness is still sufficiently assured.
CryptoNight Hash Function
Cryptonight was originally developed in 2013 as the hash function of Cryptonote, and now serve as the hash function for the popular cryptocurrency Monero. Unlike Bitcoin which is GPU-heavy, Monero chose this because of Cryptonight’s structure.
CryptoNight is defined as, “a memory-hard hash function” which means i is designed in a way to be inefficiently computable on GPU, FPGA, and ASIC architectures.
The first step of the CryptoNight algorithm is initializing a large scratchpad with pseudo-random data. Next multiple read/write operations are performed at pseudo-random addresses contained in the scratchpad. And in the final step, hashing is done on the entire scratchpad to produce the resulting value.
Simply put, it means Cryptonight was designed with the objective of being inefficient for GPUs and ASICs. The scratchpad size is required to be at least of 2MB size as a readily accessible memory to perform the hashing operation and this is exactly what makes it GPU inefficient. In computational terms, 2MB of memory per instance translates into only a limited number of possible parallelized hashing attempts.
Modern ASICs excel at mining SHA-256 because you can run multiple iterations of hashing attempts in parallel within a relatively inexpensive package using a collection of specialized processors. Once you are required to possess 2MB of memory per iteration, the use of specialized processors and even GPUs no longer afford the same advantages over the traditional CPUs used in your average home computer.
The below diagram shows the schematic of the CryptoNight Hash algorithm.
Image Credit: Dave’s Data
All the data and codes are taken from the CryptoNight whitepaper.
Step 1: Scratchpad Initialization
Scratchpad initialization is the first step of the CryptoNight hash function. It happens as follows –
- The input is hashed using Keccak function with parameters seta at b= 1600 and c=512.
- The first 32-bytes of the output of the Keccak hash is interpreted as an AES-256 key (AES) and expanded to 10 round keys.
- Next a scratchpad of 2097152 bytes (2 MiB) is allocated.
- Now bytes 64 to 191 are extracted from the Keccak final state and segmented into 8 blocks of 16 bytes each.
- Then each such block is encrypted using the below mentioned procedure:for i = 0…9 do:
block = aes_round(block, round_keys[i])
- Next AES encryption is performed on each block and the result is then XORed with the round key.
- The output blocks, therefore, become the first 128 bytes of the scratchpad. later the blocks go through encryption again and become next i.e. the second 128 bytes of the scratchpad. This process goes on and on until it is fully initialized.
Image Credit: GitHub. The diagram above shows the schematics of Scratchpad initialization process.
Step 2: Memory Hard Loop
This step is the one which makes the hash very hard to mine for GPUS.
- Firstly, bytes 0…31 and 32…63 of the Keccak output are XORed, and the resulting 32 bytes are used to initialize variables ‘a’ and ‘b’, each 16 bytes of length.
- Then those variables ‘a’ and ‘b’ enter the main loop.
- The loop is then iterated 524,288 times.
- Now in the scratchpad, when a 16-byte value needs to be converted into an address, it is interpreted as a little-endian integer, and the 21 low-order bits are considered as a byte index. But the 4 low-order bits are cleared to ensure the 16-byte alignment.
- The resultant data is then entered into the scratchpad in 16-byte blocks.Let’s look at the pseudo-code now with which each iteration is expressed in:
- In the above code, the 8-byte add function represents each of the arguments as a pair of 64-bit little-endian values and adds them together, component-wise, modulo 2^64. The result is then converted back into 16-bytes.
- On the other hand, the 8-byte_mul function uses only the first 8 bytes of each argument, that are interpreted as unsigned 64-bit little-endian integers and multiplied together. The output is then converted into 16 bytes, and at last, the two 8-byte halves of the result are swapped.
Step 3: The Result Calculation
Lastly, the result calculation steps of CryproNight Hash follows the below steps:
- When the function of memory-hard loop function is over, bytes 32 to 63 of the Keccak output is expanded into 10 AES round keys, and it is done in the same manner as in the first part.
- Bytes 64 to 191 are then extracted from the Keccak state and XORed with the first 128 bytes of the scratchpad function.
- Then the output state is encrypted in similarly like the first part, but this time using the new keys.
- Next, the result is XORed with the second 128 bytes from the scratchpad, encrypted again, and so on.
- Once XORing with the last 128 bytes of the scratchpad is done, the result is encrypted for the last time and then the bytes 64 to 191 in the Keccak state are replaced with the result.
- The Keccak state is then passed through Keccak-f i.e. the Keccak permutation with the parameter b = 1600.
- Next, the two low-order bits of the first byte of the state are used to select a hash function: 0=BLAKE-256 [BLAKE], 1=Groestl-256 [GROESTL], 2=JH-256 [JH], and 3=Skein-256 [SKEIN]. Then the selected hash function is applied to the Keccak state, and the resulting hash is the finanl the output of CryptoNight hash.
Image: Diagram of the final result generation.
Unlike the Scrypt Hashing algorithm, the Cryptonight algorithm is dependent on all the previous blocks for each new block. CryptoNight is very simple and its clever use of native AES encryption and fast 64-bit multipliers makes the algorithm as much CPU-friendly as GPU unfriendly..
CryptoNight in action:
Input: This is a test
Cryptonight uses several hashing functions, including SHA3 along with AES encryption at several stages. Both the hash functions and encryption standard are developed as open source, which shows that Cryptonight team is totally into preserving user privacy and provide the highest levels of security possible.
However, there are some concerns associated with the CryptoNight function.
To date, there are no ASICs that can mine the Cryptonight protocol and the majority of mining takes place using traditional CPUs. The fact that a typical Monero tx is about 13 kb, which is approx 25 times the size of a bitcoin tx is of concern here.
Another issue that has come to light recently is the use of botnets. Due to Cryptonight’s optimization for CPU mining, Botnet has been spread using malware into unsuspecting computers, which are then used to mine Monero. This means there is a risk of a single person who controls a botnet can gain a large proportion of the hash power.
Announced on December 21, 2012, an improved version of the earlier BLAKE function is called BLAKE2. It was created by Samuel Neves, Jean-Philippe Aumasson, Zooko Wilcox-O’Hearn, and Christian Winnerlein based on Dan Bernstein’s ChaCha stream cipher.
Their goal was to replace the then widely used, but broken MD5 and SHA-1 algorithms. When it is run on 64-bit x64 and ARM architectures, the BLAKE2b hash function is faster than SHA-3, SHA-2, SHA-1, and MD5 hash functions
Although neither BLAKE nor BLAKE2 have been standardized like SHA-3, it is widely used in many protocols including the Argon2 password hash due to the high efficiency it offers on modern CPUs. Note here that both BLAKE and BLAKE2 offer the same output sizes as SHA-3.
BLAKE was a candidate for the NIST hash function competition in 2012 but lost to Keccak in the final round
BLAKE2 supports keying, personalization, salting and hash tree modes. It can also give digests starting from 1 up to 64 bytes for BLAKE2b or up to 32 bytes for BLAKE2s hash functions. BLAKE family also has Tparallel versions designed to increase performance on multi-core processors, such as the BLAKE2bp (4-way parallel) and the BLAKE2sp (8-way parallel).
Note here that every BLAKE hash function is not susceptible to the length extension attack.
We have covered the main things you should know about the cryptographic hash function and we also know what they do. So now it is time to show you some of the major applications of it.
The primary use of the cryptographic hash function is to keep the integrity of messages and files and verify them.
A digital signature scheme is possible because of the message integrity property of the cryptographic hash. The fixed and relatively small length makes it perfect for this purpose.
Proof of Work:
As mentioned earlier, mining and adding blocks to the blockchain is primarily possible only because of the unique properties of cryptographic hash functions.
File and Data Identifier:
Hashes are used to identify files on peer-to-peer file-sharing networks, i.e. locating file sources, downloading the file and verifying its contents. Many source code management systems like Git, Monotone or Mercurial use the sha1sum of various types of content (file content, directory trees, ancestry information, etc.) to uniquely identify them. Also, cryptographic hash functions allow the fast lookup of a data in a hash table.
Storing only the hash value or digest of passwords is how this can be done as getting the original password from its hash is ‘infeasible.’ To authenticate a user, the password presented by the user is hashed and compared with the stored hash. The output of a password hash function can also be used as a cryptographic key.
Ok so there you have it. Hashing is the backbone of the blockchain technology, surely you can see that for yourself. Were you able to gain value from this article? Yes or No, do let us know!