31

The site which I maintain has been in production for 3 years. When you register, the site generates a large (20 digit) random hex password for you. It's stored MD5 hashed unsalted.

When I told the lead dev that MD5 is bad for passwords he said if bad guys get it there's no way they can crack it because the password is random. And even if the bad guy cracks it we generate it so users can't reuse it on other sites.

How can I convince him that we need to use best practices? He is very stubborn...

  • 4
    If someone cracks one of the passwords, what can they do with it? – Royce Williams Sep 13 '17 at 4:23
  • 38
    I know that you say that you generate the password, but is a user able to change the password to something that they want after registration? If so how do you store that password? If it's still unsalted MD5 you have a problem. – zero298 Sep 13 '17 at 6:38
  • 12
    I don't understand what stops the users from memorizing(or writing down) the password from your site, then reuse the nice and random-looking string on other sites. – DreamyDays Sep 13 '17 at 7:10
  • 3
    @ThomasMoors That doesn't stop them, that even encourages them. – glglgl Sep 13 '17 at 7:34
  • 4
    as @Damon says the key question here is whether user's can change their passwords after the initial ones are created. If they can't then the risk of breaking the hashes is low (but the usability of the solution is questionable as more users will not be able to remember a 20 character random string). If the users can change their passwords, whats to stop them choosing something easily crackable? – Rоry McCune Sep 13 '17 at 14:20
47

Ok, so the site generates a random password for each user at registration time. An important question is whether a user can can manually set their password later, or if they are forced to use a random site-generated password. Let's look at the two cases separately.


Random passwords

As far as I can tell, this is the scenario you are describing in the question. Unfortunately, your dev is (mostly) right. At least about single iteration of hashing vs a big slow hash. Your question kinda has the flavour of blindly applying "best practices" without considering what those practices were intended for. For a brilliant example of this, here's a good read:

The Guy Who Invented Those Annoying Password Rules Now Regrets Wasting Your Time

Suggestion

Do switch from MD5 to SHA256, probably add a per-user salt, and maybe consider going to 32 char passwords. But adding a big slow hashing function will increase your server load for little to no added security (at least barring any other goofs in your implementation).

Understanding hashing as a brute-force mitigation

The amount of work a brute-force attacker who has stolen your database needs to do to crack password hashes is roughly:

entropy_of_password * number_of_hash_iterations * slowness_of_hash_function

where entropy_of_password is the number of possibilities, or "guessability" of the password. So long as this "formula" is higher than 128 bits of entropy (or equivalent work factor / number of hash instructions to execute), then you're good. For user-chosen passwords, the entropy_of_password is abysmally low, so you need lots of iterations (like 100,000) of a very slow hash function (like PBKDF2 or scrypt) to get the work factor up.

By "20 digits hex digits" I assume you mean that there are 1620 = 280 possible passwords, which is lower than "best-practice" 2128, but unless you're a government or a bank, you probably have enough brute-force security from the entropy of the password alone.

Salts also serve no purpose here because pre-computing all the hashes is like 280 * 32 bits/hash, which is roughly 1 ZB (or 5000 x the capacity of all hard drives on the planet combined). Rainbow tables help this a bit, but quite frankly, any attacker capable of doing that, deserves to pwn all of us.

You still want to hash the password to prevent the attacker from walking away the plaintext for free, but one hash iteration is sufficient. Do switch from MD5 to SHA256 though, and maybe consider going to 32 char passwords.


Human brain passwords

Commenters on this thread seem obsessed with the idea that, despite your statement that the site generates passwords, users can in fact choose their own passwords.

As soon as the user has the possibility to change the password, the a single hash iteration is no option for storing the now low-entropy password. In this case you are correct that you need to do all the best practice things for password storage.


Salting

Either way (user-chosen or random passwords) you probably want a per-user salt.

If user-chosen, then salts are part of the best practices. 'nuff said.

If random, @GordonDavisson points out a really nice attack in comments [1], [2] based on the observation that a db lookup is essentially free compared to a hash computation. Computing a hash and comparing it against all users' hashes is essentially the same cost as comparing it against a specific user's hash. So long as you're happy getting into any account (rather than trying to crack a specific account), then the more users in the system, the more efficient the attack.

For instance, say you steal the unsalted hashed password db of a system with a million accounts (about 220). With 220 accounts, you statistically expect to get a hit in the first 260 guesses. You're still doing O(280) guesses, but O(260) hashes * O(220) db lookups ~= O(260) hashes.

Per-user salts is the only way to prevent attacking all users for the cost of attacking one user.

  • 6
    The lack of salt might still matter if there are a lot of accounts, since without salt a password-guessing attack can be run against all accounts at once. For instance, if you have a million accounts (about 2^20), an attacker will only have to try (on average) 2^60 passwords before finding one that matches some account. If you have a billion accounts, they're down to only 2^50 guesses (average) before first match. – Gordon Davisson Sep 13 '17 at 3:29
  • 16
    As Mike said, if the password is randomly generated such that it always have sufficient entropy, then using slow hash is not strictly speaking needed. However, one thing I'd definitely check is how the password is generate. Check what PRNG algorithm is used and how that PRNG is seeded. The PRNG need to be seeded with at least 80-bit entropy per generated password for the generated password to contain the full strength of 20 character hex. If the PRNG is seeded with just current vtime, as is common in many weaker applications, you might actually have much less strength than expected. – Lie Ryan Sep 13 '17 at 3:36
  • 1
    @GordonDavisson How are you computing those numbers? Is that some sort of pigeon-hole or birthday analysis? Remember that the limiting resource for brute-force attacks is electricity costs, not time, so I don't see how paralleling that makes a difference. Whether you're trying 2^80 passwords against one account, or 2^60 passwords against 2^20 accounts, you still need to pay the electricity costs of 2^80 guesses. Cryptographers like 2^128 as a security level because that's where we start getting into "multiples of the sun" in power consumption for the attack. – Mike Ounsworth Sep 13 '17 at 3:50
  • 11
    @MikeOunsworth Checking many candidate hashes against many accounts can be sped up considerably (and the power requirements decreased) by first putting the accounts' hashes in a hash table (or bloom filter or...), so you can then do a near-constant-time lookup for each candidate hash. The table (/filter) lookup won't be as fast as a single comparison, but it'll be much much faster than comparing against each account's stored hash separately. Actually, even without that a single MD5 computation followed by 2^20 compares will be faster than 2^20 MD5s, each followed by a single compare. – Gordon Davisson Sep 13 '17 at 6:01
  • 1
    Also, I should clarify that my attack is only advantageous because an unsalted hash was used. A slow but unsalted hash would be vulnerable to the same speedup (although calculating 2^60 slow hashes is going to be a big job -- just not as big a one as calculating 2^80 slow hashes). A fast but salted hash would not be vulnerable to this speedup. When you have a large number of accounts, salting matters. – Gordon Davisson Sep 13 '17 at 19:11
11

Supplementing Mike Ounsworth's answer, your dev is probably correct, providing they're generating their random numbers properly.

If you seed your PRNG that generates these passwords badly, then an attacker can infer the state of your PRNG to predict future passwords. For instance, in a hugely pathological case in which you use a Mersenne Twister with an internal state that isn't refreshed between sessions, the following attack is viable:

  1. I request some large number of accounts in sequence
  2. You generate a correspondingly large number of bytes from your PRNG and send them all to me
  3. I use those bytes to infer the internal state of your PRNG at the time when you generated my passwords
  4. From this, I infer the internal state of your PRNG at the time when you generated every subsequent user's passwords. Every future password your PRNG generates can be predicted by me. Further, the MT can be run backwards to generate all its previous outputs from a known point in time
  5. I have now computed every password in-use by your system without having access to your database

Make sure you use a cryptographically secure source of randomness. Your language's built-in PRNG may well not be.

Also, how are your users actually going to remember these passwords? Generating something long and unpredictable is just going to cause your users to save password.txt on their desktops. If the password is meant to be stashed in a config file somewhere then you probably don't have any real issue, but if it's something that's supposed to live in a user's head then you're massively overestimating the capabilities of your users, and likely causing them to invent their own security flaws.

  • 3
    Good point. Note that this attack applies no matter how secure the password (hash) storage on the server is. – Gordon Davisson Sep 13 '17 at 18:29
0

As others have said, reversing the MD5 of an 80 bit random number is a hard problem, so if anyone obtained your table of hashes, they probably wouldn't be able to access user accounts.

However, you might want to consider where the users are storing those 80 bit random numbers. It probably isn't going to be in their heads. Best case, it's in a reasonably secure keychain or password repository app. Worst case, they'll have a file with PASSWORDS_FOR_YER_APP.TXT in their home directory.

-3

MD5 as you say is insecure, mainly because of discoveries in 2013 that allow it to be collision-attacked in 2^18 time (Apparently less than a second on modern machines).

Regardless of whether of not the password is going to be used on other sites, your site is still insecure. Just because it's random and thus won't appear on lookup tables of any kind, doesn't mean it can't be broken via collision. That means that if somebody gets the hash, they can pretty easily determine something that will function as a password, assuming you check the hashes.

As others have said, use a better method - SHA family are good, but many prefer SCrypt and BCrypt for passwords, and if its randomly generated passwords you're dealing with you probably won't need salt.

  • 4
    Which MD5's collision resistance is every bit as broken as you say, the best known preimage attack still has a complexity of 2¹²³. – Dennis Sep 13 '17 at 14:25
  • 2
    Collision attacks involve the attacker generating a pair of inputs that have the same hash value. If one of the inputs isn't under the attacker's control (as is the case for a password database), weakness to collision attacks is irrelevant. – Mark Sep 13 '17 at 20:51
  • Note that sha1's collision resistance is also demonstrably broken. Nevertheless, collision resistance is irrelevant for password hashing. – Lie Ryan Sep 14 '17 at 12:26

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.