SHA-2 is a family of algorithms published by NIST in 2001 as part of the Federal Information Processing Standard. The NSA designed them to succeed SHA-1. They use Merkle-Damgård construction with a Davies-Meyer compression function.

SHA-256 is one of those algorithms. It is one of the most widely implemented and used software. It is a cornerstone of modern internet communications, seeing use in TLS, SSL, PGP, SSH, and DKIM message signing. Debian uses it to authenticate its software packages and for secure password hashing. Several cryptocurrencies also use it to verify transactions. Last time, we looked at why cryptographic hashes are important (link). This time, we'll look into the workings of SHA-256.

Peeling Back The Onion

SHA-256, short for Secure Hashing Function, is a cryptographic hashing function that produces 256-bit digests (hence the number). It uses Merkle-Damgård construction with a Davies-Meyer compression function. Merkle-Damgård shows that if a collision-resistant compression function can compress a small message, it can compress longer messages and the whole hash function is collision-resistant. Ralph Merkle proposed it in his 1979 Ph.D. thesis. Ivan Damgård independently proved it as sound (hence the name).

Given a message M, we can compress it by first breaking it up into t-sized blocks (m₁, m₂, m₃, ..., mₙ). If the last message block is smaller than size t, we pad it with zeros. A padding block bookends the message blocks, denoting the end of the message with a 1 followed by a bunch of 0s. The final 64-bits of the block is the size of the original message. Starting with the first block (m₁), we encode each block with our chosen compression function. We use an initialization vector (IV) to encode the first block, and subsequent blocks use the last encoded output (i.e., chaining variable).

SHA-256 uses Merkle-Damgård construction with a Davies-Meyer compression function.

SHA-256 uses the Davies-Meyer one-way compression algorithm. The algorithm encrypts the previous hash value (Hᵢ₋₁) using the current block (mᵢ) as the key. We use the IV (i.e., H₀) to encode the first block. The output of the encryption function is XORed (⊕) with Hᵢ₋₁ to produce Hᵢ. Expressed as an equation, it is:

Hᵢ = Eₘᵢ(Hᵢ₋₁) ⊕ Hᵢ₋₁

One Step At A Time

Let’s break down the SHA-256 hashing algorithm. Say we have a string that we want to hash. We convert that string into an array of bits. That is our message M. If our string is hello world, then turning it into binary gets us:

Next, we append a 1 to mark the end of the message and pad it with 0s.

Afterward, we pad additional zeros until the message, with 64 bits reserved at the end, is a multiple of 512 bits.

The reserved 64 bits are for the size of the original message.

So, our message is ready. Next, we generate our initial hashes.

These are the first 32 bits of the fractional parts of the square roots of the first prime. Now, we generate the constants for the round.

Since our message is so small, we will only need one round. We, first, prepare the message schedule (w) for each 512-bit chunk of our message. Our message is less than 512 bits, so we only need to do this once. We reorganize our message into 32-bit groupings (i.e., words).

Our message schedule needs to have 64 words, so we add 0-words to fill out the remaining spots.

Next, for each zero word that we added, we have to modify it accordingly:

For each index i in w[ 16: 63 ] where w[ i ] is a zero word that we added to pad out the message schedule, calculate s₀.

s₀ = rightrotate(w[ i - 15 ], 7) ⊕ rightrotate(w[ i - 15 ], 18) ⊕ rightshift(w[ i - 15 ], 3)

rightrotate(a, b) means to shift a one bit right b times. Then, add the bits that were shifted off to the beginning of a. rightshift(a, b) is just what it sounds like.

Next, you calculate s₁ like so:

s₁ = rightrotate(w[ i - 2 ], 7) ⊕ rightrotate(w[ i - 15 ], 18) ⊕ rightshift(w[ i - 15 ], 3)

Finally, you calculate the new value of w[ i ] like so:

w[ i ] = w[ i - 16 ] + s₀ + w[ i - 7 ] + s₁

All addition is addition modulo 32 (i.e., you take the sum and get its modulo for 2³²).

Stepping through w[ 16 ], we first calculate s₀.

Then, we calculate s₁.

Now, we calculate the new value of w[ 16 ].

Once we have updated all the zero words, our message schedule is complete.

Now, we need to compress our message. We start by initializing the variables a through h to the current hash values (i.e., h0 through h7).

Then, we run the compression loop:

For i in [ 0, 1, 3, … , 63 ]:

- s₁ = rightrotate(e, 6) ⊕ rightrotate(e, 11) ⊕ rightrotate(e, 25)

- ch = (e and f) ⊕ ((not e) and g)

- tmp1 = h + s₁ + ch + k[ i ] + w[ i ]

- s₀ = rightrotate(a, 2) ⊕ rightrotate(a, 13) ⊕ rightrotate(a, 22)

- maj = (a and b) ⊕ (a and c) ⊕ (b and c)

- tmp2 = s₀ + maj

- h = g

- g = f

- f = e

- e = d + tmp1

- d = c

- c = b

- b = a

- a = tmp1 + tmp2

k[ i ] is the round constant, and all addition is addition modulo 32.

So, for the first round, things go as follows:

There are 64 rounds in total. Afterward, we add each variable to its associated hash. So, the final values are:

The last step is to concatenate all the hashes to get our digest.

Capping It Off

That is SHA-256 in a nutshell. As I alluded to in the opener, SHA-256 is everywhere. In some blockchain systems, SHA-256 is used to verify transactions, secure the data and headers of each block, and more. In other words, SHA-256 is a cornerstone of some blockchain systems.