Can any password hash ever be secure?

Question

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?

bcrypt / Blowfish has a cost factor which you can use to change password hashes at any time. — Daniel Ruf, Dec 09 '15 at 15:15
That's why people _salt_ hashes. The in thing is to use bcrpyt. If quantum computers ever become viable, all encryption will become broken. — desbest, Dec 09 '15 at 15:16
@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 09 '15 at 15:30
@Benu Your question is about passowrd hashes, right? Since you mentioned deliberately slow hashes. — CodesInChaos, Dec 09 '15 at 16:31
No cryptographic algorithm is secure against an attack with unlimited computational resources (except for a 1-time pad). — Dmitry Grigoryev, Dec 09 '15 at 19:08
@desbest this is incorrect. There exist encryption algorithms specifically designed to be secure against fast calculation from quantum computers. Search `post-quantum cryptography`. Plus, you can continue to use symmetric ciphers as long as you double the key size (ie AES-128 bit security level on quantum computer uses 256 bits instead) — d0nut, Dec 09 '15 at 22:43
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 09 '15 at 23:18
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 09 '15 at 23:21
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 '15 at 03:41
@DmitryGrigoryev : That [is incorrect](https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing). — , Dec 10 '15 at 04:57
@RickyDemer Why? Given unlimited computational resources, the attacker can just brute-force the missing parts of the secret (or all the parts, if need be). — Dmitry Grigoryev, Dec 10 '15 at 06:49
@DmitryGrigoryev : Like for a 1-time pad, the attacker can do that even without the secret sharing. — , Dec 10 '15 at 07:18
@DmitryGrigoryev Shamir's Secret Sharing Scheme works such that the correct solution is indistinguishable from any other. It is information theoretically secure. Every share hold as much entropy as the secret. — Natanael, Dec 10 '15 at 08:20
@nataneal thanks for pointing me to SPHINCS. There are also Merkle signature trees and lattice-based PKI, but no CA currently issues certs with those signatures, SSL deos not support those ciphers, etc, so I stand by my "we don't _have_ them yet". — Mike Ounsworth, Dec 10 '15 at 11:46
*"a hash function that is secure, irrespective of the time it takes to execute?"* Imagine a hash function that gives a 128-bit output and takes 0 time to execute on an arbitrary input. (This is obviously not possible in practice, but stay with me.) For such a function, you could compute all 2^128 hashes in 0 time. As computer speeds increase, the amount of time required to perform a given operation approaches 0. We can design a function that is slow enough today, but it will never be secure in an environment where it takes 0 time. The boundary for practically secure lies somewhere in between. — user, Dec 10 '15 at 12:58

Mike Ounsworth · Answer 1 · 2015-12-09T23:59:45.913

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 2²⁵⁶ possible outputs, and assume it takes you 25 ms to perform each hash, it would take you 6.7x10⁵⁷ 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 2²⁵⁶ 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.

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 09 '15 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 09 '15 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 09 '15 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 09 '15 at 23:45
@corsiKa [Your logic is flawed.](http://security.stackexchange.com/a/6149/2138) — user, Dec 10 '15 at 12:50
@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 '15 at 15:04

score 14 · Accepted Answer · edited Mar 17 '17 at 13:14

14

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.

edited Mar 17 '17 at 13:14

Community

1

answered Dec 09 '15 at 15:17

amccormack

3,971
1
15
23

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 09 '15 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 09 '15 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 09 '15 at 21:07
@Bergi that would work as well. I was going for a simple example. – amccormack Dec 09 '15 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 09 '15 at 22:33
@SeanC lol, do you have any idea how large a number 2^10000 is?? That's about 10^3000, For comparison, the age of the universe is only about 10^20 ms, and there are about 10^85 particles in the universe. 2^10000 = 10^3000 is an obscenely large number. – Mike Ounsworth Dec 10 '15 at 17:49

score 3 · Answer 3 · edited Mar 17 '17 at 13:14

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.

score 3 · Answer 4 · answered Dec 09 '15 at 15:53

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.

score 2 · Answer 5 · edited Dec 09 '15 at 17:54

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?

edited Dec 09 '15 at 17:54

Mike Ounsworth

57,707
21
150
207

answered Dec 09 '15 at 15:19

Romain Clair

550
2
10

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 09 '15 at 17:55
You're right, my answer may have tried to be too general. – Romain Clair Dec 10 '15 at 10:51

score 2 · Answer 6 · answered Dec 09 '15 at 20:36

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.

Can any password hash ever be secure?

6 Answers6