On Sun, 25 Jul 1999, John Kelsey wrote:
> Has anyone looked at this from a cryptanalytic point of
> view? I think there are chosen-input attacks available if
> you do this in the straightforward way. That is, if I get
> control over some of your inputs, I may be able to alternate
> looking at your outputs and sending in new inputs, and mount
> an attack that isn't possible at all against RC4 as it's
> normally used. (This comes out of conversations with Jon
> Callas, Dave Wagner, and Niels Ferguson, from a time when I
> considered designing a Yarrow-variant using RC4 as the
> underlying engine.)
Even aside from active attacks, there is a possible problem based on
the fact that RC4 can "almost" fall into a repeated-state situation.
RC4's basic iteration looks like:
(1) i += 1;
(2) j += s[i];
(3) swap (s[i], s[j]);
(4) output s[s[i] + s[j]];
(everything is mod 256)
The danger is that if it ever gets into the state j = i+1, s[j] = 1,
then it will stay that way. It will increment i, then add s[i] to j,
which will also increment j. Then which it swaps s[i] and s[j] it will
make s[j] be 1 again.
However in normal use this never happens, because this condition
propagates backwards as well as forwards; if we ever are in this state,
we always were in this state. And since we don't start that way, we
never get that way.
Adding input entropy could break these rules. If we fold in entropy
following the pattern of RC4 seeding, we alter line 2:
(2) j += s[i] + input();
Now it is no longer true that we can't fall into (or out of) this state.
If we had a non-zero input() value and then a bunch of zeros, we could
get into the repeated state and stay there.
It may not be that easy to recognize the repeated state, but it certainly
makes the RNG seem less robust. The effect is that the "1" value keeps
bubbling through the s array, with every other value moving up one step
as the "1" value moves past it. The s array ends up rotating very slowly,
not being mixed at all. This is completely unlike normal RC4.
It is really not safe to mess with RC4's iteration rules like this. The
cipher is rather brittle in this regard.
