5
$\begingroup$

An excerpt from the wikipedia article on slide attacks states:

...The only requirements for a slide attack to work on a cipher is that it can be broken down into multiple rounds of an identical F function. This probably means that it has a cyclic key schedule. The F function must be vulnerable to a known-plaintext attack...

and:

...Once a slid pair is identified, the cipher is broken because of the vulnerability to known-plaintext attacks. The key can easily be extracted from this pairing....

The statements:

The next step is to collect 2^{n/2} plaintext-ciphertext pairs. Depending on the characteristics of the cipher fewer may suffice, but by the birthday paradox no more than 2^{n/2} should be needed.

lead me to think that even a truly random oracle would produce slid pairs, so it would appear that eliminating the existence of slid pairs is not a possibility.

My question is relatively simple. Suppose the round function of a cipher was resistant to known plaintext attack (i.e. known plaintext does not facilitate recovery of key information). Could such a cipher claim provable resistance to slide attacks? If not, what advantage would a slid pair offer an attacker?

$\endgroup$
4
$\begingroup$

Wikipedia is correct: any cipher that consists of a repeated number $n$ of iterations of the same function $F$ is vulnerable to the slide attack. Once you find a slid pair, the security of the cipher degrades to the security of $F$.

Generally speaking, 1 application of $F$ is not enough to withstand standard attack methods (e.g., differential, linear, etc). When you have a slid pair $(x, F^n(x)), (F(x), F^{n+1}(x))$ you can, for example, attack $x$ and $F(x)$ directly, thus recovering the key. What you can do precisely with a slide attack is specific to the cipher in question, however.

Note that if $F$ itself is ideal, then the slide attack is not effective. But in that case iterating $F$ is pointless, since you can use $F$ directly at $n$ times the speed!

There are two simple ways to prevent slide attacks:

  • Make your block size large enough. If your cipher has a 256-bit block, it will take (in the optimal case) $2^{128}$ plaintext-ciphertext pairs to get a slid pair, in which case it doesn't really matter whether slide attacks apply or not.

  • Make each round different. This doesn't need to be a large modification; for example, the Keccak permutation simply xors a different constant (the $\iota$ function) into the state at the end of each round, and this suffices to eliminate slide attacks.

$\endgroup$
  • $\begingroup$ This is a useful and helpful information, but it doesn't address whether the specific approach I inquired about in my question is equally valid. As such, I cannot hit the "accept as answer" button. $\endgroup$ – Ella Rose Mar 29 '16 at 20:00
  • $\begingroup$ I suppose I did misunderstand your question. I just added a couple of paragraphs addressing (I hope) the question. $\endgroup$ – Samuel Neves Mar 29 '16 at 20:56
  • $\begingroup$ Thank you! I suspected that "What you can do precisely with a slide attack is specific to the cipher in question, however", but was hoping for confirmation from someone that was more certain. $\endgroup$ – Ella Rose Mar 29 '16 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.