1996-09-23 - Re: Evolving algorithm for faster brute force key searches?

Header Data

From: “Perry E. Metzger” <perry@piermont.com>
To: jack <thecrow@iconn.net>
Message Hash: 64b7b5cc1e9db6ccf3ee6932d7a95a451e1ae74d1f0543d862a3c05d16e486a8
Message ID: <199609222305.TAA08525@jekyll.piermont.com>
Reply To: <31DD74B1.BB3@iconn.net>
UTC Datetime: 1996-09-23 01:47:04 UTC
Raw Date: Mon, 23 Sep 1996 09:47:04 +0800

Raw message

From: "Perry E. Metzger" <perry@piermont.com>
Date: Mon, 23 Sep 1996 09:47:04 +0800
To: jack <thecrow@iconn.net>
Subject: Re: Evolving algorithm for faster brute force key searches?
In-Reply-To: <31DD74B1.BB3@iconn.net>
Message-ID: <199609222305.TAA08525@jekyll.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



The problem with your idea, Jack, is that any decent crypto algorithm
will change on average half the output bits when one bit of the key is
changed. In other words, by definition, if you can do this, the
algorithm isn't as strong as it should be.

However, you are correct that failures to meet this standard properly
can be found in some popular algorithms. You might want to read Biham
and Shamir's book on differential cryptanalysis for details.

jack writes:
> I got an idea last night, maybe this has already been thought of and
> tried, but I thought I would give a quick outline of the program I was
> thinking of:
> 
> -Specify a maximum key size (assume 1024bits or something)
> -Start with an arbitrary key "aaaaaaaaaaaaaa"
> 
> Start a loop
> 
> -create five mutations of the key
> -use each key to try and decrypt a few bytes of the message
> -run a (or some) statistical analysis tests and come up with a value
> for how 'random' the decrypted bits are
> -Pick the key that produced the least random ouput
> 
> Repeat
> 
> 
> Probably this wouldnt work on any very strong algorithm, but it seems it
> might be effective against some.  I am going to write the code and try
> it out on RC4 and on a weakling little algorithm I wrote a while back.
> Let me know what yall think.





Thread