Linear and differential cryptanalysis seem well suited for constructs with a (re

Question

Linear and differential cryptanalysis seem well suited for constructs with a (relatively) simple fixed structure of boolean expressions. But some ciphers incorporate swaps of array elements where the indices to be swapped are dependent on dynamic cipher state and others may include rotations by a variable number of bits. In the case of RC4, the entire cipher state is embodied in the permutation of a fixed set of integers.

This would seem to induce a combinatorial explosion in the number of expressions needed to track bias through the system. Is that a good thing?

Side-channel challenges aside, are such constructs unambiguously stronger than those made from fixed structures, or are they just harder to analyze?

What math is used to attack/analyze them?

Explanation / Answer

As far as RC4 is concerned, actually, it's not true that standard cryptanalysis methods are useless; linear cryptanalysis has been used to attack RC4. Jovan Golic' used linear cryptanalysis to show there's a bias in the lsbits that can be used to distinguish the output after (IIRC) 2**44 bytes or so.

However, typically other methods are used against RC4. Here are the methods that have been tried:

+ Look at the initial bytes of the output, and deduce something from that. These methods exploit the fact that the RC4 key setup leave strong biases in the permutation (and that these biases are correlated with the original keys). The analysis used here tends to be probabilistic (for example, "if permutation element 1 is value N at step 7 of the key setup, it's likely to be value N at the end of the key setup").

+ Notice that, while the RC4 cipherstate is impressively large, only a small part of the state is actually sampled to produce a byte of output. With this, we can assume a "random state", and step the simulated cipher a few steps; whenever the cipher samples a permutation element it hasn't used before, assume all possible values for it. This combinatorial approach was used to determine the relative probabilities of pairs of outputs; this can be used to distinguish the output from random with about 2**30 outputs.

+ Notice that the the internal RC4 state biases the RC4 output. For example, on occasion, N consecutive outputs are generated using only N permutation elements (and i and j); when you see that particular output sequence (at the correct i offset), then with probability about 1/256, that was due to that scenario (and hence you have a nontrivial guess at a portion of j and some of the permutation state). Alas, this happens fairly infrequently; the RC4 state update churns things well enough that we can't (or, at least, don't know how to) use several of them to derive even more RC4 state.

On the other hand, the techniques used against RC4 generally aren't (at least, in my experience) of much use for other ciphers.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.