# Simple RC4 key generation scheme

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.

-
OK, so in the end I will use RC4-drop512, with my scheme of combining the master key and the nonce. The nonce will be sent in two steps: first unencrypted with the corresponding generated PRN stream used only to send the second nonce in an encrypted packet. Thanks everyone for your comments. –  cvoque Mar 5 '13 at 8:50

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.

-
Just to avoid confusion - I am not trying to modify RC4's key scheduling algorithm but merely generate a new key to run the standard RC4's KSA on. –  cvoque Mar 3 '13 at 20:26
@cvoque, ahh, my mistake! Sorry for mis-interpreting the question. I've edited my answer just now to reflect what you were actually asking. Sorry about my confusion. –  D.W. Mar 3 '13 at 20:49
@ D.W. So, what you are basically saying is that it is hard to analyze possible weaknesses of such a scheme and thus one should stick to something standard. I will definitely look into the recommended block ciphers. Thanks! –  cvoque Mar 3 '13 at 21:01