[cryptography] Oddity in common bcrypt implementation
solar at openwall.com
Tue Jun 14 20:22:55 EDT 2011
On Tue, Jun 14, 2011 at 04:52:30PM -0500, Marsh Ray wrote:
> I don't see an official reference for the format of bcrypt hashes.
> There's the Usenix 99 paper, which is a great read in many ways, but
> it's not a rigorous implementation spec.
Yes. I am aware of three discrepancies between the paper and the actual
1. Hash size (192 vs. 184). IIRC, the paper doesn't mention the hash
size explicitly, though. It merely says that the last step encrypts a
2. Maximum plaintext length (55 vs. 72). This one even resulted in
slightly erroneous dollar cost numbers in the scrypt paper.
3. Order of ExpandKey()s in the costly loop:
There might be more.
The crypt(3) man page from crypt_blowfish, which I wrote in 2000, says
this about bcrypt (and it always did):
Maximum password length
72 (uses 8-bit characters)
This is the man page we have on Owl, and you can find it on a few other
Linux distros as well.
> http://openwall.com/ seems to be a popular source for a C implementation
> of bcrypt. Openwall seems to be getting it from John the Ripper.
> I wonder if JtR is simply looking to find a hit and not bothering with
> the last 16 bits?
> Solar, did you expect people to use your implementation for validating
> passwords (as well as cracking them) when you wrote it?
Not "when I wrote it", but that's not the reason. The code in JtR has:
/* This has to be bug-compatible with the original implementation :-) */
BF_out[index] &= ~(BF_word)0xFF;
IIRC, I notified Niels of this in 1998. The bcrypt paper was not yet
written, but OpenBSD was already using the $2a$ revision at the time,
and this little detail was not a sufficient reason to make any change.
IIRC, this was not an attempt to use base-64 encoding more optimally,
but rather it was an implementation bug in the base-64 encoder function
(something like ">" instead of ">=").
Then I released my bcrypt code from JtR for reuse, under the name of
crypt_blowfish in 2000. Several Linux distros started using it (patched
into glibc), as well as PostgreSQL's contrib/pgcrypto, CommuniGate Pro
messaging server, and some other programs. More recently, this same
code got into PHP 5.3.0+. Of course, those hashes are fully compatible
As to optimizations in JtR (but not in crypt_blowfish) similar to what
you ask about, there's one: instead of encrypting the 192-bit constant
64 times, JtR encrypts a 64-bit constant (one Blowfish block) 64 times.
It only processes the extra 128 bits if there's a match in the 64 bits.
This optimization achieves very little (could be 0.1% for typical cost
settings), though - because it is outside of bcrypt's most costly loop.
In OpenMP-enabled builds of JtR, this optimization is not done;
otherwise, I'd have to pass multiple copies of the relatively large
Blowfish state out of the parallel section (either copy that data or
keep it somewhere easily accessible from both the parallel and the
sequential code, either of which would be a performance hit). Well,
I guess this is more than you cared to know. ;-)
More information about the cryptography