[cryptography] Oddity in common bcrypt implementation

Marsh Ray marsh at extendedsubset.com
Mon Jun 20 15:09:19 EDT 2011


On 06/20/2011 12:55 PM, Solar Designer wrote:
>
> 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.

There are certainly more bugs lurking where the complex rules of 
international character data "collide" with password hashing. How does a 
password login application work from a UTF-8 terminal (or web page) when 
the host is using a single-byte code page?

I once looked up the Unicode algorithm for some basic "case insensitive" 
string comparison... 40 pages!

> Another is that unsigned integer types should be used more (by default),

I know I use them whenever possible. Even into the 18th century 
Europeans were deeply suspicious of negative numbers.
http://en.wikipedia.org/wiki/Negative_number#History

There may be arguments for consistently using signed ints too, but bit 
manipulation isn't one of them. And why stop with negative numbers, why 
not include the complex plane, div0, and infinities too? Sorry, I'm 
getting silly.

> 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).

Yeah IMHO

    unsigned char data[] = { 0xFF, 0xFF, 0xFF, 0xFF };

should always compile without warnings.

> 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.

Well, XOR has the property that setting a bit an even number of times 
turns it off. This is obviously not what you want when combining flags, 
for example. I suspect there are as many mistakes to be made with XOR as 
there are with OR. It's very hard to predict the ways in which bitwise 
expressions will be buggy.

> 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).

It would make sense for C to have more bit manipulation operators. Some 
processors have instructions for bit replacement, counting bits, finding 
the lowest '1', etc.

> 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.)

Seems like "make check" is a good place for it.

> 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.

Yes, I think this a big criticism of the bcrypt algorithm. It's just not 
documented precisely enough for standardization.

> 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.

Years ago I worked at a place that insisted our passwords be all upper 
case. "Because that's the last thing cracking programs typically search 
for" was their rationale. I didn't have the heart to tell them about LM.

It sounds obvious now that I hear myself typing it, but generalizations 
about the frequency might not apply in any specific case. Some admin 
somewhere has a password rule that enforces a near worst-case on their 
users. http://extendedsubset.com/?p=18

> 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.

Haha, more seem to be made available all the time.

> Yes, this is similar to what I proposed on oss-security - using the
> "$2x$" prefix to request the buggy behavior.

Somebody needs to start keeping a master list of these prefixes. This is 
the kind of thing that IETF/IANA can be good at (but it can take a long 
time).

>> 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).

Perhaps you could do an exhaustive search up to a certain length and 
look at frequency of randomized collisions or rainbow cycle lengths 
above that?

> 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.)

Well, that decision can only be made locally by the admin, since he's 
the only one who knows where these hashes might be migrated.

- Marsh



More information about the cryptography mailing list