13
$\begingroup$

I am confused about how long a stream cipher can be used before you should change the key. To be concrete, let me use the stream cipher based on RC4 as an example.

Let's say I want to encrypt a very long message. I pick a key with 128 bits and start encrypting using the RC4 stream cipher. How many rounds does RC4 have to run before its PRG starts over again? How about Salsa20: how long can that run with the same key before running the risk of leaking information?

I realize that as a practical matter the period will probably be far longer than any real-world message, but I am still interested in knowing the bound.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
13
$\begingroup$

The internal state of RC4 consists of a shuffled 256-element array and two pointers into that array. Thus, there are a total of $$256! \times 256^2 \approx 2^{1700.00}$$ possible states. Since the state update function of RC4 is reversible, it acts as a permutation on this set of possible states, so that every starting state will eventually recur after sufficiently many iterations.

How many is sufficiently many? Well, if we assume that the update function behaves like a random permutation (which it, of course, does not, but it's a good first approximation), then the expected cycle length is approximately $2^{1700}/2 = 2^{1699}$ iterations(!). Indeed, the probability that the cycle length starting from a random state is at least $k$ iterations is approximately $1 - k/2^{1700}$; this means that hitting a cycle of less than, say, $2^{200}$ iterations should happen less than once in $2^{1700-200} = 2^{1500}$ initializations, i.e. basically never within the lifetime of the universe.

Of course, as noted, the RC4 state update function is not a random permutation. For example, there's a known class of $254!$ short cycles of $256^2-256 = 65280$ states each; fortunately, the standard RC4 key setup is guaranteed never to hit them. For more information on the actual cycle structure of RC4, see e.g. "Cryptanalysis of RC4-like Ciphers" by S. Mister and S. E. Tavares.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If think not 254! but 255! short cycles and 256*255! = 256! states values inside this short cycles. Always, if j = i + 1 (modulo N=256) and S[i+1] = 1. this properties are conserved, since i is increased by one and j as well because S[i], after increasing i, is one too and finally S[j=i+1] is set to one by swaping S[i] and S[j]. The position of the one in S is alway moving by one, after N = 256 steps, it is again at the same position. The other N-1 S-values move cylic by one after N steps. After N*(N-1) steps the cycle is complete. $\endgroup$
    – user36865
    Jul 15, 2016 at 8:47
11
$\begingroup$

By definition of Salsa20 used as a stream cipher, it uses a 64-bit block counter and 64-bytes blocks, limiting its capacity to $2^{73}$ bits. After that, the counter would rollover, and thus the output. In a sense, this is the period.

RC4 has no such explicit limit on the size of its output. We do not know how to exactly compute the period size, which very likely depends on the key. Since the RC4 state can take at most $2^{16}\cdot 256!$ values, and RC4 outputs $8$ bits at each step, its period must be less than $2^{1703}$ bits. I do not know if this upper bound can be improved, but I'd be surprised if the exponent could be lowered by more than 25. The expected period for an iterated random permutation of $n$ elements is $(n+1)/2$, therefore I'd be surprised if the average RC4 period was lower than $2^{1676}$ bits. However, there could be much shorter period for some keys, and given the overly simplistic key scheduling of RC4 it might even be possible to exhibit such a key.

Improve this answer
$\endgroup$
2
  • $\begingroup$ fgrieu, With the pseudo code for the PRNG component of RC4 comprising only 4 lines, do you think that there is a danger of cellular automata /emergent behaviour? This would seem like the ideal environment for such to thrive and thus truncate the period. Perhaps with certain keys? $\endgroup$
    – Paul Uszak
    Sep 5, 2015 at 13:53
  • $\begingroup$ @Paul Uszak:because the RC4 transformation is a bijection, contrary to most interesting cellular automatons, I do not think that Wolfram's a new kind of science considerations can apply to it. At least I'm not afraid of an RC4 state becoming self-aware :-) and I see no clear reason that its simplicity necessarily leads to much short periods than expected for an iterated random mapping. But, as pointed in the answer, I'm however ready to believe that a key can be exhibited that leads to short period. $\endgroup$
    – fgrieu ♦
    Sep 6, 2015 at 18:42
3
$\begingroup$

The RC4 period depends on the exact key (PDF) that was used, but should in general be very long. It is expected to be at least 10^100.

See the first link, page 4, for a more detailed description of the relationship between the key and the period.

Improve this answer
$\endgroup$

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