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 2n (where n is the block size). There are only a few known scenarios in which the slide attack performs better than the bound. In this paper we concentrate on {\it efficient} slide attacks, whose time complexity is less than . We present a number of new attacks that apply in scenarios in which previously known slide attacks are either inapplicable, or require at least 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 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 .

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