is there any hash collision attack that is not defeated by adding a salt first?

Question

In the references I've read, all the uses of "collision attacks", whether classical collision attack or chosen-prefix collision attack, goes like this: "Alice creates a 'good' document and an 'evil' document that have the same hash. Alice presents the 'good' document to Bob, who signs it by taking a hash of the document and signing the hash. Alice now swaps out the 'evil' document and Bob's signature will still appear valid."

But aren't these attacks trivially defeated if, instead of taking the hash of the document, Bob adds a random salt, hashes the document plus the salt, and then signs the concatenation of the hash and the salt? Is there any set of conditions where this defense would not work?

Because I see lots of sources saying you have to stop using SHA-1 due to the known collision attacks, and by the above reasoning, I don't understand why, when you could just add a salt to whatever you're hashing.

(I have also read about how specific implementations can protect against collision attacks by using the hash function as an HMAC, i.e. adding a salt. My question is more general -- is there any case where a collision attack is not defeated by adding a salt?)

Answer 1

• Suffix salt

  If you add the salt after the message, $\operatorname{MD5}(m \mathbin\| salt)$, that doesn't prevent Alice from finding two collisions. Example;

  Consider that if the message $m$ of Alice is an exact multiple of the block size of the $\operatorname{MD5}(m \mathbin\| salt)$ then your signature will be vulnerable to hash chosen-prefix collisions. Because Alice can prepare two messages $m_1$ and $m_2$ so that $$\operatorname{MD5}(p_1\mathbin\| m_1) = \operatorname{MD5}(p_2\mathbin\| m_2)$$

  Once Alice found the pairs such that

  $$strlen(p_1\mathbin\| m_1)=strlen(p_2\mathbin\| m_2) = t \cdot 512$$

  then adding your salt, even not known to Alice before, will not prevent Alice to forge. This is due to the Merkle-Damgård construction;

  • Both messages have the same internal compression values before the length added padding. Adding anything after those will not affect their collision.

• If you add the salt after the message $\operatorname{MD5}(m \mathbin\| salt)$, that doesn't prevent Alice from finding two collisions. Example;

• Prefix salt

  If you add the salt before the message, $\operatorname{MD5}(salt \mathbin)$, this will prevent Alice from finding two collisions.

  We may see this in this way; the salt, especially it is one block, will be like an IV to MD5 since the first call of the compression function will calculate

  $$ h_1 = C(salt,IV),$$ then $h_1$ will be a new IV for the rest of the compressions. This can be considered that you are using a family of MD5 hashes with different IV's. Since the IV is no control of Alice this is secure. Actually, this is similar to what HMAC does;

  $$ \operatorname{HMAC}(K, m) = \operatorname{H}\Bigl(\bigl(K' \oplus opad\bigr) \parallel \operatorname{H} \bigl(\left(K' \oplus ipad\right) \parallel m\bigr)\Bigr) $$

  Consider the inner hash and, you will have a similar structure to change the IV of the hash function.

  Your construction is vulnerable to length extension attack, however, since the resulting hashes will be different after the extension, this will not cause a forgery.

  And note that HMAC is proven to be not affected by the collisions of the hash function, even it can be safe for MD5, however, we don't advise, use at least HMAC-SHA256.