So in this case, where the FBI is involve, using a SHA-1 hash poses no extra security vulnerability.
I imagine that many companies are better prepared to deal with the FBI than this data center was. I have a hard time imagining the FBI going into a Google data center and easily walking out with a few racks. But even if that's too optimistic, I doubt the FBI could go about seizing servers for very long. If nothing else, this would eventually piss off big companies who will lobby Congress to curtail the FBI.
meeeh...
remember the fbi is not a person, it's an organization. the org can have bad actors in it who might be able to access the encrypted passwords but not be able to confiscate servers.
also, confiscating a server(s) is much more visible / detectable...
Modern consumer video cards can do billions per second now. You might as well just store them in plaintext instead of using SHA1/MD5 with or without salting. :/
72^8 >> 1e9
It would still take more than 8 days to brute force at 1 billion/sec. And using a longer password (16 chars?) would make this a very long time.
Or is there other trick that makes this fast? Or, is it simply that people don't choose random, long passwords?
Secure password hashes protect application developers from the disclosure of hundreds or thousands of user passwords from their database. It allows them to attest to their userbase "your password is cryptographically stored in a manner that makes them hard to break even by dedicated hardware; you should consider changing your password if it's weak and shared", instead of, "expect to see your password on Pastebin any day now".
That is true.
However, it seems to me that the combination of an effectively-random password and password hashing does protect users, because their password is not effectively crackable in a situation like this. Additionally, there's a tradeoff between how secure your password hashing is and how much randomness users need to put into their password: every additional factor of 1000 in the iterations of the hash saves you a random character or two.
Not sure if this is what you were looking for or the particular hash bitcoin uses, but a $110 Radeon 5830 can get you around 250Mhash/s
So, actually, in this case the two happen to be related but different - SHA-1 being considered potentially flawed but not (yet) the stronger SHA-2.
Also, the Bitcoin block headers that are hashed are (I think) 80 bytes (640 bits) long, salted passwords probably a bit shorter.
Wikipedia says SHA-256 runs about 2/3 the raw throughput of SHA-1. You can the comparative rate yourself on any nix computer:
$ openssl speed sha1 sha256 -snip- Doing sha1 for 3s on 16 size blocks: 7760096 sha1's in 2.99s Doing sha1 for 3s on 64 size blocks: 5502820 sha1's in 3.00s -snip= Doing sha256 for 3s on 16 size blocks: 5460366 sha256's in 3.00 Doing sha256 for 3s on 64 size blocks: 3169031 sha256's in 3.00s -snip- *
So... about 2/3 faster. I don't know enough about crypto implementation, but I'd guess this ratio would scale roughly to the much faster GPU implementations as well.
Sounds about right http://blog.zorinaq.com/?e=43 And a few times more if it's md5.
That's always part of the problem.
What the user chose as their password should be irrelevant if using a good hash.
[Edit: I stand corrected on the effect of password length.]
Let's also assume that this perfect SHA-4 function is freakishly fast, say, a million times faster than SHA-1.
Now, even though my imaginary SHA-4 function is perfect in every way, it would be strictly worse to use this for password hashing than SHA-1. Why? Because cryptographic attacks aren't the problem here. The problem is that the entropy of a user's password is very VERY small. So small, in fact, that attacks on passwords aren't done through cryptographic weaknesses, they are done by simply hashing everything someone might pick as a password and asking "did I get it right?". An attacker will repeat this process for a little while, and eventually they'll get the answer "YES, this user chose to make abc123 as their password!".
A "perfect in every respect" hash then would be one that takes a consistent, acceptably-long time. Some large fraction of a second perhaps.
Of course, this fictional hash wouldn't be the right choice for everything. But for password hashing, it's a good start.
No, not really. Hashing functions aren't designed for passwords, they're mainly used for integrity checks and other uses which need to be fast: why do you think one of the axes the SHA-3 hashes are competing on is speed?
You have your 10gb file and want to send it to your coworker and let him know it's really yours and no one has messed with it. So you run an HMAC over it and then sign it with your private key.
You want it to be as fast as possible. It would be optimal if there was a single x86 instruction called sha4 which did this in the time it takes to do an add.
Hashing is really, really not meant for passwords.
Or, go on and tell me more about all the things hashes are used for as if I just fell off the turnip truck.
This discussion is not about checksums on files. It's abotu passwords. And your "perfect hash" in your example about passwords is "freakishly fast." In fact, like the other guy that replied to me mentioned, this is the entire point of the workfactor in bcrypt, right?
Of course, bycrypt is really, really not meant for checksums. Good thing nobody was talking about checksums then.
I then didn't respond to the rest of the post because when you said "for password hashing, it's a good start" I again assumed you were talking about my hash function, which is not good for hashing. Yours would be perfectly fine.
I apologize.
This is why they invented key stretching: http://en.wikipedia.org/wiki/PBKDF2
Just set number of rounds to 10000000000 instead of, like, 10000 for SHA1.
1 billion passwords per second is 86 trillion passwords per day. If a hacker wanted to gain access to a particular password then it can become trivial to crack with fairly modest resources. The only thing that protects you is a sufficiently complex and long password.
8 days for one password is a very short amount of time comparatively (tiny for a botnet). If you use bcrypt, which you can force a certain complexity on, you can get that amount of time up much higher.
However, if you find Hale's bcrypt page (http://codahale.com/how-to-safely-store-a-password/) convincing, and I do, salting really doesn't matter because with modern GPUs you can bruteforce a reasonably-sized alphanumeric password, if the hash algorithm is a general-purpose (read: fast) one.
The solution is not salt, the solution is to use a purposely slow hash function.
Just use the bcrypt defaults. You will be fine. You will in particular be so much better off than salted SHA-1 that this topic will be mooted. Later on, maybe in 5-10 years, you can re-engage with the debate about what a good cost factor for bcrypt will be in 2020.
So now people are twitchy about "just use the defaults", especially when it comes to something they don't really understand, like cryptography.
I've been looking into this over the past few days, and I've decided to just extract the relevant files from py-bcrypt, and get rid of the compatibility layer.
http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/
Its from OpenBSD and implemented by the developers of the algorithm. It is what the Python/Ruby/Lisp/PHP etc. versions are derived from or wrap
There is no chance that, after selecting bcrypt, you will be forced to scramble to replace it with salted SHA-1 hashes. bcrypt is strictly better than what you're doing now.
You could do something similar.
PBKDF2(password, iterations=10) == PBKDF2(PBKDF2(password, iterations=5), iterations=5)
Thus you could, say, increase the number of iterations every month. All that said, you should still use bcrypt; this is just an interesting property IMO.
http://stackoverflow.com/questions/3722780/do-any-security-e...
I think I'm right in choosing bcrypt, but one interesting argument against it was that, being slower, it would facilitate DoS attacks. You want the password hashing to be slow to prevent brute-forcing, but, if it's too slow, attackers could supposedly DoS your login system by trying tons of passwords.
I'm not a security expert, and I didn't know what to respond to that. How would one mitigate this problem? Is it even really a problem?
You can always store the password of the users again and update the crypto used, (more iterations, different digest algorithm). It's never a question of if it will be broken, but when.
Choosing iterations for a PBKDF takes a bit of common sense, yes if you're going to roflscale and think 100000000 iterations is a good idea currently, then you may run into performance issues.
The correct balance is performance vs security and you can only choose one. You want to authenticate the user as fast as possible while also making it unfeasible to recover the data. As with everything, a little common sense and knowledge goes a long way.
Takeaway: Cost to crack one MD5 password: $1. Cost to crack one scrypt password: $50M to $200B.
You want your login to be slow compared to the rest of your application. It's okay to take half a second to verify a login.
Note that almost nobody uses scrypt. We don't recommend it, not because it's insecure, but because it's painful to implement for most companies.
But use either. Or just use PBKDF2. All of the adaptive hashes are fine.
> All of the adaptive hashes are fine.
I am so glad you say this.I can't count the arguments I've heard centered around what is The One True Way to store passwords... this topic turns every programmer on the planet into an instant Crypto Expert (TM).
STFU and use one. Hell, glib's crypt() lets you pick any of three computationally expensive schemes, so use one of those.
I find this a bit of a misnomer. I understand what you mean in context, of course, but, strictly speaking, bcrypt is a "hash", and "salted" is always good.
> Salted hashes are a straight-up vulnerability. -- tptacek
You usually add a salt (an additional string which is stored in the clear, but which makes your local instance globally unique, so the attacker can't precompute value to hash mappings ("Rainbow Tables" [which are faster to make if you have alien technology, from what I've heard]) for all sites.
I'd still suggest using bcrypt or scrypt.
1. The next time a user logs in to your system and you verify against the SHA-1 hash that they are who they say they are, recompute the correct hash for bcrypt. Then, delete the SHA-1 hash. It does you no good to have a bcrypt version if you keep the SHA-1 version around.
2. Generate the bcrypt hash from the SHA-1 hash. That is, pretend that the SHA-1 hash is the user's password. This isn't as clean (your password authentication software will then have to do SHA-1 followed by bcrypt) but it means you'll be able to migrate your entire database all at once if you so choose. This also causes a very (very, very) slightly higher chance of password collisions, although there's not much to worry about from that.
You ostensibly have a hash method identifier per hash, so just create "sha+bc" and "bc" along with your current "sha".
Also, why is the risk of a collision greater? It seems to me that, if anything, it should be lower, as SHA hashes always consist of a fixed number of bits, and thus aren't as likely to collide when hashed to bcrypt, assuming the length of a bcrypt hash is the same (or larger) number than a SHA one.
Basically, it seems to me that, if they're going to collide, they're more likely to collide at the SHA level, which is a problem either way.
Now clearly if I hash a password F(P) and another password F(Q) there is a 1 in 2^128 chance they collide.
Now imagine we do G(F(P)) and G(F(Q)). We first have the chance of 1 in 2^128 that F(P) == F(Q) which implies G(F(P)) == G(F(Q)). However, that is not all!
We now have a new 1 in 2^128 chance that G(F(P)) == G(F(Q)). So we have (about) a 1 in 2^127 chance that the passwords will collide.
But, none of this really matters. Collisions aren't what you worry about with password hashes.
I disagree that there's a 2^128 chance that they will collide. Trivially, I can show you a hash that will never collide for up to some N, and that is F(P) = P mod 2^128. This will never collide unless P is more than 128 bits long.
My rationale, above, was that SHA constrains the space to 128 bits. Therefore, for different SHA hashes (ones that haven't already collided), the probability that bcrypt will collide might be smaller (or zero, as in my example above).
In reality it doesn't work like that, I know, but in theory you can't be sure that the probabilities of collision will add (or, well, multiply) up.
Clearly it's impossible to be less than zero. So no matter what you do, Defining H(X) to be G(F(X)) will have strictly more collisions than F(X).
The reason I would argue it's greater than zero is that if a function H existed such that H(X) will never collide for X less than 2^128, it would probably have some cryptographic weakness.
(I didn't downmod you).
My only answer was "It's always a bad thing to be clever with crypto, just do it by the book" but he asked for more and I couldn't give him a sound debunking (or an authoritative endorsement).
I build systems -- and do it very well -- and all I know about crypto is what I've had to learn to implement other peoples crypto systems.
But if you don't mind a follow-up, wouldn't it still defeat rainbow tables? Why not?
But what it WOULD do -- which is what to be honest tricked me about the concept -- is that it would still offer protection from a precomputed rainbow table that knew nothing of your sheme to derive salt from the password. (eg, the rainbow tables that are publicly searchable right now)
At the very least, you will make it harder for someone to crack all of your passwords by computing one table with a single salt.
(Be prepared for your comment score to visit the grey depths if you attempt to relitigate Coda's blog post here and don't know exactly what you're talking about.)
Assume wall time is held constant at 1 second per password using both methods: is there an entropy loss or weakness associated with recursive hashing that bcrypt avoids?
I'm no crypto expert, but I think this is due to the way bcrypt was designed, and their use of a pessimized Blowfish cypher. SHA512 was designed for speed, which is the opposite of what you want with a password hashing scheme.
tptacek talks a little about this in this blog post:
http://chargen.matasano.com/chargen/2007/9/7/enough-with-the...
"Bcrypt uses Blowfish instead of MD5. Blowfish is a block cipher with a notoriously expensive setup time. To optimize Blowfish to run much faster, you’d have to contribute a major advance to cryptography. We security practioners are all “betting people”, and we usually like to place our bets on the side that “demands major advances in cryptography”."
Other interesting links: http://stackoverflow.com/questions/3722780/do-any-security-e... http://en.wikipedia.org/wiki/Bcrypt
Now let’s re-explain rainbow tables:
1. take a “dictionary” —- say, of all combinations of alphanumerics
less than 15 characters
2. hash all of them
3. burn the results onto a DVD.
You now have several hundred billion hash values that you
can reverse back to text —- a “rainbow table”.
Alphanumeric usually means either 36 or 62 possible characters. Let's take 36. Then there are 36^14 possible 14 character alphanumeric passwords. (He said less than 15, so we should also consider 13 characters, 12 characters, and so on, so this is going to come out a little low since I'm just doing 14 exactly). That's 6.14 x 10^21 possible passwords.If you could compute 10 billion hashes/second, that would take 20000 years. (41 million years if mixed case alphanumeric is allowed). Could anyone REALLY make a table covering all 14 character or less alphanumerics in 2007, and fit it on DVD?
I believe there were tables for 14 character Windows passwords then, but due to poor design Windows passwords were in effect treated as two 7 character passwords. You just needed tables that covered the hashes of all 7 character passwords, which is a lot more tractable. Could that be what the author was thinking of?
http://en.wikipedia.org/wiki/Rainbow_table http://en.wikipedia.org/wiki/Dictionary_attack
Bcrypt it is :-)
"Any normal person can brute force millions of SHA-1 hashes (salted however much you want) per second on a GPU."
This is not true of bcrypt.
This security layer is the only code I've ever written that years later would still cause me to wake up in the middle of the night thinking "oh no! What if an attacker did X, Y and Z??!!"
Note: as far as I know, the security I put on it has never been broken. But it still caused nightmares even so.
This makes a lot of sense. If more sites storing non-critical data did this we'd have far less password fatigue and people more wary about what they trust to such sites. Just now they see their "password1" as impenetrable security when they might as well have no password at all.
Not having a password has a similar psychological effect as showing the password field in plain text, I think.
> Just store in plaintext because I am already assuming you are.
No, actually, I don't think I will store plaintext passwords.
> All the this talk about sha-1 vs bcrpyt vs scrpyt is nice and all but I have little faith that most companies care about this as much as HN does.
So what? Just because other people don't do it doesn't mean you don't have to also. Fortunately for us, there are a lot of startup founders here who might read this and learn something.
> I believe that most people are using the default password storage mechanism for their framework which are already known to be easy to break if the database is compromised.
I disagree. I think most people use SHA-1 because they know better than to store plaintext passwords. What they don't know is that it's terribly broken.
> But all of that is mute anyways.
No, it's really not.
> Unless you have access to the site's source how would you know if they are hashing at all much less which one they are using?
There are two problems here. (1) If you have access to the site's password database, there's a really good chance you have access to the entire database, and can look up how they're doing it. (2) Even if you can't lookup how they're doing it, you just try them all and find which one it is. I'd bet you money that if someone's hashing passwords, they're using one of {MD4, MD5, SHA0, SHA1, SHA2, DES}. If, god forbid, they're not using one of those and actually wrote their own hashing algorithm, you have even more to worry about.
> The best practice is to use a random password for each site you use.
For sure, no doubt about it. But what we're talking about here is the best practice for application developers, not the users. The users can't do anything about how their password is stored.
> I just don't see any point in having an rememberable password for websites and hashing just leaves a false sense of security as illustrated by md5.
Or, you know, you could use bcrypt and be secure about it.
Yes I hope there are.
> I disagree. I think most people use SHA-1 because they know better than to store plaintext passwords. What they don't know is that it's terribly broken.
SHA-1 is the default on django and its easy to break that my entire point. It leaves a false sense of security.
> There are two problems here. (1) If you have access to the site's password database, there's a really good chance you have access to the entire database, and can look up how they're doing it. (2) Even if you can't lookup how they're doing it, you just try them all and find which one it is. I'd bet you money that if someone's hashing passwords, they're using one of {MD4, MD5, SHA0, SHA1, SHA2, DES}. If, god forbid, they're not using one of those and actually wrote their own hashing algorithm, you have even more to worry about.
They might as well be using ROT-13 if they are using any of those. Now with todays GPUs and rainbow tables the passwords might as well be in plaintext. The real solution is site security not password security.
> Or, you know, you could use bcrypt and be secure about it.
For how long? 4-5 years? Who will be maintaining your site then?
That does not imply you don't worry about it though -- it's defense in depth. In the same way sometimes you'll need to go through two sets of doors locked with different keys to access a secured server room (or anything else, for that matter), it's worthwhile to protect everything you can as best you can.
> They might as well be using ROT-13 if they are using any of those. Now with todays GPUs and rainbow tables the passwords might as well be in plaintext. The real solution is site security not password security.
Exactly my point. That's why you use bcrypt.
> For how long? 4-5 years? Who will be maintaining your site then?
First, the premise of that question is that bcrypt is going to be secure for only 4-5 years, which is entirely wrong. You can modify the work factor on bcrypt as time goes by. I could, for example, make it take twice as long to generate a hash every year. I could have the program do this automatically. As for you actual question, which isn't terribly relevant, either (1) me or (2) the next guy, who I hope will have knowledge about security as well, but if he doesn't, then I just have to hope he'd keep the workfactor increases in the code.
I guess what I am really trying to say is that the state of web/Internet security is very poor right now and I don't believe bcrypt is worthy pursuit (sorry I am really not trying to troll). Since Mt.Gox was just hacked my salted password is on pastebin and then someone attempted to break into my gmail account but that will never happen because I use two factor authentication.
Maybe that is the best solution to all of this.
I know I am getting totally destroyed here by the down voting and I'll probably end up in negative karma for this but I standby all of it.
I am saying that your advice is appropriate for users (who cannot control what the server does) but inappropriate for servers (who cannot control what the user does).
--
Obligatory statement on NEVER USING SHA-1 HASHES to make passwords "safe".
Any normal person can brute force millions of SHA-1 hashes (salted however much you want) per second on a GPU.
If the FBI so wanted (although I don't believe they do) I'm sure they could brute force almost every single password in that database. Granted, it's the government and they have better ways of obtaining such information, but if there is someone the FBI is watching on Instapaper's databases and they so wanted, storing the SHA-1 hash of the password all but handed them over to the FBI.
I am now glad my Instapaper password was generated randomly, 16 characters long, and I will now change it just to be safe.
For anyone running a database which stores ussername/passwords, take a look at bcrypt or scrypt. They're millions (no, I am not exaggerating) of time better than SHA-1.
(Edit: Grammar)