How should k2 be produced in the RC4A stream cipher (A modification of RC4)?

Question

RC4A is a slight modification of the simple RC4 stream cipher designed to strengthen it against a number of attacks. Here's that paper.

However in the paper, the second key k2 is only mentioned twice and provides only a loose description of what it should be:

We take one randomly chosen key k1. Another key k2 is also generated from a pseudorandom bit generator (e.g. RC4) using k1 as the seed. Applying the Key Scheduling Algorithm, as described in Fig. 1, we construct two S-boxes S1 and S2 using the keys k1 and k2 respectively.

The main thing here is that k2 is "generated from a pseudorandom bit generator (e.g. RC4) using k1 as the seed", and S1 and S2 are constructed "using the keys k1 and k2 respectively".

In source code implementations of RC4A I have come across two different ways of handling S2, none of which use a PRBG to produce k2. This results in different output for the same input:

1. S-boxes S1 and S2 are exactly the same (using k1 for both).
2. All 256 values of S-box S1 constitute the key k2 for S2.

In a cryptography course, it is suggested to use a "nonce" for k2, which has the same length of k1 but doesn't explain how it is calculated from k1 as a seed (which is understood to be how k2 is produced).

Finally, another article appears to show that k2 is produced by feeding a number of bytes from S1 into the original RC4 PRGA, producing a keystream:

To be more specific, in KSA of RC4, the array S1 is initialized, using the secret key K. WK, 16 bytes of keystream, are generated from the array S1 in PRGA of RC4. Then, the array S2 is initialized in KSA of RC4, using WK.

I am assuming K refers to k1 and WK refers to k2 in the original article.

Related pseudo-code:

RC4_KSA(K, S1)
For i = 0 … l – 1
WK[i] = RC4_PRGA(S1)
RC4_KSA(WK, S2)

One problem with this approach is that when calculating k2, the RC4 PRGA would swap values in S1, altering it. S1 is used in the RC4A PRGA and would produce a different keystream than if it had not been altered. This can be avoided by using a second copy of S1 for RC4 PRGA, leaving the original unaltered.

So there is ambiguity in how the second key for S2 is produced, with implementations differing in output keystream for same input.

A few questions:

1. Do the two differing implementations in practice undermine RC4A's security claims by not using a PRBG/PRGA to produce k2?
2. Does it matter what k2 is, how it's produced, or if it's the same as k1?
3. What is the proper way to produce k2 that all implementations should follow?

Thank you!

Answer 1

Do the two differing implementations in practice undermine RC4A's security claims by not using a PRBG/PRGA to produce k2?

I wouldn't think so. I get the impression that the authors just intend k2 to be derived from k1. They have not amended the algorithm so much as to use a different key schedule for k1. That leads to the requirement to create a second permutation using the existing key scheduling algorithm, thus a different key has to be found from somewhere. The truth of this is proven by the fact that different implementations use different techniques.

Frankly it's a little disappointing that the authors didn't address k2's generation more specifically.

Does it matter what k2 is, how it's produced, or if it's the same as k1?

From a cursory inspection of fig.3, it appears that each alternate output comes from each state permutation. There doesn't seem to be any interaction between them. I posit that if k1 = k2 then the outputs would be identical pairs. This seems consistent with the authors' comments regarding improved security by having more variables. A PRNG is as good a way as any, but. Ideally the inner state of the PRNG should be equivalent to the length of the key, but since a RC4 key can technically be 2048 bits, that's a problem. Few smallish XOR shift or LFSR PRNGs have such a large state. See below.

What is the proper way to produce k2 that all implementations should follow?

Again, the fact that differing implementations use differing ways of generating k2 proves that there is no proper way to produce it. Proper would just be that k1 ≠ k2. My personal choice would be a simple 256 byte randomly generated S box. Note: it is confusing that the authors use the term S box to refer to the internal state array. I'm suggesting a real S box so that k2 = SBOX[k1] for all bytes.

There is a wonderful alternative solution to both initial key stream bias and generation of the two states. Two fully widened Pearson hashes can be used. One derangement makes k1, and a second independent derangement makes k2. Since this is a new variant of RC4, there cannot be any backward compatibility for passwords anyway. This means that the entire key scheduling algorithm can be scrapped. And it's a perfect fit as a fully widened Pearson hash output is exactly 2048 bits. Yes the maximum state size of such a hash is only 1684 bits, but who uses passwords that have 210 bytes of entropy anyway?

---

Opinion on the paper

I find section 5 very poor. Every (even amateur) cryptographer knows that RC4's Achilles heel is bias. Indeed the authors' motivation is to improve RC4's security. This must mean bias reduction. So how can they possibly put forward an RC4 derivative without a bias assessment? What is the point of section 2 if they then just forget about possible biases of their own creation?

"Diminished" from section 5.3 is not good enough. It means nothing that their baby passes randomness tests. The original RC4 did too. This speaks to the vagueness and generality of current test suites, but also forms a cop out for the authors. I don't know if this is intentional. If they wanted a quick and dirty solution, all they had to do was add a von Neumann extractor after the PRNG component and RC4 becomes bias free.

As pointed out in the comments to you, RC4A can be distinguished now via observation of 2^23 outputs. The author's began their paper saying that the original RC4 could be distinguished after 2^25 outputs. They seem to have gone backwards, although in fairness attacks improve with time.