From: collins@newton.apple.com (Scott Collins)
Date: Fri, 20 Aug 93 12:56:57 PDT
To: catalyst@netcom.com
Subject: Re: cypher breaking and genetic algorithms
Message-ID: <9308201852.AA16537@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


Oops, forgot to CC:cypherpunks.  Sorry.

  -- Peter Baumbach writes: --
  What if the GA "knew" the plain-text, the cyphertext, and the
  encryption algorithm, and was searching for a decryption algorithm
  without the encryption key? Would that be for fruitful?

The attack I was describing assumed that the genetic strings _were_ keys
and the population was about finding the right key.

Peters response suggests that rather than a population comprising keys, a
population of 'programs' -- probably built from (constantly reordered)
modules that performed the same atomic operations used by the encryption
algorithm (and then some).  This is a very strong generalization, and one
that is getting more attention in the field.  'Genetic Programming'.  In
practice this can lead to more fluid populations.

In this instance, though, you can think of a key as a program to be
executed by an encryption or decryption machine and see that a population
of programs is similar in expressive power to a population of keys.

In the case of cryptanalysis of a _good_ cipher, it is the terrain (of the
problem space) itself that gives us the clues about the expected
performance of GA's.  For a population to improve, it has to be able to
measure the performance of an individual (how high has it climbed?) so that
it can give increased resources to the more successful (whose children are
likely to climb higher on a continuous surface).

In cryptanalysis, the goal (the mountain peak) is the correct plaintext. 
An individual, however it may be constructed, yields a trial decryption. 
Its performance must be measured against the only standard available in
this case, the known plaintext (or the expected statistics of plaintext if
known plaintext is not available).

If there were an accurate measure of how 'good' a trial decryption was then
your GA could climb.  However that would imply a continuous 'goodness'
function, whose surly bonds strong ciphers surely seek to slip.

It is this reliance on continuousness that make GAs great at climbing
hills, but rarely better than undirected random search at finding a needle
in a haystack.


Scott Collins         | "Few people realize what tremendous power there
                      |  is in one of these things."     -- Willy Wonka
......................|................................................
BUSINESS.   voice:408.862.0540  fax:974.6094   collins@newton.apple.com
Apple Computer, Inc.   1 Infinite Loop, MS 301-2C   Cupertino, CA 95014
.......................................................................
PERSONAL.   voice/fax:408.257.1746    1024/669687   catalyst@netcom.com