Date: Sat, 9 Sep 2006 13:36:24 +0400 From: Solar Designer <solar@...nwall.com> To: john-users@...ts.openwall.com Subject: Re: encryption strength vs. the time it takes to find the same password with different key sizes On Thu, Aug 31, 2006 at 01:58:17PM -0700, Bolan, Scott wrote: > It is my understanding that *all* 32 bit hashes can be cracked. Here is > the reasoning. > > - Since a hash has a finite length, multiple passwords will generate the > same hash. (the pigeon hole principle: there are more possible > passwords then there are hashes) Yes. > - a 32 bit key has 2^32 possible hashes (4,294,967,296). Now you have started to confuse things. What exactly are you referring to by a "32-bit hash" - a hash that accepts 32-bit inputs (which you call keys?) and/or one that produces 32-bit outputs (hash values)? For the former, there can be _at_most_ 2 ** 32 different hashes - or less. > A big number but on a reasonable computer this is 1 - 4 weeks of work. You can't know the time it'd take to search all those keys with such precision unless you define a specific hash function. For example, if an optimal implementation for a given hash function would be taking 1 second to compute on a modern CPU, then the time to search 2 ** 32 of possible inputs would be: 2 ** 32 / 86400 / 365 = 136 years However, if 10 million hashes could be computed per second, then the time would be: 2 ** 32 / 10 ** 7 / 60 = 7 minutes Both are realistic. > So instead of a 'naive' brute for attack, (a, b, c, ... , aa, ab, ac, > ...), you can try all possible hashes. How? The hashes are _known_. You need to find inputs that produce those hashes. > You just need to find *a* password that hashes to the correct value > (there are many). That's true - and this is helpful primarily when the hash size is more limited than the input size. > I suspect that the password you found would work for the 32 bit > encryption but not for the 64 bit encryption. This is because you just > found one of the passwords that worked for the 32 bit encryption and not > the 'actual' password. The above paragraph doesn't make sense at all. -- Alexander Peslyak <solar at openwall.com> GPG key ID: 5B341F15 fp: B3FB 63F4 D7A3 BCCC 6F6E FC55 A2FC 027C 5B34 1F15 http://www.openwall.com - bringing security into open computing environments -- To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply to the automated confirmation request that will be sent to you.
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.