Cryptology ePrint Archive: Report 2016/1177

Efficient Slide Attacks

Achiya Bar-On and Eli Biham and 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}$.

Category / Keywords: secret-key cryptography / Slide Attacks, Cryptanalysis, Recovering Unknown S-boxes, GOST, 3K-DES

Date: received 23 Dec 2016

Contact author: orrd at cs haifa ac il

Available format(s): PDF | BibTeX Citation

Version: 20161230:194338 (All versions of this report)

Short URL: ia.cr/2016/1177