21

My understanding is the the main reason MD5 is insecure, is that it can be calculated too quickly, allowing too many attempts to be tried. People recommend instead using a hash that has been designed to be deliberately slow, to provide better security.

However, that only provides security at the current computational speed. Once computers become faster, then these will be no better than md5. So I wonder, is it even possible to have a hash function that is secure, irrespective of the time it takes to execute?

Improve this question
16
  • 3
    @desbest AES is considered to be quantum-safe. As are (I believe) SHA2 and SHA3. What we're missing are signature and public key algorithms.
    – Mike Ounsworth
    Dec 9, 2015 at 15:30
  • 7
    No cryptographic algorithm is secure against an attack with unlimited computational resources (except for a 1-time pad).
    – Dmitry Grigoryev
    Dec 9, 2015 at 19:08
  • 15
    There are passwords so weak that they are insecure regardless of which hash function is used. An example of such a weak password is password. There are passwords so strong that they can be expected to be secure for years to come even if hashed with just MD5. An example of such a strong password is WvpM8jSs4bLqS4aW2skKqsIjM6r6C41B (which of course lost its strength when I posted it here, but there are more passwords where that came from). The boundary between weak and strong passwords lies somewhere between password and WvpM8jSs4bLqS4aW2skKqsIjM6r6C41B.
    – kasperd
    Dec 9, 2015 at 23:18
  • 7
    Where exactly the boundary between secure and insecure passwords lies does however depend on which hash function you are using. So by using a stronger hash function you can push the boundary. If a lot of users choose passwords whose strength lies close to that boundary, then pushing the boundary between weak and strong passwords a little bit can have a significant impact on the average security of your passwords.
    – kasperd
    Dec 9, 2015 at 23:21
  • 6
    Your understanding of the main issue with MD5 is not actually the real issue. The main issue with MD5 is that cryptographers have identified weaknesses in it which permit mathematical attacks to dramatically reduce the number of hashes that actually need to get tried. MD-5 should take, on average, 170,141,183,460,469,231,731,687,303,715,884,105,728 attempts to crack. In reality, due to mathematical exploits, it takes 16,777,216. Usually those numbers are written as 2^127 and 2^24.1, but I wrote them out to show the remarkable change in scale a mathematical attack makes.
    – Cort Ammon
    Dec 10, 2015 at 3:41

6 Answers 6

Reset to default
13

First, MD5 has other problems besides fast hashing speeds, including collision vulnerabilities.

Once computers become faster, then these will be no better than md5. So I wonder, is it even possible to have a hash function that is secure, irrespective of the time it takes to execute?

No, a hash function itself could always be cracked using a sufficiently fast computer ( sufficiently fast being the ambiguous silver bullet). However, implementations of hashing algorithms can address this.

As an example, bcrypt provides mechanisms to address the increase in computation speed.

bcrypt uses the concept of rounds to calculate hashes. For example, bcrypt will hash your password with a salt and a number of rounds:

bcrypt("password","salt",10000)

Note: As pointed out by darkhogg, the rounds parameter isn't actually submitted to bcrypt. Instead a work factor is sent. The difference being that what is sent is actually a number N which is the exponent used to calculate the rounds. So although 10,000 is used here as an example for the number of rounds, the actual work unit you would need to supply to get 10,000 rounds would be much smaller.

hashes the combined salt and password 10,000 times before storing the hash, the salt and the number of rounds. So suppose at the initial time of implementation 10,000 rounds of hashing takes .02 seconds. A year after the initial implementation, you notice that 10,000 rounds only takes .01 seconds, or half the time. You can change the rounds to 20,000. The next time a user logs in, their hash will be computed with 10,000 rounds to authenticate, but the hash will be stored with 20,000 rounds, for future authentication.

Improve this answer
6
  • 6
    Careful! you don't usually specify the number of rounds directly to bcrypt, but instead a work factor, which ends up in an exponent. Right now, on my machine, a work factor of 12 takes 320ms to hash a value, and a value of 13 takes 635ms. Using a value of 10000 will probably make the hash calculation last more than the remaining life of the universe.
    – Darkhogg
    Dec 9, 2015 at 17:22
  • 2
    Good catch. I was trying to explain the concept of rounds, and forgot all about the actual work factor input. I clarified my answer. Thanks.
    – amccormack
    Dec 9, 2015 at 17:29
  • Would you really recompute the hash only once the user logs in? I thought you could just run the another 10000 rounds on the stored hash to get it up to 20000,
    – Bergi
    Dec 9, 2015 at 21:07
  • @Bergi that would work as well. I was going for a simple example.
    – amccormack
    Dec 9, 2015 at 21:15
  • isn't the number of rounds used as a power of 2 for the cost... meaning you would be encrypting the password+salt 2^10000 times
    – SeanC
    Dec 9, 2015 at 22:33
25

So I wonder, is it even possible to have a hash function that is secure, irrespective of the time it takes to execute?

No, of course not. Think of a hash function as something that takes in any string and outputs a short fingerprint of that string. If I have a computer fast enough to list all possible strings and compute their fingerprints (aka hash values), then I can build a lookup table mapping every hash value back to the string that produces it. With an infinitely fast computer with infinitely large memory I can build a lookup table which breaks any hash function, even theoretical ones. Period.

For a real hash function like SHA2 which has a 256-bit output, assume you were magically handed that lookup table for all 2256 possible outputs, and assume it takes you 25 ms to perform each hash, it would take you 6.7x1057 x age of the universe just to verify that the lookup table is correct. Now, if instead of being handed the lookup table, you had to compute it yourself through trial-and-error, that number would be even bigger. So yes, all hash functions can be broken by a "really fast computer", but like really really really fast, like ages of the universe faster than any computer that we have today. [As pointed out by @BlueRaja-DannyPflughoeft in comments, getting enough electricity to do this computation would require consuming several stars so it's not physically possible for a pre-interstellar society]

The reason that attacks are tractable on modern hash functions, which forces us to do tricks like salt&iterate to make them slower, is that for things like passwords you don't need to check all 2256 possible pre-images. If everybody used random password generators then this would be true, but people don't ... in fact 1.5% of us (1 out of every 68 people) use the password "123456" (source). So you only need to check things that people commonly use as passwords. A list of the 100k most common passwords will get you almost all the users on the internet, which a modest computer can check in a few minutes if they are only hashed once. We compensate for people's weak passwords by making each hash computation take longer. If they are salted&hashed 10,000 times then that few minutes on modest hardware goes up to months on a custom GPU rig.

In summary; a lot of the problems we have with hashes aren't because the hashes themselves are weak, but because we're asking them to protect data which is easy to guess.

Improve this answer
6
  • 12
    Interesting tidbit: If you had a computer which used the minimum amount of energy physically possible to flip a single bit, it would take you more energy than exists in the entire sun to build a counter that counts from 0 to 2^256. So we are not going to have computers that can brute-force a hash of that magnitude anytime soon.
    – BlueRaja - Danny Pflughoeft
    Dec 9, 2015 at 21:25
  • Starting with roughly 1e68 years with current tech, and recognizing that with doubling speed every 18 months (thus, 10x every 5 years) it should only take roughly 350 years before such a calculation takes only a month! Hurray!
    – corsiKa
    Dec 9, 2015 at 23:12
  • Nitpticking I know, but there are are more than 1000 minutes in a day, so a few minutes on modest hardware turns to at most a few days on modest hardware :-) 1000 is a low number of rounds by current standards.
    – Steve Jessop
    Dec 9, 2015 at 23:31
  • @SteveJessop It's actually the salting, not the 1000 rounds, that accounts for most of the slowdown because you can't reuse any results from one computation to another.
    – Mike Ounsworth
    Dec 9, 2015 at 23:45
  • 2
    @BlueRaja-DannyPflughoeft Thanks for this. Using pure mathematics we sometimes forget we live in a physical universe which gives us limits outside of pure math. It's a little silly to think that anything could potentially be computable.
    – Steve Sether
    Dec 11, 2015 at 15:04
3

As Mike Ounsworth, amccormack and Romain Clair have stated in their answers, if you have unlimited computing powers, then you will be able to break any hash algorithm by simply (pre-)calculating every possible input.

Your real question is probably: What do I need the hash for and how long will I save it? So if you use hashes for storing passwords I recommend this link: How to securely hash passwords?

But if you just need it because you want to uniquely calculate a temporary identifier for some input, then md5 might still be sufficient for you.

Improve this answer
3

The security of everything is always in a state of change. 40 years ago the DES algorithm was also widely considered to be secure, but increased computing speed has made it crackable with a rather modest amount of dedicated hardware.

30 years ago the unix crypt algorithm (also based on DES) was considered to be slow enough at generating hashed passwords to be secure. It's now obsolete.

More modern password hashing algorithms like bcrypt are designed to have a variable difficulty to account for increasing computing speeds. So as computing power increases, the difficulty of the algorithm can be increased to keep up. Simply increasing raw computing power that we've seen over the last 40 years is unlikely to make bcrypt obsolete.

Security exists within a context, and the context is always changing. Still, we can only account for change we can predict. The increases in computing power are predictable changes. We can't plan for an unknown breaking of the algorithm however (as has happened with MD5).

The point being that any security could potentially be broken at any time. Security is never guaranteed.

Improve this answer
2

Short answer is no.

Most cryptosystems used today, including hash functions, are only secure against an attacker who has limited computational power. They can all be defeated using brute force, but it will take a very very long time to achieve it.

But is it really useful to try to break a cipher if it takes you more than 100 years of intense and extensive computation?

Improve this answer
2
  • Be careful with terminology; this question is about hashes, "ciphers" are different - they require a key while hashes do not. "Breaking" a cipher is very different from "breaking" a hash.
    – Mike Ounsworth
    Dec 9, 2015 at 17:55
  • You're right, my answer may have tried to be too general.
    – Romain Clair
    Dec 10, 2015 at 10:51
2

Once computers become faster, then these will be no better than md5.

They will still be better but maybe not sufficiently better.

Basically an attacker cracks (properly salted) password hashes by taking possible passwords and running them through the password checking function. So

Time to crack password hash = (time to check a password against a hash)*(number of passwords attacker needs to try)

So I wonder, is it even possible to have a hash function that is secure, irrespective of the time it takes to execute?

No.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .