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.
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.