Incorrect S2 value (and potential solution)

[bryc]

This is your code for generating S-boxes S1 & S2:

    const S1 = generateSBlock(key);
    const S2 = generateSBlock(S1.join(""));

The problem lies with S1.join(). This converts an array of integers to a string in a literal way, which I don't think you intended. For example, the code [186, 93, 154, 66].join("") produces the string 1869315466 resulting in a 10-byte string of decimal number, rather than the 4 original bytes. This is a JavaScript quirk which simply combines the decimal numbers with no whitespace in between. A more logical approach (and what one would expect) is to produce the 4-byte string º]šB (hex=0xBA5D9A42) from the array.

As it is now, the length of k2 will increase from 256 to 500-700 and render it incompatible with other implementations of RC4A, due to this very specific requirement.

Here is a quick fix for rc4a.js. It makes use of a second argument to generateSBlock specifying whether to interpret key as string or array:

function generateSBlock(key, isarr) {
    const S = Array.from(Array(256), (_, i) => i);
    const keyLength = key.length;

    let j = 0;
    for (let i = 0; i < 256; i++) {
        var keyidx = (isarr ? key[i % key.length] : key.charCodeAt(i % key.length));
        j = (j + S[i] + keyidx) % 256;
        swap(S, i, j);
    }

    return S;
}

function rc4a(text, key) {
    const S1 = generateSBlock(key);
    const S2 = generateSBlock(S1, true);
// ...

---

If interested, there is also another potential problem with even the above fix. The original paper on RC4A is very vague when referring to how S2 is generated. It only mentions k2 twice. Here is a quote:

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.

They suggest that k2 be produced using a pseudo-random bit generator, such as RC4, with k1 being the seed (where k2 has same length as k1). This would require the addition of another PRBG, such as RC4's PRGA (taking care to not mutate the original S-box), or any other algorithm such as a LFSR or LCG. As far as I can tell, the only important aspect is that k1 ≠ k2 due to the outputs being the same, so you could theoretically reverse k1 and use that as k2. Unfortunately, this means that no two implementations will be the same because of the loose language.

I have come across another JS implementation of RC4A which simply duplicates S1 for S2 like so:

    const S1 = generateSBlock(key);
    const S2 = generateSBlock(key);

It "solves" this problem by ignoring the existence of k2 completely, and using a copy of S1 for S2. This is however incorrect, as the outputs will be identical because S1 and S2 are identical, so the keystream will be repeating digits.

If the RC4-KSA indeed qualifies as a PRBG in the paper, I highly suggest using the 256-byte output S1 as the key for S2 (and therein my suggested fix), due to it being already used in other implementations.

[bryc]

Looking at related papers referencing RC4A, many do show pseudocode for generating a second key using RC4-PRGA. I also found evidence that k2 should not equal k1.

From article The Most Efficient Distinguishing Attack on VMPC and RC4A:

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.

Elsewhere in the article:

l represents the size of secret key in bytes

Related Pseudocode:

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

Based on this pseudocode, it appears the proper way to produce the second key k2 is to feed a certain number of input bytes from S1 into the original RC4 PRGA (without XORing keystream to message). I am unsure if the length should be a fixed 16 bytes, or the same length as k1. I am assuming the latter due to the l variable shown in in pseudocode.

Strangely, a number of other papers contain very similar text:

From RC4A Stream Cipher for WLAN Security: A Hardware Approach:

In KSA for RC4A, like KSA of RC4, the array S1 is initialized, using the secret key K, Keystream, WK, are generated from the array S1 like PRGA (Pseudo Random number Generation Algorithm) of RC4. Then, like S1, the array S2 is initialized using WK.

Pseudocode from that article (appears to be exactly the same):

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

A third article called A Pragmatic Study on Different Stream Ciphers And On Different Flavors of RC4 Stream Cipher:

In KSA for RC4A, like KSA of RC4, the array S1 is initialized, using the secret key K, Key stream, WK, are generated from the array S1 like PRGA (Pseudo Random number Generation Algorithm) of RC4. Then, like S1, the array S2 is initialized using WK.

Pseudocode from that article (appears to be exactly the same):

KSA (K)
RC4_KSA(K,S1)
For i=0……….I-1
WK[i]=RC4_PRGA(S1)
RC4_KSA(WK,S2) 

Based on these insights, I attempted to implement the RC4_PRGA k2 method:

function rc4a(key, msg) {
    function swap(S, i, j) {
        var tmp = S[j]; S[j] = S[i]; S[i] = tmp;
    }
    function xorout(msg, keystream) {
        for(var cipher = [], i = 0; i < msg.length; i++) {
            cipher[i] = msg[i] ^ keystream[i];
        } return cipher;
    }
    function rc4_ksa(key) {
        for (var S=[],i=j=0; i<256; i++) {S[i] = i;}
        for (i = 0; i < 256; i++) { 
            j = (j + S[i] + key[i % key.length]) % 256;
            swap(S, i, j);
        } return S;
    }
    function rc4_prga(S) {
        var keystream = [];
        for (var k=i=j=0; k<key.length; k++) {
            i = (i + 1) % 256;
            j = (j + S[i]) % 256;
            swap(S, i, j);
            keystream[k] = S[(S[i] + S[j]) % 256];
        } return keystream;
    }
    function rc4a_prga(S1, S2) {
        var keystream = [];
        for (var k=j1=j2=i=0; k<msg.length; k+=2) {
            i = (i + 1) % 256;
            j1 = (j1 + S1[i]) % 256;
            swap(S1, i, j1);
            keystream[k] = S2[(S1[i] + S1[j1]) % 256];
            if(msg[k + 1] === undefined) {break;} // skip j2 if next byte in msg doesn't exist
            j2 = (j2 + S2[i]) % 256;
            swap(S2, i, j2);
            keystream[k + 1] = S1[(S2[i] + S2[j2]) % 256];
        } return keystream;
    }

    var S1 = rc4_ksa(key);
    var key2 = rc4_prga(S1.slice(0)); // Clone S1 so rc4_prga doesn't alter original
    var S2 = rc4_ksa(key2);
    var keystream = rc4a_prga(S1, S2);

    var output = {
        plain: msg,
        cipher: xorout(msg, keystream), // final xor of msg<->keystream
        keystream: keystream,
        S1: S1,
        S2: S2,
        key1: key,
        key2: key2
    }
    return output;
}

The inner for (var key2=[]... loop is the RC4-PRGA which operates on S1 (and unswaps after) to produce key2. hex7c0's RC4A implementation output can still be produced by replacing S2 = ksa(key2) with S2 = ksa(key). It is also simple to match your implementation by replacing S2 = ksa(key2) with S2 = ksa(strarr(S1.join(''))), with use of an string-to-array function strarr() (since my code operates on arrays not strings). There is also a variant which is simply S2 = ksa(S1), making a total of 4 unique implementations, all variations on S2.

Another alternative is to use S1 as k2 (since it's still derived from k1) but truncate it to the length of k1. This appears more correct than using all 256 bytes of S1, essentially using the input bytes that would be fed into rc4_prga, but still may not qualify as a "pseudorandom bit generator".

var key2 = S1.slice(0,key.length);

---

Other evidence:

A cryptography course instructs students to calculate S2 based on a "nonce" second key (same length as first key):

RC4A's key scheduling algorithm (KSA) is: Use the RC4 KSA to initialize S1 based on the key; use the RC4 KSA to initialize S2 based on the nonce.

When RC4A is initialized with the key 000102030405060708090a0b0c0d0e0f and the nonce 101112131415161718191a1b1c1d1e1f, these are the values of the S1 and S2 array elements...

A paper confirms that the second state table must use a different key and must be derivative of k1:

The key scheduling algorithm of RC4A is very similar to the KSA of RC4. The only difference is that, in RC4, KSA generates one state table by using one key, RC4A generates two state table by using two different keys. First key k1 produces randomly and the second key k2 is generated by using the first one. Designers mainly focus on pseudorandom generation algorithm of RC4A.

The book RC4 Stream Cipher and Its Variants also confirms the requirement of two different keys:

RC4A [139] tries to increase the security of RC4 by using two S-boxes S1 and S2. The key scheduling of RC4A is the same as the RC4 KSA, except that it uses two different secret keys two construct the two S-boxes.

The book Stream Ciphers also implies that k2 is generated using RC4 (implying the PRGA):

If one generates K2 from K1 by a simple RC4 algorithm as suggested in [209], we can mount the following attack. Assume that the initialization vector precedes the main key. With a chosen initialization vector, we may enforce that the first two bytes of K2 depend in a simple way on the first two bytes of the main key.

I have found a number of additional source code for RC4A with different interpretations of S2, but none that implement RC4 PRGA for k2.

C# code uses duplicate S1 and S2 s-box.

Python 3 code has many variants of RC4, including RC4A with duplicate S1 and S2 s-box.

An implementation of RC4A in C is using the 256 indexes of S1 to produce S2 (e.g. S2 = KSA(S1)).