Paper 2019/509

New Slide Attacks on Almost Self-Similar Ciphers

Orr Dunkelman, Nathan Keller, Noam Lasry, and Adi Shamir

Abstract

The slide attack is a powerful cryptanalytic tool which has the unusual property that it can break iterated block ciphers with a complexity that does not depend on their number of rounds. However, it requires complete self similarity in the sense that all the rounds must be identical. While this can be the case in Feistel structures, this rarely happens in SP networks since the last round must end with an additional post-whitening subkey. In addition, in many SP networks the final round has additional asymmetries -- for example, in AES the last round omits the MixColumns operation. Such asymmetry in the last round can make it difficult to utilize most of the advanced tools which were developed for slide attacks, such as deriving from one slid pair additional slid pairs by repeatedly re-encrypting their ciphertexts. In this paper we overcome this "last round problem" by developing four new types of slide attacks. We demonstrate their power by applying them to many types of AES-like structures (with and without linear mixing in the last round, with known or secret S-boxes, with 1,2 and 3 periodicity in their subkeys, etc). In most of these cases, the time complexity of our attack is close to $2^{n/2}$, which is the smallest possible complexity for slide attacks. Our new slide attacks have several unique properties: The first attack uses slid sets in which each plaintext from the first set forms a slid pair with some plaintext from the second set, but without knowing the exact correspondence. The second attack makes it possible to create from several slid pairs an exponential number of new slid pairs which form a hypercube spanned by the given pairs. The third attack has the unusual property that it is always successful, and the fourth attack can use known messages instead of chosen messages, with only slightly higher time complexity.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Slide attack1-KSA1K-AESSlid setsHypercuber of slid pairssuggestive structuresSubstitution slide
Contact author(s)
orrd @ cs haifa ac il
History
2019-10-04: revised
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/509
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/509,
      author = {Orr Dunkelman and Nathan Keller and Noam Lasry and Adi Shamir},
      title = {New Slide Attacks on Almost Self-Similar Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2019/509},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/509}},
      url = {https://eprint.iacr.org/2019/509}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.