SHA

SHA history and familySearch on YouTubeBookmarkSaved

OriginsSearch on YouTubeBookmarkSaved

• NIST and NSA designed SHA in 1993.
• In 1995, it was revised as SHA-1.
• It is the US standard for use with the DSA signature scheme.
• The standard is FIPS 180-1 1995, also Internet RFC 3174.
• The algorithm is SHA. The standard is SHS.
• It is based on the design of MD5, with key differences.
• It produces 160-bit hash values.
• Results from 2005 on the security of SHA-1 raised concerns about its use in future applications.

SHA familySearch on YouTubeBookmarkSaved

The bit length in the name gives the output size.

Revised secure hash standardSearch on YouTubeBookmarkSaved

• NIST issued the revision FIPS 180-2 in 2002.
• It adds 3 more versions of SHA: SHA-256, SHA-384, SHA-512. Each has a different digest length in bits.
• Their design gives security compatible with the increased security of the AES cipher.
• The structure and detail are similar to SHA-1, so the analysis is similar.
• The security levels are higher.

SHA-1 algorithmSearch on YouTubeBookmarkSaved

ParametersSearch on YouTubeBookmarkSaved

The "How SHA works" slide gives these values for SHA-1:

The slide gives the output as "four 32-bit blocks". This is an error. The buffer $(A, B, C, D, E)$ has five 32-bit words, and $5 \times 32 = 160$ bits.

Overview stepsSearch on YouTubeBookmarkSaved

1. Padding: pad the message until its length is 64 bits short of a multiple of 512.
2. Append length: append a 64-bit value that gives the length of the original message.
3. Divide the input into 512-bit blocks.
4. Initialise the CV, a 5-word (160-bit) buffer $(A, B, C, D, E)$.
5. Process the blocks in 16-word (512-bit) chunks:
   • Copy the CV into a single register. This register holds the intermediate and the final results.
   • Divide the current 512-bit block into 16 sub-blocks of 32 bits each.
   • Do 4 rounds of 20 steps each on the message block and the buffer.
   • Expand the 16 words into 80 words ($20 \times 4$) by mixing and shifting. Use $K[t]$ for $t = 0$ to $79$.
   • Add the output to the input to get the new buffer value.
6. Output: the hash value is the final buffer value.

Initial bufferSearch on YouTubeBookmarkSaved

The slide gives the initial values byte by byte:

The slide lists the bytes of A to D from low-order to high-order. The standard writes each word as a big-endian hex number.

SHA-1 compression functionSearch on YouTubeBookmarkSaved

Block processingSearch on YouTubeBookmarkSaved

Figure 12.5 shows how SHA-1 processes one 512-bit block $Y_q$:

The chaining value $CV_q$ comes in as 160 bits (five 32-bit words $A, B, C, D, E$). After round 4, five adders add each word to the matching word of $CV_q$. The result is $CV_{q+1}$ (160 bits). Addition is mod $2^{32}$.

Step functionSearch on YouTubeBookmarkSaved

The slide gives the step as:

$ABCDE = F[t] + E + S^5(A) + W[t] + K[t]$

The slide says that the buffer shifts "right by 1 bit" for the next step. The figure shows a shift of one word position, not one bit. In full notation, each of the 20 steps in a round replaces the 5 buffer words thus:

$(A, B, C, D, E) \leftarrow (E + f(t, B, C, D) + (A \ll 5) + W_t + K_t,\; A,\; (B \ll 30),\; C,\; D)$

Round functionsSearch on YouTubeBookmarkSaved

Round 1 is a selection: if $b$ then $c$, else $d$. Rounds 2 and 4 give the parity. Round 3 gives the majority, which is true when two or three of $b, c, d$ are true.

ConstantsSearch on YouTubeBookmarkSaved

The slides define $K[t]$ as a constant for each step, $t = 0$ to $79$. The standard (FIPS 180-1) uses one value for each round:

Message scheduleSearch on YouTubeBookmarkSaved

Figure 12.7 shows the creation of the 80-word input $W_t$. The expansion adds redundancy and interdependence among message blocks.

• Words $W_0 \dots W_{15}$ are the 16 words of the 512-bit block $Y_q$.
• For $t = 16$ to $79$, four earlier words go into an XOR, and $S^1$ rotates the result 1 bit to the left:

$W_t = S^1\left(W_{t-16} \oplus W_{t-14} \oplus W_{t-8} \oplus W_{t-3}\right)$

Each new word depends on many earlier words. Thus a change in one message word spreads through the schedule.

ComparisonsSearch on YouTubeBookmarkSaved

SHA-1 versus MD5Search on YouTubeBookmarkSaved

Table 12.3Search on YouTubeBookmarkSaved

Notes from the table: all sizes are in bits. "Security" means that a birthday attack on a message digest of size $n$ produces a collision with a work factor of approximately $2^{n/2}$.

SHA-1 versus SHA-512Search on YouTubeBookmarkSaved

SHA-512Search on YouTubeBookmarkSaved

Setup stepsSearch on YouTubeBookmarkSaved

1. Padding.
2. Append length.
3. Divide the input into 1024-bit blocks. The padded message is the message ($L$ bits), then a 1 and zeros (100...0), then a 128-bit length field. The total is $N \times 1024$ bits.
4. Initialise the chaining variable: $8 \times 64 = 512$ bits, in eight 64-bit words $A, B, C, D, E, F, G, H$.
5. Process the blocks. This is the heart of the algorithm:
   • Process the message in 1024-bit blocks.
   • Each block goes through 80 rounds that update the 512-bit buffer (the temporary chaining variables).
   • Each round uses a 64-bit value $W_t$ from the current message block.
   • Each round uses a round constant $K_t$ based on the cube roots of the first 80 prime numbers.

The chaining is as follows. $IV = H_0$ and block $M_1$ go into function $F$. Word-by-word addition mod $2^{64}$ of $H_0$ and the output of $F$ gives $H_1$. This continues to $H_N$, which is the hash code.

Round functionSearch on YouTubeBookmarkSaved

The slide describes each of the 80 steps for one block. The slide says "512-bit block", but the block is 1024 bits and the buffer is 512 bits. Each round uses these equations:

$T_1 = h + \text{Ch}(e, f, g) + \left(\Sigma_1^{512} e\right) + W_t + K_t$

$T_2 = \left(\Sigma_0^{512} a\right) + \text{Maj}(a, b, c)$

$a = T_1 + T_2, \quad b = a, \quad c = b, \quad d = c, \quad e = d + T_1, \quad f = e, \quad g = f, \quad h = g$

Message scheduleSearch on YouTubeBookmarkSaved

The schedule expands the 16 words of block $M_i$ (64 bits each) into 80 words. For $t = 16$ to $79$, the figure combines four earlier words:

$W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16}$

For example, $W_{16}$ uses $W_0$, $\sigma_0(W_1)$, $W_9$ and $\sigma_1(W_{14})$. The figure labels the combining box "XOR". The standard (FIPS 180) uses addition mod $2^{64}$.

$\sigma_0(x) = \text{ROTR}^{1}(x) \oplus \text{ROTR}^{8}(x) \oplus \text{SHR}^{7}(x)$

$\sigma_1(x) = \text{ROTR}^{19}(x) \oplus \text{ROTR}^{61}(x) \oplus \text{SHR}^{6}(x)$

Quick self-testSearch on YouTubeBookmarkSaved

Who designed SHA, and what are the standards and revisions?

NIST and NSA designed SHA in 1993. It was revised in 1995 as SHA-1. The standard is FIPS 180-1 (1995), also Internet RFC 3174. The algorithm is SHA, and the standard is SHS. FIPS 180-2 (2002) adds SHA-256, SHA-384 and SHA-512 for compatibility with AES security.

Summarise the four SHA family generations.

SHA-0 (1993): first version, withdrawn due to security flaws. SHA-1 (1995): 160-bit hash, used in SSL/TLS, Git and signatures, now broken by collision attacks. SHA-2 (2001): SHA-224/256/384/512, SHA-512/224 and SHA-512/256, Merkle-Damgard, still secure. SHA-3 (2015): Keccak, a different design, includes SHAKE128 and SHAKE256.

Give the SHA-1 parameters from the "How SHA works" slide.

Digest length 160 bit. Input text 512 bit. Sub-block size 32 bit, so $512/32 = 16$ sub-blocks. 4 rounds with 20 iterations each. Chaining variable $5 \times 32 = 160$ bit. $K[t]$ constant for $t = 0$ to $79$.

List the six SHA-1 overview steps and the buffer initial values.

Pad to 64 bits short of a multiple of 512. Append the 64-bit message length. Divide into 512-bit blocks. Initialise the buffer: A = 01234567, B = 89ABCDEF, C = FEDCBA98, D = 76543210, E = C3D2E1F0. Process each block in 4 rounds of 20 steps and add the output to the input. Output the final buffer.

Write the SHA-1 buffer update equation and name its terms.

$(A,B,C,D,E) \leftarrow (E + f(t,B,C,D) + (A \ll 5) + W_t + K_t,\; A,\; (B \ll 30),\; C,\; D)$. The terms are the 5 buffer words, the step number $t$, the round function $f$, the message word $W_t$ and the constant $K_t$. $S^t$ is a circular left shift of a 32-bit word by $t$ bits.

Give the four SHA-1 round functions.

Round 1: $(b \text{ AND } c) \text{ OR } ((\text{NOT } b) \text{ AND } d)$, same as MD5. Round 2: $b \text{ XOR } c \text{ XOR } d$. Round 3: $(b \text{ AND } c) \text{ OR } (b \text{ AND } d) \text{ OR } (c \text{ AND } d)$. Round 4: $b \text{ XOR } c \text{ XOR } d$.

How does SHA-1 create the 80-word input $W_t$, and why?

$W_0..W_{15}$ are the message words. For $t \ge 16$, $W_t = S^1(W_{t-16} \oplus W_{t-14} \oplus W_{t-8} \oplus W_{t-3})$. For example, $W_{16}$ uses $W_0, W_2, W_8, W_{13}$. The expansion adds redundancy and interdependence among message blocks.

Compare SHA-1 with MD5.

A brute-force attack is harder on SHA-1 (160 bits against 128 bits). At the time of the slide, SHA-1 had no known attacks, unlike MD4/5. SHA-1 is a little slower (80 steps against 64). Both are simple and compact. SHA-1 is optimised for big-endian CPUs (SUN), MD5 for little-endian CPUs (PC).

Fill table 12.3 for SHA-1 and SHA-512.

SHA-1: digest 160, message $< 2^{64}$, block 512, word 32, steps 80, security 80. SHA-512: digest 512, message $< 2^{128}$, block 1024, word 64, steps 80, security 256. Security is the birthday work factor, about $2^{n/2}$.

Give the SHA-512 round equations $T_1$ and $T_2$ with their functions.

$T_1 = h + \text{Ch}(e,f,g) + \Sigma_1^{512}(e) + W_t + K_t$, with $\Sigma_1 = \text{ROTR}^{14} \oplus \text{ROTR}^{18} \oplus \text{ROTR}^{41}$. $T_2 = \Sigma_0^{512}(a) + \text{Maj}(a,b,c)$, with $\Sigma_0 = \text{ROTR}^{28} \oplus \text{ROTR}^{34} \oplus \text{ROTR}^{39}$. Then $a = T_1 + T_2$ and $e = d + T_1$. The other words move down one register.