Large-scale high-resolution computational validation of novel complexity models in linear cryptanalysis

摘要

Linear cryptanalysis is one of the few major attack techniques in today's cryptography. Every new cipher comes with strong arguments against it. Still, some recent relevant ciphers such as the ISO/IEC lightweight block cipher present proved to be particularly vulnerable to linear cryptanalysis. Since most attacks published today - including the linear cryptanalysis - have complexities beyond practical reach, the evaluation of their complexities has to rely on rather theoretical computational models. The latter are often based on unproven and not always precise assumptions that might result in inexact models. Very recently, in FSE'13, it has been demonstrated that the standard models the cryptanalysts have been relying on for a long time in linear attacks, while being quite adequate for a wide range of parameters, tend to fail when the attack to be evaluated tries to recover a high number of bits in the secret key of the cipher. However, this is actually the top-priority goal of any adversary. To amend the standard models that proved somewhat inaccurate in this crucial parameter range, a new model has been proposed based on an enhanced wrong key randomization hypothesis. However, this model has been verified only for quite small ciphers of 20-bit block size. At the same time, in the real-world applications, the block size of a cipher is usually 32 bits and higher. Thus, the experimental verification of the model remains quite limited. In this article, we aim to bridge this gap and study this novel model for much bigger ciphers. We are able to perform its computational validation for cipher with up to 36 bits with meaningful resolution. Our work confirms that the new model of FSE'13 is significantly more accurate for a wide range of cipher parameters.