7
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
8
$\begingroup$

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 $\frac1{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.

Improve this answer
$\endgroup$
9
$\begingroup$

Algorithms which swap bytes in an array are notoriously hard to analyze; the two main examples are RC4 (encryption) and MD2 (hashing). Being "hard to analyze" does not mean that they are strong; only that we do not have a generic framework such as differential cryptanalysis to apply to them. Both RC4 and MD2 are, academically speaking, "broken" (there are known attacks which are at least theoretically faster than what would be expected from the key/output length). Cryptanalysis is "ad hoc". For instance, in the case of RC4, the main result is due to Mantin and Shamir: they show that the probability of the second output byte of a RC4 stream to be 0 is about twice what it should be (1/128 instead of 1/256). The mathematics are elementary: they simply follow the algorithm description.

Being hard to analyze is not a good thing. It may slow down an attacker, but it also prevents algorithm designers from working efficiently. Simple, regular structures are preferred: we do not want algorithms that are just difficult to break; we want algorithms that we know are difficult to break.

Also, a RAM-based structure with a mutable array implies heavy implementation costs on very small architectures (smartcards, where RAM is the scarcest resource) and on dedicated circuits (FPGA, ASIC). On a PC, RAM access is relatively fast, but still not as fast as one could hope for. MD2 is known to be very slow and RC4 is outperformed by more recent stream ciphers. Hardness of analysis and performance issues make mutable arrays unpopular in recent algorithm designs.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.