Cryptology ePrint Archive: Report 2014/847
Reflections on Slide with a Twist Attacks
Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir
Abstract: Slide attacks use pairs of encryption operations which are slid against each other. Slide with a twist attacks are more sophisticated variants of slide attacks which slide an encryption operation against a decryption operation. Designed by Biryukov and Wagner in 2000, these attacks were used against several cryptosystems, including DESX, the Even-Mansour construction, and Feistel structures with four-round self-similarity. They were further extended in 2012 to the mirror slidex framework, which was used to attack the 20-round GOST block cipher and several additional variants of the Even-Mansour construction. In this paper, we revisit all the previously published applications of these techniques and show that in almost all cases, the same or better results can be achieved by a simpler attack which is based on the seemingly unrelated idea of exploiting internal fixed points. The observation that such fixed points can be useful in cryptanalysis of block ciphers is known for decades and is the basis of the reflection attack presented by Kara in 2007. However, all the examples to which reflection attacks were applied were based on particular constructions such as Feistel structures or GOST key schedules in which it was easy to explicitly list and count the fixed points.
In this paper, we generalize Kara’s reflection attack by using the combinatorial result that random involutions on 2^n values are expected to have a surprisingly large number of O(2^n/2) fixed points (whereas random permutations are expected to have only O(1) fixed points). This makes it possible to reduce the complexity of the best known attack on additional cryptographic schemes in which it is difficult to explicitly characterize and count the internal fixed points.
Category / Keywords: secret-key cryptography / Cryptanalysis, Reflection attack, Slide with a twist, Fixed points, Random Involutions, Feistel structures, Even-Mansour scheme, DESX, GOST
Date: received 16 Oct 2014, last revised 22 May 2015
Contact author: orrd at cs haifa ac il
Available format(s): PDF | BibTeX Citation
Version: 20150522:142106 (All versions of this report)
Short URL: ia.cr/2014/847
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]