Applications of Evolutionary Computation to Cryptology

Stjepan Picek

promotor: prof.dr. B.P.F. Jacobs (RU)
co-promotors: dr. L. Batina (RU), dr. D. Jakobovic (University of Zagreb) and dr. E. Marchiori (RU)
Radboud Universiteit Nijmegen
Date: 6 July, 2015, 12:30
Thesis: PDF

Summary

This thesis encompasses several applications of evolutionary computation methods to the cryptology area where those applications are quite diverse. The goal of such an approach is to show that evolutionary computation can (and should) be considered as a viable choice when addressing certain difficult problems in cryptology. Colloquially said, genetic algorithms are not only genetic, but also generic. Naturally, this sentence is true for various evolutionary algorithms not only genetic algorithms. Key words for this thesis are simplicity, speed and generic approach.

First, we give a short outline of all the topics considered as well as a disclaimer about the approach we follow and the list of contributions.

Next, an overview of relevant topics from cryptology and evolutionary computation is given, followed by a short survey of related work. We present multiple examples to support our claim that evolutionary computation (EC) can be applied to diverse areas.

Chapter GET the Program presents a framework capable of evaluation, generation and transformation of Boolean functions and S-boxes. This framework serves not only as a standalone tool, but also as a fundamental part of the experimental setup when evolving Boolean functions and S-boxes. We present each of the framework’s modules independently wherever we briefly discuss its capabilities. We also give short examples on the use of the framework.

In Chapter Cryptographic Boolean Functions: One Output, Many Design Criteria, we discuss the evolution of Boolean functions. We concentrate on several objectives as well as on a set of algorithms in an effort to give a statistically sound comparison of different EC methods. This chapter is somewhat different from the other ones since we are not interested only in the results, but also in the comparison of the effectiveness of presented methods. Naturally, since there is a plethora of parameters one can set for each of the problems, this chapter is not intended as an extensive analysis (although we conduct more than 10,000 experimental runs for each objective), but as a field guide.

In Chapter S-boxes: Phantom Menace, we discuss the evolution of S-boxes that have a better DPA resistivity. From an evolutionary standpoint, this topic represents a natural extension of the evolution of Boolean functions, but from the implementation perspective it is completely independent. Furthermore, the complexity of an S-box evolution is much higher than in the Boolean function case. The end goal in this chapter is to find S-boxes that have better resistance against side-channel attacks.

Chapter Need for Speed: Pipelining Combinatorial Circuits presents an application of evolutionary algorithms with the goal of increasing the throughput of combinatorial circuits. Although we demonstrate this novel approach for cryptographic application, it is valid in a general circuit design where the goal is the increase of the circuit’s throughput. We evolve an AES S-box tower field implementation where we succeed in obtaining a 50% higher throughput.

In Chapter A Search for the Fault, a new method for finding search space parameters that cause faults in smart cards is presented where we explain the design and implementation of a custom-made genetic algorithm. Here we guide an interested reader from the standard implementation of genetic algorithm, through the customization process, to obtain, finally, a memetic algorithm that combines the strengths of three different search methods. The final algorithm is capable of finding faults, but also of rapidly characterizing the search space.

Lastly, we give a short conclusion where we offer some guidelines for future work as well as some lessons learned from this research. We also give instructions about the framework we use as well as several examples of evolved nonlinear elements in Appendices A and B.