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
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
