Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 01 Sep 2006 10:36:10 +0200
From: Simon Marechal <simon@...quise.net>
To: john-users@...ts.openwall.com
Subject: Re: encryption strength vs. the time it takes to find
 the same password with different key sizes

Bolan, Scott wrote:
> This is not quit what you were asking but it might be of interest.
> 
> 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)
> 
> - a 32 bit key has 2^32 possible hashes (4,294,967,296).  A big number
> but on a reasonable computer this is 1 - 4 weeks of work.
> 
> So instead of a 'naive' brute for attack, (a, b, c, ... , aa, ab, ac,
> ...), you can try all possible hashes.  This will give you *a* correct
> password although it probably won't give the *the* correct password.
> You just need to find *a* password that hashes to the correct value
> (there are many).

Just a note: if that would work, that would mean that all hashes
produced by your hashing function could be generated by hashing a hash
(surjective function). As it's easy to see that hashing any hash will
produce another hash, it's injective too.

That means that your function is bijective in the hash domain. I'm not a
math/crypto wizard but i'm pretty sure that:
* it's not true for any good hash function
* if it was true, it would be easy to find collisions, meaning the hash
would be useless

I would suggest if your goal is to find a collision to try all typable
sequences (a, b, c, ...), you'll have the same probability it works than
trying hashes, except there are more than 2^32 possible combinations and
they will be typable.

-- 
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.