[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20060408222825.GB22501@openwall.com>
Date: Sun, 9 Apr 2006 02:28:25 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: hash collisions (was: help me understand password cracking)
On Sat, Apr 08, 2006 at 01:05:06PM -0500, Dennis Olvany wrote:
> Here's another interesting thing. Sometimes two different
> inputs will result in the same hash. This is called a collision. It is
> very rare, though.
Correct.
> Collisions are possible because there are a finite number of unique
> hashes and an infinite number of inputs.
Not exactly.
For most hash types, the number of inputs is also finite - even in
theory. And it is finite for all of them in practice.
The reason why collisions are possible is different - most cryptographic
hashes are simply not designed to avoid collisions. This is the reason
for the possibility of collisions with LM hashes and traditional crypt(3)
hashes - where the number of possible inputs is smaller than the number
of possible unique hashes.
It is true that when the number of possible inputs is larger than the
number of possible unique hashes, collisions are unavoidable - no matter
what the hashing method is and how it is designed.
> Though unless I'm mistaken, crypt may not be susceptible to collisions
No, it is susceptible.
> because the input is truncated to a finite 64 bits.
No. The input is truncated to 56 bits and the output is 64 bits. So
collisions could have been avoided. But the design does not avoid them.
For most passwords (99.6%), collisions with LM hashes are not possible.
The same applies to traditional crypt(3) hashes - but separately from LM
hashes (so it is possible to have a password which would collide with
another one for LM, but not for crypt(3) hashes, and vice versa). For
the remaining 0.4%, collisions with these hash types are possible (also
separately - so it's different sets of colliding passwords).
This is almost pure theory. Most users of John won't ever have a
collision in practice - and those few who will, won't notice (because
they would almost certainly be running John against many thousands of
hashes).
--
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.
