Step-by-step explanation of SHA256

In today’s information age we need security for our passwords, online transactions, repositories, emails and more. That security is developed with the use of the hash algorithm SHA256 standardized by NIST in FIPS 180-4.

Let's start with preprocessing the message.

Preprocessing the message

When the message is received in bytes at the parameter of SHA256 a few steps are taken before scheduling. Starting with counting the message length.

The message length is counted in bytes (bytes are base-2 strings of 8-bits 0s and 1s) if the message is "abc" then the count is 24 bits. At the end of each message we pad 1 bit (0x80 in HEX).

After the message length is counted and 1 is padded, we pad all 0s (K) till the size ≡ 448 (mod 512), leaving 64 bits free for the counted message length in two 32-bit words (64 bits).

When padding the message is done the block is parsed into 16 - 32-bit words, of which 14 contain the message, and the last 2 words contain the message length in big-endian order (big-endian order means that the MSB is stored in the lowest address and the LSB is stored in the highest level address in register).

After we've padded and parsed the message and stored it in the block, we're ready to schedule the block into 64 - 32-bit words.

Scheduling the message

When the message is scheduled, the pre-processed block is taken and looped through to take each 32-bit word one-by-one out of the block. Then each of the 16 32-bit words get stored at index 0..15.

After we've stored the 16 32-bit words at index 0..15 we're going to take those words and fill index 16..63, we do this by applying σ₁ and σ₀ (σ₁ stands for small sigma 1, and σ₀ for small sigma 0).

NOTE: All additions are done with modulo 2³².

σ₁ rotates index-2 right 17 index positions (meaning it shifts to right 17 times and every bit that shifts outside of the 32-bit word gets appended to the left side of the word) after ROTR XOR is applied (XOR flips the bit in the 32-bit word bit-by-bit, 1 XOR 0 = 1, 0 XOR 1 = 1, 1 XOR 1 = 0, 0 XOR 0 = 0) after each bit is flipped we rotate index-2 right 19 times XOR is applied for the last time, then index-2 is shifted right 10 times (shift right lets the bits fall off the 32-bit word), and return the result of σ₁ + 32-bit word at index-7.

After that σ₀ is applied (σ₀ stands for small sigma 0), σ₀ rotates index-15 right 7 times while XOR flips the bits again then ROTR rotates index-15 right 18 times, XOR is applied one last time, then index-15 is shifted right 3 times and, the result of σ₀ + 32-bit word at index-16 is returned.

From index 16..63 the words received as output from σ₁ and σ₀ are stored as the scheduled message.

So index 0..15 contain the 16 32-bit m-block words and 16..63 the scheduled version of the 16 32-bit m-block words.

Now the message (M) is scheduled we arrive at the last layer of the algorithm, compression.

Compression function

The compression part of the secure hash algorithm is where its power is found.

First we start at the 64 round constants (words) (K) which are declared and represent the first thirty-two bits of the fractional parts of the cube roots of the first sixty-four prime numbers, (resource FIPS 180-4 (NIST)).

Second the 8 words of initial hash values {h0, h1, ..., h6, h7} are declared. The initial hash values consist of the eight 32-bit words in hex, which are gained by taking the first thirty-two bits of the fractional parts of the square roots of the first eight prime numbers (resource FIPS 180-4 (NIST)).

Third the 8 working word variables are declared {a, b, ..., g, h}, and two temporary words (T1, T2).

We start with assigning the 8 initial hash values (h0..h7) to the 8 working variables (a..h). Where {h0=a, h1=b, h2=c, h3=d, h4=e, h5=f, h6=g, h7=h}. The two temporary words use modulo, Σ₁, Σ₀, Ch, Maj, the 64 round constant (K), and the scheduled message (M).

To access each index in K and M and compress the message a 0..63 round loop is used.

NOTE: All additions are done with modulo 2³².

• T1 = h + Σ₁(e) + Ch(e,f,g) + K[i] + M[i]
• T2 = Σ₀(a) + Maj(a,b,c)

NOTE: All of this works at the bit level with boolean logic so if we have NOT(A) where A = 0101, then a becomes 1010.

NOTE: Σ (big sigma) functions are different from σ (small sigma).

• Σ₀ rotates word a right 2 times applies XOR, then rotates word a right 13 times applies XOR, then rotates word a right 22 times, and returns the result of Σ₀.
• Σ₁ rotates word e right 6 times applies XOR, then rotates word e right 11 times applies XOR, then rotates word e right 25 times, and returns the result of Σ₁.
• For Ch word e is simulated bit-by-bit against word f while boolean expression AND is applied, then XOR is applied word e the boolean expression NOT is applied on the entire word then the word is taken and simulated bit-by-bit against the word g while boolean expression AND is applied and returns the result of Ch.
• For Maj word a is simulated bit-by-bit against word b while boolean expression AND is applied, then XOR is applied and the process is repeated for word a and word c, then XOR is applied and the process is repeated for word b and word c, and returns the result of Maj.

NOTE: Σ (big sigma) functions are different from σ (small sigma).

Expanding on the round operation, h = g, g = f, f = e, e = d + T1, d = c, c = b, b = a, a = T1 + T2.

In the final step, the i-th intermediate hash value (Hi) is computed by assigning the initial hash values {h0, .., h7} to {h0..h7 + a..f} where:

Then the message is digested by appending [h0, h1, h2, h3, h4, h5, h6, h7] to return the final 256-bit key.

That's SHA256 explained.

Closing

If you want to stay updated on topics like Systems Thinking, Clear Thinking, Rust, Crypto, and Philosophy, check out X/Twitter, here I’ll update you when new blogs go live.

If you want to see programmed examples Click Here to go to the repository.

If you're building in the crypto space and see some major improvement or if you're just curious and want to connect with a like minded individual,

You can reach me at l@lmpkessels.com or, send me a DM on X/Twitter.