6

If I have a salt of 16bytes and 16bytes of data, how fast can one find another 16bytes of data so that MD5(salt + data) == MD5(salt + other data)?

I don't expect an answer accurate to the nanosecond, just an estimation like "a few seconds", "a few hours", "a few civilizations".

Serge Profafilecebook
  • 173
  • 1
  • 3

1 Answers1

12

What you want is not a collision but a second preimage.

A collision is: find two distinct messages m and m' which hash to the same value.

A second preimage is: given a message m, find a distinct message m' such that both messages hash to the same value.

Second preimages are harder because the attacker does not get to choose both messages at will. MD5 is very broken against collisions (collisions can be generated in less than a second) but not against second preimages. For that, the best known attack is a generic preimage attack which is theoretical only, since it has cost 2123.4, i.e. much higher that what can be done in practice.

So the raw answer to your specific question is: it cannot be done (with existing technology and known attacks on MD5).

(I am here talking only about finding a second preimage on MD5, not about the security of using MD5(salt + data) in any specific context, whether 'salt' and 'data' are known or not. I suspect that anybody who uses MD5(salt + data) actually wants either a password hashing function, or HMAC.)

Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
  • So MD5(salt + password) is still quite secure. Thank you for the information. – Serge Profafilecebook May 09 '14 at 07:38
  • 1
    No, we cannot say _in general_ that "MD5(salt + password)" is "secure". As a way to store password hashes for ulterior verification, it is terrible and weak. What I say is that, given one password, finding another one which yields the same hash value will be hard -- but in most cases of password hashing, the attacker just want to find the actual user's password, not another one. – Thomas Pornin May 09 '14 at 10:11
  • How would you validate a password without a hash? – Serge Profafilecebook May 09 '14 at 13:47
  • I don't reject the concept, but the method. Password hashing has been the subject of a lot of theory and practice, from which it appears that "MD5(salt+data)", while better than "MD5(data)", is still weak. Better ways are known and used; read [this answer](http://security.stackexchange.com/questions/211/how-to-securely-hash-passwords/31846#31846) for an introduction. – Thomas Pornin May 10 '14 at 11:34
  • Technically finding a second preimage would still count as finding a collision, wouldn't it? It's just that you need to find a very specific collision. – flarn2006 May 12 '21 at 02:38