0

I was wondering about md5 encryption. It is good, and I agree that it is unbreakable.

But this is why we have rainbow tables.

What if bunch of people gather together and start brute forcing and creating a hash for every single possible combination of characters. Especially if you are someone like NSA then you probably have computational power to generate hash tables for all possible combinations within relatively "short" time. Therefore wouldn't that render md5 encryption pointless?

Sorry if this is inadequate question, but I simply couldn't stop thinking about this.

Quillion
  • 1,134
  • 5
  • 16
  • 25
  • 1
    Rainbow tables are still a time/space trade-off. They might have the hash computed, but how quickly can they make the match? – schroeder May 08 '14 at 19:21
  • 1
    If they have powerful enough technology to compute and store all the hashes, what is stopping them from having technology to access the hash relatively fast? – Quillion May 08 '14 at 19:25
  • 16
    Whichever source used the words "MD5" and "unbreakable" in the same sentence: You shouldn't trust that source anymore. – Philipp May 08 '14 at 19:40
  • The Distributed Rainbow Table Project already generated ~4TB of [rainbow tables for MD5](https://web.archive.org/web/20160402172945/https://www.freerainbowtables.com/en/tables2), so that anyone could download them. – sampablokuper Aug 30 '16 at 14:09

2 Answers2

23

First of all, MD5 is not an encryption algorithm. It is a hash function. Encryption generally implies decryption, which you cannot do with a hash function.

Who said MD5 is good or unbreakable? It is 'breakable'. The complexity of obtaining a collision for MD5 is around 2^64. This is the equivalent of an exhaustive key search of 64 bits, quite weak for modern cryptosystems.

Another aspect you need to know is you dont need to know the hash of every possible plaintext, but only the first collision they obtain. If A and B for example hashed give the same value, you would only need to store one of them.

MD5 is no longer used in 'reliable' systems. Unix passwords for example stopped being hashed using MD5 quite a long time ago. Now they use SHA-512 (equivalent of a 256 symmetric key).

Anton Garcia Dosil
  • 623
  • 3
  • 7
  • 1
    Thanks, I am completely clueless when things come to hashing and storing passwords, so I thought I would try to learn @_@ – Quillion May 08 '14 at 19:58
  • What is your definition of “breaking”? And where did you get the 2^64 from? – Gumbo May 08 '14 at 20:04
  • 2
    The Birthday Paradox. Read more on it if you like. The final conclusion is that given n numbers there is a probability of sqrt(n) that there is a collision. So for MD5 (128 bits), we would obtain a collision on 2^(128/2) on average - 2^64. My definition of breaking would be obtaining a second preimage for a given hash. – Anton Garcia Dosil May 08 '14 at 20:10
  • 1
    @Quillion Cryptographic weaknesses aside, MD5 is a poor choice for a hashing function. [Use bcrypt](http://codahale.com/how-to-safely-store-a-password/). – Stephen Touset May 08 '14 at 20:45
  • 3
    @AntonGarciaDosil 2^64 is the complexity of a [collision attack](http://en.wikipedia.org/wiki/Collision_attack), not of a [preimage attack](http://en.wikipedia.org/wiki/Preimage_attack). [MD5’s preimage resistance is still 2^123.4 for full preimage.](http://en.wikipedia.org/wiki/MD5#Preimage_vulnerability) – Gumbo May 08 '14 at 20:50
  • @Gumbo Correct. Ill edit it now. – Anton Garcia Dosil May 08 '14 at 20:53
  • 1
    @AntonGarciaDosil - The best collision attack for MD5 is only [2^18 time](https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities). Granted MD5 is still secure for preimage attacks on high-entropy information (best public attack is 2^123). MD5 shouldn't be used for passwords, mostly because users often choose weak low-entropy passwords and MD5 is too fast. Also note MD5crypt ($1$) and SHA512crypt ($6$) used in unix passwords are NOT simply an application of md5 or sha512. They are 1000 or 5000 (default) salted iterations of the simple hash. https://en.wikipedia.org/wiki/Crypt_(C) – dr jimbob May 09 '14 at 06:30
  • 1
    @AntonGarciaDosil - Your statement "SHA-512 (equivalent of a 256 symmetric key)" is completely wrong. For the hash of a password, what matters is not a collision attack but preimage resistance, so for ultra-strong passwords sha512crypt has the strength of 512-bit (unless you fear your attacker has large scale fast quantum computers in which case Grover's algorithm reduces it to 256-bit strength). Granted, you only get 512-bits of security against a very secure passphrase with more than 512-bits of security. Most passwords are far weaker in the realm of 20-80 bits of entropy. – dr jimbob May 09 '14 at 06:33
  • 2
    "My definition of breaking would be obtaining a second preimage for a given hash" - Best second preimage attack on MD5 has complexity of 2^123. Collision attacks are much easier as you get to change both sides of the equation. Preimage attacks don't let you do that. With N=365 days, you need 41 ~ O(sqrt(N)) people in a room for two people to have 90% chance that at least one pair of two people have the same birthday (collision attack). But you need 329 ~ O(N) people in a room before its 90% likely that someone will have the same birthday as you (preimage / second preimage attack). – dr jimbob May 09 '14 at 06:40
5
  • MD5 is not "encryption" - it's a one-way hashing algorithm.
  • MD5 is not "unbreakable" - meaning of unbreakable here is open to interpretation; I'll take it as having security issues. Infact, MD5 is excluded from FIPS as not secure enough.
  • "every single possible combination of characters" - this equals infinity. And not even NSA can likely handle computation of never ending, infinite byte combinations.
Community
  • 1
LB2
  • 420
  • 2
  • 8
  • 1
    There is an upper bound of 2^128 possible outputs from MD5. This is much less than infinity. – Stephen Touset May 08 '14 at 20:46
  • 1
    @StephenTouset Correct in context of preimage attack, but it's not clear from the question if that's the context. I was quite _literally_ answering the _"every single possible combination of characters"_, and that is infinite (with having messages sharing the hash of course). – LB2 May 08 '14 at 20:52