Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 20 Jun 2011 07:29:06 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Either my test script is b0rken or BF has an 8-bit bug

On Mon, Jun 20, 2011 at 04:15:16AM +0400, Solar Designer wrote:
> ... It is almost as bad as I thought it was.  In my
> testing so far, I am able to construct password pairs that differ in two
> characters, yet produce the same hash on Owl.  For example, "ab"
> followed by the pound sign ("\xa3" in C) produces the same hash as the
> pound sign alone does (when I use the same salt for testing, indeed):
> 
> $2a$05$/OK.fbVrR/bpIqNJ5ianF.CE5elHaaO4EbggVDjb8P19RukzXSM3e
> 
> This will require some non-trivial handling.  Not only do we need to
> patch the bug in JtR and in crypt_blowfish, but we also need to get this
> change accepted into affected software (to be identified), and even then
> we could want to continue to support those alternate hashes available in
> the wild, maybe with some non-default setting in JtR (and in other apps?)

One idea I had is to provide an external filter() for JtR (after fixing
the bug in it) to be used when cracking potentially wrong bcrypt hashes
(produced with the buggy crypt_blowfish).  The translated passwords
would produce the same bcrypt hashes, but using the correct bcrypt code.
For example, "\xa3" (pound sign) would be translated to "\xff\xff\xa3",
which produces the above hash on OpenBSD.

Unfortunately, there exist passwords with no correct equivalent.  For
example, "A\xa3" (letter "A" and the pound sign) produces this expanded
key with the buggy code:

ffa30041ffffffa3ffffa300ffa30041ffffffa3ffffa300ffa30041ffffffa3ffffa300ffa30041ffffffa3ffffa300ffa30041ffffffa3ffffa300ffa30041ffffffa3ffffa300

Notice that the pieces separated by NUL bytes are not the same.  We'd
need to embed NULs to encode this, but a NUL terminates processing of
the input password.

Thus, the filter() idea has to be abandoned, or at least the filter()
will only work for some passwords, but not for all.

I also did some research on impact of the bug (I am mostly concerned
about systems and apps that use crypt_blowfish, not about JtR).  Here's
a summary of my current understanding:

For passwords of length other than n*4-1 (3, 7, 11, 15, ...), any 8-bit
character (one or more) results in a hash incompatible with OpenBSD's,
but does not result in any characters being ignored (no security risk).

For passwords of length n*4-1 (3, 7, 11, 15, ...), 8-bit characters in
positions i*4-3 (1, 5, 9, 13, ...) result in hashes compatible with
OpenBSD's (the bug is fully mitigated), as long as there are no other
8-bit characters (in other positions).

For passwords of length n*4-1 (3, 7, 11, 15, ...), 8-bit characters in
positions i*4-2 (2, 6, 10, 14, ...) result in hashes incompatible with
OpenBSD's and with single characters right before the 8-bit characters
ignored (not affecting the hash value).

For passwords of length n*4-1 (3, 7, 11, 15, ...), 8-bit characters in
positions i*4-1 (3, 7, 11, 15, ...) result in hashes incompatible with
OpenBSD's and with pairs of characters right before the 8-bit characters
ignored (not affecting the hash value).

For passwords of length n*4-1 (3, 7, 11, 15, ...), 8-bit characters in
positions i*4 (4, 8, 12, ...) result in hashes incompatible with
OpenBSD's, but without any characters ignored (no security risk).  These
are similar to passwords of other lengths.

Thus, the probability for an arbitrary password with a single 8-bit
character to have any of its characters ignored may be estimated as
1/8 (assuming uniform distribution of password lengths and of positions
in which the 8-bit character may be).

This fails for unusually long passwords, though, as the 72-character
limit comes into play much earlier than it would have without 8-bit
chars or with correct code.  Up to three characters may be ignored by a
single 8-bit character in passwords of 40 characters or more.

What a mess.

Alexander

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.