Related Tags

# What are the different steps in SHA-256?

Imama Zahoor

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

### Overview

The SHA-256 algorithm is a part of the SHA-2Secure Hashing Algorithm 2, a set of secure cryptographic hash functions used for the protection and encryption of online data.

We can divide the algorithm for SHA-256 into three steps, as outlined below.

### Step one: Appending bits

The first step involves preprocessing the input message to make it compatible with the hash function. It can be divided into two main substeps:

The total length of our message must be a multiple of $512$. In this step, we append bits to the end of our message such that the final length of the message must be 64 bits less than a multiple of 512. The formula below depicts this step:

$m+p=(n*512)-64$

where $m$ = length of the message, $p$ = length of the padding, and $n$ = a constant.

The first bit that we append is $1$ followed by all $0$ bits.

### Length bits

Next, we take the modulus of the original message with 232 to get $64$ bits of data. Appending this to the padded message makes our processed message an exact multiple of $512$.

The image below illustrates the final message after step one is completed.

The original message after preprocessing

### Step two: Buffer initialization

Before we begin carrying out computations on the message, we need to initialize some buffer values. The default eight buffer values are shown below. These are hard-coded constants representing hash values.

A = 0x6a09e667
B = 0xbb67ae85
C = 0x3c6ef372
D = 0xa54ff53a
E = 0x510e527f
F = 0x9b05688c
G = 0x1f83d9ab
H = 0x5be0cd19


Moreover, we have to initialize an array containing $64$ constants, denoted by $k$.

k[0..63] =
0x428a2f98 0x71374491 0xb5c0fbcf 0xe9b5dba5 0x3956c25b
0x59f111f1 0x923f82a4 0xab1c5ed5 0xd807aa98 0x12835b01
0x243185be 0x550c7dc3 0x72be5d74 0x80deb1fe 0x9bdc06a7
0xc19bf174 0xe49b69c1 0xefbe4786 0x0fc19dc6 0x240ca1cc
0x2de92c6f 0x4a7484aa 0x5cb0a9dc 0x76f988da 0x983e5152
0xa831c66d 0xb00327c8 0xbf597fc7 0xc6e00bf3 0xd5a79147
0x06ca6351 0x14292967 0x27b70a85 0x2e1b2138 0x4d2c6dfc
0x53380d13 0x650a7354 0x766a0abb 0x81c2c92e 0x92722c85
0xa2bfe8a1 0xa81a664b 0xc24b8b70 0xc76c51a3 0xd192e819
0xd6990624 0xf40e3585 0x106aa070 0x19a4c116 0x1e376c08
0x2748774c 0x34b0bcb5 0x391c0cb3 0x4ed8aa4a 0x5b9cca4f
0x682e6ff3 0x748f82ee 0x78a5636f 0x84c87814 0x8cc70208
0x90befffa 0xa4506ceb 0xbef9a3f7 0xc67178f2


### Step three: Compression function

Now that we have our message and buffers ready, we can begin computation. Recall that our processed message is $n*512$ bits long. This will be divided into $n$ chunks of $512$ bits. Each of these chunks is then put through $64$ rounds of operations and the output from each round serves as the next input.

The image below illustrates the complete cycle:

The 64 rounds of operation performed on a message chunk

Moreover, each input consists of two constants—$K(i)$ and $W(i)$. $K(i)$ is pre-initialized and $W(i)$ is initialized by breaking each of the $512$ bit chunks into $16$ subblocks of $32$ bits each for the first 16 rounds. After that, $W(i)$ must be calculated at each subsequent round. The following formulas show the calculation:

1. $s^0=(W[i-15]$ right rotate $7)$ XOR $(W[i-15]$ right rotate $18)$ XOR $(W[i-15]$ right shift $3)$
2. $s^1=(W[i-2]$ right rotate $17)$ XOR $(W[i-2]$ right rotate $19)$ XOR $(W[i-2]$ right shift $10)$
3. $W(i) = W[i-16] + s⁰ + W[9-7] + s¹$

Now that we know how a message chunk is processed, let us take a look at each round. Consider the diagram below:

Each round of operation

Each round carries out the following set of computations:

• $Ch = (E$ AND $F)$XOR $(($NOT $E)$ AND $G)$
• $Ma = (A$ AND $B)$XOR $(A$AND $C)$ XOR $(B$ AND $C)$
• $∑A = (A>>>2)$XOR $(A >>> 13)$XOR $(A >>> 22)$
• $∑E = (E>>>6)$XOR $(E >>> 11)$XOR $(E >>> 25)$
• $Am=$(addition) mod (232 )

The output from each round is fed as input to the next round until the last chunk is reached. The output from the last block will be the final hash digest of length $256$ bits.

RELATED TAGS

CONTRIBUTOR

Imama Zahoor