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)
- 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
-
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} }