[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
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.
