Optimization methods in Cryptanalysis
This project is supported by the Danish Council for Independent Research, Technology and Production and carried out at DTU mathematics.
Project description
The aim of the project is to develop new techniques that can be applied to assess the security
of cryptographic algorithms. We want to use tools from combinatorial and integer optimization to
break symmetric encryption schemes by nding an optimal solution from a related optimization
problem. The two main parts of the project are the formulation of the optimization problem and
the application of an appropriate optimization method. In particular, we focus on the derivation
of Boolean equation systems from a cipher, the transformation of these systems into integer
programming problems and combinatorial optimization problems as well as the adaptation of
hill climbing algorithms by de ning an appropriate neighborhood function.
Theoretical foundation
Many cryptosystems can be described as systems of multivariate polynomial equations over the
binary field GF(2). The characteristic feature of those equations is their relative sparsity, each
equation contains only a few variables and a few terms. Additionally, each variable is only
contained in a limited number of equations. This implies that a change in a value of one variable
affects only a small number of equations, meaning that the variables have a high locality. We
will mainly consider lightweight encryption schemes such as stream ciphers and lightweight block
cipher. These encryption schemes usually generate equation systems which still have a reasonable
size, i.e a couple of thousand variables.
Integer optimization is a well studied eld and the development of solvers progresses very
fast. Furthermore, integer programming has already been employed to tackle difficult discrete
problems such as the well-known traveling salesman problem. The traveling salesman problem
shows the potential of integer optimization in solving difficult discrete problems as well as
the importance of finding a good formulation of the problem. For a good formulation the traveling
salesman problem is solvable for a couple of thousand cities while it is not solvable for even
very few cities using a di erent formulation.
Most neighborhood search algorithms used in combinatorial optimization are sensitive to
changes in the cost function. It is more likely that an algorithms will be successful in finding a
global minimum when the cost function does not have big jumps. When we consider systems
with a large variable locality, we expect that the objective function behaves rather 'smooth'.
Research directions
- Our approach is based on the hypothesis that we can describe cryptosystems as relatively small systems of sparse multivariate Boolean
equations where finding a solution corresponds to breaking the security of the system.
-
The we can either transform such an equation system into a combinatorial optimization problem and
apply neighborhood search methods with a specially tailored neighborhood function in
order to efficiently find a global minimum. Here the main difficulty seems to be the formulation of a suitable cost function.
-
Another approach is to apply suitable conversion methods in order to transform the problem of solving the
equation system into a mixed-integer programming problem and use commercial solvers to
find a solution.
- Metaheuristics are also suitable for areas of cryptanalysis where optimization actually is the purpose such as
- finding near collision for hash function
- finding low weight differential paths
- exploiting noise information
Publications
-
Mohamed Ahmed Abdelraheem,Julia Borghoff, Erik Zenner, Mathieu David.
Cryptanalysis of the Light-Weight Cipher A2U2.
Proceedings of IMACC 2011.