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

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

• This may be helpful. Oct 30, 2016 at 3:19
• I'm not sure how a rainbow table fits in to your underlying question. You are asking about the chance of collision. Can you explain how you expect a rainbow table affects possible collisions? Oct 30, 2016 at 8:04
• Answered here crypto.stackexchange.com/questions/6757/… Oct 30, 2016 at 16:02
• @schroeder if you have a rainbow table of 200 million hashes, obviously the chance of collision is tremendously higher (initially) than brute forcing the hash, right? Oct 30, 2016 at 18:37
• In your mind, what's the difference between creating a rainbow table and bruteforcing hashes? Oct 30, 2016 at 18:38

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.

• "Adobe should know better than to use MD5 to hash passwords and not even use a salt value" You would think so, but apparently they used 3DES with no salts. Oct 30, 2016 at 18:32
• :-) Wow. I took Adobe to basically mean "any large company known to the public offering digital services". I didn't expect the actual Adobe to do that badly on securing their customer's credentials. Oct 31, 2016 at 14:32