How To Safely Store A Password

http://codahale.com/how-to-safely-store-a-password/#

by IgorPartola • 16 years ago

298 210 16 years ago

jimwise3• 16 years ago

I'm not so sure. The other side of the coin is that ``{MD5, SHA1, SHA256, SHA512, SHA-3, etc}'' have had extensive peer review in the cryptography world.

There's a long history of ``clever new ways'' to use existing crypto algorithms turning out to have serious flaws -- a good example is early attempts to improve the strength of (56-bit key) DES by encrypting three times with three keys. This turns out to introduce enough non-randomness to make the result much weaker than one might expect; standard 3DES works by encrypting with the first key, decrypting with the second, and encrypting with the third, which results in very different properties of the output cyphertext.

I'm not saying BCrypt has the same sort of issues, but I'd like to see some cryptanalysis of this before trusting my users' data with it. Notably, there seems to be no links to such analysis on the BCrypt home page -- not even an argument from the author as to why this code should be cryptographically sound.

Xk19• 16 years ago

No. Use Bcrypt. Always.

Bcrypt is backed by Blowfish, designed by Bruce Schneier. Go look it/him up. It's secure.

MD5/SHA1/etc are not weak because they are cryptographically weak (though some are), it is weak because they are fast. SHA3, when it is picked, will still be a very bad choice because it too will be fast.

So, why Bcrypt? Well, it uses Blowfish. Blowfish has a very slow key scheduling algorithm which basically involves a lot of hashing to get the round subkeys. Bcrypt makes this even slower. So what? Well, with Bcrypt you could set it up to take .3 seconds to verify a password. Try bruteforcing on that.

ax0n3• 16 years ago

Indeed. Blowfish is also standardized and has withstood peer review, cryptanalysis and has otherwise been baptized by fire. Plus, if it's good enough for people as picky as Theo DeRaadt, it's probably good enough for you.

jimwise3• 16 years ago

The question is not whether BCrypt is backed by Blowfish, the question is whether BCrypt uses Blowfish in a way which is cryptographically sound. If it does not, then an attacker may not need to use brute force. Assuming the author has read more of Mr. Schneier's book than the quoted preamble, he should know this -- Schneier discusses this at length in both editions of Applied Cryptography.

Again, an example of this is the 3DES encrypt/decrypt/encrypt process vs. a more naive encrypt/encrypt/encrypt process. One is substantially stronger than the other. One is a secure way to use DES, and one is not.

kd0amg• 16 years ago

Bcrypt is backed by Blowfish, designed by Bruce Schneier. Go look it/him up. It's secure.

Well, yes, I trust the Blowfish cipher (and GP probably does too). The question is how we can be sure it isn't being somehow misapplied, i.e. whether the way bcrypt uses it opens some other hole. That's what I (and probably GP) would like to see an expert weigh in on.

Ixiaus3• 16 years ago

Question, I use SHA512 for my passwords; is that also "fast" in comparison to bcrypt?

sparky2• 16 years ago

"A Future-Adaptable Password Scheme" by Provos and Mazieres. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80....

An HTML version appears to be here: http://www.usenix.org/event/usenix99/provos/provos_html/node... Some of the links, particularly the main page, appear to be broken.

jimwise3• 16 years ago

As with the website, that paper discusses only the speed of BCrypt. There is no cryptanalysis at all, and no indication that BCrypt was submitted anywhere for peer review of its cryptographic soundness.

This doesn't mean BCrypt is unsound. It does mean that I would want to see such analysis before using it.

tocomment2• 16 years ago

HN, is this the consensus? I thought certain hashes worked fine when properly salted?

frisco2• 16 years ago

Yes, this is consensus. "Salting" isn't actually a real security practice. See: http://chargen.matasano.com/chargen/2007/9/7/enough-with-the...

aidenn02• 16 years ago

That article actually states that salting is a real security practice, is a necessity, and that it's been in UNIX since 1976,

ax0n3• 16 years ago

In a case like the Gawker incident, it isn't safe. If the source code to the password hashing algo is compromised (it was) then the salt becomes useless. In short, just use bcrypt.

Xk19• 16 years ago

No. No no no.

The source code to the hashing algorithm means nothing. It is already open source!

The reason that the salt is there is to prevent against rainbow tables.

The salting did NOT become useless. If they had not salted passwords, then many many more passwords would have been broken because instead of having to brute force each and every one, you'd just look it up in a massively large hash table.

aidenn02• 16 years ago

Salting and choice of hashing algorithm are orthogonal. If it takes X amount of time to brute force a password of strength Y and you do salt, then an attacker can crack N passwords of strength Y in time NX. If you don't salt, then an attacker can crack all* passwords of strength Y in time N, which is a huge difference.

sph• 16 years ago

The problem is that it's relatively easy to brute-force attack even a salted hash today.

On the first day, people stored passwords in plain text. If someone got access to your database, they had all the passwords.

On the second day, people decided to hash the passwords so that people couldn't unencrypt them. Then the attackers created rainbow tables that correlated each hash with its associated password since the password would always hash to the same value (so you have "109BCA" in your database, but they have a table that has that hash and that "12345" hashes to that value).

On the third day, people decided to salt the hashes to render the rainbow tables ineffective. Now, each password would hash to a different value so they couldn't just look up the password for a given hash. However, as computing power increased it became easy to just brute-force the password. You have the hash and you have the salt so you can just try every password with the hash until you get a match.

  hashed_password = "ACBDEF1234567890"
  salt = "12345"
  possible_passwords = ["password1", "ilikesheep", "micro$oft"]
  possible_passwords.each do |pass|
    if Digest::SHA1.hexdigest("#{pass}#{salt}") == hashed_password
      real_password = pass
    end
  end

The problem is that code like that has gotten really cheap to run and it's incredibly parallel (you can have loads of machines each take a piece of the workload - oh, and hopefully no one will make a joke that you'd never write that in Ruby; I just felt that would be easy pseudo-code to demonstrate). You can just try combinations of passwords at random, but there are lists of more common passwords that you can try first making it go even faster. Hashing algorithms are meant to be fast because they're meant to be usable on a large piece of data. As such, it also becomes fast to brute force check all sorts of combinations.

On the fourth day, people started using things like bcrypt because bcrypt was made to be slow. The fact that bcrypt is slow means that if someone wants to brute force it, it will be very slow going for them. If one can check 10,000 SHA1 hashes in a second, but only 10 bcrypt hashes in a second, it will take 1,000x longer to crack the bcrypt stored password (those are just made-up numbers as an example).

Salting is better than not salting because they have to brute force the password. However, as computing power increases it isn't so much better because brute forcing is becoming easy. One needs to use a slow algorithm to make sure that cracking it will also be slow (prohibitively slow). Bcrypt also allows you to specify how much work you want it to have to do. This way, as computing power increases, you can increase the amount of computing power needed to compute the bcrypt. By contrast, hashes are meant to go fast and so every day they're getting less secure.

tzs• 16 years ago

Salting was introduced long before rainbow tables were invented.

amalcon• 16 years ago

The salt does exactly one thing: it makes the attacker pay to get each password, as opposed to making them pay once and get all of them. When the cost is a fraction of a second on a commodity CUDA setup, it's not really that helpful to make an attacker pay it multiple times.

jmillikin5• 16 years ago

"It’s important to note that salts are useless for preventing dictionary attacks or brute force attacks. You can use huge salts or many salts or hand-harvested, shade-grown, organic Himalayan pink salt. It doesn’t affect how fast an attacker can try a candidate password, given the hash and the salt from your database."

Why are you storing the whole salt in your database? Isn't it much more common to keep half of it in a configuration file? I know Django has a SECRET_KEY parameter for this sort of thing, and hopefully other frameworks do also.

For that matter, why is authentication being handled by the web server? If you've got data worth stealing (billing, emails, medical), you can afford to spring the extra few hundred for a proper authentication server.

Gawker's password handling (7-bit salt, in the database, digested with crypt) seems like the worst possible implementation of secure password storage.

beej714• 16 years ago

If you want to crack passwords ultrafast, you make a look-up table of the hashes of all probable passwords. Without a salt, this is rather a smaller table. A 7-bit salt makes the table larger, but not hugely larger, and not troublesomely larger.

The 128-bit salt used by bcrypt makes the table intractably hugely large. You cannot precompute it.

Of course, you know the salt (because it's stored right there in /etc/shadow), so you can still run through dictionary words and try them all. But bcrypt is designed to take arbitrarily long amounts of real time to do this.

So in the case of bcrypt, it's not really an issue that the salt is stored right there alongside the hashes password.

tptacek27• 16 years ago

Those password crackers that are belting through billions and billions of passwords an hour with just a couple of video cards aren't using rainbow tables, are they? You could have zero bit salt: you're still boned.

Bcrypt is not better because it has a better salt. It's better because one iteration of bcrypt takes a long time, and millions of iterations take an intractably long time.

izak30• 16 years ago

I may be mistaken, as I was only browsing. I was looking at Django's auth system last night (as all of this had me curious about the backend). I don't think that SECRET_KEY is used for part of the salt at all, I think it's primarily used for validation of site-generated data, signing requests, and cookie encoding/decoding.

jmillikin5• 16 years ago

You're probably correct; when I used Django I had to reimplement the auth, since their built-in doesn't support roles, and I didn't look too closely at their implementation.

StavrosK8• 16 years ago

You are correct, Django's hashes are stored as salt$digest, or maybe salt$function$digest nowadays. It wouldn't be very good if all your password hashes became invalid because you changed the secret key.

tptacek27• 16 years ago

That salt is a public value. The security of salted password schemes is meant not to depend on the secrecy of the salt.

Every time this topic comes up, 15 people chime in with various schemes in which some of the "salt" is derived from the hostname and some of it is stored in an encrypted vault and some of it is inferred from the color of the user's eyes. This is why Coda is making fun of "Himalayan pink salt".

To understand how irrelevant these details are, consider AES encryption. In addition to hiding an AES key, you can also hide portions of the AES CBC IV (a public value). You could use a random number of rounds. You could mix in tweaks with the round key. All of these things are possible, but (a) nobody analyzes AES based on those random hacks, because they don't fundamentally alter the properties of AES, and (b) nobody does those things, because they are silly.

Gawker could use the best conceivable practices in cryptography to obscure passwords; they could be using Colin Percival's scrypt function (which nobody uses yet) to be (in some way) provably resilient to hardware-assisted cracking. You could still level this criticism at them, for "not doing something to further obscure the encryption they used".

This is not a new argument; what I am re-explaining here is Kerckhoffs' principle.

jmillikin5• 16 years ago

> That salt is a public value. The security of salted password schemes is meant not to depend on the secrecy of the salt.

I don't understand why you'd add extra content to the password unless you keep it secret. The whole point of a salt/nonce is to prevent attackers from attacking the digest, right? You need some per-user data, to defend against rainbow tables, and some per-site data, to protect weak passwords.

My fundamental objection to schemes like bcrypt/scrypt is that they impose a heavy performance penalty on authentication to avoid a relatively rare case; besides, any theoretical entity capable of reversing a typical salted-password implementation is also capable of reversing bcrypt/scrypt.

cosgroveb• 16 years ago

Chrome OS is using scrypt!

whakojacko• 16 years ago

How is that really any better? You should assume that if an attack can get to your database, they can get to your web servers and take all of that as well. Such a scheme certainly wouldn't have saved Gawker.

jhchen2• 16 years ago

In Gawker's case this is exactly right. The database AND the source code was accessed so the config file defense would not have worked.

jmillikin5• 16 years ago

Config files are not typically world-readable; the httpd reads them before dropping permissions. Otherwise, a vulnerability in the httpd would allow access to everything in the config (remote server passwords, signing keys, etc).

There's no reason why compromising the database would allow attackers into the web server, unless you've configured SSH to allow signing in from arbitrary remote systems.

Cushman8• 16 years ago

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 tailor the numbers so that cracking a weak password isn't any faster than cracking a strong one, right? Plus it will encourage your users to use a stronger password in the first place, since it'd make login slightly faster.

Any obvious problems with this plan?

tptacek27• 16 years ago

It's not hard to do this (with Ruby bcrypt, it's 2 lines of code using the public interface), but I think you're overthinking it. Most users will use crappy passwords. Set the work factors uniformly high.

Cushman8• 16 years ago

Definitely a good point.

I feel like it might still help you to avoid wasting time exhaustingly hashing already strong passwords. I mean, how high does that uniform work factor have to be?

The guy whose password is "password" or "qwerty12" is gonna get cracked no matter what, sure. But what about people whose passwords are a couple of dictionary words? If the work factor means each hash takes a second or two, even a slightly complex dictionary attack becomes fruitless (for most crackers...)

So the user can still log in, but it takes a second or two, and there's that little message, "To ensure the safety of your password, your login has been slowed down. If you use a more secure password, like <generate password>, you will login much faster!"

And the young lady using "6ab$TRa?" isn't being punished for the fact that most users use crappy passwords, nor is your server.

joshu• 16 years ago

Dumb idea:

Have the work factor also be a function of the password itself... this would cause even more difficulty brute-forcing the password, as it means intermediate steps would also have to be tested - breaking one weak password doesn't give you any information about other passwords.

mfukar2• 16 years ago

The definition of a "weak" password is so loose it doesn't make sense to make your work factor a function of it. The most common attack on this kind of schemes is a side-channel attack, where you single out a subset of the password alphabet with a relatively small "work factor" and crack passwords which use that alphabet quickly.

BCrypt is already based on the premise that there are passwords which are easy to compute, and tries to avoid that differentiation. Why would you introduce it back in?

Cushman8• 16 years ago

I see it as a kind of side-channel defense; take the set of passwords which it is possible to crack quickly and use the work factor to even it out so that the total time to crack a password remains relatively constant.

Of course it's a good point that the challenge then becomes determining what that set of passwords is. And not having run the numbers, I can't be sure how much room for improvement there is.

gcr3• 16 years ago

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 pretty bad because if an attacker can see how hard a password is to test, he now knows something about the password.

It may be better if, given a single unchanging hash, if it takes a variable amount of time to test a given password against this hash, though that might have its own can of worms.

Cushman8• 16 years ago

Yeah, obviously if you can tell from the hash which class the password came from you lose the benefit.

gxti6• 16 years ago

> 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.

rorrr• 16 years ago

Doesn't matter. 5 seconds or 0.1 seconds per test means that you cannot brute-force. Even for 5-letter English lowercase letters your search space is 11,881,376 combinations. At 0.1 sec/try it will take you 6.8 days on average to find just one password.

jasonwatkinspdx3• 16 years ago

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 and use a wider range of characters. I can likely ignore all candidate passwords that are shorter or that do not include non-alpha characters.

How useful is this? 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, and in a double whammy, I get to use bcrypt with a low work factor when brute forcing against these rows.

I'm not a cryptographer, and so it's entirely likely I've made some mistake here. But as a general rule, I think it is an _extremely_ bad idea to use cryptography in any way that exposes additional information about individual rows in a database.

Cryptography is not a place for innovative thinking. Even cryptographers need their cleverness to undergo exhaustive review.

alanh• 16 years ago

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!

a_m0d• 16 years ago

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.

bostonvaulter22• 16 years ago

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?

pavel_lishin• 16 years ago

Follow-up question: I assume this also means that it would result in new hashes for the same passwords?

wladimir• 16 years ago

Yes. But from what I understand, that's even the case if you bcrypt() the same password with the same load factor multiple times, as it uses a random salt.

miGlanz3• 16 years ago

Imagine this Python code (I'm using SHA1 iterated multiple times, basically PBKDF2):

    import hashlib
    hashed = password
    for i in range(50000):
        hashed = hashlib.sha1(salt + hashed)

Provided we also store the number of iterations (along with the salt), and provided I didn't do anything stupid above, we could simply add more iterations after these 5 years and update hash and number of iterations field. Would it be a viable solution?

tptacek27• 16 years ago

Yes.

beej714• 16 years ago

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.

miGlanz3• 16 years ago

What about performing the hashing again, on the existing hash (of course it would be simplest to encrypt from the beginning when user logs in again, but just for discussion's sake). Let's say we have a legacy db with hashes created with small work factor. We could simply perform the hashing on these previous hashes (increasing work factors as appropriate). We could simply annotate the fact that one have to perform the hashing two times.

Of course we're 'overthinking' it again, but is the above solution viable?

gxti6• 16 years ago

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.

yummyfajitas• 16 years ago

I'm no expert, but I think you could just convert a database via function composition:

    new_hash = (bcrypt new_work_factor) . old_hash -- new hashing function

    new_hashed_passwords = map bcrypt old_hashed_passwords -- convert the old hashed passwords to new

Of course, this will fail horribly if (bcrypt new_work_factor) is somehow an inverse (or partial inverse) of old_hash. It could also fail horribly if (bcrypt new_work_factor) maps it's input into a low "rank" (sorry, I'm a mathematician, not a crypto expert) region of old_hash's domain.

eru2• 16 years ago

But if one of those two properties where true, that would probably give you some hints into how to attack bcrypt.

kurin• 16 years ago

If a user logs in, and their work factor is the low one, authenticate them, and then calculate the new hash with the higher work factor, and save the new hash and work factor.

timtadh3• 16 years ago

B-crypt and S-crypt are great libraries to use to solve this problem. However, the poor man's approach is as follows with HASH being your favorite hash function

    h = HASH.new()
    HASH.update(password)
    HASH.update(salt)
    for x in xrange(X):
        HASH.update(HASH.digest())
    return HASH.digest()

this approach "strengths" the hash by forcing you to calculate it over and over again. You should set X to be the number of rounds you want to conduct. Ie. how slow you want you server to respond to an individual request. It is always a trade-off between server slowness for individual requests and "security" of the hash function. The goal is to make dictionary attacks take longer than is feasible for you attackers to conduct.

[Note: you should absolutely have a different salt for each password with this approach.]

tptacek27• 16 years ago

For what it's worth: this is essentially PBKDF2.

cperciva2• 16 years ago

Actually, it's essentially PBKDF1, but that's close enough for non-cryptographers.

brown9-22• 16 years ago

Why would you use this "poor man's approach" over bcrypt or scrypt? My understanding is that these two work on a very similar concept (work factor) and are free to use.

csytan2• 16 years ago

I can think of one reason: Lack of the available libraries on a particular platform.

jrockway2• 16 years ago

Because building your own square-shaped wheel is more fun than talking a walk over to your friendly neighborhood wheel store and buying a round one?

burgerbrain2• 16 years ago

Because we all know rolling your own in the crypto world instead of deferring to the experts never leads to catastrophe!

ams61102• 16 years ago

Some projects require FIPS 140-2 compliance. I've not been able to find that blowfish or bcrypt are certified. See http://csrc.nist.gov/publications/fips/fips140-2/fips1402ann...

IgorPartola2• 16 years ago

Why not also add

  HASH.update(salt)

On each iteration as well? Then again, if things were this simple, someone would have already said "just do this", it would have been peer-reviewed and would have become widely used. Anyone know why this hasn't caught on yet in web frameworks like Django/Rails?

Xk19• 16 years ago

If you're talking about why you don't do hash.update(salt) on every round, well it turns out that H(salt || H(H(H(H(H(H(password))))))) is just as strong as H(salt || H(salt || H(salt || H(salt || H(salt || H(salt || H(salt || password))))))). So you don't add any security by doing that.

When working with cryptography, "why not also add" is really dangerous, because some times you get less secure systems after doing so. And other times you get no benefits from doing so.

Raphael3• 16 years ago

What value of X would be good for a web app? 10? 100? 1000?

tptacek27• 16 years ago

1000 is a minimal value.

timtadh3• 16 years ago

As I said, it depends on how slow you want your server to respond to a given request. For instance, you could set X so high that it takes a minimum of 1 second to respond to a request. That is probably not necessary. The real answer is you need to take the estimated minimum amount of time to calculate one of hash using the function you have chosen. Then compute using that number as the basis the minimum number of rounds to assure reasonable security for a single password. Reasonable security could be it would take 1 year to a do a full dictionary attack alphanumeric only or perhaps 1 month or 1 week. The value you choose for the time it takes to brute force one password is the level of protection you are providing your users.

EDIT: also what Thomas said. It is in the standard that 1000 should be the minimum value. I would use higher based on the level of protection you want to give your users. Note that different hash functions have different costs so this will also impact the choice of X.

adulau2• 16 years ago

When seeing the title, I was expecting an article about CMAC or HMAC or even PBKDF2-like function but it's the "old" bcrypt.

mfukar2• 16 years ago

You say that as if it's a bad thing.

EDIT: Oh, you mean it was similar to other submissions. Fair enough.

adulau2• 16 years ago

Not really. Just it was already mentioned sometimes ago about the fixed cost function in bcrypt:

http://news.ycombinator.com/item?id=762708

mcgin• 16 years ago

I made an attempt to implement bCrypt on the last web app I built. The problem I found with it is that there was no robust implemention of the algorithm for the tech stack I was using (J2EE) - I'm not sure whether that is the case outside of Java. jbCrypt was the only thing I could find, and if you look at the source, it really is a poor implementation. I could have gone ahead and rolled my own implementation, however I'm no security expert, and much prefer to rely on something more robustt then my own implementation which in all likelihood would have bugs in it.

retroryan• 16 years ago

What did you end up using? What are good solutions on a java platform?

jbellis• 16 years ago

I googled [bcrypt api] to see how hard it would be to wrap with JNA (my guess: not very), but the first hit was "jBCrypt - strong password hashing for Java." So I stopped looking.

shabble• 16 years ago

The part that I don't quite understand about bcrypt and the "scales with hardware speed" claim, is that, as I understand it, validating a password requires 3 parameters; password string, salt, and cost factor.

If you start out now with some given cost factor, that is unfeasibly breakable with modern hardware, that factor will remain stored somewhere, presumably in the database. Once computing hardware speeds up to the point that your factor is now practical to break, you can increase the cost factor for new passwords, but older ones remain susceptible to cracking. The only option would be to re-encode them periodically with the new factor to keep them secure.

Can anyone clarify if I've understood this correctly, or if I'm missing something fundamental about bcrypt? I've looked over the usenix paper, but I can't see anything obvious to confirm one way or the other.

Strilanc• 16 years ago

If you're using bcrypt then the client has transmitted the password to you. You can store a higher cost hash after verifying the password against the old hash.

asdfor3• 16 years ago

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 be safe just force them to use a strong enough password

hashed(password + salt) = epic win

davebob• 16 years ago

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

asdfor3• 16 years ago

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.

Raphael3• 16 years ago

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.

asdfor3• 16 years ago

"do a quick email confirmation". And what happens if one or more of your users gets targeted for a long period of time ? You will force them to open there inbox every time they want to log in your site ? And this gets even better if they target your site generaly, it will be a lot of fun for the majority of your userbase to have to do that "open inbox" step, bet users will love it :)

Sorry mate but your method sounds easily exploitable ... heck using reCaptcha would be less punishing for the user than your approach.

niels_olson• 16 years ago

Fun fact: this has been posted to Hacker News before, when it first came out. I think most would agree this is a great example of why re-posting should be allowed.

http://news.ycombinator.com/item?id=1091104

bigiain2• 16 years ago

Thanks to codahale for writing this, r11t the HN user who originally posted this early this year, and the discussion by everyone on that HN thread which convinced me of the correctness of the bcrypt approach.

I've already shipped one project which I'm sure at least part of the reason we successfully pitched was our demonstrated indepth understanding of password security requirements.

(I also realised in retrospect that a project I'd designed and specced before reading that article/discussion was going to be wrong in it's password handling, I'm disappointed we never got to build that product, but I'm kinda glad I'm not sitting here thinking "Fuck, what am I gonna do if $project's database ever gets compromised? It'll be just as bad as Gawker...")

IgorPartola2• 16 years ago

I admit I games the system a bit to re-post this link, but it seemed very relevant. I learned a ton from this discussion, so my selfish reasons were met.

16s• 16 years ago

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.

count• 16 years ago

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.

Waywocket2• 16 years ago

Worse, Windows up to Server 2003 by default stores LAN Manager hashes as well. To describe the cracking of these as 'trivial' would trivialise the work 'trivial'.

tocomment2• 16 years ago

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?

gxti6• 16 years ago

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.

seunosewa• 16 years ago

Actually, you have to go a bit beyond 16 bytes to be sure.

joeguilmette• 16 years ago

I use a different password for every website. It is easy to remember, I just have a portion of my password that changes for every website. For example:

dg76fb23S for Facebook, dg76fb23S for hacker news

Been working great for years :)

steveklabnik• 16 years ago

Your Facebook and HN passwords are the same? ;)

And if someone ever sees these in plaintext, it's trivially extrapolate-able to other sites. Dunno.

Raphael3• 16 years ago

>dg76fb23S for Facebook, dg76fb23S for hacker news

So you use the same password for everything.

city412• 16 years ago

My issue is asking a lot of people to change their password because I've decided to change my encryption algorithm. Is there a best practice for upgrading encryption without forcing users to do that? Something like when the user logs in, hold onto their plaintext password for a bit, confirm it's correct against your current algorithm, and then re-encrypt it with bcrypt?

dangoldin• 16 years ago

Good question.

My gut instinct would be to do just that but I wonder if there's a better way. You'd probably also want to track the encryption of each user so you know when you can make the final switch.

Another alternative is to just send "update your password" emails to everyone framing it as an improvement to your site's security.

Waywocket2• 16 years ago

>Another alternative is to just send "update your password" emails to everyone framing it as an improvement to your site's security.

I guarantee everyone with a decent spamfilter will miss those e-mails - that looks exactly like a standard phishing attempt.

niktech• 16 years ago

Why not do it behind the scenes?

Simply use the existing MD5/SHA1 hash as input to bcrypt and update all password hashes in your database in one go. Then, whenever the user logs in you first apply the old hash function followed by bcrypt before comparing with what you have in the DB.

city412• 16 years ago

Nice, thanks. This is why I asked. That approach had not occured to me.

Seth_Kriticos• 16 years ago

What the article tries to say is, that your password hashing function needs three attributes:

* it has to be dog slow (to make brute forcing hard)

* it should be complicated enough to avoid collisions (this really applies to most hash functions)

* it should be suitably salted, to avoid rainbow tables

-> bcrypt is designed like this, if in doubt, use it

pmjordan• 16 years ago

The Java implementation linked from the article, jBCrypt, http://www.mindrot.org/files/jBCrypt/jBCrypt-0.2-doc/ uses java.lang.String's compareTo() function (lexicographical comparison) to validate the hashes of passwords. Is there cause for concern about this in practice, considering it will probably have varying runtimes for different match lengths? (I realise that running in a JITted VM means I can't predict the assembly language produced anyway)

boscomutunga• 16 years ago

I think sooner or later computing power is going to increase to the point of making bicrypt look like md5 or lesser,i think what matters is protecting the hash.

iana• 16 years ago

If an attacker steals a DB of passwords, it is only a matter of time before computing power catches up and is able to crack the list, regardless of the methods used to hash the values. Advances in cryptography are rare, advances in processor capabilities are not. bCrypt may be the best we can do at this point to delay this inevitability, but programmer's shouldn't come away from this thinking that using bCrypt "solves" this problem. An interesting question related to this is how long a time period is considered "safe" enough to protect a stolen list? If the list is protected from brute-force cracking for 3 years after theft, is that enough time to render the passwords unusable? 5 years? It seems like the answer to this question would be used to calculate an appropriate value for bCrypt "speed".

easysecured• 16 years ago

What if there are no passwords to start with. If users do not enter a password and instead a hashed key is generated for the device used by the user which then encrypts everything before it is stored on the server.

This key could be generated in real time and would not be displayed anywhere on the form and will be transferred in stealth mode to the server.

With no passwords to enter or transmit, there will be nothing to hack.... If the key generated in origin is itself a strong key decrypting information stored on the server will require first hacking the key which if not stored on the server in the first place will make life hell for hackers as they will require access to the individual devices as well.

Cheers, gurudatt

How To Safely Store A Password

Related Stories