[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20060909093624.GA11537@openwall.com>
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.
