Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<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

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ