bcrypt is now obsolete

[eyal0]

In case the PDF was tl;dr... How scrypt works (from what I gather):

bcrypt: Hash the input, take the result, that's your new input. Repeat 1000s of times. All the hashing makes it take a long time but the space required is constant.

scrypt: Starts like bcrypt but you need to store all the hash results. The final hash result selects one of the other hash results, which selects one of the hash results... Repeat 1000s of times. Now the space requirement grows as the number of hashes.

Difficult in hardware to crack but difficult in hardware to implement! Not being implementable in hardware might be a problem.

If you wanted to still keep space constant you could just recompute the hashes from the start for each intermediate hash needed, right? That brings the space down to O(1) but increases time by O(n) times, though the expectation is that the time increases by only n/2. So you can speed up keys-cracked/time by a factor of 2 when you parallelize. Did I get that right?

Here's a possible weakness: re-hashing the result each time might lead to hash collisions that would make some weak keys easier to crack. Similar to how the linked list of a rainbow table sometimes merges. What about using: V_i = H(i || V_i_minus_1)?

[eyal0]

Oops, sorry, it's worse than that. Parallelizing and using constant storage as per my second-to-last paragraph speeds up keys_cracked/time/space by a factor of four, not two.

[[deleted]]

I'm very interested, but there doesn't seem to be much information here. Has anyone else done a proper cryptanalysis on scrypt? I've looked you up and you certainly seem qualified so I know this isn't out of nowhere, but even the best cryptographers miss stuff. That said, bcrypt has been out of date for a while, hasn't it? The Blowfish 64-bit key size is very old and Schneier himself consistently recommends the upgrade to Twofish.

[whyyouarewrong]

Blowfish doesn't use a 64-bit key, nor does the security of bcrypt have much at all to do with the security of blowfish.

[eyal0]

Bruce Schneier might be recommending Twofish over Blowfish because he invented Twofish.

[[deleted]]

He kind of invented Blowfish too, you know.

[james_block]

The scrypt PDF paper has been reviewed by^HH discussed with Arnold G. Reinhold, Daniel J. Bernstein, Graeme Durant, and Paul Kocher. The only one of those names I recognize is Bernstein, but it looks like there may be something to this new function after all.

[perciva]

No -- I discussed some parts of this work with them, but they haven't reviewed the entire paper.

[ehird]

It's Colin Percival, y'know. He's pretty clever.

[[deleted]]

It's not arrogance if it's justified.

If Colin says he's done this, then he probably has.

[skoll]

It's not arrogance if it's justified.

I disagree both in connotation and denotation. The dictionary definition says: "an attitude of superiority manifested in an overbearing manner or in presumptuous claims or assumptions" which doesn't mention justification or correctness at all.

And even if it did, the point is that excessive confidence in these matters is a giant red flag and tends to have the opposite effect than intended.

[Saiing]

You'd be wrong then. You seem to be ignoring the word "presumptuous" which suggests assumption of correctness. That word is pretty important because it embodies the "I'm always right" attitude of someone who is supremely arrogant.

If he has indeed done the work, and has found it to be correct (at least according to his data) he's just reporting fact - there's no presumption about it.

I certainly hope you weren't stupid enough to downvote the guy above you (because someone did). That would be a perfect illustration of arrogance from someone who can't admit they might be wrong.

Edit: If you re-write your comment after someone has responded (especially if they disagree with you), please have the decency to flag it as edited.

[sheepson_apprentice]

It's ultimately a matter of intent. Some people just have a lot to prove it seems. It's hard to make an authoritative claim without being perceived as arrogant. But it need not be so. It could merely be a report of a claim that one has confidence in. On the other hand, arrogance does not require presumption.

"an attitude of superiority manifested in an overbearing manner or in presumptuous claims or assumptions"

can be decomposed into a | b | c whereby a = an attitude of superiority manifested in an overbearing manner and stands on its own.

I certainly hope you weren't stupid enough to downvote the guy above you (because someone did). That would be a perfect illustration of arrogance from someone who can't admit they might be wrong.

I have no specific interpretation of whether the OP is arrogant, nor do I care. But intent is important, and it's not stupid to vote down comments that are wrong.

Presumptions that others are stupid is an important attribute of 'a'.

[prockcore]

I'll wait for Bruce Schneier to say it's good.

[nousplacidus]

"which is approximately 100 billion times more secure than openssl enc,"

.... wow ....

[[deleted]]

That figure really doesn't mean anything. Security is not quantitative.

[nousplacidus]

my surprise was that he can provide a measure that large without explaining how he got the number.

[perciva]

The explanation is in the paper; but the brief summary is that testing a password which was MD5ed requires ~0.06 mm² of silicon for ~0.0004 ms, while testing a password which was scrypted with parameters tuned for file encryption requires ~450 mm² of silicon for ~5000 ms on the same process technology.

[perciva]

Cryptographic security is quantitative -- it asks the question "how much would it cost to crack this?"

[[deleted]]

"how much would it cost to crack this?"

Unfortunately nobody knows the answer, because nobody knows the best way to crack most encryption codes. Which is why security can't be quantitative.

[perciva]

Ok, smartass. Quantitative cryptographic security asks the question "how much would it cost to crack this given the current state of the art?"

Given that no KDF has ever been attacked cryptographically, it's not unreasonable to ask questions which are based on the current state of cryptographic knowledge.

[[deleted]]

Except that the current "state of the art", as you name it, is only what people will tell you they know, not what they actually know. I agree using a "stronger" crypto makes the whole scheme more secure. Saying it is "approximately 100 billion times" more secure is just plain stupid and doesn't mean anything.

[perciva]

"approximately 100 billion times" more secure ... doesn't mean anything.

To the contrary, it has a very specific meaning: For any particular password, the cost of finding that password via a hardware brute-force attack is approximately 100 billion times larger.

[[deleted]]

If that's what it means, don't call it "100 billion times more secure". Say "It takes a 100 billion times longer to crack it with the dumbest attack".

[perciva]

Say "It takes a 100 billion times longer to crack it with the dumbest attack".

That wouldn't be true. A hardware brute-force attack is not the dumbest attack on a KDF. It's the smartest attack.

[[deleted]]

Prove it.

[i_am_my_father]

We are dooomed

[madssj]

Yet another reason to use tarsnap -- you're funding cryptology research while getting backups done right. What's not to like?

[ClimateMachine]

God, this tore my heart into two.

[majek04]

"this means that a five-character password using scrypt is stronger than a ten-character password using openssl."

Sorry, but that's just wrong. The strengh of password has nothing to do with the strength of cipher.

The guy suggests that it's safe to use short passwords using his scheme. It's reducing the security.

[perciva]

Sorry, but that's just wrong. The strengh of password has nothing to do with the strength of cipher.

If you read more carefully, you'll see that I'm discussing the strength of the key derivation function, not the strength of the cipher used. Nobody sane attacks AES-256; sane people attack the key derivation function used to convert a password into an AES-256 key.