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

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). The following details why.

Because earlier code leaves $\mathtt i=256$ and the first execution of i := (i + 1) mod 256 makes that equivalent to $\mathtt i=0$, not initializing $\mathtt i$ makes no difference in subsequent code; and hence has no security implication whatsoever.

But earlier code leaves $\mathtt j$ to a key-dependent value, thus the lack of initialization of $\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$; thus the output generated has a short cycle of (at most) $256\cdot 255$ bytes. This never occurs in real RC4 (as observed in 1994 by Hal Finney, in An RC4 cycle that can't happen, summarized on the RC4 page), but occurs for $2^{-16}$ of the keys in the modified cipher.

share|improve this answer

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.