Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How To Safely Store A Password

codahale.com

Post reply on HN
Print view View original

161–170 of 219 posts

Re: How To Safely Store A Password

#161

Post by Locke1689 »

tptacek wrote: post #155
Locke1689 wrote: post #141

Earlier quoted context omitted.

It's not deep enough to provide true knowledge of cryptography and cryptographic attacks while it also doesn't give practical advice on what to actually do in situations that require cryptography (read: always use high-level primitives). Applied Cryptography is pretty good (if outdated), I think, if you're seeking to gain a beginner-level knowledge of cryptography. Practical Cryptography, on the other hand, is a far…

If you think _Practical_ is outdated (and I'm not saying it isn't), you should come over and let us buy you coffee sometime.

Haha I'll take you up on that when I get back to Northwestern. I'll admit that the only reason I think it's outdated is because I was just teaching basic cryptography to the network security students and ran across a few things that made me think "Hmm, Niels/Schneier should really include this in their next printing." Some things I'm thinking of are EAX/GCM instead of the conventional CTR.

Re: How To Safely Store A Password

#162

Post by alanh »

jasonwatkinspdx wrote: post #151
Cushman wrote: post #32

I wonder, is it easy to use bcrypt with a variable work factor per-password? I'm thinking you could take your entropy analysis of the user's password and set it so that "weaker" passwords use a higher work factor. This analysis could be easily done before hashing every time the password is input, so an attacker wouldn't be able to single out weak passwords from the hash file. Theoretically, you should be able to tail…

This exposes information about the password: namely it's estimated entropy. The bet you're making is that the increased work factor overshadows any advantage an attacker may gain knowing that information. How could someone use this? Well, I could decide to only target the rows with a low work factor. Since your entropy estimate is high for these rows, I can know that it's more likely they'll be 8 characters or longer…

If I’m remembering my discrete math correctly, your claim isn’t correct:

> … Let's assume 2 choices of work factor. Also let's assume strong passwords of length 8 have 96^8 ~= 53 bits of entropy and eak passwords of length 8 or less have 27^8 ~= 38 bits of entropy.

> You just let me cut the search space for strong passwords of length 8 to to ~15 bits…

You can’t subtract bits of entropy like that.

Here’s something I hope will convince you this reasoning is faulty.

Imagine a universe of 3-digit passwords, and there are two kinds of passwords: Strong ones use a mix of digits 0–7, and weak ones only use the digits '0' or '1'.

You could see the strong passwords could be any of 8^3 = 512 different combinations (~9 bits of entropy), except the 2^3 = 8 combinations (3 bits of entropy) that would only contain ones and/or zeros. So while a worst-case for brute-forcing a known-weak password is trying 8 strings, the worst-case for brute-forcing a known-strong password is trying 504 strings. This is still the same order of magnitude, and still approx. 9 bits of entropy! You removed such an incredibly small sliver of passwords, that an attacker really isn’t any better off than before.

Another way to think of this is, just because the user didn’t use only lowercase letters, doesn’t mean that none of the characters are!

Back to your example, with a strong password search space of 96^8. Now if you know a password is strong, that means it isn’t one of the 27^8 possible weak passwords. By how much does this reduce our search space?

  7,213,895,789,838,336 possible strings of length 8

- 0,000,282,429,536,481 possible 'weak' 8-char passwords

= 7,213,613,360,301,855 possible 'strong' 8-char passwords

We’ve reduced our search space by only .0039%.

That said, rolling your own crypto — which the grandparent post isn’t really quite doing — is something you should run away from, fast, unless you really are a cryptographer!

Re: How To Safely Store A Password

#163

Post by gxti »

gcr wrote: post #143
andreyf wrote: post #133

Earlier quoted context omitted.

"6ab$TRa?" has never been counting on the difficulty of hashing for security, and probably won't for some time. False.

Elaborate. Obviously its security depends on the hashing scheme (if it's CRC32, you could find a collision pretty easily), but educate us -- is that all you meant?

To nitpick, the topic at hand is pre-image attacks, not collision attacks. Pre-image is where you know the hash and want the plaintext, collision is where you create two plaintexts with the same hash but don't care about the actual hash value. The former is recovering information, the latter is falsifying trust and almost always involves signatures.

Collision attacks don't apply to many situations but are much easier to execute, for example a MD5 pre-image attack requires approximately 2^128 steps but a collision attack requires only about 2^64 steps. This is why MD5 is totally unsuitable for collision resistance, and in fact has already been successfully exploited to fabricate a real-world CA certificate, but still puts up mild resistance to password cracking. Not that I'm recommending you use it or anything -- do what the nice gentleman says and just use bcrypt already!

Re: How To Safely Store A Password

#164

Post by gxti »

gcr wrote: post #142
Cushman wrote: post #32

I wonder, is it easy to use bcrypt with a variable work factor per-password? I'm thinking you could take your entropy analysis of the user's password and set it so that "weaker" passwords use a higher work factor. This analysis could be easily done before hashing every time the password is input, so an attacker wouldn't be able to single out weak passwords from the hash file. Theoretically, you should be able to tail…

Hm. I don't know about bcrypt at all -- is it possible, given the ciphertext, to know roughly how much work is required to test a password? E.g. an attacker can go "Oh! this password will take FIVE SECONDS to test, so I know it must be a simple password." or "Hey, check this out; this password can be tested in 0.1 seconds. It must be pretty complex." In general, I'd guess that these kinds of information leaks are pre…

> is it possible, given the ciphertext, to know roughly how much work is required to test a password?

The work factor is an input to the digest function, both when creating and when validating the password. Normally it should be stored alongside the digest itself so you can increase the work factor over time without disrupting existing passwords. So you are correct. It might theoretically be possible to correctly balance the work factor to counter variation in password info entropy so that all passwords take about the same time to crack, and this would be very cool and impress members of the opposite sex, but it would not improve security at all.

Making a probabilistic password checker is also a superficially interesting idea. Maybe my mind is too small to explore it completely, but it seems that at best it would be no better than just increasing the work factor.

Re: How To Safely Store A Password

#165

Post by Raphael »

asdfor wrote: post #117

Its really simple , AS LONG AS the user uses a weak password, using bcrypt or not wont protect him. Why ? Well instead of brute forcing the hashed password i'll directly try to bruteforce using the normal login method of your site (even if you rate limit my login attempts it wont take that much time...(see proxys)(if you are thinking about rate limiting per username etc you suck). If you need yours users account to b…

I think rate limiting per user is perfect. And if the real person wants to log in while someone else used up their attempts, do a quick email confirmation.

Re: How To Safely Store A Password

#166

Post by a_m0d »

jasonwatkinspdx wrote: post #151
Cushman wrote: post #32

I wonder, is it easy to use bcrypt with a variable work factor per-password? I'm thinking you could take your entropy analysis of the user's password and set it so that "weaker" passwords use a higher work factor. This analysis could be easily done before hashing every time the password is input, so an attacker wouldn't be able to single out weak passwords from the hash file. Theoretically, you should be able to tail…

This exposes information about the password: namely it's estimated entropy. The bet you're making is that the increased work factor overshadows any advantage an attacker may gain knowing that information. How could someone use this? Well, I could decide to only target the rows with a low work factor. Since your entropy estimate is high for these rows, I can know that it's more likely they'll be 8 characters or longer…

If I understand the grandparent correctly, there would be no way to determine which rows have a higher work factor. The work factor would be determined when the password is given, based on the password entropy - the correct password will always have the same entropy, therefore the same work factor. If the work factor is calculated on the wrong password (typo, etc.) it will not generate the correct hash anyway. Therefore an attacker has no way of determining which password hashes have a high work factor, and which ones have a low work factor.

Re: How To Safely Store A Password

#167

Post by gxti »

beej71 wrote: post #80
bostonvaulter2 wrote: post #48

If you have a 5-year old database using a given bcrypt work factor, how difficult is it to transition to a new, higher work factor?

This is a good practical question. My read of the algorithm is that you must force each user to enter a new password, and encrypt that at the new higher cost. If you wanted to "upgrade" the passwords to the higher cost key schedule, you'd just continue the key schedule where it left off--but this would require knowing the original password! So that's not really an option.

You can upgrade passwords when the user logs in. The sanest thing to do seems to be to store all the public variables (work factor, salt) alongside the digest so each password can be handled separately.

Re: How To Safely Store A Password

#168

Post by gxti »

tocomment wrote: post #150

Some everyone is saying how easy it is to crack md5. Say I have an md5 hash and I know it was created from a 1000 byte string. How long would it take to enumerate all 1000 byte strings that could create that hash?

Actually you can (almost surely) stop cracking at 16 bytes, because that's how long MD5 digests are and any more bits than that are going to give you hashes you've already seen. You won't get back the original string but you don't need the original string.

Re: How To Safely Store A Password

#169

Post by count »

16s wrote: post #121

Micrsoft Active Directory stores what it calls an NT Hash in NTDS.DIT files on domain controllers. These are unsalted, md4 hashed, unicode strings. They are fast and easy to crack if you ever do get your hands on them. The point is that many big companies don't do passwords right, so why expect Gawker to do so? Edit: md4 is not a typo. They use md4 not md5... OK.

And that's not the only place they're stored (assuming the default cached credentials setting is still in place). Also, with the advent of pass-the-hash, you don't need to crack Windows AD passwords to use them anymore. Just having the hash is enough for loads of fun.

Re: How To Safely Store A Password

#170

Post by asdfor »

davebob wrote: post #160
asdfor wrote: post #117

Its really simple , AS LONG AS the user uses a weak password, using bcrypt or not wont protect him. Why ? Well instead of brute forcing the hashed password i'll directly try to bruteforce using the normal login method of your site (even if you rate limit my login attempts it wont take that much time...(see proxys)(if you are thinking about rate limiting per username etc you suck). If you need yours users account to b…

please explain what you mean by rate limiting and why that's no good.

In some period of time a user is only able to do some amount of login attempts, after that he has to wait until he can try again to login. You can do that per IP or per username, doing it per username its not good because someone can abuse that to block the genuine user to log in. Doing it per ip is the best option you have and i didn't say that its not good, what i said is that if the user uses a weak password even if you put a rate limit they will be able to find the password soon enough.
Post reply on HN