Can a Rainbow Table find multiple plaintext passwords to match a given hash

Question

Given that:

• an MD5 hash can map to multiple plaintext strings (it is not unique)
• a rainbow table may store several million plaintext passwords with matching hash
• MY password is "password123", mapping to 482c811da5d5b4bc6d497ffa98491e38 MD5 hash

Can't a second plaintext string be found which hashes to "482c811da5d5b4bc6d497ffa98491e38"? And thus, can be entered as MY password into adobe.com, and thus gain illegal entry via a legitimate login?

What's the chances of this hash collision outcome? Obviously that depends on the size of the password list / rainbow table, but roughly..?

Answer 1

Can't a second plaintext string be found which hashes to "482c811da5d5b4bc6d497ffa98491e38"?

Yes - it's even easier than you fear with MD5, which is broken; e.g. it is possible to generate collisions on purpose, although I'm not sure whether it's already possible to generate collisions without controlling the input at least partially.

You may want to google "birthday paradox". It asks: "What's the chance that two persons in a room share the same birthday?" and it's relevant to your question.

It will also give you the math to calculate the chances of hash collisions given the size of the hash function output and the number of elements/passwords you expect to hash. I think a rough estimate that's often used is that you're likely to see collisions after hashing n passwords, where n is the square root of the your hash function output space. So, with your example of a 128 bit hash, that would roughly start to happen after 2^64 hashed passwords (which I'd think is still infeasible to do with today's hardware iff md5 isn't completely broken yet, so there's probably no need to panic yet, but I'd start walking calmly towards the next exit...).

And thus, can be entered as MY password into adobe.com, and thus gain illegal entry via a legitimate login?

Probably not, since Adobe should know better than to use MD5 to hash passwords and not even use a salt value.

Passwords aren't hashed using bare-metal fast hash functions such as md5 or sha1 or even sha256 any more (at least not by anyone who wants to keep them safe in today's world). These hash functions are much too fast and can be implemented on hardware such as graphics cards parallel gpus (or even more specialized hardware) which can then hash millions or billions of candidate passwords per second (depending on the hash function used) to brute force a password. You can try it out yourself using a program such as hashcat.

Better options for hash functions are hash functions designed to be slow, pbkdf2, scrypt and bcrypt for example. They do hundreds of thousands of iterations to slow themselves down. The number of iterations can be configured to account for faster CPUs.

Also, passwords aren't hashed "naked". Usually you salt them; e.g. add a random salt value to them; this will make the creation of rainbow tables much more difficult, since now one table must be calculated for each separate salt value.