1,020 karma · joined August 20, 2010
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.
> 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.
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.
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.
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.
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!".
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.
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.
--
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)
"And he asked a question. And I was like, I’m sorry did you say you were Tom Furness? And he said yes. I said, then I would love to answer your question, but first, will you have lunch with me tomorrow? And there’s a lot in that little moment. There’s a lot of humility, but also asking a person where he can’t possibly say no."
Although, admittedly, that's after you got them to say a few words to you and you're in front of a large group of people.
[1] http://www.youtube.com/watch?v=ji5_MqicxSo 19:40
Edit:
For those who don't know, here's the setting of this talk:
This talk is one in a series given at CMU called the "Last Lecture" series with the hypothetical setting of 'what if you had one last talk to give?'. Randy Pausch, a professor at CMU, didn't have to pretend. He was diagnosed with pancreatic cancer, and in August of 2007 (when he gave the talk) was told he had three to six months left to live.
If you haven't seen it, watch the whole talk. It's really good.
A SHA{1,2,3,128,256,512} hash is very VERY VERY fast. So fast, in fact, that an attacker who has the hash could easily run through all 8 character passwords given a few GPU machine clusters.
PBKDF2 is very much like a SHA hash, but it is repeated over and over. Instead of just salt||SHA1(password||salt) you compute salt||SHA1(SHA1(SHA1(SHA1(SHA1(password||salt))))). This makes it so an attacker with the hash has to do much more work in order to brute force the password.
Now, that's not exactly how it works, but just read the wikipedia article for that.
They go forward six and a half turns, and go back six and three quarters.
... what? That has nothing to do with number theory.
> More seriously, numbers, and number theory, can be quite interesting and often leads to computational insight in algorithm computation or numerical solving. But ultimately, unless you're a numbers geek, it doesn't really teach anything.
There are a number [1] [2] [3] [4] of practical uses of number theory that do teach something. I've only listed the simplest uses with respect to cryptography, because those are the ones with which I am familiar, but I assure you, number theory is one of the more applied branches of mathematics.
Granted, some number theory has very few applications. But you won't ever find something practical if you're always asking "Is this practical? I better not look further if it isn't."
[1] http://en.wikipedia.org/wiki/RSA
[2] http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exch...
[3] http://en.wikipedia.org/wiki/Digital_Signature_Algorithm
[4] http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
> Except random numbers aren't random. They only appear to be. If an online casino seeds its random number generator with current time, then you can do the same, and predict which cards it will deal.
> So here you are saying that bcrypt generates a random seed, and I'm thinking "how does bcrypt get around the aforementioned problem?"
> If you don't want to answer my specific question ("why is bcrypt stronger..."), then don't.
]
I'm neither tptacek nor a security expert, but I think I know bcrypt well enough to answer your questions. Apologies if anything I say isn't correct; someone correct me if that's the case.
Starting with the problem: SHA1+salts are well and good. The password isn't in plaintext, so I can't just read it. SHA1 has no real cryptographic attacks on it. The salts prevent rainbow table attacks.
Except there's a major flaw. SHA1 is fast. SHA1 is very fast.
When you hash your password with SHA1+salt (even if you use a 1024 bit salt) an attacker will get a GPU cluster and run billions of hashes per second until they bruteforce your password. Anything under eight characters will fall in under a day, easily.
Now, let's talk bcrypt. Based off of blowfish (which has a reasonably long key-schedule algorithm), bcrypt is designed to be very slow. Very very slow.
If you want to think of a very naive way of doing this, imagine my hashing function is simply salt||SHA1(SHA1(SHA1(SHA1(...(SHA1(password||salt)))))) It is easy to see how this would take significantly longer than simply salt||SHA1(password||salt). Now there's some other details that you don't seem to be interested in, but that's the main idea. If you care to read more, see the paper.
This means that if an attacker would try to bruteforce even the simplest passwords, it would take significantly longer. Look at the chart on page 11, for example. The nice thing about this is that you can, over time, adjust it to take longer and longer as computers get faster and faster.
So, bcrypt isn't some fancy thing which picks salts in some random way (although it does get salts; as for how, I don't know, but /dev/random would work just fine).
If you care about it and want to look in to it more, scrypt is also interesting -- it also uses as much memory as it can to stop simply throwing just CPU time at a problem.
Eleven seconds to compute the 1,000,000th Fibonacci number. Compared with the naive method which takes 143 seconds.
Code below:
def add(a, b): return (a[0]+b[0], a[1]+b[1])
def sub(a, b): return (a[0]-b[0], a[1]-b[1])
def divsq5(a): return (a[1], a[0]/5)
def mul(a, b): return (a[0]*b[0]+5*a[1]*b[1],a[0]*b[1]+a[1]*b[0])
def subi(x, a): return (x-a[0],-a[1])
def pow(b, e):
r = (1, 0)
while e > 0:
if e & 1 == 1:
result = mul(r, b)
e = e >> 1
b = mul(b, b)
return r
twophi = (1,1)
def fib0(n):
return divsq5(sub(pow(twophi, n), pow(subi(2,twophi), n)))[0]>>n
def fib1(n):
a = 0
b = 1
while n > 0:
(a,b) = (b, a+b)
n -= 1
return aI would start by brute forcing their private keys, and go from there.
And probably block cycles too.
Imagine the case where he had not escaped quotes, but had escaped < and >. In that case, I could put a doublequote/singlequote to break out of the JSON. Then I could just put whatever javascript I wanted and run it.
But that is true, trying to filter specific character sequences for example, "eval" is never a good idea.
Try to login or create an account. Enter this as your username (or password, as long as it's not valid: you need an error), hit submit. Error + XSS.
</script><script>alert(1);</script>
You escape quotes, which is good, so I can't break out of the JSON request. But you have to remember how the HTML parsing of a page works. </script> will break out from within a javascript string.
The most basic imp is defined as
mov 0 1
See elwin's comment below on vampires (for now, hopefully above soon).
Edit:
And there are other comments with negative points where the number doesn't show. And still other comments with positive score that are showing up. Consider me confused.
" onclick="alert('do evil here')" onfocus="alert('do evil here')" foo="
It errors out, and my javascript is now in the input box. They click the name and then it runs my javascript.
It's great you've escaped < and >, but you need to do more.