International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 09 May 2015

PhD Database PhD Database
Name: Liam Keliher
Topic: Linear Cryptanalysis of Substitution-Permutation Networks
Category: secret-key cryptography

Description: The subject of this thesis is linear cryptanalysis of substitution-permutation networks (SPNs). We focus on the rigorous form of linear cryptanalysis, which requires the concept of linear hulls.\r\n\r\nFirst, we consider SPNs in which the s-boxes are selected independently and uniformly from the set of all bijective n x n s-boxes. We derive an expression for the expected linear probability values of such an SPN, and give evidence that this expression converges to the corresponding value for the true random cipher. This adds quantitative support to the claim that the SPN structure is a good approximation to the true random cipher. We conjecture that this convergence holds for a large class of SPNs.\r\n\r\nIn addition, we derive a lower bound on the probability that an SPN with randomly selected s-boxes is practically secure against linear cryptanalysis after a given number of rounds. For common block sizes, experimental evidence indicates that this probability rapidly approaches 1 with an increasing number of rounds.\r\n\r\nWe then consider SPNs with fixed s-boxes. We present two new algorithms for upper bounding the maximum average linear hull probability for SPNs. These algorithms, named KMT1 and KMT2, are the first completely general algorithms for this purpose -- they can be applied to any SPN, and they compute an upper bound that is a function of the number of encryption rounds being evaluated. In contrast, other approaches to this problem either require that the SPN linear transformation have a specific structure, or compute a single value independent of the number of rounds. By applying KMT1 and KMT2 to the AES, we establish the provable security of the AES against linear cryptanalysis.\r\n\r\nAs a straightforward application of our work with linear hulls, we analyze the Q cipher, an SPN submitted to the European Commission\'s NESSIE cryptographic competition. By using linear characteristics, not linear hulls, the designer of Q evaluates the cipher to [...]
Expand

Additional news items may be found on the IACR news page.