[cryptography] Oddity in common bcrypt implementation
solar at openwall.com
Mon Jun 20 13:55:59 EDT 2011
On Mon, Jun 20, 2011 at 12:11:38PM -0500, Marsh Ray wrote:
> On 06/20/2011 09:59 AM, Solar Designer wrote:
> >On Wed, Jun 15, 2011 at 04:22:55AM +0400, Solar Designer wrote:
> >Yesterday, I was informed of a bug in
> >JtR, which also made its way into crypt_blowfish, and which made the
> >hashes incompatible with OpenBSD's for passwords with non-ASCII characters
> >(those with the 8th bit set). Yes, it was an unintended/inadvertent
> >sign extension. What's worse, in some cases it results in other
> >characters in those passwords being ignored.
> This would result in false positives from JtR?
No. The matching of hashes was precise, so in order for JtR to report a
cracked password it'd need to actually try the right expanded key.
It resulted in most (but not all) passwords with non-ASCII chars that
were hashed on OpenBSD (or on some other systems that implemented bcrypt
without the bug) not being cracked, even when the correct passwords were
input to JtR (such as in a wordlist).
> >Very nasty, and embarrassing.
> Looks to me like a very ordinary bug.
> JtR wasn't intended to be a security-critical piece of software. It
> doesn't need to be and it wasn't tested as such.
That was exactly my thinking when I was writing the code initially, but:
> Taking code which works well for one set of requirements and re-using it
> in another context with a subtly different set of requirements is a
> classic Software Engineering mistake. AIUI, others borrowed JtR code and
> used it in a security-critical context. They didn't "recertify" it for
> its new usage, i.e. test it for false positives. This is a mistake on
> their part.
No, I was the one to make the code available separately from JtR for
such reuse. I re-reviewed it at the time, and I added a different set
of tests ("make check" in crypt_blowfish), but I missed this bug and my
test vectors didn't include 8-bit chars.
> >I am surprised this could go unnoticed for 13 years.
> Perhaps it says something about the frequency of chars > 127 in actual
> user passwords? I don't even know how to type them on my US keyboard and
> I'd be reluctant to use them in my passwords.
Yes. It also says something about the frequency of password hash
migrations between different platforms (such as Linux to/from OpenBSD).
If one person in 200 uses a password with 8-bit chars, and one admin in
5000 does such a migration, that's only one inconvenienced user in a
million. This is unlikely to get researched and reported.
> Or maybe it also says something about the willingness of JtR users to
> report issues with false positives?
No, not that.
> >I am trying to learn some lessons from this.
> The best C developers might get the sign extension thing right 98% of
> the time. This bug is simply going to appear with some degree of
> frequency in everybody's code. The signedness of chars is even different
> between compiler platforms. It takes a ton of testing and independent
> review to weed out the other cases.
Yes, one lesson is that such pieces of code need more testing. Maybe
fuzzing with random inputs, including binary data, comparing them
against other existing implementations.
Another is that unsigned integer types should be used more (by default),
despite of some drawbacks in some contexts (such as extra compiler
warnings to silence; maybe the compilers are being stupid by warning of
the wrong things).
Yet another lesson is that in crypto contexts XOR may be preferred over
OR in cases where both are meant to yield the same result (such as when
combining small integers into a larger one, without overlap).
If anything goes wrong with either operand for whatever reason
(implementation bug, miscompile, CPU bug, intermittent failure), XOR
tends to preserve more entropy from the other operand. In case of this
crypt_blowfish sign extension bug, its impact would be a lot less if I
used XOR in place of OR. A drawback is that XOR hides the programmer's
expected lack of overlap between set bits (the code is not
self-documenting in that respect anymore).
And I am reminded of a near miss with miscompile of the Blowfish code in
JtR, but luckily not in crypt_blowfish, with a certain buggy version of
gcc. So I am considering adding runtime testing. (JtR has it already,
but in crypt_blowfish it's only done on "make check" for performance
reasons. Yet there's a way around those performance reasons while
maintaining nearly full code coverage.)
Finally, better test vectors need to be produced and published. If 8-bit
chars are meant to be supported, must include them in test vectors, etc.
> >More detail here:
> >Although the code fix is a one-liner, fixing this in all affected
> >software is difficult, especially where backwards compatibility matters.
> >I'd appreciate any suggestions.
> For places where it's used for password validation, it may need to be
> bug-compatible, right?
Yes, that's the major difficulty. I proposed a way of dealing with it
in the oss-security thread.
> Fix JtR of course, including the addition of an option to exploit the
> bug. :-)
It is easy to continue supporting the bug as an option. It is tricky to
add code to exploit the bug - there are too many special cases. Might
not be worth it considering how uncommon such passwords are and how slow
the hashes are to compute. It would be curious to estimate the actual
real-world impact of the bug, though, given some large bcrypt hash
databases and a lot of CPU time.
> I'd suggest fixing it with a run-time parameter to make it
> bug-compatible. The downstream vendors can then determine if and how it
> can be configured by the admin and decide on policies for the default
Yes, this is similar to what I proposed on oss-security - using the
"$2x$" prefix to request the buggy behavior.
> What would be helpful for the downstream vendors is any expert guidance
> you could give on the severity to inform the policy decisions. E.g.,
> "bug-compatible mode reduces cracking time by X% in cases where...".
I included some info on that in my first oss-security posting on this,
and referenced my postings to john-dev with more detail. This estimate
is very complicated, though. It is complicated even for the case when
there's just one 8-bit character, and I don't dare to make it for other
cases (lots of if's).
I think the bug-compatible mode simply must not be used for newly set
passwords. It's only to get old hashes processed right during a
transition period. (And most systems don't even need that, because
affected passwords are so rare.)
Thank you for your comments!
More information about the cryptography