Simple RC4 key generation scheme

Question

I would like to ask you about your opinion on the following scheme of combining a master key and a nonce and stretching the result to the full 256-bytes RC4 key.

• Master key $K_m$ is a pre-shared secret of length $M$ bytes
• nonce $K_n$ is sent unencrypted and is of length $N$ bytes
• both $K_m$ and $K_n$ are chosen to be high-entropy strings
• the $i$-th byte of the resulting key would be $K[i] = (K_m[i \bmod M] + K_n[i \bmod N]) \bmod 256$

The period of the string $K$ is $LCM(M,N)$, so I would choose the $M$ and $N$ such that $LCM(M,N) \ge 256$.

Is there anything obviously wrong with this scheme?

PS: This scheme would be used on an 8-bit micro-controller embedded system. Limited speed/memory prevents me from using a more standard method.

Answer 1

I am familiar with the RC4 related key attacks; I can say that if you publish the nonce, and use any of the first 256 bytes of the RC4 keystream, that you are vulnerable to those attacks.

These attacks exploit a correlation between specific bytes of the RC4 key, and the initial output values; with your approach, the attackers can guess what (say) byte 2 of the master key was (by computing what the corresponding RC4 key is for each message, and checking to see if the RC4 byte statistics is what he'd expect); this would allow him to recover the entire master key with enough messages.

I would strongly urge you that, if you can't follow D.W. advice, and you have to live with this scheme, that you always discard the initial (at least) 512 bytes of the RC4 keystream immediately after you rekey RC4. Why 512 and not 256? Well, some statistical analysis shows that byte 258 of the generated keystream has a measurable bias towards the value 03; it is unknown why it is, or if it has any correlation with the initial key; but it is a bad sign.

Answer 2

I don't think this is a great idea. I don't know of anyone who has analyzed it carefully, but it is basically relying upon RC4 to be secure against a particular kind of related-key attack (one that probably hasn't been studied much).

We know that in general RC4's key schedule algorithm is not very resistant to related-key attacks. For instance, it is a bad idea to concatenate a master key and a nonce and use that as the RC4 key. RC4 is not secure in that scenario. For example, that is exactly the mistake that created such a devastating security vulnerability in WEP. I know that's not quite what you are proposing, but what you are proposing reminds me of that fiasco and makes me think your proposal is risky. I suppose it's possible that it could be OK, but it would take a lot of detailed analysis to establish that, and I am suspicious.

Instead, if you want to use RC4 in this scenario, I recommend you use a pseudorandom function (PRF) for key derivation: generate k = PRF(Km,Nonce), and use k as your RC4 key for that packet. However, this does require a separate PRF function: e.g., AES-CMAC, SHA1-HMAC, etc. I realize that that might be problematic on an 8-bit embedded microcontroller.

Given that you are working with a 8-bit microcontroller, I suspect you're probably going to be better off not using RC4 at all and using a block cipher that is good for embedded systems (e.g., Skipjack, RC5, etc.). Search on this site and you can find more information about such things.