Date: Sun, 9 Apr 2006 06:15:28 +0400 From: Solar Designer <solar@...nwall.com> To: john-users@...ts.openwall.com Subject: Re: hash collisions On Sat, Apr 08, 2006 at 08:31:53PM -0500, Dennis Olvany wrote: > Solar Designer wrote: > >For most hash types, the number of inputs is also finite - even in > >theory. And it is finite for all of them in practice. > > Do you refer to password hashing specifically? Primarily, yes - but also to: > Algorithms such as MD5 and SHA1 digest the entire input, correct? Yes. > So, while I suppose that the > input may be finite I would venture to guess that it is only limited by > a maximum file size, which is certainly far beyond 56 bits. Actually, MD5 and SHA-1 encode the length of input in bits as a 64-bit value, which gives us a (very large) theoretical limit on the maximum input length they can support - regardless of OS. So the input length - and thus the number of possible inputs - is finite (albeit very large). Please remember that we're discussing the theory here. Collisions are extremely rare in practice anyway, unless they're caused on purpose. > >[crypt] input is truncated to 56 bits > > Crypt truncates to eight characters, right? Yes. > I am thinking that 8 characters at 8 bits per character is 64 bits. Those are 7-bit characters, which gives 56 bits. > The most significant bit in each character is removed Yes. > because it is always zero? No. Those bits just wouldn't fit into 56-bit DES keys. Usually the most significant bits are in fact zero, though. crypt(3) didn't have to use DES in this unfortunate way, propagating the key length of DES onto input passwords, but traditional crypt(3) happens to be designed this way. > Perhaps it causes a cryptographic weakness for every eighth bit > to be a zero? No, it does not cause any unexpected weakness - beyond the values of those bits in the input password not affecting the resulting hash. Those zeroes do not become a part of the DES key anyway. -- Alexander Peslyak <solar at openwall.com> GPG key ID: B35D3598 fp: 6429 0D7E F130 C13E C929 6447 73C3 A290 B35D 3598 http://www.openwall.com - bringing security into open computing environments Was I helpful? Please give your feedback here: http://rate.affero.net/solar
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.