From: Jim McCoy <mccoy@communities.com>
Date: Mon, 23 Sep 1996 18:27:12 +0800
To: cypherpunks@toad.com
Subject: Re: Evolving algorithm for faster brute force key searches?
In-Reply-To: <ae6af5030202100433cd@[207.167.93.63]>
Message-ID: <v03007800ae6bed0079e3@[205.162.51.35]>
MIME-Version: 1.0
Content-Type: text/plain


Adam Shostack <adam@homeport.org>
[...]
>	Weak systems are thus useful for research and training
>purposes.  I suspect Tim is on the money with a genetic algorithim
>having a flat `fitness landscape,' but there may be something that a
>human misses which an evolved algorithim finds.
>
>	Also, it may be possible to evolve something against a
>reduced round version of a cipher (using a training space that is not
>flat) that will still work better than brute force against a full
>system.  If you have cycles to spare, it might be an interesting
>avenue of research.

While a well-designed algorithm has a flat search space in the case of
a single instance of a particular ciphertext/plaintext, this is not
necessarily the case for repeated encryptions using the same key and
possibly for other examples (hence differential cryptanalysis, etc.)
If there is a way to break a system that is less than a brute-force
search of all possible keys then the landscape is not flat.  The hard
part with making such discoveries using evolutionary methods is that
even if the landscape is not completely flat the positive and negative
reinforcement needed to perform selection in such an environment almost
always necessitates that the fitness function be crafted with this in
mind by the researcher and few evolutionary programming researchers know
anything about crypto.

While there are a few strikes against such research (as the oft repeated
"flat landscape" phrase shows) I would not let the current state of the
art in this area disuade anyone interested.  Most of the research done
so far has been done by people who either knew little about crypto or
little about evolutionary programming.  There are also other areas of
crypto relevance which may prove more amenable to evolutionary programming
methods, like factoring...

jim