Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

11.4 SHA-2

In this section and the next, we look at what is involved in making a real cryptographic hash function. Unlike block ciphers, where there are many block ciphers to choose from, there are only a few hash functions that are used in practice. The most notable of these are the Secure Hash Algorithm (SHA) family, the Message Digest (MD) family, and the RIPEMD-160 message digest algorithm. The original MD algorithm was never published, and the first MD algorithm to be published was MD2, followed by MD4 and MD5. Weaknesses in MD2 and MD4 were found, and MD5 was proposed by Ron Rivest as an improvement upon MD4. Collisions have been found for MD5, and the strength of MD5 is now less certain.

The Secure Hash Algorithm was developed by the National Security Agency (NSA) and given to the National Institute of Standards and Technology (NIST). The original version, often referred to as SHA or SHA-0, was published in 1993 as a Federal Information Processing Standard (FIPS 180). SHA contained a weakness that was later uncovered by the NSA, which led to a revised standards document (FIPS 180-1) that was released in 1995. This revised document describes the improved version, SHA-1, which for several years was the hash algorithm recommended by NIST. However, weaknesses started to appear and in 2017, a collision was found (see the discussion in Section 11.1). SHA-1 is now being replaced by a series of more secure versions called SHA-2. They still use the Merkle-Damgård construction. In the next section, we’ll meet SHA-3, which uses a different construction.

The reader is warned that the discussion that follows is fairly technical and is provided in order to give the flavor of what happens inside a hash function.

The SHA-2 family consists of six algorithms: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, and SHA-512/256. The last three digits indicate the number of bits in the output. We’ll describe SHA-256. The other five are very similar.

SHA-256 produces a 256-bit hash and is built upon the same design principles as MD4, MD5, and SHA-1. These hash functions use an iterative procedure. Just as we did earlier, the original message $M$ $M$ is broken into a set of fixed-size blocks, $M = M^{(1)} | | M^{(2)} | | \dots | | M^{(N)}$ $M = M^{(1)} | | M^{(2)} | | \dots | | M^{(N)}$ , where the last block is padded to fill out the block. The message blocks are then processed via a sequence of rounds that use a compression function $h^{'}$ $h^{'}$ that combines the current block and the result from the previous round. That is, we start with an initial value $X_{0}$ $X_{0}$ , and define $X_{j} = h^{'} (X_{j - 1}, M^{(j)})$ $X_{j} = h^{'} (X_{j - 1}, M^{(j)})$ . The final $X_{N}$ $X_{N}$ is the message digest.

The trick behind building a hash function is to devise a good compression function. This compression function should be built in such a way as to make each input bit affect as many output bits as possible. One main difference between the SHA family and the MD family is that for SHA the input bits are used more often during the course of the hash function than they are for MD4 and MD5. This more conservative approach makes the design of SHA-1 and SHA-2 more secure than either MD4 or MD5, but also makes it a little slower.

In the description of the hash algorithm, we need the following operations on strings of 32 bits:

$X \land Y =$ $X \land Y =$ bitwise “and”, which is bitwise multiplication mod 2, or bitwise minimum.
$X \lor Y =$ $X \lor Y =$ bitwise “or”, which is bitwise maximum.
$X \oplus Y =$ $X \oplus Y =$ bitwise addition mod 2.
$\neg X$ $\neg X$ changes 1s to 0s and 0s to 1s .
$X + Y =$ $X + Y =$ addition of $X$ $X$ and $Y$ $Y$ mod $2^{32}$ $2^{32}$ , where $X$ $X$ and $Y$ $Y$ are regarded as integers mod $2^{32}$ $2^{32}$ .
$R^{n} (X) =$ $R^{n} (X) =$ rotation of $X$ $X$ to the right by $n$ $n$ positions (the end wraps around to the beginning).
$S^{n} (X) =$ $S^{n} (X) =$ shift of $X$ $X$ to the right by $n$ $n$ positions, with the first $n$ $n$ bits becoming 0s (so the bits at the end disappear and do not wrap around).

We also need the following functions that operate on 32-bit strings:

\begin{array}{r} C h (X, Y, Z) & = & (X \land Y) \oplus (¬ X \land Z) \\ M a j (X, Y, Z) & = & (X \land Y) \oplus (X \land Z) \oplus (Y \land Z) \\ Σ_{0} (X) & = & R^{2} (X) \oplus R^{13} (X) \oplus R^{22} (X) \\ Σ_{1} (X) & = & R^{6} (X) \oplus R^{11} (X) \oplus R^{25} (X) \\ σ_{0} (X) & = & R^{7} (X) \oplus R^{18} (X) \oplus S^{3} (X) \\ σ_{1} (X) & = & R^{17} (X) \oplus R^{19} (X) \oplus S^{10} (X) . \end{array}

$\begin{array}{r} C h (X, Y, Z) & = & (X \land Y) \oplus (¬ X \land Z) \\ M a j (X, Y, Z) & = & (X \land Y) \oplus (X \land Z) \oplus (Y \land Z) \\ Σ_{0} (X) & = & R^{2} (X) \oplus R^{13} (X) \oplus R^{22} (X) \\ Σ_{1} (X) & = & R^{6} (X) \oplus R^{11} (X) \oplus R^{25} (X) \\ σ_{0} (X) & = & R^{7} (X) \oplus R^{18} (X) \oplus S^{3} (X) \\ σ_{1} (X) & = & R^{17} (X) \oplus R^{19} (X) \oplus S^{10} (X) . \end{array}$

Define initial hash values $H_{1}^{(0)}, H_{2}^{(0)}, \dots, H_{8}^{(0)}$ $H_{1}^{(0)}, H_{2}^{(0)}, \dots, H_{8}^{(0)}$ as follows:

\begin{matrix} H_{1}^{(0)} = 6A09E667 & H_{2}^{(0)} = BB67AE85 & H_{3}^{(0)} = 3C6EF372 & H_{4}^{(0)} = A54FF53A \\ H_{5}^{(0)} = 510E527F & H_{6}^{(0)} = 9B05688C & H_{7}^{(0)} = 1F83D9AB & H_{8}^{(0)} = 5BE0CD19 \end{matrix}

$\begin{matrix} H_{1}^{(0)} = 6A09E667 & H_{2}^{(0)} = BB67AE85 & H_{3}^{(0)} = 3C6EF372 & H_{4}^{(0)} = A54FF53A \\ H_{5}^{(0)} = 510E527F & H_{6}^{(0)} = 9B05688C & H_{7}^{(0)} = 1F83D9AB & H_{8}^{(0)} = 5BE0CD19 \end{matrix}$

The preceding are written in hexadecimal notation. Each digit or letter represents a string of four bits:

0 = 0000, 1 = 0001, 2 = 0010, \dots, 9 = 1001,

$0 = 0000, 1 = 0001, 2 = 0010, \dots, 9 = 1001,$

A = 1010, B = 1011, \dots, F = 1111.

$A = 1010, B = 1011, \dots, F = 1111.$

For example, BA1 equals $11 * 16^{2} + 10 * 16^{1} + 1 = 2977$ $11 * 16^{2} + 10 * 16^{1} + 1 = 2977$ .

These initial hash values are obtained by using the first eight digits of the fractional parts of the square roots of the first eight primes, expressed as “decimals” in base 16. See Exercise 7.

We also need sixty-four 32-bit words

\begin{matrix} K_{0} = 428A2F98, & K_{1} = 71374491, & …, & K_{63} = C67178f2 . \end{matrix}

$\begin{matrix} K_{0} = 428A2F98, & K_{1} = 71374491, & …, & K_{63} = C67178f2 . \end{matrix}$

They are the first eight hexadecimal digits of the fractional parts of the cube roots of the first 64 primes.

Padding and Preprocessing

SHA-256 begins by taking the original message and padding it with the bit $1$ $1$ followed by a sequence of $0$ $0$ bits. Enough $0$ $0$ bits are appended to make the new message $64$ $64$ bits short of the next highest multiple of $512$ $512$ bits in length. Following the appending of $1$ $1$ and $0$ $0$ s, we append the $64$ $64$ -bit representation of the length $T$ $T$ of the message. (This restricts the messages to length less than $2^{64} \approx 10^{19}$ $2^{64} \approx 10^{19}$ bits, which is not a problem in practice.)

For example, if the original message has 2800 bits, we add a 1 and 207 0s to obtain a new message of length $3008 = 6 \times 512 - 64$ $3008 = 6 \times 512 - 64$ . Since $2800 = 101011110000_{2}$ $2800 = 101011110000_{2}$ in binary, we append fifty-two 0s followed by 101011110000 to obtain a message of length 3072. This is broken into six blocks of length 512.

Break the message with padding into $N$ $N$ blocks of length 512:

M^{(1)} | | M^{(2)} | | \dots | | M^{(N)} .

$M^{(1)} | | M^{(2)} | | \dots | | M^{(N)} .$

The hash algorithm inputs these blocks one by one. In the algorithm, each 512-bit block $M^{(i)}$ $M^{(i)}$ is divided into sixteen 32-bit blocks:

M^{(i)} = M_{0}^{(i)} | | M_{1}^{(i)} | | \dots | | M_{15}^{(i)} .

$M^{(i)} = M_{0}^{(i)} | | M_{1}^{(i)} | | \dots | | M_{15}^{(i)} .$

The Algorithm

There are eight 32-bit registers, labeled $a, b, c, d, e, f, g, h$ $a, b, c, d, e, f, g, h$ . These contain the intermediate hash values. The algorithm inputs a block of 512 bits from the message in Step 11, and in Steps 12 through 24, it stirs the bits of this block into a mix with the bits from the current intermediate hash values. After 64 iterations of this stirring, the algorithm produces an output that is added (mod $2^{32}$ $2^{32}$ ) onto the previous intermediate hash values to yield the new hash values. After all of the blocks of the message have been processed, the final intermediate hash values give the hash of the message.

The basic building block of the algorithm is the set of operations that take place on the subregisters in Steps 15 through 24. They take the subregisters and operate on them using rotations, XORs, and other similar operations.

For more details on hash functions, and for some of the theory involved in their construction, see [Stinson], [Schneier], and [Menezes et al.].

Algorithm 3 The SHA-256 algorithm

1: for $i$ $i$ from 1 to $N$ $N$ do

⊳ This initializes the registers with the $(i - 1)$ $(i - 1)$ st intermediate hash value
2: $a \leftarrow H_{1}^{(i - 1)}$ $a \leftarrow H_{1}^{(i - 1)}$
3: $b \leftarrow H_{2}^{(i - 1)}$ $b \leftarrow H_{2}^{(i - 1)}$
4: $c \leftarrow H_{3}^{(i - 1)}$ $c \leftarrow H_{3}^{(i - 1)}$
5: $d \leftarrow H_{4}^{(i - 1)}$ $d \leftarrow H_{4}^{(i - 1)}$
6: $e \leftarrow H_{5}^{(i - 1)}$ $e \leftarrow H_{5}^{(i - 1)}$
7: $f \leftarrow H_{6}^{(i - 1)}$ $f \leftarrow H_{6}^{(i - 1)}$
8: $g \leftarrow H_{7}^{(i - 1)}$ $g \leftarrow H_{7}^{(i - 1)}$
9: $h \leftarrow H_{8}^{(i - 1)}$ $h \leftarrow H_{8}^{(i - 1)}$
10: for $k$ $k$ from 0 to 15 do
11: $W_{k} \leftarrow M_{k}^{(i)}$ $W_{k} \leftarrow M_{k}^{(i)}$ ⊳ This is where the message blocks are entered.
12: for $j_{1}$ $j_{1}$ from 16 to 63 do
13: $W_{j_{1}} \leftarrow σ_{1} (W_{j_{1} - 2}) + W_{j_{1} - 7} + σ_{0} (W_{j_{1} - 15}) + W_{j_{1} - 16}$ $W_{j_{1}} \leftarrow σ_{1} (W_{j_{1} - 2}) + W_{j_{1} - 7} + σ_{0} (W_{j_{1} - 15}) + W_{j_{1} - 16}$
14: for $j$ $j$ from 0 to 63 do
15: $T_{1} \leftarrow h + Σ_{1} (e) + C h (e, f, g) + K_{j} + W_{j}$ $T_{1} \leftarrow h + Σ_{1} (e) + C h (e, f, g) + K_{j} + W_{j}$
16: $T_{2} \leftarrow Σ_{0} (a) + M a j (a, b, c)$ $T_{2} \leftarrow Σ_{0} (a) + M a j (a, b, c)$
17: $h \leftarrow g$ $h \leftarrow g$
18: $g \leftarrow f$ $g \leftarrow f$
19: $f \leftarrow e$ $f \leftarrow e$
20: $e \leftarrow d + T_{1}$ $e \leftarrow d + T_{1}$
21: $d \leftarrow c$ $d \leftarrow c$
22: $c \leftarrow b$ $c \leftarrow b$
23: $b \leftarrow a$ $b \leftarrow a$
24: $a \leftarrow T_{1} + T_{2}$ $a \leftarrow T_{1} + T_{2}$
25: $H_{1}^{(i)} \leftarrow a + H_{1}^{(i - 1)}$ $H_{1}^{(i)} \leftarrow a + H_{1}^{(i - 1)}$ ⊳ These are the $i$ $i$ th intermediate hash values
26: $H_{2}^{(i)} \leftarrow b + H_{2}^{(i - 1)}$ $H_{2}^{(i)} \leftarrow b + H_{2}^{(i - 1)}$
27: $H_{3}^{(i)} \leftarrow c + H_{3}^{(i - 1)}$ $H_{3}^{(i)} \leftarrow c + H_{3}^{(i - 1)}$
28: $H_{4}^{(i)} \leftarrow d + H_{4}^{(i - 1)}$ $H_{4}^{(i)} \leftarrow d + H_{4}^{(i - 1)}$
29: $H_{5}^{(i)} \leftarrow e + H_{5}^{(i - 1)}$ $H_{5}^{(i)} \leftarrow e + H_{5}^{(i - 1)}$
30: $H_{6}^{(i)} \leftarrow f + H_{6}^{(i - 1)}$ $H_{6}^{(i)} \leftarrow f + H_{6}^{(i - 1)}$
31: $H_{7}^{(i)} \leftarrow g + H_{7}^{(i - 1)}$ $H_{7}^{(i)} \leftarrow g + H_{7}^{(i - 1)}$
32: $H_{8}^{(i)} \leftarrow h + H_{8}^{(i - 1)}$ $H_{8}^{(i)} \leftarrow h + H_{8}^{(i - 1)}$
33: $H (m) = H_{1}^{(N)} | | H_{2}^{(N)} | | H_{3}^{(N)} | | H_{4}^{(N)} | | H_{5}^{(N)} | | H_{6}^{(N)} | | H_{7}^{(N)} | | H_{8}^{(N)}$ $H (m) = H_{1}^{(N)} | | H_{2}^{(N)} | | H_{3}^{(N)} | | H_{4}^{(N)} | | H_{5}^{(N)} | | H_{6}^{(N)} | | H_{7}^{(N)} | | H_{8}^{(N)}$
34: return $H (m)$ $H (m)$

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 11.4 SHA-2

Create new playlist

Sign In

Sign Up

Table of Contents for
11.4 SHA-2