Neural Aided Statistical Attack for Cryptanalysis

Yi Chen; Yantian Shen; Hongbo Yu; Sitong Yuan

Paper 2020/1620

Neural Aided Statistical Attack for Cryptanalysis

Yi Chen, Yantian Shen, Hongbo Yu, and Sitong Yuan

Abstract

In Crypto’19, Gohr proposed the first deep learning-based key recovery attack on 11-round Speck32/64, which opens the direction of neural aided cryptanalysis. Until now, neural aided cryptanalysis still faces two problems: (1) the attack complexity estimations rely purely on practical experiments. There is no theoretical framework for estimating theoretical complexity. (2) it does not work when there are not enough neutral bits that exist in the prepended differential. To the best of our knowledge, we are the first to solve these two problems. In this paper, we propose a Neural Aided Statistical Attack (NASA) that has the following advantages: (1) NASA supports estimating the theoretical complexity. (2) NASA does not rely on any special properties including neutral bits. (3) NASA is applicable to large-size ciphers. Moreover, we propose three methods for reducing the attack complexity of NASA. One of the methods is based on a newly proposed concept named Informative Bit that reveals an important phenomenon. Four attacks on 9-round or 10-round Speck32/64 are executed to verify the correctness of NASA. To further highlight the advantages of NASA, we have performed a series of experiments. At first, we apply NASA and Gohr’s attack to round reduced DES. Since NASA does not rely on neutral bits, NASA breaks 10-round DES while Gohr’s attack breaks 8-round DES. Then, we compare the time consumption of attacks on 11-round Speck32/64. When the newly proposed three methods are used, the time consumption of NASA is almost the same as that of Gohr’s attack. Besides, NASA is applied to 13-round Speck32/64. At last, we introduce how to analyze the resistance of large-size ciphers with respect to NASA, and apply NASA to 14-round Speck96/96. The code of this paper is available at https://github.com/AI-Lab-Y/NASA. Our work arguably raises a new direction for neural aided cryptanalysis.

Note: The code is available now

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Contact author(s): chenyi19 @ mails tsinghua edu cn
History: 2021-10-05: last of 11 revisions; 2020-12-31: received; See all versions
Short URL: https://ia.cr/2020/1620
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1620,
      author = {Yi Chen and Yantian Shen and Hongbo Yu and Sitong Yuan},
      title = {Neural Aided Statistical Attack for Cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1620},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1620}
}