Cryptology ePrint Archive: Report 2021/719

Conditional Differential-Neural Cryptanalysis

Zhenzhen Bao and Jian Guo and Meicheng Liu and Li Ma and Yi Tu

Abstract: Although it has been a long-standing question that whether computers can learn to perform cryptanalytic tasks, positive answers made by breakthrough machine-learning-based cryptanalysis are still rare. In CRYPTO 2019, a remarkable work made by Gohr shed light on a positive answer. It shows that well-trained neural networks can perform cryptanalytic distinguishing tasks at a superior level to traditional differential-based distinguishers. Additionally, a non-traditional key-recovery procedure was devised, integrating with the Upper Confidence Bounds and Bayesian optimization. Combining the neural distinguishers with a classical differential, integrating the advanced key-recovery procedure, an 11-round key-recovery attack on Speck32/64, a small-sized modern cipher designed by researchers from NSA, was achieved, which has a competitive performance compared with the state-of-the-art result. However, it turns out to be still difficult for the community to achieve a comparable performance increase on longer reduced-versions of the same cipher. This difficulty calls into a question: to what extent is the advantage of machine-learning approaches over traditional ones, and whether the advantage generally exists on modern ciphers? To answer these questions, we devised the first practical 13-round and improved 12-round neural-distinguisher-based key-recovery attacks on Speck32/64 and 16-round key-recovery attacks on Simon32/64. The results confirm the advantages of using machine-learning approaches in cryptanalysis. However, the main reason lies in the enhancement made on the classical components. The crucial technical element for the improved attacks is the concept of conditional (simultaneous) neutral bits/bit-sets, which is derived from the concept of neutral bit with a long history in cryptanalysis. This fact indicates an outcome: a strengthened combination between the classical cryptanalysis and machine learning approaches is one way for machine-learning-based cryptanalysis to maximize its advantage. Apart from best attacks, we exhibit substantial details of the key-recovery phase that is missing a theoretical model to analyze its complexity and success probability. Some observations on important statistics could serve as a rule of thumb on tuning parameters and making trade-offs. To answer whether the advantage of machine learning approaches shown in the cryptanalysis of Speck32/64 can also be obtained on other primitives, we produce various neural distinguishers and traditional DDT-based distinguisher on Simon32/64. The answer is slightly negative. The same approaches for Speck32/64 indeed apply to Simon32/64. However, the advantage over the pure differential-based approach seems to be limited.

Category / Keywords: secret-key cryptography / Neural Distinguisher, Key Recovery Attack, Differential Cryptanalysis, Simon, Speck, Generalized Neutral Bits, Bayesian Search

Date: received 30 May 2021, last revised 3 Oct 2021

Contact author: zzbao at ntu edu sg, guojian at ntu edu sg, meicheng liu at gmail com, skloismary at gmail com, tuyi0002 at e ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20211003:101900 (All versions of this report)

Short URL: ia.cr/2021/719


[ Cryptology ePrint archive ]