Timing attack by Genetic algorithm
In this short text, we show how we used a genetic algorithm to emulate a timing attack. We do not aim at being serious with respect to potential real use cases; the presentation is mainly driven by the fun of designing genetic algorithm and exploring a less known, yet interesting vulnerability of systems.
(Prepare yourself for vanilla Java!)
Timing attack
Password verification is a common feature of a lot of systems. Every cryptographic concern apart, the very basic idea is to compare the equality of two strings. Below is an easy example:
Of course, in a real system, you would compare hashes or so, but let’s stay simple. What we would like to do is hack this object to find back the secret password.
The topology on String induced by our CredentialCheck object clusters the string landscape in the following fashion:
- Singleton string (except
S) are as bas asSECRET PASSWORbecause they all do not have the correct size Sis not worst thanSICRET PASSWORD, since they both fail after the first character checkSECRET HEJEOPOis about 6 times better thanSICRET PASSWORD
and so on… This holds true in the perspective of the CredentialCheck object, and gives a perfect example of a system vulnerable to timing attack. Thinking it would be fruitful to return as fast as possible, we do not provide a constant-time algorithm. According to the input test string, the system takes more or less operations to complete its task. This is an indirect information about the actual true password.
From the attacker perspective, we do not really have access to the operation count. The idea of timing attack is when an attacker manages to measure the elapsed time required to perform the check, and takes benefit from this meaurement to guess information about the password. Such a hack could be performed via a simple bridge:
First trial by brut-force
Using the elapsed time to measure is the basic idea behind the timing attack, but brings much more variance in measurements! The following brute-force test, where we averaged execution times on 1.000.000 trials, speaks for us:
The best candidate we obtained is AXBQCPTNOEHSTNND, which has nothing in common with out password. This algorithm is already about 1.000.000*26*16 (~2²⁹) time long. Brute forcing on every combination of 16-size strings with an average of 1000 would be 1000*26¹³, so a bit more than 2⁸⁵ operations.
The brut-force strategy is thus a major fail. Yet, our system is not safe…
Genetic algorithm
Our MeasuredCredentialCheck gives us a test function that measures the goodness of a String object: the lowest the score, the better the String; and the minimum is reached only for the secret password.
We think of String as biological objects with genetic DNA driven by a char array. In order to hack ourselves, we are going to implement an evolutionary (genetic) algorithm. The idea is to create a population of those biological strings, and emulate biological evolution on it.
The score that a bio-String obtains on the MeasuredCredentialCheck test gives its reproduction power. Reproduction of bio-String is called cross-over. After reproducing our strings, we will also mutate their DNA, to bring biodiversity in the population.
There are lots of different additional evolutionary operations that we could also perform: duplicate the best competitors, kill the worst competitors, create islands of population and realize migrations, and so on… The definition of cross-over and mutations themselves are quite free.
Whatever the choices we do, some basic principles should be kept in mind when designing genetic algorithms:
- Biological diversity is really important: it is not necessarily a good idea to mitigate the effect of mutations.
- Reproduction should be done with care: too much reproduction could slow down the learning proces by giving bad competitors too much efficiency in the evolutionary process.
- Particular attention should be given to population extinction. Keeping the population size constant is a good idea for a start.
By computing successive generations, we hope the global trend to converge to an optimal configuration, and hopefull hack the password!
Generic plan of our genetic algorithm
For our genetic algorithm design, we are going to keep things simple.
As you may see (I hope, because I put great love in making the code less verbose than average Java!), given a population of String assumed to be sorted by efficiency (the bests first), the next population is designed as
- the top previous candidates (according to some config percentage)
- mutated and cross-over individuals
- truncated to get the total population size.
The first condition ensures that the top candidates are found back in the resulting population. This is to boost a bit the process (we fan-tuned!). Cross-over and mutations do not happen every time: the NaturalSelection object operates them randomly. When it does do something, it does according to the following algebraic rules:
Again, I think having put enough love in the code to make it crystal clear: mutation takes a random number of chars in the string DNA and modify them randomly. Cross-over of (a,b) takes a first segment of a and uses it to replace the firsts elements of b accordingly. We have chosen this cross-over because we suspected (hem hem) that the CredentialCheck object is coded as it is (we stole the info from github, for example).
now that we know how natural selection works, we can design our evolution plan:
And again, I think what’s happening here should be clear: given an initial random population, we evaluate it (generation 0) and start the evolutionnary process: compute the next generation and stop if something perfect is found, or wait for the timeout.
The result
The result is quite interesting. The attack test goes as follows:
We started with a quite small population (2⁹ = 512) for every string size between 1 and 19, inclusive. The total population size is thus 9728 (~2¹³). The elapsed time for the attack is put for information only.
The cost of the genetic algorithm is roughly given by O(n log(n) * m) where n is the population size, and m the iteration count. Here we’re around 2²⁹ for 1.000, but we’ll see that the optimal is hit around 200. It goes without sayig that we did not optimized our design (for example, testing passwords of length less than 8 is not very useful).
Letting this algorithm run gives the following results:
As you see, the start is quite complicated and slow. In red, we spotted two generations where the best competitors (!) are very short strings. In green, we spotted two generations where the “SEC” prefix was already found in the best competitor.
We hit the optimal configuration at generation 190, after around 1.2 seconds (running the algorithm many times could give up to only ~100 generations!). In red, we spotted interesting noisy behavior of the Java Virtual Machine. As you may see, the best competitors for those generations is as bad as a singleton string!
We think this is due to the extreme stochastic nature of the measurements we have. It is still interesting to see that although those bad-but-still-best performers exist in the same proportion as the other ones, the general pattern is quickly recovered to something closed to SECRET PASSW.
We think that the genetic nature of the process, compared to a brut force, makes it such that the statically correct pattern is transmitted in the DNA even though some generations suffer bad luck.
As a matter of fact, there is the population after some more time, where we could note that the percentage of optimal competitors increases around 20%.
For informational purpose, here is another run with geometric informations, in terms of Levenshtein-distance:
Preventing timing attack
Okay, now that we hacked ourselves successfully, how could we protect? Well, usually it can be quite hard to protect a system against timing attack because both the compiler and the runtime could be using end-fast instructions. It could also come from arithmetic operations in the processor and related stuffs.
A first move could be to heavy the CredentialCheck object to make it finish in constant-instruction count:
Running our algorithm on this service won’t work:
Does that mean we’re safe? I don’t know. But maybe we’re safer than before!
Final words
Here is how I spent some time, having fun in emulating timing attack by a genetic algorithm approach. Although the setup is not perfect, I hope it triggers your curiosity about one topic or the other, and that you had fun reading the Java code.
Code is freely available on my github(/Judekeyser/genetictimingattack), if you wonder how things are designed.
Any constructive feedback is appreciated.
Cheers!
