[wplug] Limitations of brute forcing crypto (was some crap about windows password hacking..blah)

Bryon Gill bgtrio at yahoo.com
Tue Oct 12 23:03:30 EDT 2004


I was thinking the same thing- it's a fantasy, but...

1. Sometimes proving to yourself that it is in fact a fantasy is a useful 
exercise.
2. Everytime I read about some teenager or grad student making some amazing 
technical advance, they always say something like "I was naive enough not to 
know that I wasn't supposed to be able to do that."

Bryon

ps - those who aren't familiar already should lookup lzip compression (better 
compression ratio than even bzip2) if you want to see where taking compression 
to the utmost gets you!


On Tue, 12 Oct 2004, Patrick Wagstrom wrote:

>> If I can get a bzip2 file of all possible values and hashes at something
>> less than 9.4 GB, then this is useful, otherwise, it is only an amusing
>> fantasy.
>
> I think you're going to have to call this one at fantasy.  You're better
> off looking for a weakness in the algorithm than brute forcing it.
> Actually, you're better off trying to engineer a replacement set of DLLs
> that call the windows functions to do it for you, but I digress.
>
> You might be interested to know that SHA-0 was broken at this years
> Crypto conference and a modified version of SHA-1 was found that allows
> for collisions.  These both rely on intricacies of the protocols.
>
> Your "strategy" will not get you anywhere.  There are a lot of people
> who are a whole lot smarter than you and I (and anyone else on this list
> most likely) who designed and evaluated these algorithms.  If it was
> possible to contain all the hashes in on 9.4GB file then it wouldn't be
> secure in the first place.
>
> Furthermore you're running into some problems with theory here.  The
> issue with these algorithms is that they're one way hash functions that
> take an arbitrary input and convert it to another 128 bit string such
> that you can't map it backwards.  Being as there are more than 2^128
> different combinations of programs out there (as 1st year CS students
> learn, the set of all computer programs is countable, but infinite) that
> means there must be some collision.  This to have all possible values an
> hashes would mean that you've found a way to compress all possible data
> down to less than 9.4GB.  Congratulate yourself, you've just won
> yourself the Fields Medal (well, not until 2006).
>
> For further reading, might I recommend Applied Cryptography by Bruce
> Schneier.  It also has a wonderfully hilarious section explaining the
> thermodynamic limitations of brute force algorithm hacking on page
> 157-158.
>
> --Patrick
>
>
> _______________________________________________
> wplug mailing list
> wplug at wplug.org
> http://www.wplug.org/mailman/listinfo/wplug
>


More information about the wplug mailing list