Re: Evolving algorithm for faster brute force key searches?

At 8:01 PM 7/5/96, jack wrote:
>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

Schneier actually used my explanation of why this won't work in the Second
Edition of his book.

Basically, with any strong. modern cipher, there is no concept of "getting
closer" to a solution. Thus, the "fitness landscape" for a
brute-force-needed cipher looks like a flat plain (if portrayed in two
dimensions), with the solution/key being a single-point spike rising from
the plain. No hill-climber can find this spike except by landing right on
it, which means evolutionary programming, genetic algorithms, simulated
annealing, and neural net sorts of approaches are worthless.

With some weak ciphers, this might work. I think Schneier makes some
comments about who's looked at this. But weak ciphers are not too
interesting.

--Tim May

We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^1,257,787-1 | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."

Timothy C. May wrote:

| With some weak ciphers, this might work. I think Schneier makes some
| comments about who's looked at this. But weak ciphers are not too
| interesting.

	At the most recent Crypto, someone mentioned that FEAL is
useful because just about any new attack you can think of works well
against it.  I think it was Susan Langford.

	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.

Adam


-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

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