Hacker News Reader

I see, so basically it's like forcing users to make long, un-dictionary-attackable passwords, without requiring users to remember long, un-dictionary-attackable passwords.

I like that idea. But why do you store the salted SHA256 of the scrypt hash and not the scrypt hash directly?

Edit: Thinking about it more, I'm guessing it is for the case where your DB gets stolen. With the salted hashes, attackers can't just send the direct scrypt hash down to the server to get authenticated.

The whole idea of salts is to prevent rainbow table attacks i.e. you can't use precomputed hashes.

In this case you'd need to precompute an SHA256 of a dictionary of scrypt hashes which would have been computed from a dictionary of english words.

In practical terms, if you steal the DB and wanted to reverse passwords, you'd need to scrypt lets say 100 million words, then SHA256 them, then compare them to what's in the DB.

The original blog entry argues (or maybe it was the post on the same site that linked to) that we should use more compute intensive hashing algorithms, rather than relying on salts. scrypt is definitely more compute intensive.

So if you didn't use a salt and wanted to throw a 100M word dict at this, how long would that take on decent hardware to create the rainbow table of 100M words which could be used repeatedly against stolen dictionaries? On a decent GPU you can do around 1.2 billion SHA256 hashes per second. So the SHA256 step is trivial.

ASIC bitcoin hardware can do around 4.5 million scrypt hashes per second: https://bitcoinmagazine.com/13000/new-benchmark-scrypt-minin...

So you could create your rainbow table to attack the non-salted version of this in around 25 seconds.

A salted version of this same system would need the scrypt to be salted because SHA256 is so fast. If you just salted the SHA256 you'd be able to use a precomputed scrypt rainbow table and then you only have to compute the salted SHA256's which as you can tell from my benchmark above is very fast.

So clearly the salt is needed and you need to compute scrypt(salt + password) -->> send to server and then SHA256(scryptHash). Note that you don't need to add the salt on the SHA256 side because you've already defeated a rainbow table attack by your initial salting.

So how fast could you attack a salted system like this using GPU's for your SHA256 and ASICS for your scrypt based on the benchmarks above?

You can pretty much ignore the SHA256 step because it's so fast, so you'd get around 4.5 million guesses per second using ASICS doing scrypt.

Compared to 1.2 billion guesses using a GPU for SHA256, that's not too bad.

Cryptocurrency mining ASICs cannot be used for password cracking because they are not designed to hash arbitrary strings, and do not support arbitrary scrypt parameterization. They are designed to take in a block template of some sort, and then internally handle iterating the nonce to minimize load on the communication bus and the host processor.

An interesting thing about GPU password cracking that many people don't realize is that the GPU is responsible for not only hashing candidate passwords, but also generating those candidate passwords. The bus bandwidth isn't enough and the CPU isn't fast enough to keep it fed with candidate passwords otherwise.

You could, of course, build password cracking ASICs that have internal processors for generating candidate passwords, but I'm not convinced that it doesn't make more sense to stick with GPUs or maybe FPGAs there.

You'd be better off with FPGA which are available in significantly smaller process sizes (and therefor lower running costs) than ASICs you roll yourself. There's also a certain level of reusability that you don't get with SHA256 etched into silicon.

Not true re GPU bandwidth/dictionaries. see cudahashcat - we're using it on a switched PCIe bus feeding dictionaries with plenty of bandwidth. You're not limited to mask attacks, which is what you're describing.

Are you sure about that? I'm more familiar with oclhashcat, and it certainly can't keep the GPU busy with a pure dictionary attack. It'll feed the GPU with a dictionary, then apply rules on GPU to generate variants.

Correct. If you store the scrypt hash directly, it effectively becomes a plaintext password and a compromise of your database lets the attacker login to any account.

This is something I've wanted in browsers since I was about 15 - I've written a proposal on Specifiction for discussion around putting this in the Web Platform: http://discourse.specifiction.org/t/html-server-relief-passw...

The problem with the approach you mention is that clientside bugs can evilly break things. If the clientside code silently gives wrong results, not only will you not know, but, assuming they run it from the start (i.e. when they register), it will actually "work" - until the client moves to another machine or updates. That's not a good situation.

You may be able to detect this with testing, but not necessarily. And yes, it'll probably happen sooner or later, given the nature of JS compilers.

I don't know if there's a method that avoids this problem that still has the advantages that you mention.

If you're worried about this, you could do server-side hashing during signup, and client-side hashing during login.

This is brilliant. But since we are often told that composing cryptographic promitives can turn out to be unexpectedly dangerous, can you point me to some articles where this technique is studied in more detail? Preferably by experts such as yourself.

mrb, this is awesome, thanks for sharing. Can you comment on storing the scrypt as an md5 hash and how that would impact security? [Asking because I'm confined to server side systems that only support md5]

IMHO While MD5 has a fraction of the keyspace of SHA2, it's still a very hard problem to reverse it and intuitively it seems this might provide a huge improvement over salted and stretched (multiple rounds) of md5 on the server.

Thanks again.

Since MD5 isn't really vulnerable to a preimage attack, this would probably work fine - 2^128 possibilities are essentially impossible to brute-force.

I'm curious - what kind of infrastructure would constrain you to md5?

The attacker would then intercept that scrypt hash sent from the client and use it to authenticate.

You can't. The scrypt hash should be protected by HTTPS the same way a website password is protected by HTTPS.

> The only downside of server relief is that you need custom code on the client-side

That, and the major reason we do hashes even over TLS: if the server gets cracked and the attacker has access to the stored hashes, breaking a SHA256 is trivial (ie, brute-forcing b when knowing s = SHA256(b)). Then, the attacker can assume the identity of any individual whose SHA256 s got broken, by sending the bcrypt b directly from a crafted client, without having to find p where b = bcrypt(p).

People have odd ideas about how serious the vulnerabilities in hashes are. These hashes, even old and obsolete ones, are still entirely secure for password like hashing if the password is random enough, which scrypt output is.

Even MD5 is still (AFAIK) effectively unbreakable in this use case (finding md5 collisions is possible, finding the input given an md5 is not). According to http://en.wikipedia.org/wiki/MD5#Preimage_vulnerability finding input to generate a given md5 has a complexity of 2^123.4 - i.e. never going to happen. And that's Md5, an obsolete hash!

Sha1, also considered obsolete, has a bad rep because there are scary theoretical collision attacks. This isn't good news, certainly, but for a sense of perspective: nobody, not even with lots of distributed computing power, has ever actually managed to find a collision since that would take around 2^60 attempts. I don't think anyone has ever found even a theoretical weakness in its preimage resistance.

And you're talking about sha2 - there have been no published reports on any attacks, even theoretical, on the full sha2 (they have found weaknesses on reduced versions, suggesting room for improvement - but that's largely of academic interest).

Collision attacks are another matter. If you're using a hash to sign potentially hostile content rather than recognize friendly content, md5 is clearly dangerous, and sha1 may well become so. But that's relevant to things like certificate authorities, not message authentication.

He's not using "broken" in the sense of "arbitrary preimages", is he? He's using "broken" in the sense of "easy to brute-force", right?

I meant it in the brute-force sense, yes. I'm not sure how practical it would be when the input of the SHA-2 is random, however.

Yeah - brute forcing is really only a relevant attack if the number of possibilities is fairly limited (even with a really fast hash). Scrypt output is likely to be effectively random (if salted) - and without salt, you'd need to build an expensive (but potentially feasible) rainbow table of possible scrypt output.

> you'd need to build an expensive (but potentially feasible) rainbow table of possible scrypt output

I don't think that's feasible. "Expensive" is an understatement. To compute the rainbow table you need to do the work of actually calculating the scrypt output for each password, even though you don't have to store it. The space is just too big, therefore the time cost.

It's a question of size - clearly a rainbow table of 1 is feasible. I'm guessing a rainbow table of a million won't be too expensive either, and with a million common passwords, you'd likely crack something.

But yeah, it's not likely to be a major threat. In any case, salting makes it irrelevant.

Is scrypt even implemented without a salt? If not, then it doesn't matter. And if so, why?

Good point - it is implemented with a salt! However, the way that's done depends on the implemetation. The underlying KDF doesn't require nor generate a salt, so if you're implementing it client side, you'd need to ensure salting works.

If collisions are not too hard to find, isn't the process just:

1: Steal database 2: find collision 3: authenticate with the input that hashes to the same value

What stops that from happening?

Re-read that comment, particularly the part about the difference between a collision attack and a preimage attack.

MD5 is (currently) vulnerable to collisions, but not to preimages. So you can find two inputs that have the same hash, but not an input that hashes to some particular value in a database.

@teraflop - Oh, so does that just mean basically that you can, e.g. generate a bunch of MD5 hashes and some will be the same? But if you have a target you're basically SOL finding a collision for that? That would make sense if that's what it means.

Yep.

More specifically: if you just hash a bunch of arbitrary strings that aren't specially-constructed for the purpose of colliding, then collisions are basically random, and extremely improbable. But you can fairly easily generate two files, differing only in a small number of bits, with the same MD5 hash by taking advantage of the structure of the algorithm.

Examples here: http://www.mscs.dal.ca/~selinger/md5collision/

Another consequence of that is that even MD5 collisions aren't at all trivial to exploit in general. An attacker can create a collision, but it's a slow process, and the colliding content is pretty constrained. You'd probably need to be very well informed, and invest quite some creativity to find two messages that are "valid" to whatever system is processing those and have sufficiently different meanings to be useful to you.

Clearly doable in specific instances, but it's not going to be an addition to the script-kiddie attack handbook anytime soon.

> These hashes, even old and obsolete ones, are still entirely secure for password like hashing if the password is random enough

Ah, got you, I'm wrong. Thanks!

I thought it was trivial to quickly compute SHAs so you can try lots of passwords.

In the case of sending bcrypt output wouldn't the "password" be long and essentially random and therefore not easy to enumerate?

Or is SHA also reversible?

well breaking SHA256 by brute force is only trivial when your input space is small. presumably scrypt has 256 bit output so bruteforcing to find the scrypt output would be difficult.