At 12:19 AM -0700 7/27/99, James A. Donald wrote:
> --
>At 08:44 PM 7/26/99 +0200, Anonymous wrote:
>> 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.
>
>Why don't we start that way?
>
>The initialization rule is for i = 0 to 255
> j = j+ s[i] + input(i)
> swap s[i], s[j]
>next i;
>
>To go bad at the end of initialization it has to wind up in the
>state j=1 (which can always be forced true by some suitable input, and
>s[1] =1;
>
>What stops it from ending up with s[1]=1?
>
Nothing, but after RC4 key setup, i and j are reinitialized to zero. That
breaks up the conditions for the repeated state. I must confess that until
yesterday I never understood why these indicies were reinitialized before
cipher generation. Now I know. What I said yesterday about the sequential
incrementing of i preventing repeated states is clearly wrong. (Anonymous'
posting arrived on the same mail check that posted my messages. Sigh.)
I am still not ready to give up on switching between extracting and
depositing entropy in RC4. I think there will be a need for a secure,
lightweight and fast nonce generator and RC4 could provide that.
One fix is to do what RC4 does and always reinitialize i and j after
running in deposit mode. An attacker who could choose the entropy to
deposit and some how figured out the right values to use could put you into
the repeated state during that entropy deposit. But this would do no harm
and you would exit the repeated state after the deposit. The situation is
equivalent to an attack on vanilla RC4 where the attacker can force you to
choose the last part of your key.
It would also be wise to always extract some cypher bytes between entropy
deposits so an attacker who got you to make two deposits in a row would not
know the value of j at the start of the second deposit.
One other thought I had is to save the previous cipher byte and add it to
the entropy byte in each cycle. I don't think this step is needed, but it
does force an attacker to break RC4 itself in order to mount a chosen
entropy attack. That might give people more confidence in this approach to
nonce generation.
Arnold Reinhold
