Paper 2016/1177

Efficient Slide Attacks

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

Abstract

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}$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Slide AttacksCryptanalysisRecovering Unknown S-boxesGOST3K-DES
Contact author(s)
orrd @ cs haifa ac il
History
2016-12-30: received
Short URL
https://ia.cr/2016/1177
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1177,
      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{https://eprint.iacr.org/2016/1177}},
      url = {https://eprint.iacr.org/2016/1177}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.