4
$\begingroup$

So, reading the chapter about hash functions from the book "Applied Cryptography". There's a point where, as a conclusion, the construction:

SHA-X(SHA-X(0^b || m))

Saying:

Prepending the message with a block of zeros makes it so that, unless something unusual happens, the first block input to the inner hash function im hd is different than the input to the outer hash function.

The thing is I don't quite get it.

Forgetting about the prepending of a block of 0's to the inner hash function, let's state that it's clear that:

If we find a collision for the output of the inner hash function, then we get a collision for the output of the outer hash function.

So, how is it different prepending a block of all 0's to the message to mitigate length extension attack?

If I have the messages:

m=m1..mk
m'=m1..mk,mk+1

When prepending a block of 0's to both of them as input for the inner hash function will give us the same "problematic" situation we have with length extension attacks. We will have a partial message collision up to

0b||m1..mk

And then we have mk+1 "to play" and be able to generate a length extension attack...

I'm aware that there's obviously something wrong with my reasoning, so I'm hoping someone can give me a hand and point out what it is.

$\endgroup$
6
$\begingroup$

The objective of the construction $H'(m)=H(H(0^b\mathbin\|m))$ is not to strengthen $H$ against collision attacks; as noted in the question, that does not work.

The objective is preventing a length-extension attack. In such attack, an adversary knows the hash $h=H(m_0)$ of some unknown $m_0$, and the length $l$ of $m_0$. Then from $h$ and $l$ s/he constructs a short $m_1$ such that for any given $m_2$, it is easy to compute $h'=H(m_0\mathbin\|m_1\mathbin\|m_2)$. Essentially, $m_1$ is the padding internally appended to $m_0$ in the normal computation of $h=H(m_0)$, so that the internal state of the hash after hashing $m_0\mathbin\|m_1$ is the known $h$.

A length-extension attack can matter in practice, e.g. $F_k(m)=H(k\mathbin \|m)$ is insecure as a Message Authentication Code if $H$ has a length-extension property, as SHA-1, SHA-256 and SHA-512 do. That's one reason to use HMAC to build a MAC or Key Derivation Function.

If the $0^b$ is the question's construction was absent, as in $H'(m)=H(H(m))$, we'd have the property: $\forall m,H'(H(m))=H(H'(m))$. We can construct some (largely artificial) protocols which would be secure for $H$, but are insecure for $H'$ due to that property; and correspondingly, that property makes some security proofs hairy, impossible, or weaker. With $H'(m)=H(H(0^b\mathbin\|m))$, that or similar properties do not hold, which is good for simpler/stronger security proofs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.