Automatic design of Feistel ciphers using constraint techniques.

摘要

In symmetric key cryptographic algorithms that operate on the Feistel principle, Cryptographic substitution boxes (S-boxes) are employed to introduce confusion into the message being encrypted. These S-boxes constitute the non-linear part in most cryptographic algorithms, and their design has been the focus of attention among researchers for several years. The concerns yield major design requirements. In particular, they should be highly nonlinear. Current work in S-box design to satisfy security requirements employ approaches such as human-made, math-made, generate-and-test, spectral inversion and local search. Recent approaches employ neural networks and distributed methodologies.This work addresses the application of constraint-based search techniques to find cryptographic substitution boxes (S-boxes). In this approach, variables are defined, the domain of each variable is specified, and common security requirements for an S-box are modeled into constraints involving relevant variables. The model is input to a solver that outputs the S-boxes.We have made a number of contributions. First, the quality of obtained S-boxes is superior to the ones currently published by the Data Encryption Standard (DES) as part of its specification based on Matsui's security metric. Second, due to the enormity of the problem, several heuristics are investigated for n-ary Constraint Satisfaction Problem (CSP) solvers to speed up S-box search and generation. We apply the properties of CSPs to reduce the search space to obtain solutions both, efficiently and having higher quality according to Matsui's measure for non-linearity. We derive new results on Linear Approximation Tables for an S-box, and on the condition of a partially assigned S-box to form a complete S-box. A method of visiting S-box variables that will efficiently generate S-boxes is identified. A form of value-ordering to propel this efficiency further has been discovered. The properties of constraints are used to discover new forms of symmetry of S-boxes. Finally, a novel metric for search efficiency of systematic searches such as this application has been quantified.