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.

|improve this question
  • 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 8 '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 8 '14 at 19:25
  • 15
    Whichever source used the words "MD5" and "unbreakable" in the same sentence: You shouldn't trust that source anymore. – Philipp May 8 '14 at 19:40
  • The Distributed Rainbow Table Project already generated ~4TB of rainbow tables for MD5, so that anyone could download them. – sampablokuper Aug 30 '16 at 14:09
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).

|improve this answer
  • 1
    Thanks, I am completely clueless when things come to hashing and storing passwords, so I thought I would try to learn @_@ – Quillion May 8 '14 at 19:58
  • 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 8 '14 at 20:10
  • 1
    @Quillion Cryptographic weaknesses aside, MD5 is a poor choice for a hashing function. Use bcrypt. – Stephen Touset May 8 '14 at 20:45
  • 3
    @AntonGarciaDosil 2^64 is the complexity of a collision attack, not of a preimage attack. MD5’s preimage resistance is still 2^123.4 for full preimage. – Gumbo May 8 '14 at 20:50
  • 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 9 '14 at 6: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.
|improve this answer
  • 1
    There is an upper bound of 2^128 possible outputs from MD5. This is much less than infinity. – Stephen Touset May 8 '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 8 '14 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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