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.