[MalaWiki] [TitleIndex] [WordIndex]


 This work is licensed under a Creative Commons License 
 See http://creativecommons.org/licenses/by-nc-nd/2.0/ 
Cracking codes with Genetic Algorithms 
by +mala 
1.  Introduction 
1.1 Note 
2.  GA Basics 
2.1 What is a GA? 
2.2 how does a GA work? 
3.  GA Techniques 
3.1 Choosing the Problem 
3.2 Model and chromosomes 
3.3 Fitness 
3.4 Reproduction e Mutation 
3.5 Genetic Algorithms and probability
4.  Programming 
4.1 GAlib 
4.2 Generic structure of a GA in C++ 
5.  Examples 
5.1 NSCE 
5.2 Mono-alphabetic Ciphers 
6.  Bibliography 
1.  Introduction
It was February 2003 when, on an anti-crack forum, I read the thread (that
you can still find at http://board.anticrack.de/viewtopic.php?t=1108)
entitled "Genetic Algorithms". The+Q wrote: 
<<This made me think, is there a limit to GA? More and more "un-solvable" 
problems are solved by GA, and im starting to feel its only a matter of 
time until hard crypto algorithms are cracked by such meens..>>  
The+Q wasn't the only one to  nurture such strong enthusiasm for genetic
: in the forum several reversers started to ask information on how to
develop programs that used them and I soon started to study and experiment
with them. Everyone thought that by using GA's we could radically change the
approach to reversing and  crypto-analysis. 
Now, two years later not much has changed. Instead, the old threads
On genetic algorithms are drying up and very little new material on GA has
come up: its enough to know that, even now, the tutorial that 
The+Q wrote in 2003 is cited as an example of genetic algorithm applied to
Why did this happen? Why did people stop talking about how powerful genetic
algorithms were soon after trying to use them? 
Is it not sufficient to just understand the theory in order to be able to
resolve every problem? 
I too, during my experiments, found myself more times incapable of finding a
solution  to problems that didn't seem at all so complicated, and every time
I asked myself where's the limit of these techniques. 
Even now I feel that I'm a long way from having learnt everything that
genetic algorithms 
Ask us to comprehend before being able to use them in a truly efficient way,
but at least I got past the stage of  "I don't know how they work, 
But they usually work, therefore they must work". 
I need this personal test to come to a conclusion, it's also for whoever
else that has the patience to follow me and start to work with GA's knowing
already (more or less) what to expect. 
1.1 Note 
I imagine you're already asking why this text has such a particular title
and if it will be of any real use, even if you're not reverse engineers or
Well, The response to the first question is fairly simple: given my dual
interest in both reversing and cryptography, it appeared interesting to me
to conduct experiments in both fields, accumulating them under the name of
"code cracking". In reality, the examples on which I worked are more varied:

not all of them regard code cracking, not all of them had a positive result.
How and ever , from every one of them I learnt something that I'll try to
transmit through these pages. 
As for the usefulness of the text your reading I believe that it's a
sufficient quantity of suggestions and principal ideas to permit anyone to
write genetic algorithms for whatever problem they want to resolve.
Naturally, a greater preparation on the specific argument to which you're
dedicating yourselves will noticeably simplify your work.
Lastly, if at the end of reading this text you're still alive and you're
still interested in genetic algorithms, try taking a look at 
http://mala.homeip.net/malawiki/GeneticAlgos for updates, source code, 
comments on the text, suggestions and voodoo curses. 
2.  GA Basics 
In this section I'll talk about genetic algorithms as simply and generally
as possible, introducing some definitions that will be then used in the rest
of this text. If you are already familiar with GA you can skip this section, 
but I'd advise you to take a look at it anyway, if for nothing else then
to verify that your terminology is exactly the same as mine. 
2.1 What is a GA? 
A GA is a Genetic Algorithm, that is an algorithm genetic (if you're asking
why they call it GA and not AG, do a search with google and see which gives
the most results). 
If we consult the relative  literature, we discover that  
Genetic Algorithms are a family of  computational models that try to evolve.
These models put into practice the Darwinian concept of "the  survival of
the fittest", parting from a population of possible solutions (usually
casual) to a given problem and leaving them to evolve on the basis of some
measurements of their success.  

Academics are still discussing trying to find a precise definition for
Genetic Algorithms. In the meantime, the same term is used with two
different exceptions: following a literal interpretation, this refers to a
literal model introduced and studied by John Holland (1975) and from his
With a meaning a little bit more ample, a Genetic Algorithms is a "model 
Based on a population that uses selection operators and recombination
To generate new points in a search space". 
Seeing as these definitions are as much rigorous as they are unclear, here
are a few examples that will help you better understand the significance of
what was written
A simple case (if not completely commonplace, but its one of the principles
that the literature offers us) could be that in which the PROBLEM consists
in  filling up a line with ones. The POPULATION, that is the group of
possible solutions, could then be represented by a series of strings of
initially casual "bits"  as long as the row desires to be. 
The MEASURE OF SUCCESS of a generic element of the population, which from
now on we'll refer to as CHROMOSOME, will be for example the number of bits
in a string that have a value of 1. You can easily guess that the best
chromosomes will be those closer to the solution, and it's these that will
have a better possibility of "surviving".
In a board game like, for example, Lights Out or Chinese draughts (which 
You can find  respectively, at http://www.2flashgames.com/f/f-35.htm and 
http://www.math.it/damacinese/dama.htm), the PROBLEM consists in ending the
game with a particular configuration: In Lights Out this deals with
switching off all the lights, whereas In Chinese draughts you need to end
with a single piece in the centre of the game board. The POPULATION, in both
could be made up of CHROMOSOMES that represent sequences of moves, 
and the MEASURE OF SUCCESS could be the closeness to the configuration that
resolves the problem, that is how much one gets close to the configuration
with the least lights on or a single piece in the centre. 
In another example (that we'll describe in detail further on) The PROBLEM  
Consists in finding a password to register a program, The POPOLATION
Is made up from CHROMOSOMES that represent the _potentially_ valid password
(that is, satisfying some necessary conditions) an the MEASURE OF SUCCESS is
given by the closeness of the password to the correct one, calculated  
On the basis of the same algorithm used inside the program. 
A last example is that of Mono-alphabetic Ciphers (in which for every letter
of text there is only one other letter that always corresponds to another:
just so we understand each other, 
The same one used in the Puzzle Week). In this case, the PROBLEM 
Consists in finding a substitution of letters that resolves the cryptogram, 
the POPULATION is made up of CHROMOSOMES that corresponds to the various
cipher alphabets and the MEASURE OF SUCCESS is given from how much an
alphabet is good, 
that is , in how much the resulting deciphered text using that alphabet is a
valid test. 
2.2 How does a GA work? 
From the Wikipedia web page (http://it.wikipedia.org/wiki/Algoritmo): 
"In its most simple and intuitive definition an algorithm is a sequence  
 ordered into simple passes that have the purpose of bringing a more complex
task to an end (a cooking recipe, for example, could be considered as an  
 algorithm that parting from a group of single basic food elements
 and following a sequence of passes, produces as a result a prepared dish).
In a more formal mode, we can therefore define an algorithm  
 as an ordered sequence furnished with instructions that, given one or a
series of elements in input, produces one or a series of results in output."

In what sequence of passes, then, does a genetic algorithm follow?  
At a fairly abstract level  (later on we'll increase the detail), 
The operations to follow are the following : 
1) Initialization
   As a first step for the Algorithm a startup population is created , 
Made of casual solutions (chromosomes). When, in Genetic Algorithm theory we
talk about "solution to a problem", naturally, its meaning shouldn't be
intended as a "unique solution", or even a "correct solution". Just as a
mathematical function, on the basis of different input values, can give
different results, in the same way we can think about the presence of
different possible solutions. 
And naturally, as in the case of mathematics we can have a MAXIUM or an
OPTIMUM of a problem, 
The solution that were searching for in the end is an OPTIMUM. 
2) Calculation of the Fitness 
   A value of "fitness" is assigned to every  chromosome on the basis of its
   efficiency with respect to the problem.
   Usually the fitness value corresponds to the value of the function
   (that is, that for which one desires to find the MAXIUM), but its not
   indispensable that its always like that: for example , in the
   of the GAlib (and , to be more precise , at the following address:
   http://lancet.mit.edu/galib-2.4/Overview.html)this distinction 
   is made note explicitly. 
3) Reproduction
   The chromosomes that have a higher fitness are those that more easily
   parents of the next solutions during the phases of reproduction.
   The choice of the parents however comes out in a casual manner , 
   All together the better members of a population are given a better    
   probability of being chosen. 
   Through operators that can change from one problem to another, the 
   chosen chromosomes can generate children , who in turn inherit part
   of their own genes from one parent and part from another. 
   Through a mutation operator, in the end, some casual changes are
   on some of their children's genes before these enter to become part of
   new population. 
4) Successive Generation   
   If the optimal solution has been found (or if some other condition
   from outside has been obtained , for example: a max limit for execution
   time), the algorithm terminates.  
   In the contrary case, the old assembly of chromosomes is substituted by
   newly generated children: the new generation is complete, and we turn to
   point 2. 
2.3 Summary (and glossary) 
    The problem that you desire to resolve. As you will see further on ,
    the point of view of GA It will always deal with  a MODEL of your
    made by you in its use and consumption. 

    An assembly of chromosomes. The dimension of a population can vary from 
    A problem to another and that variation can change the performance of a 
    genetic algorithm noticeably. 
    The generic element in a population. These are the possible solutions to
    problem , not necessarily the most optimum ones but at least solutions
    are compatible with the problem. For example , if the solution is a set
    moves to win a board game, a chromosome will be a sequence of moves,
    not winning but at least valid. 
    It's the value that's assigned to every chromosome in order to evaluate
its suitability for the problem to be resolved. The bigger the fitness the
better the presence of the chromosome in the gene pool and therefore all the
more likelihood that it will reproduce. 
    This is the function for which one tries to find the MAXIMUM to resolve
the problem. Its value is often used as a fitness value. 
    The selection procedure is actuated before reproduction. This consists
    the selection (Casual) of chromosomes that will reproduce, the bigger
    fitness value the higher their probability of selection. 
    This is the process through which children chromosomes are generated 
    Parting from parent chromosomes selected in precedence. The mode with
    this comes to place and the operators that are used are described in the

    next chapter. 
    The Mutation consists in the change (casual)of some genes in a freshly
generated child chromosome. Not all the new chromosomes mutate : even in
this case the selection is casual. 
    Once the selection, reproduction and mutation procedures have
    A new population of chromosomes is created. This constitutes a new
generation. As you are sure to notice, the number of generations  
    Also corresponds to the number of algorithm's iterations and is often
used to give an estimate of the efficiency of the same algorithm. 
3.  GA Techniques 
In the previous chapter we made several references to the "goodness" and the

Performance of a genetic algorithm . Naturally we weren't referring to the 
Characteristics of an algorithm  at a high level of extraction, but to those
Of a GA complete in all its specifics, parting from the model of the problem

Up to arriving at the selection of the probability of reproduction and
Of single chromosomes. 
How do we construct, then, a genetic algorithm? What are the steps that WE 
Must carry out to render it complete? But above all, how can we create a
good genetic algorithm? The chapter that you are about to read will try to
respond to these very demands.  
3.1 Choice of the problem 
If you really want to make genetic algorithms that work, pay great attention

To the problems that you choose! It's clear, unfortunately, that the exact
opposite usually occurs: you have a problem and you have to decide how to
resolve it. Well, in this case think well before choosing to implement a GA.

Talking with several people I asked if there existed a problem that a
genetic algorithm couldn't possibly resolve. The responses were more often
than not, 
Very vague, showing me among other things what was the average knowledge of
the argument. All together some of them were able to clarify my ideas
Usually they started with an honest "I don't know" which was closely
followed with a enlightened "perhaps". 
Trying to unite the "perhaps" clarifications and joining them with my (still
scarce) relative experience, I arrived at these conclusions: 
- Genetic algorithms are perfectly indicated for filling rows or squares
  ones. All together , whatever problem to which a solution is found by hand

  in less time than that required by a GA tends to loose our interest,
  especially when you read it for the ninety-seventh time. 
  In general, however, it's a good thing to evaluate the time that could be

  required to hit a solution (for example brute force) and confront it to
  That which it is effectively taking. 
- often genetic algorithms give the impression of functioning insofar as,  
  reflecting on it, the population cant do anything other than evolve. 
  In reality, especially in the case of problems with a certain complexity, 
  These evolve with an incredible velocity in the beginning, then they slow
  More and more as they approach the solution until they almost stop. 
  Therefore Yes, sooner or later they resolve the problem, but we need to
  WHEN they do it: if a brute force algorithm ,or worse, by shooting casual

  numbers you have a higher probability of finishing in less time then
  about using GA's. 
- in some cases a GA may not be optimum solution, because maybe it requires
  elaboration time than another algorithm ,but may, at the same time, be the
  most rapid solution to develop , in so much as it may require a different
  knowledge of the problem. For example, 
  sometimes reverse engineering an algorithm (hopefully a one-way algo) its
  simply to use it "without bothering to check" and allow a GA to work on
- in some cases, the calculation of the fitness can be extremely boring in
  of time. If there's no other way to evaluate a chromosome, it may be time
  start considering another algorithm (or another model). 
- genetic algorithms aren't very good at resolving problems for which "a
  change in input corresponds to big variations in output" (did you ever
  talk about hash?). As a matter of fact, reproduction and mutation usually
  rise to offspring that aren't very different from the parents: the result
  which gives rise to objective function values that are very far away from
  those anticipated (and as a consequence, worse). For the same reason, the
  problems for which it's guaranteed that "for small changes in input there
  is a corresponding small change in output" are particularly suitable for
  resolution with genetic algorithms. 
  An alternative that was suggested to me for "hash type" problems was to
  a different model, that's able to cancel, ignore, compensate or at least
  render this property of theirs less evident: for this reason I'm inviting
  to read the next point and the next section. 
- Since, as you'll see shortly, for a good result from a genetic algorithm
having a good model is indispensable, a discriminating factor for deciding
if the problem is resolvable or not is in who constructs the model.
Essentially speaking: if you're not capable of modeling the problem in an
adequate manner , maybe you're better off looking for another method.


2014-06-11 14:17