I just can't figure out why on earth the $IV$ in Merkle–Damgård has to be fixed (that's what the Katz-Lindell book says)? Because even if you choose it randomly from say $\{{0,1}\}^n$ then the resulting construction still remains collision-resistant, or not?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ One reason is convenience: a variable IV would need to be transmitted, perhaps authenticated.. Another reason is explained here following with the IV replaced by a constant of unknown origin $\endgroup$– fgrieu ♦Aug 23, 2015 at 14:27
-
$\begingroup$ @fgrieu If you'll add your comment as an answer, I'll accept it. Thank you btw $\endgroup$– pa5h1nh0Aug 23, 2015 at 23:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
One reason is convenience: if the IV was variable, it would have to be transmitted to a party verifying the hash, and we'd have to deal with its integrity.
Another reason is that it avoids an attack in a Merkle–Damgård variant with padding reduced to appending a single 1 bit and as many zeros as necessary to end the block. With such scheme and common compression functions, like the ones in MD5, SHA-1, and the SHA-2 familly, ability to choose the IV implies ability to chose a secret prefix that does not change the hash.
Notice that the compression function $C$ used in these hashes is of the form $$(X,K)\rightarrow C(X,K)=X\tilde+ E(X,K)$$ where $X$ is the current state (initially the IV), $K$ is the block to hash, $\tilde+$ is a variant of addition (with a few carries suppressed), and $X\rightarrow E(X,K)$ is a reversible block cipher with key $K$.
Who defined an $IV$ that's not a nothing-up-my-sleeves number could have chosen a secret one-block $K$, computed $IV = E^{-1}(0,K)$, which insures $IV=C(IV,K)$. That allows insertion of $K$ at the beginning of any message, without changing the hash.
