Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

A particular educational software program published by a U.S. government agency uses a variant of RC4 to obfuscate its data files (see Stack Overflow question). The variant of RC4 in question is identical to standard RC4 except at the beginning of the pseudo-random generation algorithm. The developer omitted the first two lines below (from Wikipedia's description) because he based his code on an erroneous implementation from Planet Source Code from around 2005.

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

Thus, i and j retain their final values from when the key scheduling algorithm ran (i = 256, not 0, and j = (j + S[i] + key[i mod keylength]) mod 256 from when i = 255 during the KSA).

In this case, the encryption provides no actual security because the key is hardcoded into the software, but suppose the developer had used the code to encrypt a secret file on his hard drive. Does this implementation error significantly weaken RC4's strength?

share|improve this question
add comment

1 Answer 1

up vote 7 down vote accepted

Yes, that omission weakens the cipher: the output $\mathtt K$ has a short cycle (at most 65280 bytes) for a sizable class of keys (one in 65536).

Not initializing $\mathtt i$ makes no difference in the values of $\mathtt i$ effectively used for the rest of the algorithm, since $0\equiv 256 \pmod{256}$; and hence has no security implication whatsoever.

But not initializing $\mathtt j$ has an effect. In particular, if at the end of key scheduling $\mathtt j=1$ and $\mathtt S[1]=1$, then (by induction) during the whole of the stream generation we have $\mathtt j=(\mathtt i+1)\bmod 256$ and $\mathtt S[\mathtt j]=1$, and the output generated has a short cycle of (at most) $256\cdot 255$ bytes, which never occurs in real RC4, but occurs for $2^{-16}$ of the keys in the modified cipher. It would be easy to experimentally check that.

This was noted in 1994 by Hal Finney, in An RC4 cycle that can't happen, summarized on the RC4 page.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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