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?)


1 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.

  • $\begingroup$ Are you assuming I always use the same salt? But I'm talking about generating a different salt every time. $\endgroup$
    – Bennett
    Jan 21, 2021 at 1:04
  • $\begingroup$ I'm assuming unknown salt for Alice nothing more. Note that; during canonical verification, the salt must be the same, i.e. once you assigned a salt for signature, you can't change that. $\endgroup$
    – kelalaka
    Jan 21, 2021 at 1:09
  • $\begingroup$ Oh I think I understand what you mean -- are you saying that if x and y both have length multiples of 512, and if MD5(x) = MD5(y), then MD5(x || salt) = MD5(y || salt)? Then yes that attack would work. But even in that case, can't you trivially defeat this attack by concatenating the salt before the message, and then taking the hash? $\endgroup$
    – Bennett
    Jan 21, 2021 at 1:24
  • $\begingroup$ Well, if Alice knows the prepended salt a few minutes beforehand, they can, see in corkami, otherwise, no. $\endgroup$
    – kelalaka
    Jan 21, 2021 at 1:30
  • $\begingroup$ Yeah I was assuming that Alice doesn't see the salt before Bob generates it and signs Alice's document. In that case then, I don't understand why this doesn't moot all "collision attacks". Is there any scenario where a collision attack isn't defeated by having someone generate a salt and pre-pend it to the content? $\endgroup$
    – Bennett
    Jan 21, 2021 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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