Breaking Codes with Genetic Algorithms

Genetic Algorithms in Elixir — by Sean Moriarity (57 / 101)

👈 Chapter 7 Preventing Premature Convergence | TOC | Understanding Mutation 👉

Imagine that you’ve been tasked with protecting the integrity of your firm’s data. One day, a hacker manages to get on your system and encrypts all of your data before demanding a ransom to decrypt it.

Luckily, the hacker decided to use a basic XOR cipher with what appears to be a 64-bit key. That means, if you’re able to determine the key, you’ll be able to easily apply the cipher in reverse to restore all of your data.

XOR ciphers are reversible ciphers that work by applying a bitwise XOR with a key on every character in a string. Unicode characters are represented with 16-bits. Given a key and a string, you can encrypt the string by applying an XOR of every character with your key. The following image demonstrates this process:

To decrypt an XOR cipher, you can apply the same process in reverse — if you know the key. XOR is the inverse of itself, so you can apply the cipher on encrypted text with the same key to obtain the decrypted version. The following image illustrates this:

Because of the hacker’s choice to use a basic XOR cipher, all you need to do is find the 64-bit key they used to encrypt your data. Unfortunately, it’s not feasible to search through all 2⁶⁴ possible keys. Instead, it makes sense to use a genetic algorithm.

Representing the Problem

First, create a new file scripts/codebreaker.exs.

Next, create the shell of your Problem definition:

​ ​defmodule​ Codebreaker ​do​
​   @behaviour Problem
​   alias Types.Chromosome
​   ​use​ Bitwise
​ 
​   ​def​ genotype, ​do​: ​# genotype​
​ 
​   ​def​ fitness_function(chromosome), ​do​: ​# fitness​
​ 
​   ​def​ terminate?(population, generation), ​do​: ​# population​
​ ​end​

Notice the additional use Bitwise at the beginning of your module definition. You’ll need this to implement the fitness function.

Now you need to implement your problem-specific functions.

You’re trying to find the 64-bit key the hacker used to encrypt your information. Naturally, you’ll want to represent your chromosome as a bitstring with 64-bits:

​ ​def​ genotype ​do​
​   genes = for _ <- 1..64, ​do​: Enum.random(0..1)
​   %Chromosome{​genes:​ genes, ​size:​ 64}
​ ​end​

Here, you generate random binary genotypes of size 64 and return a new Chromosome struct.

Evaluating and Stopping

Next, you need a way of evaluating how close you are to finding the correct key. Luckily, you remember one of the names of the files on your desktop: ILoveGeneticAlgorithms. It appears the name of this file has been changed to LIjs‘B‘k‘qlfDibjwlqmhv. Given you have an encrypted string, and you know the decrypted version, you can guess a key and apply it on your encrypted string to see how close it gets you to the decrypted version.

Implement your fitness function like this:

​ ​def​ fitness_function(chromosome) ​do​
​   target = ​'ILoveGeneticAlgorithms'​
​   encrypted = ​'LIjs`B`k`qlfDibjwlqmhv'​
​   cipher = ​fn​ word, key -> Enum.map(word, rem(& &1 ^^^ key, 32768)) ​end​
​   key =
​     chromosome.genes
​     |> Enum.map(& Integer.to_string(&1))
​     |> Enum.join(​"​​"​)
​     |> String.to_integer(2)
​ 
​   guess = List.to_string(cipher.(encrypted, key))
​   String.jaro_distance(target, guess)
​ ​end​

You start the function by declaring your target, which is the correctly decrypted version of one of your encrypted filenames, as a charlist. You also define encrypted in the same way. Next, you define a basic XOR cipher which iterates through each character in a provided word and applies an XOR before taking the remainder of the result of the XOR and 32768 to ensure your guessed cipher has codepoints within the usable character range for Elixir strings.

The next step generates an integer key from the provided chromosome. Your chromosomes are lists of 1s and 0s. To convert the list of 1s and 0s to a decimal integer, you need to convert the list to a string and then parse the string with a base 2, indicating the number is a binary representation of an integer.

After you’ve defined your key, you need to generate a guess from your key. The guess is just an attempt at decrypting encrypted with the key your chromosome represents. Finally, you compare your guess with the target using String.jaro_distance/2. String.jaro_distance/2 is a measure of the similarity between two strings. It returns a value between 0 and 1, with 1 meaning the compared strings are identical.

Because your fitness function returns 1 only when the strings are identical, you can safely assume that you’ve identified the correct key when the fitness of a chromosome is 1. Therefore, your termination criteria is this:

​ ​def​ terminate?(population, _generation), ​do​:
​   Enum.max_by(population, &Codebreaker.fitness_function/1).fitness == 1

Running the Algorithm

Now, add the following below your module definition:

​ soln = Genetic.run(Codebreaker,
​                    ​crossover_type:​ &Toolbox.Crossover.single_point/2)
​ 
​ {key, ​"​​"​} =
​   soln.genes
​   |> Enum.map(& Integer.to_string(&1))
​   |> Enum.join(​"​​"​)
​   |> Integer.parse(2)
​ 
​ IO.write ​"​​\nThe Key is ​​#{​key​}​​\n"​

With your algorithm complete, you’re ready to run. First, go to lib/genetic.ex and edit the evolve/3 function to run generations without mutation by commenting out the mutation line, like this:

​ ​def​ evolve(population, problem, generation, opts \\ []) ​do​
​   population = evaluate(population, &problem.fitness_function/1, opts)
​   best = hd(population)
​   IO.write(​"​​\rCurrent best: ​​#{​best.fitness​}​​\tGeneration: ​​#{​generation​}​​"​)
​   ​if​ problem.terminate?(population, generation) ​do​
​     best
​   ​else​
​     {parents, leftover} = select(population, opts)
​     children = crossover(parents, opts)
​     children ++ leftover
»    ​# |> mutation(opts)​
​     |> evolve(problem, generation+1, opts)
​   ​end​
​ ​end​

Now, run your algorithm like this:

​ ​$​ mix run examples/codebreaker.exs
​ Current ​Best:​ 0.273

After awhile, you might get tired of your algorithm running and not making any progress. More than likely, your algorithm is suffering from premature convergence. Uncomment the mutation/1 function in run/2 and try running your algorithm again:

​ ​$​ mix run examples/codebreaker.exs
​ Current ​Best:​ 1.000
​ Key is 2491717835680677893

To see that this key is, in fact, the correct key, open up iex and use it to uncipher your encrypted string, like this:

​ ​$ ​​iex​
​ iex(1)> use Bitwise
​ Bitwise
​ iex(2)> key = 2491717835680677893
​ 2491717835680677893
​ iex(3)> cipher = fn word, key -> Enum.map(word, & rem(&1 ^^^ key, 32768)) end

​ ​#Function<13.126501267/2 in :erl_eval.expr/5>​
​ iex(4)> List.to_string(cipher.('LIjs`B`k`qlfDibjwlqmhv', key))
​ "ILoveGeneticAlgorithms"

Congratulations, you’ve cracked the code.

👈 Chapter 7 Preventing Premature Convergence | TOC | Understanding Mutation 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.