|From:||Solar Designer <solar-cxoSlKxDwOJWk0Htik3J/w-AT-public.gmane.org>|
|Subject:||Re: Either my test script is b0rken or BF has an 8-bit bug|
|Date:||Mon, 20 Jun 2011 07:29:06 +0400|
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
Copyright © 2011, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds