Mourouzis, T; (2015) Optimizations in Algebraic and Differential Cryptanalysis. Doctoral thesis , UCL (University College London).

PDF PhD_Thesis_Theodosis_Mourouzis.pdf Available under License : See the attached licence file. Download (3MB)

Abstract

In this thesis, we study how to enhance current cryptanalytic techniques, especially in Differential Cryptanalysis (DC) and to some degree in Algebraic Cryptanalysis (AC), by considering and solving some underlying optimization problems based on the general structure of the algorithm. In the first part, we study techniques for optimizing arbitrary algebraic computations in the general non-commutative setting with respect to several metrics [42, 44]. We apply our techniques to combinatorial circuit optimization and Matrix Multiplication (MM) problems [30, 44]. Obtaining exact bounds for such problems is very challenging. We have developed a 2- step technique, where firstly we algebraically encode the problem and then we solve the corresponding CNF-SAT problem using a SAT solver. We apply this methodology to optimize small circuits such as S-boxes with respect to a given metric and to discover new bilinear algorithms for multiplying sufficiently small matrices. We have obtained the best bit-slice implementation of PRESENT S-box currently known [6]. Furthermore, this technique allows us to compute the Multiplicative Complexity (MC) of whole ciphers [23], a very important measure of the non-linearity of a cipher [20, 44]. Another major theme in this thesis is the study of advanced differential attacks on block ciphers. We suggest a general framework, which enhances current differential cryptanalytic techniques and we apply it to evaluate the security of GOST block cipher [63, 102, 107]. We introduce a new type of differential sets based on the connections be- tween the S-boxes, named “general open sets” [50, 51], which can be seen as a refinement of Knudsen’s truncated differentials [84]. Using this notion, we construct 20-round statistical distinguishers and then based on this construction we develop attacks against full 32-rounds. Our attacks are in the form of Depth-First key search with many technical steps subject to optimization. We validate and analyze in detail each of these steps in an attempt to provide a solid formulation for our advanced differential attacks.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item