Understanding the SHA Algorithm: A Deep Dive

The Secret Sauce of Cryptography

“Have you ever wondered how your data stays secure while being transferred over the internet?

Recently, while building my P2P-File Sharing Web App, I came across a problem while sharing data, how can I know that my cute little web app is transferring data from sender to receiver without any data leak? After researching, I found out that embedding a data integrity feature will solve this issue, which can be done through the hashing algorithm, and I Stumbled across same thing which is SHA-256, But what is SHA-256?

So, In this tutorial, I am gonna tell you what is and how the SHA-256 algorithm works, along with visual diagrams and an interactive website. I suggest that You just take a pen and a piece of paper for sure if you want to study the actual algorithm behind it, Or you can continue if you are not dumb like me.

If you want the live preview of how SHA-256 creates the final digest then you can check the latest and the updated website here, which illustrates under the hood implementation of SHA-256.

What is SHA?

SHA(Secure Hash Algorithm) is a family of cryptographic functions that is used to provide a secure mechanism to provide a unique, fixed-size representation of data.

Think of it as a digital fingerprint — no matter how big you feed data into, it remains the s same and unique.

The Term “Family,” which I introduced to her,e is most important because,se as it shows, SHA isn’t just a single algorithm but a collection of multiple collections of related functions. Each family has a series of functions such as — SHA-0, SHA-1, SHA-256, and others — that have been designed to address different security needs and performance requirements.

Over the decades vulnerabilities have been found including the computational overhead; which introduced new variants to enhance the security measures and efficiency in computing.

Core Principles

Before diving deeper into the algorithm, we must take note of the core principles which must need to be followed to make SHA more secure.

1. One-Way Functions: Also Known as Trapdoor functions — These are the functions that are easy to do and hard to undo.
2. Avalanche Effect: A small change in the input creates a larger impact on the digest(output) creation.
3. Collision Resistance: It’s extremely difficult to find two different inputs which eventually create the same output.

How SHA Works: Step-by-Step

I guess just explaining the things that how SHA works is bogus and also boring, so I am gonna explain How one of its members, SHA-256 works by which you can relate to how other members of that family work.

So, my flow is going to be simple I will first explain the concept and an example that holds for it.

Step — 1: Message Padding

Before the main hashing process begins, there is some preprocessing must be done so that the input message ensures the necessary algorithm’s requirements. In SHA-256, this process is primarily called message padding.

The primary goal of the padding is to extend the original message so that its length (in bits) is congruent to 448 modulo 512, which is then followed by 64 bits of message length addition, resulting in the final message size being of final length in the multiples of 512 bits.

The word which is mentioned here is multiples of 512 bits, which says that the 512 bits of padding are done for SHA-256, but for different algorithms like SHA-384 and SHA-512 (both part of the SHA-2 family), the padding length of 1024 going to be the same.

Example

A. Original Message — medium

Let’s say you have a message “medium”

The word “medium” has six characters. Each of these is ASCII, and the 8-bit binary looks like this as follows:

• m: ASCII 109 → 01101101
• e: ASCII 101 → 01100101
• d: ASCII 100 → 01100100
• i: ASCII 105 → 01101001
• u: ASCII 117 → 01110101
• m: ASCII 109 → 01101101

So finally, the binary representation of the word “medium” is:

01101101 01100101 01100100 01101001 01110101 01101101

Total bits = 6 x 8 = 48 bits

B. Append a Single ‘1’ Bit

Next, append a 1-bit to mark the end of the original message. The message becomes:

[Original 48 bits] + 1 bit = 48 + 1 = 49 bits

Conceptually:

01101101 01100101 01100100 01101001 01110101 01101101 1

C. Append ‘0’ Bits

For SHA-256, the total length before adding the length field must be 448 bits(which is 512–64).

• Current length = 49 bits
• Zeros needed = 448–49 = 399 zeros.

Append these 399 zero bits:

[Message with 49 bits] + [399 zero bits] = 448 bits total

01101101 01100101 01100100 01101001 01110101 01101101 1 0000...0000

(Here, “0000…0000” represents the 399 zeros.)

D. Append the 64-bit Representation of the Original Message Length

As we know, the original message length is 48 bits long. Now, representing 48 in a 64-bit looks like this:

• 48 in binary is 00110000 in 8-bit format, but we need 64 bits, so we add zeros at the start and make it 64 bits.
• In 64 bits, this becomes

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00110000

E. The Final Message

The final message after padding becomes of size 512 bits, which consists of:

• The original message (24 bits)
• The ‘1’ bit (1 bit)
• The 423 zero bits
• And finally, ly the 64-bit representation of the original message length.

Total length = 24 + 1 + 423 + 64 = 512 bits, which is exactly one block for SHA-256.

Step — 2. Message Schedule

Now that we’ve padded the message “medium” to a 512-bit block, we can proceed to the next step: the Message Schedule.

First, if the message is greater than 512 bits, it is broken into 512 bits of each, but as our message “medium” is settled in the 512 bits of the message,ge we don’t need to take an overhead of it.

I will try my level best to explain the process in easy steps; the process goes like this:

2.1 — Splitting the 512-bit block into 16 Words

First, I will explain the meaning of the “word” in the context of message scheduling.

So, the word is defined as a 4-byte(32-bit) message unit formed of the current 512-bit block. So here is the breakdown:

• Block Size: SHA-256 processes data in 512-bit blocks
• Word Size: Each 512-bit block is then divided into 16 words, where each word is 32 bits(512 bits ÷ 16 = 32 bits).

As shown above, we first break the 512-bit block off of the message from Step 1 into parallel binary and hex codes and make 16 words (W0 to W15), which looks like this.

W0  = 6D656469 (contains "medi")
W1  = 756D8000 (contains "um" + padding start)
W2  = 00000000 (padding zeros)
W3  = 00000000 (padding zeros)
W4  = 00000000 (padding zeros)
W5  = 00000000 (padding zeros)
W6  = 00000000 (padding zeros)
W7  = 00000000 (padding zeros)
W8  = 00000000 (padding zeros)
W9  = 00000000 (padding zeros)
W10 = 00000000 (padding zeros)
W11 = 00000000 (padding zeros)
W12 = 00000000 (padding zeros)
W13 = 00000000 (padding zeros)
W14 = 00000000 (padding zeros)
W15 = 00000030 (message length: 48 bits)

Now, as we created all of the W’s until 15, we left with W16 to W63, which is then written using the formula.

W[i] = W[i-16] + s0 + W[i-7] + s1

Where:
s0 = (W[i-15] rightrotate 7) ⊕ (W[i-15] rightrotate 18) ⊕ (W[i-15] rightshift 3)
s1 = (W[i-2] rightrotate 17) ⊕ (W[i-2] rightrotate 19) ⊕ (W[i-2] rightshift 10)

I have written the easiest form after researching the web

Those who don’t know what the W[i-15] rightrotate 7 — this indicates that we take the i-15 bit and perform a circular right rotation by 7 bits. This means that the bits removed from the right part will eventually get attached to the left, which means that no information is lost,t which ensures that no data is lost during this mixing process.

So now let’s calculate the value of W16, which fits in the formula like

W[16] = W[0] + s0 + W[9] + s1

First, we need to calculate the s0 and s1 because we know the values of w[0] and w[9].

Calculate s0 and s1:

W1 rightrotate 7  = 00B6DB00
W1 rightrotate 18 = 0001DAF6
W1 rightshift 3   = 0EADB000
s0 = 00B6DB00 ⊕ 0001DAF6 ⊕ 0EADB000 = 0E1C61F6

Similarly, from the formula, we can calculate s1

W14 rightrotate 17 = 00000000
W14 rightrotate 19 = 00000000
W14 rightshift 10  = 00000000
s1 = 00000000 ⊕ 00000000 ⊕ 00000000 = 00000000

Final W16 calculation

W16 = W0 + s0 + W9 + s1
W16 = 6D656469 + 0E1C61F6 + 00000000 + 00000000
W16 = 7B81C65F

This process is undergoes from the rest of the words until from W17 to W6,3, which is a new word created using the previous one created before.

Step — 3. Compression Functions

This is the most important part of the hashing algorithm because this is the place where we mix up the things to make it as secure as possible.

3.1. Initialization of Working Variables

Before starting the rounds of processing which is generally a for loop running 64 times, SHA-256 begins by setting up the eight working variables.

These working variables (often labeled as a, b, c, d, e, f, g, h) are derived from my favorite numbers — Prime numbers, in this way.

• a = H₀
• b = H₁
• c = H₂
• d = H₃
• e = H₄
• f = H₅
• g = H₆
• h = H₇

For example, let us want the value of H₀, then it is found by considering only the fractional part of the square root of the first prime number, which is sqrt(2), which roughly equals 1.41421356237 and then multiplying the fractional part with ²³² and then taking the integral part which in result gives the 32-bit number.

The result then finally being converted to the Hexadecimal, If anyone finds it confusing then I mentioned an image below, which you can refer to for understanding.

Similarly, we calculate the other eight values of H ranging from (H₁ to H₇).

As we did this for H, we need to calculate the constant K’s, but the change here is instead of sqrt of prime numbers in H, we calculate cube root from 0 to 63(K0 to K63) of the first 64 prime numbers.

After carefully observing, we concluded that these two variable values always remain constant (H and K), No matter what your message is.

a = H0 = 0x6a09e667
b = H1 = 0xbb67ae85
c = H2 = 0x3c6ef372
d = H3 = 0xa54ff53a
e = H4 = 0x510e527f
f = H5 = 0x9b05688c
g = H6 = 0x1f83d9ab
h = H7 = 0x5be0cd19

K[0] = 0x428a2f98
K[1] = 0x71374491
...
K[63] = 0xc67178f2

3.2. Processing in 64 Rounds

The core compression occurs here in the form of a for loop, which is specifically called a loop of 64 rounds from 0 to 63. In each round, the algorithm uses the previous iteration from the message schedule and is constantly specific to the round. In this way, each round will upgrade the set of variables, which, as a result, is a mix of bits thoroughly.

For every round (For loop), the following things happen one after another:

A. T1 Calculation

T1 = h + Σ1(e) + Ch(e, f, g) + K[i] + W[i]

• h = current value of the working variable h.
• Σ1​(e): A function that does several-bit rotation specifically on the letter e. For example, it might rotate e right by 6, 11, and 25 bits and then do the XOR operation on the results. Here the rotation is similar to what we studied before in the message scheduling.
• Ch(e, f, g): The “Ch” here is a chosen operation between f and g, based on the positional value of the e. In simple terms, for each bit position, if the corresponding bit of e is 1, then we take a bit from f else we choose g.
• K[i]: A constant unique to the current round.
• W[i]: The i^{th} word from the message schedule

B. T2 Calculation

T2 = Σ0(a) + Maj(a, b, c)

• Σ0​(a): Similar to Σ01(e) but applied to A, it rotates a right by a few different amounts(For example, by 2, 13, and 22 bits) and does the XOR operations on the results.
• Maj(a, b, c): As the name suggests, it’s a majority function. For each position, it takes the majority bit value(i.e., the bit that appears in at least two out of the three variables a, b,c).

C. Update the Working Variables

After T1 and T2 calculations, we then calculate the rest of the values as shown here.

h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1+ T2

3.3. After 64 Rounds: Updating the Hash Values

Once all 64 rounds are complete, the working variables are combined, and new values are introduced in them, which then results in updated hash values (H0 to H7) using the below formulas:

H0 = H0 + a
H1 = H1 + b
H2 = H2 + c
H3 = H3 + d
H4 = H4 + e
H5 = H5 + f
H6 = H6 + g
H7 = H7 + h

So this is the end of the compression functions also, whose result is concluded like this

Initialize:
  a = H₀, b = H₁, c = H₂, d = H₃, e = H₄, f = H₅, g = H₆, h = H₇

For i = 0 to 63:
  T₁ = h + Σ₁(e) + Ch(e, f, g) + K[i] + W[i]
  T₂ = Σ₀(a) + Maj(a, b, c)
  h = g
  g = f
  f = e
  e = d + T₁
  d = c
  c = b
  b = a
  a = T₁ + T₂
After Rounds:
  H₀ = H₀ + a
  H₁ = H₁ + b
  ...
  H₇ = H₇ + h

Step — 4. Producing the Hash Digest

As in the previous step, we created the updated hash values, for the word “medium”.

H₀ = c082456a
H₁ = 7766e23a
H₂ = 18db084c
H₃ = d34b6ff5
H₄ = 10baef50
H₅ = 6548b897
H₆ = cc80e9b7
H₇ = d3e121c8

After combining or specifically concatenating all of them, we have this value as a final SHA-256 digest.

c082456a7766e23a18db084cd34b6ff510baef506548b897cc80e9b7d3e121c8

Conclusion

From Message Padding to the compression function and then the final construction of the message digest, we have uncovered the Step-by-Step approach of the SHA-256 algorithm.

So this ends our talk for SHA-256, which started with just a problem of data integrity maintenance in P2P-file-sharing to a message digest creation. In the upcoming articles, I will try my level best to show how I implemented this feature on my web App. So stay tuned and keep grinding.