Paper 2014/847

Reflections on Slide with a Twist Attacks

Itai Dinur, Orr Dunkelman, 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.