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.