I wonder what are the advantages of using bcrypt over an iterated and salted KDF based on some cryptographic hash function like SHA-1 (or SHA-3)? I guess the authors of bcrypt chose Blowfish (a block cipher) for a serious reason, but we could barely replace it in with SHA-1/SHA-3 (a hash function). What is wrong with such an approach? What are security properties brought by a block cipher that are not by hash functions?
8
-
$\begingroup$ No one on this site can read the authors' minds, so any answer can only be speculative. Regarding SHA-1 in particular, this is actually a good thing: since around 2005 this should be considered deprecated and not used for new designs any more. But we can't know if the authors of bcrypt foresaw this in '99. $\endgroup$– tyloJul 3, 2019 at 15:14
-
$\begingroup$ SHA-1 was just an example. Replace it by SHA-3 if you prefer. I just wonder why they chose a block cipher and not a hash function. $\endgroup$– matlinkJul 4, 2019 at 12:40
-
$\begingroup$ If there are 2 ways to achieve the same goal, and it comes down to just choosing one, they might have flipped a coin. The point is, there can be no definitive answer to this kind of choice except speculation, unless you ask the authors. And pure speculation is basically useless from a scientific point of view. $\endgroup$– tyloJul 4, 2019 at 14:39
-
1$\begingroup$ It's important that a password stretching function based on an iterated function $f$ has just a few properties. (At least to be competitive with ancient algorithms like PBKDF2 and bcrypt). Computing $f^n(x)$ (as in $f^3(x) = f(f(f(x)))$) must not cost significantly less than $n$ times the cost to calculate $f(x)$ once. You want to maximize your efficiency of $f$ to give password crackers the smallest advantage possible. And the entire stretching function has to be one-way. It doesn't matter if you use a hash or block cipher because a one way function can be made from a block cipher. $\endgroup$– Future SecurityJul 6, 2019 at 17:30
-
$\begingroup$ @tylo with a quick google search, i could not find any indication that any of the bcrypt authors are dead. Niels Provos made a youtube video 4 days ago and appears to be very much alive. David Mazières made a twitter post 7 days ago, and also appears to be alive. (TIL one of the bcrypt authors is a youtuber! neat) $\endgroup$– hanshenrikSep 11, 2019 at 20:35
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
1
The bcrypt KDF does not use the entire block cipher as-is. It relies on a modified version of its key schedule. This is important because blowfish, unlike many other ciphers, has an extremely expensive key schedule. It requires about four kilobytes of fast memory, compared with SHA-1 which is so light that it can almost be computed entirely in x86 registers. Although bcrypt is not nearly as memory-hard as other, modern KDFs like Argon2, it was still quite good at the time and is still better in many ways than PBKDF2, which internally uses a hash function like SHA-1 or the SHA-2 family.
See Why can't one implement bcrypt in Cuda? for more information on why memory hardness is good. It explains why you can't get as much out of the massive parallelism of a GPU with bcrypt. There's also the wonderful answer by Thomas Pornin elsewhere which goes into more detail about bcrypt's security.
-
$\begingroup$ Mr. Pornin's fine explication of bcrypt's security, from 2011, still dazzles, and the part about the NIST at the end of his answer turned out to point towards something rather ominous. $\endgroup$– PatriotJul 7, 2019 at 1:11
$\begingroup$
$\endgroup$
2
A good way to find out what the authors meant would probably be reading their original paper where they introduced bcrypt : https://www.usenix.org/legacy/event/usenix99/provos/provos.pdf
I think comparing bcrypt with e.g. pbkdf2 is not quite fair for bcrypt since it was an earlier construction and ideas like tweakable number of iterations are actually inspired by bcrypt.
-
1$\begingroup$ I'm here asking this especially because I didn't find the answer in their paper. I thought there were some security advantages to use a block cipher rather than a hash function, like how block ciphers are studied compared to hash functions. For example, there exist MD5 crypt, which was used in some Linux distributions. $\endgroup$– matlinkJul 4, 2019 at 15:58
-
$\begingroup$ @matlink: I see. No, there are no fundamental differences between using a block cipher and a dedicated hash function (like SHA-1). In fact, SHA-1 is a block cipher in a Davies-Mayer hashing mode. The structural difference is that blowfish has an expensive key schedule, as elaborated by forest in another answer. So it's less about block cipher vs. hash function, more about expensive implementation vs. easy implementation. $\endgroup$– KrisJul 8, 2019 at 8:06