On Thu, 11 Jul 2002, Reckhard, Tobias wrote:
Yes, this is called a collision. With the crypt algorithm, which produces 56 bit results, every 72,057,594,037,927,936th (==2^56) password gets the same hash value. With other words, if you
I think you're forgetting about the birthday paradox. See http://www.rsasecurity.com/rsalabs/faq/2-4-6.html for some information on attacks against hash functions.
[salt]
typical MD5 "crypts" use much larger ranges). The value is taken by random. So every password has 4096 possible results. To be able to decrypt, the salt itself is stored in plain as the first two bytes of the password "hash". So for a million words you would need 4 billion precalculated hashes.
However, since the salt is stored in plaintext in the shadow file, if you get that, the advantage of salt disappears.
That is, if you only want to decrypt one password and happen to have the right translation table for this salt at hand. Therefore you would need [number of salt flavours]*[number of words] dictionary entries to be able to crack a password with an arbitrary salt on the fly. I can't see something disappearing here... Talking about all these hash lengthes and numbers of words you should always keep in mind that hardly anyone generates their 8 character passwords with a perfect random number generator, and even this would buy you only about 80^8=2^(50.6) possible passwords. The quality of the hash can become quite irrelevant if you consider that most people's passwords only contain [a-z0-9], which makes about 41.4 bits in the optimistic case of 8 characters. You should convince yourself that this keyspace is easily exhaustable within a reasonable period of time on current consumer hardware. That said, the whole discussion becomes quite irrelevant... Ciao, Roland +---------------------------+-------------------------+ | TU Muenchen | | | Physik-Department E18 | Raum 3558 | | James-Franck-Str. | Telefon 089/289-12592 | | 85747 Garching | | +---------------------------+-------------------------+