Bitcoin
$5,566.72
-7.16
Ethereum
$173.21
-1.47
Litecoin
$41.08
-1.16
DigitalCash
$131.45
-5.79
Monero
$88.15
-1.86
Nxt
$0.05
0
Ethereum Classic
$7.21
-0.26
Dogecoin
$0.00
-0

Cryptographic Hash Functions – Deep Dive

Hash functions are what makes the blockchain technology, in all of its purpose and intent, “the blockchain technology,” Its encryption or security capability allows the blockchain technology to achive the authenticity of data it needs.

The hash function is a cryptographic algorithm but is different from the other two encrytion echniques – the public key algorithm and the secret key algorithm, as there is no key involved in the encryption process and it is a one-way process i.e. there is no way you can get back the input from the output. We will discuss this later in the article in detail.

What is Hashing or Hash Function?

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?

Birthday Attack

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.

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[0]) 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 (as in SHA-3 which is discussed later in the article) 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.

Now let us 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.

SHA-256

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-256 Encryption:

Input: Hello

Output: 185F8DB32271FE25F561A6FC938B2E264306EC304EDA518007D1764826381969

SHA-3

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.

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.

SHA-3 Encryption:

Input: Hello

Output:efb4a6c7cbf6263be2c615fe97299799310361b3c290591bcc6415f5c4b779244b480453345f754a904aee49289986a0530080d04106b6157a14d6847796b1cf

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.

The above image shows a snapshot of a sub-block from the compression function of the RIPEMD-160 hash algorithm.

RIPEMD-160 Encrytion:

Input: Hello

Output: d44426aca8ae0a69cdbc4021c64fa5ad68ca32fe

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

Output: a084f01d1437a09c6985401b60d43554ae105802c5f5d8a9b3253649c0be6605

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.

BLAKE2

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.

Applications

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.

File Verification:

The primary use of the cryptographic hash function is to keep the integrity of messages and files and verify them.

Digital Signature:

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.

Password Verification:

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.

Conclusion

So we hope that by now you totally understand the how cryptographic hash function works, what makes it so unique and why it is so important for the tremendous rise of our blockchain technology.

Of course, it needs a sheer amount of calculation and that is possible only because of rapid advancement in our hardware capability. As blockchain technology is for masses, cryptographic hash provides the required “as little as needed” operation ability.

The current top and popular hashing algorithms are likely to be obsolete eventually and replaced by better, more secure and efficient hashing algorithms, as evident from the superiority of SHA-3 over SHA-2 or that of BLAKE2b over SHA family. So keep yourself updated as more and more hash inventions are likely to happen in near future.

Leave A Reply

Your email address will not be published.