Could a strong round function be immune to slide attacks

Question

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?

Answer 1

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.