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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisReflection attackSlide with a twistFixed pointsRandom InvolutionsFeistel structuresEven-Mansour schemeDESXGOST
Contact author(s)
orrd @ cs haifa ac il
History
2015-05-22: revised
2014-10-22: received
See all versions
Short URL
https://ia.cr/2014/847
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/847,
      author = {Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir},
      title = {Reflections on Slide with a Twist Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2014/847},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/847}},
      url = {https://eprint.iacr.org/2014/847}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.