Don't use bcrypt • Hacker News Board

Re: Don't use bcrypt

#131

Post by tptacek » Mon, Mar 19, 2012, 7:31 PM UTC

bascule wrote: post #117

JoachimSchipper wrote: post #116

Earlier quoted context omitted.

Why? "Use bcrypt" is boring from a crypto-nerd point of view, but it's a really useful meme.

I thought I explained that in my blog post. scrypt is superior to bcrypt in every regard. At the very least, I'd rather the meme be: Use bcrypt, scrypt, or PBKDF2.

The problem is that PBKDF2 isn't superior to bcrypt in every regard:

* It has marginally worse library support and is built out of universally available primitives, which increases the odds that generalist devs will DIY it.

* It is actually faster than bcrypt (see Colin's paper); in other words, even without waiting for a hypothetical research result against bcrypt, PBKDF2 is already "vulnerable".

* PBKDF2 deployments virtually all use SHA2 as their PRF, and PBKDF2/SHA2 is a construction that depends entirely on the security of hash functions; hash functions are more poorly studied than block ciphers.

* Attacker tools are (mostly, but not entirely) built out of preexisting infrastructure and not by cryptographers; of the three functions, the best accelerated brute force support is available for PBKDF2/SHA2. For instance, is there a widely-available GPU implementation of bcrypt?

* The standards process that ran for PBKDF2 did not include the extensive peer review that (say) AES went through, and isn't a significant asset for PBKDF2. Meanwhile, bcrypt had broad deployment long before PBKDF2 was widely deployed, and on higher-value target systems.

You'd rather the meme be "Use bcrypt, scrypt, or PBKDF2". I'm fine with that meme! But that's not what you said. You said "please don't use bcrypt".

PBKDF2 isn't bad. It has one significant asset: you can point to a PKCS standard to convince pointy-haired product managers to accept it into systems. But given the choice between an HN cargo cult and "technology made palatable to enterprise-grade engineering managers", I'll take the cargo cult in this instance.

(Another strength of PBKDF2 that it shares with scrypt but not bcrypt: you can use it as a proper KDF for your AES keys... but note that if you need to generate your own AES keys, you're very likely in trouble for other reasons).

Re: Don't use bcrypt

#132

Post by JoachimSchipper » Mon, Mar 19, 2012, 7:42 PM UTC

marshray wrote: post #125

JoachimSchipper wrote: post #114

Earlier quoted context omitted.

You're right, but don't forget Deep Crack. (FPGA-)hardware-based attacks have only become cheaper since then; I would be surprised if the NSA doesn't have a few arrays. (Also, 80 bits is usually enough to withstand attack, no?)

Yep. There are off-the-shelf FPGA arrays available. Still, bad guys would probably find it much cheaper to rent botnet time for a $0.02/(host*day) or whatever the going rate is. A solid 80 bits of security out of any of these functions might turn out to be safe forever. But, in practice, most password databases are going to have some fraction of users choosing passwords straight out of the cracker's dictionary, some…

COPACOBANA cost ~$10 000 and apparently is as fast as 2500 PCs for the DES cracking it's optimized for, so ~$4/PC-work-unit plus insignificant power costs. You'd need to find someone with experience with implementing crypto in hardware, though. On the other hand, botnets risk detection.

(If you're buying in bulk, ASICs are cheaper, but few will be willing to pay for that much cracking power.)

Re: Don't use bcrypt

#133

Post by marshray » Mon, Mar 19, 2012, 7:47 PM UTC

mturmon wrote: post #70

smacktoward wrote: post #49

> I write this post because I've noticed a sort of "JUST USE BCRYPT" cargo cult... This is absolutely the wrong attitude to have about cryptography. No. This is incorrect. This is exactly the right attitude for most developers to have about cryptography, because on a subject as complex as cryptography most developers (including me!) are nowhere near smart enough to understand the ins and outs. Encouraging people to m…

One more example: pseudorandom number generation (non-cryptographic). There are lots of algorithms out there, and lots more you could design, but the Mersenne twister has pretty much become the first-choice algorithm. Especially with linear congruential generators, it's easy for people who don't know what they're doing to add "extra randomization" that makes the resulting numbers worse than the originals. It's better…

MT uses a lot of memory. IIRC, it's multiple KiB where 64 bits ought to do fine.

A modern CSPRNG like the SHA-3 candidate Skein can produce random data at a steady rate of only a few cycles per byte. I wonder if at some point something like that will dethrone MT for non-crypto PRNGs.

Re: Don't use bcrypt

#134

Post by tptacek » Mon, Mar 19, 2012, 7:50 PM UTC

cdavidcash wrote: post #122

moxie wrote: post #54

This article doesn't feel very well done to me. He writes: "The first cipher I'd suggest you consider besides bcrypt is PBKDF2." PBKDF2 is not a cipher. It's a KDF, and it's almost always used with an HMAC or a cryptographic hash rather than a cipher. The thesis of this article seems to be "PBKDF2 is well understood, where bcrypt is not." In fact, the opposite is probably true. bcrypt uses a block cipher (blowfish) t…

Cryptographic hash functions, by contrast, are not well understood at all. They are "magic" in many ways, and aren't modeled after anything. Many more "bad things" happen in this space than in the block cipher space. Is this a common opinion amongst practitioners? The opposite philosophy (e.g., that a random oracle is a "weaker object" than an ideal cipher) underlies some lines of work in the theoretical cryptography…

Yes, it's a common opinion (I quoted Schneier on it downthread).

Re: Don't use bcrypt

#135

Post by 16s » Mon, Mar 19, 2012, 7:53 PM UTC

Microsoft uses PBKDF2 for newer domain cached credentials (DCC2). These password hashes are stored in the registry of Windows clients (laptops and desktops) and allow users to logon when the domain is unavailable. They use 10240 iterations. It's very compute intensive to crack... roughly 330 guesses per second. Great article BTW!

Edit: I only post this to add to the examples of who uses PBKDF2 in addition to what the article lists.

Re: Don't use bcrypt

#136

Post by JoachimSchipper » Mon, Mar 19, 2012, 7:54 PM UTC

tptacek wrote: post #131

bascule wrote: post #117

Earlier quoted context omitted.

I thought I explained that in my blog post. scrypt is superior to bcrypt in every regard. At the very least, I'd rather the meme be: Use bcrypt, scrypt, or PBKDF2.

The problem is that PBKDF2 isn't superior to bcrypt in every regard: * It has marginally worse library support and is built out of universally available primitives, which increases the odds that generalist devs will DIY it. * It is actually faster than bcrypt (see Colin's paper); in other words, even without waiting for a hypothetical research result against bcrypt, PBKDF2 is already "vulnerable". * PBKDF2 deployment…

I agree, but:

> PBKDF2 deployments virtually all use SHA2 as their PRF, and PBKDF2/SHA2 is a construction that depends entirely on the security of hash functions

A quick look at Wikipedia (and my own recollection) suggests that it may be more commonly used with HMAC-SHA2. Although the HMAC construction is not provably secure [1] and poorly understood, it seems to be fairly resistant to attack (e.g. HMAC-MD5 is not known to be broken, AFAIK.) Also, iterated hashes are much harder to break than single hashes.

[1] Bellare has a result based on a nonstandard but not entirely implausible assumption about the underlying hash function, IIRC. But, as you point out, hash functions are poorly understood...

Re: Don't use bcrypt

#137

Post by derefr » Mon, Mar 19, 2012, 7:57 PM UTC

bascule wrote: post #105

smacktoward wrote: post #49

> I write this post because I've noticed a sort of "JUST USE BCRYPT" cargo cult... This is absolutely the wrong attitude to have about cryptography. No. This is incorrect. This is exactly the right attitude for most developers to have about cryptography, because on a subject as complex as cryptography most developers (including me!) are nowhere near smart enough to understand the ins and outs. Encouraging people to m…

You're defending cargo cult cryptography? If you try to use crypto without understanding it, you're at great risk of using it wrong.

I can use a microwave without any understanding of its functioning, or I can try to understand electromagnetism well enough to build my own. I know which method I'd trust not to render me sterile.

Re: Don't use bcrypt

#138

Post by marshray » Mon, Mar 19, 2012, 7:58 PM UTC

cperciva wrote: post #130

marshray wrote: post #94

Earlier quoted context omitted.

OK, it's in the Scrypt paper. http://www.tarsnap.com/scrypt/scrypt.pdf Here's my opinion on this: * These numbers are more appropriately expressed exponentially. I.e. "factor of 5" = 2 bits of security. * 2 bits of security is not significant at all. * The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry and it buys you maybe about 12 bits of security against such an attacker. * For co…

The Scrypt x5000 seems to only apply when your attacker has access to a chip foundry If your attacker is using GPUs, scrypt probably gives you an even bigger win, due to the compute/memory balance they use.

So I reckon he won't use GPUs then, eh?

Note that the defender pays a cost for this too though. Where he could be happily running PBKDF2 or Bcrypt in multiple Apache process on his multicore servers, Scrypt is going to completely trash the L2/L3 caches and saturate the memory bus and make everything else on the server run like a dog.

Scrypt is operating as designed, of course, but it raises the question of whether or not a defender with a busy website on a farm of multicore servers would be able to configure his work factor as high (in terms of single thread benchmark ms) with Scrypt as he would with Bcrypt or PBKDF2.

Re: Don't use bcrypt

#139

Post by cperciva » Mon, Mar 19, 2012, 7:59 PM UTC

dchest wrote: post #23

cperciva wrote: post #10

Earlier quoted context omitted.

Only as a cryptographic mixing/expansion function. There is no reason to think that scrypt's security would be any less if the PBKDF2 calls were replaced with xor.

Doesn't it provide more protection against possible flaws in Salsa? Also, somewhat related question -- what if Salsa core in scrypt is replaced with BLAKE core (with fewer rounds than in hash), and SHA-2 in PBKDF2 with BLAKE, thus making it possibly smaller (hardware and lines of code). Will this work well?

Doesn't it provide more protection against possible flaws in Salsa?

In a very theoretical sense, yes. But Salsa would need to be very very broken in order for that to matter (hence the "no reason to think" comment).

what if Salsa core in scrypt is replaced with BLAKE core (with fewer rounds than in hash), and SHA-2 in PBKDF2 with BLAKE, thus making it possibly smaller (hardware and lines of code). Will this work well?

Probably. I proved the security under the random oracle model, but the property I actually need is approximately "can't be iterated fast", which is a far weaker requirement.

Re: Don't use bcrypt

#140

Post by tptacek » Mon, Mar 19, 2012, 8:01 PM UTC

JoachimSchipper wrote: post #136

tptacek wrote: post #131

Earlier quoted context omitted.

The problem is that PBKDF2 isn't superior to bcrypt in every regard: * It has marginally worse library support and is built out of universally available primitives, which increases the odds that generalist devs will DIY it. * It is actually faster than bcrypt (see Colin's paper); in other words, even without waiting for a hypothetical research result against bcrypt, PBKDF2 is already "vulnerable". * PBKDF2 deployment…

I agree, but: > PBKDF2 deployments virtually all use SHA2 as their PRF, and PBKDF2/SHA2 is a construction that depends entirely on the security of hash functions A quick look at Wikipedia (and my own recollection) suggests that it may be more commonly used with HMAC -SHA2. Although the HMAC construction is not provably secure [1] and poorly understood, it seems to be fairly resistant to attack (e.g. HMAC-MD5 is not k…

You're right, but the kinds of research results that would accelerate a brute force PBKDF2/HMAC-SHA2 cracker are a superset of the results that would jeopardize HMAC-SHA2 as a MAC. Not to downplay it (it's very important that you get HMAC right) but HMAC-SHA2 is just double-applying SHA2.

I was imprecise, but my point is just, PBKDF2/xSHAx is a construction that relies entirely on the properties of cryptographic hash algorithms; scrypt and bcrypt rely instead on properties of ciphers.