Why does NIST say that 2nd preimage resistance depends on the message length

Question

In NIST FIPS 202 on the table, It is written as

Function	Output Size	Collision	PreImage	2nd Preimage
SHA-1	160	< 80	160	160–L(M)
SHA-224	224	112	224	min(224, 256–L(M))
SHA-512/224	224	112	224	224
SHA-256	256	128	256	256–L(M)
SHA-512/256	256	128	256	256
SHA-384	384	192	384	384
SHA-512	512	256	512	512–L(M)

with $L(M) = \lceil \log_2(len(M)/B) \rceil$ where $B$ is the block length of the function in bits, i.e., B = 512 for SHA-1, SHA-224, and SHA-256, and B = 1024 for SHA-512.

For the discussion directs to NIST 800-107r1. and it is on the appendix;

The actual second preimage resistance strength for SHA-1, SHA -224, SHA-256 and SHA-512 is approximately $(L – M)$, where $L$ is the output block size of the hash function, and the message is $2^M$ input blocks in length.

For example, if a message that is $2^{33}$ bits in length (i.e., a gigabyte long) is hashed by SHA-256 (whose input block size is $2^9$ bits), the second preimage resistance strength is $(L – M) = (256 – 24) = 232$ bits (where $L = 256$, and $M = \log_2(2^{33}/2^{9}) = (33 – 9) = 24).$ That is, the amount of work required to find a second preimage is $2^{232}$.

It is important to note that the amount of work is based on the number of compressions function executions (compressing single message blocks), not on the number of hash function executions (hashing messages of more than one block in length)

First of all, there is no reference for this claim. Is there any reference for this claim?

Is there a better explanation for this attack?

Answer 1

The reference for the claim is here, titled "Second Preimages on $n$-bit Hash Functions for Much Less than $2^n$ Work" by J. Kelsey, B. Schneier.

The attack is specific to un-truncated Merkle-Damgaard hash functions. I haven't understood the mechanism of the attack, but as far as I understood, it require some unrealistically large working memory for the attack to work, and therefore it doesn't affect real-world security of SHA-1/2 hash functions.

Answer 2

DannyNiu's provide the article, and this is going to provide the details;

This work has a serious result on the security of the iterated hash functions (MD- construction). From $n$-bit hash function we want $2^{n/2}$ collision resistance and $2^n$ preimage and secondary preimages resistances. They showed that

• Damgard-Merkle construction cannot satisfy this security, for a given message of size $2^k$ blocks the seconday image attack requires $k\times 2^{n/2+1} + 2^{n-k+1}$ work.

Now Details

MD construction;

• MD construction uses a compression function $F(H,M)$ where the size of $H$ is equal to the output size like 160 in SHA-1 and the size of $M$ is defined by the hash function like SHA-1 512 and SHA-512 has 1024.

• Message is padding to math the required size with the last bytes encodes the message size. The message size is called MD-strengthening.

• The hash is simply the chaining $$h[i]= F(h[i-1],M[i])$$ with a initial fixed value $h[-1]$ ( following the style of the article, it is usually $h_0$)

This construction hash a reduction proof that If an attacker can find a collision in the whole hash, then he can likewise find one in the compression function ( consider the contrapositive)

Expandable message

This is the core definition; This is a kind of collision where two different sized messages collide in the input to the last position. Note that they cannot continue to collide after the last since the message size.

• Finding a Collision on Two Messages of Different Lengths

  This is related to Joux's multi-collision technique where once a collision is found it is extended to find multiple messages that has the same collision with equal length. They removed the equal length to produce expandable messages.

• ALGORITHM: FindCollision($\alpha$, $h_{in}$)

  1. Compute the starting hash for the $\alpha$-block message by process ing $\alpha - 1$ dummy message $q$ blocks:

     • $h_{tmp} = h_{in}$.
     • For $i=0$ to $\alpha -2$:
       • $h_{tmp} = F(h_{tmp},q)$

  2. Build lists $A$ and $B$ by using $2^m$ distinct messages $M(i)$

     • for $i=0$ to $2^{n/2}-1$
       • $A[i] = F(h_{in}, M(i))$
       • $B[i] = F(h_{temp}, M(i))$

  3. Search $i,j$ such that $A[i]=B[j]$

  4. Return colliding messages $(M (i), q\mathbin\|q\mathbin\|\ldots \mathbin\|q\mathbin\|M (j))$, and the resulting intermediate hash $F(h_{in} , M (i))$.

  The amount of work is $\alpha-1 + 2^{n/2+1}$ compression function call.

• ALGORITHM: MakeExpandableMessage($h_{in}$ , $k$)

  The above algorithm will be used to generate expandable messages that cover a huge range of possible lengths. First, it will find a colliding pair of blocks $1$ and $2^{k-1}+1$ and $1$ and $2^{k-2}+1$ until reaching a collision pair of length $1$ and $2$.

  1. Let $h_{tmp} = h_{in}$

  2. For $i=0$ to $k-1$

     • $(m_0,m_1,h_{tmp}) = FindCollision(2^i + 1, h_{tmp} )$
     • $C[k − i − 1][0] = m_0$ // this is a tuple list that store pairs with different lenghts.
     • $C[k − i − 1][1] = m_1$

  3. Return the list $C$

Work: $k \times 2^{n/2+1} + 2^k \approx k \times 2^{n/2+1}$ compression function calls.

Now, we have $k \times 2$ messages and this can be used to build messages between $k$ and $k+2^k=1$ blocks that don't change the hash result until the last block.

• There is another algorithm that produces arbitrary length messages that skipped with negligible work. Please refer to the article.

• There is also a more efficient method if fixed points ( $h[i − 1] = F (h[i − 1], M [i]))$ can easily be found in the compression function.

Finding the second pre-images from the expandible messages

Normally MD construction prevents the MvOV96 attack by appending the length of the message. Consider that the length is not appended and we have a targeted message that has $2^{55}$ blocks. Now search for $h^* = C(h[−1], M )$ such that $h^*$ is colliding with one of the intermediate values of the target message. With the collision attack, we need around $2^{105}$ different messages to find a hit. One we find this can be used to form a smaller message that has the same hash value as the target, i.e. secondary image. Since MD hash length at the and this foils this attack.

The main point of this attack overcome the defense by using the Expandable message messages. The below algorithm finds the second preimage for a message of $2^k + k + 1$ blocks.

ALGORITHM: LongMessageAttack($M_{target}$ )

1. $C = MakeExpandableMessage(k)$

2. $h_{exp}$ = the intermediate hash value after processing the expandable message in $C$.

3. Compute the intermediate hash values for the targer message $M_{target}$

   1. $h[−1] =$ the $IV$ for the hash function
   2. $m[i] = $the $i$th message block of $M_{target}$.
   3. $h[i] = F (h[i − 1], m[i])$, the $i$th intermediate hash output block.

   Store $h[i]$ in a fast searchable strcture while exculuding $h[0, 1, \ldots, k − 1]$

   4. Find a message block that links the expandable message to one of the intermediate hash values for the target message after the $k$th block

      • Try linking messages $M_{link}$ until $F (h_{exp}, M_{link} ) = h[j]$.

   5. Use the expandable message to produce a message $M^∗$ that is $j$ blocks long.

   6. Return second preimage $M^ ∗ \mathbin\|M_{link} \mathbin\|m[j+1]\mathbin\|m[j+2] \mathbin\| \ldots \mathbin\| m[2k +k]$.

Work For the generic expandable message-finding algorithm, this is $k \times 2^{n/2+1} + 2^{n−k+1}$ compression function calls.