Paper 2016/1177

Efficient Slide Attacks

Achiya Bar-On, Eli Biham, Orr Dunkelman, and Nathan Keller


The slide attack, presented in 1999 by Biryukov and Wagner, has already become a classical tool in cryptanalysis of block ciphers. While it was used to mount practical attacks on a few cryptosystems, its practical applicability is limited, as typically, its time complexity is lower bounded by $2^n$ (where $n$ is the block size). There are only a few known scenarios in which the slide attack performs better than the $2^n$ bound. In this paper we concentrate on {\it efficient} slide attacks, whose time complexity is less than $2^n$. We present a number of new attacks that apply in scenarios in which previously known slide attacks are either inapplicable, or require at least $2^n$ operations. In particular, we present the first known slide attack on a Feistel construction with a {\it 3-round} self-similarity, and an attack with practical time complexity of $2^{40}$ on a 128-bit key variant of the GOST block cipher with {\it unknown} S-boxes. The best previously known attack on the same variant, with {\it known} S-boxes (by Courtois, 2014), has time complexity of $2^{91}$.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Slide AttacksCryptanalysisRecovering Unknown S-boxesGOST3K-DES
Contact author(s)
orrd @ cs haifa ac il
2016-12-30: received
Short URL
Creative Commons Attribution


      author = {Achiya Bar-On and Eli Biham and Orr Dunkelman and Nathan Keller},
      title = {Efficient Slide Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1177},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.