Secure Hash Algorithm 2, 256-bit
Secure Hash Algorithm 2, 256-bit (SHA-256) is a cryptographic hash function belonging to the SHA-2 family of hash functions. First published by the United States National Security Agency (NSA) in 2001, SHA-256 is now formally standardized in the Federal Information Processing Standards Publication 180-4 (FIPS 180-4). SHA-256 is an iterative, one-way cryptographic hash function that can process a message to produce a 256-bit condensed representation called a digest. Any change to the message will, with a high probability, result in a different digest, enabling SHA-256 to determine the message’s integrity.
Notation and Conventions
The following symbols and terminology related to bit strings and integers will be used.
- A number with the prefix $\text{0b}$ means such number is in base 2 (binary). Similarly, a number with the prefix $\text{0x}$ means such number is in base 16 (hexadecimal).
- A hex digit is the representation of a 4-bit number and is an element of the set ${\text{0x0}, \text{0x1},…, \text{0x9}, \text{0xa},…, \text{0xf}}$. For example, the hex digit $\text{0x}7$ represents the 4-bit number $\text{0b}0111$, and the hex digit $\text{0xa}$ represents the 4-bit number $\text{0b}1010$.
- An integer between $0$ and $2^{32} -1$ inclusive may be represented as a 32-bit data type. The least significant four bits of the integer are represented by the right-most hex digit of the integer representation. For example, the decimal integer $291$ is represented by the hexadecimal integer $\text{0x}00000123$.
Mathematical Symbols
| $\land$ | Bitwise conjunction (AND) |
| $\lor$ | Bitwise inclusive disjunction (OR) |
| $\oplus$ | Bitwise exclusive disjunction (XOR) |
| $\neg$ | Bitwise complement (NOT) |
| $\gg$ | Bitwise right-shift |
Constants
SHA-256 uses the same sequence of 64 constant 32-bit integers denoted as $K_0, K_1, …, K_{63}$. The 64 integers are listed below:
| 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 |
These integers represent the first 32 bits of the fractional parts of the first 64 prime numbers’ cube roots.
Operations and Functions
The following operation defines a circular shift (rotation) of $x$ by $n$ positions to the right, where $x$ is a 32-bit integer:
\[\displaystyle \text{ROTR}(x, n) = (x \gg n) \lor (x \ll 32 - n)\]Furthermore, the following logical functions are used:
\[\displaystyle \text{Ch}(x, y, z) = (x \land y) \oplus (\neg x \land z)\] \[\displaystyle \text{Maj}(x, y, z) = (x \land y) \oplus (x \land z) \oplus (y \land z)\] \[\displaystyle \Sigma_0(x) = \text{ROTR}(x, 2) \oplus \text{ROTR}(x, 13) \oplus \text{ROTR}(x, 22)\] \[\displaystyle \Sigma_1(x) = \text{ROTR}(x, 6) \oplus \text{ROTR}(x, 11) \oplus \text{ROTR}(x, 25)\] \[\displaystyle \sigma_0(x) = \text{ROTR}(x, 7) \oplus \text{ROTR}(x, 18) \oplus (x \gg 3)\] \[\displaystyle \sigma_1(x) = \text{ROTR}(x, 17) \oplus \text{ROTR}(x, 19) \oplus (x \gg 10)\]Preprocessing
Preprocessing consists of three steps: padding the message, parsing the message into blocks, and setting the initial hash value.
Padding
Let $M$ denote the raw message (in bits) and let the length of message $M$ be denoted as $l$ (in bits, $0 \leq l < 2^{64}$).
- Append a single "1" bit to the end of $M$.
- Append $k$ "0" bits, where $k$ is the smallest non-negative solution to: $$ l + 1 + k \equiv 448 \bmod 512 $$
- As $l$ can be represented by a 64-bit integer, the final 64 bits are reserved for representing $l$.
For example, the message “abc” has a length of $l=24$ bits, so the message is padded with a single “1” bit, then 423 “0” bits, and then the 64-bit message length $l$ to become the 512 padded message:
\[\displaystyle \text{0b}\underbrace{01100001}_{\textbf{"a"}} \underbrace{01100010}_{\textbf{"b"}} \underbrace{01100011}_{\textbf{"c"}} \overbrace{1}^{\text{single "1" bit}} \;\; \overbrace{000...00}^{\text{423 "0" bits}} \overbrace{\text00...\underbrace{011000}_{l = 24}}^{\text{64 bits}}\]Parsing
The message and its padding must be parse into $N$ 512-bit blocks $M^{(1)}, M^{(2)}, …, M^{(N)}$. Furthermore, each 512-bit block can be divided into sixteen 32-bit integers:
| $M^{(1)}_0$ | $M^{(1)}_1$ | $\cdots$ | $M^{(1)}_{6}$ | $M^{(1)}_7$ | $M^{(1)}_8$ | $\cdots$ | $M^{(1)}_{15}$ |
| $M^{(2)}_0$ | $M^{(2)}_1$ | $\cdots$ | $M^{(2)}_{6}$ | $M^{(2)}_7$ | $M^{(2)}_8$ | $\cdots$ | $M^{(2)}_{15}$ |
| $M^{(3)}_0$ | $M^{(3)}_1$ | $\cdots$ | $M^{(3)}_{6}$ | $M^{(3)}_7$ | $M^{(3)}_8$ | $\cdots$ | $M^{(3)}_{15}$ |
| $M^{(\cdots)}_0$ | $M^{(\cdots)}_1$ | $\cdots$ | $M^{(\cdots)}_{6}$ | $M^{(\cdots)}_7$ | $M^{(\cdots)}_8$ | $\cdots$ | $M^{(\cdots)}_{15}$ |
| $M^{(N)}_0$ | $M^{(N)}_1$ | $\cdots$ | $M^{(N)}_{6}$ | $M^{(N)}_7$ | $M^{(N)}_8$ | $\cdots$ | $M^{(N)}_{15}$ |
Initializing Hash Values
For SHA-256, the initial hash value $H^{(0)}$ is made up of the following 32-bit integers:
\[\displaystyle H^{(0)}_0 = \text{0x6a09e667}\] \[\displaystyle H^{(0)}_1 = \text{0xbb67ae85}\] \[\displaystyle H^{(0)}_2 = \text{0x3c6ef372}\] \[\displaystyle H^{(0)}_3 = \text{0xa54ff53a}\] \[\displaystyle H^{(0)}_4 = \text{0x510e527f}\] \[\displaystyle H^{(0)}_5 = \text{0x9b05688c}\] \[\displaystyle H^{(0)}_6 = \text{0x1f83d9ab}\] \[\displaystyle H^{(0)}_7 = \text{0x5be0cd19}\]These were obtained by taking the first 32 bits of the fractional parts of the first 8 prime numbers’ square roots.
Hashing
When hashing, SHA-256 uses a message schedule of sixty-four 32-bit integers, eight working 32-bit variables, and a hash value of eight 32-bit integers. Each message block $M^{(1)}, M^{(2)}, …, M^{(N)}$ is processed in order, using the following steps:
For $i = 1$ to $N$:
- Prepare the message schedule $W_j$: $$ W_j = \begin{cases} M^{(i)}_j & 0 \le j \le 15 \\ \sigma_1(W_{j-2}) + W_{j-7} + \sigma_0(W_{j-15}) + W_{j-16} & 16 \le j \le 63 \end{cases} $$
- Initialize eight working variables with the $i-1$ hash value: $$ a = H^{(i-1)}_0,\quad b = H^{(i-1)}_1,\quad c = H^{(i-1)}_2,\quad d = H^{(i-1)}_3 $$ $$ e = H^{(i-1)}_4,\quad f = H^{(i-1)}_5,\quad g = H^{(i-1)}_6,\quad h = H^{(i-1)}_7 $$
- For $j = 0$ to $63$: $$ T_1 = \big[h + \Sigma_1(e) + \text{Ch}(e,f,g) + K_j + W_j\big] \bmod 2^{32} $$ $$ T_2 = \big[\Sigma_0(a) + \text{Maj}(a,b,c)\big] \bmod 2^{32} $$ $$ h = g,\quad g = f,\quad f = e $$ $$ e = \big[d + T_1\big] \bmod 2^{32} $$ $$ d = c,\quad c = b,\quad b = a $$ $$ a = \big[T_1 + T_2\big] \bmod 2^{32} $$
- Compute the $i$th intermediate hash value $H^{(i)}$:
After repeating steps one through four above a total of $N$ times (that is, after processing block $M^{(N)}$), the resulting 256-bit message digest is formed by concatenating the eight hash values:
\[\displaystyle \text{digest} = \textbf{CONCAT}\big(H^{(N)}_0, H^{(N)}_1, H^{(N)}_2, H^{(N)}_3, H^{(N)}_4, H^{(N)}_5, H^{(N)}_6, H^{(N)}_7)\]The number of possible digests SHA-256 can generate is $2^{256} \approx 1.15792 \times 10^{77}.$ A brute-force attack against SHA-256 hashes would take a modern GPU ($1.15 \times 10^8$ hashes per second) $2.3 \times 10^{51}$ times the age of the universe to complete.