Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
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.