RC4 Klein (or other) attack susceptibility question

Question

What issues do yall see with the following in terms of key recovery and related key attacks:

RC4 used to "sign" a nonce:

3 byte nonce concatenated with 16 byte long term key > RC4 Keystream Generator > 259 bytes keystream output

Discard first 256 bytes of keystream leaving only last 3 bytes "Signature"

3 byte Nonce / 3 byte Signature pairs are the only information sent publicly

Answer 1

There are a bunch of problems with this.

• One obvious one is that your "signature" is three bytes long, which is 24 bits and subject to brute forcing.
• Another is that for most cases, a three-byte nonce is insufficient in size. That's only a little over 16 million requests, and in most applications, that's not enough. For a single connection, TLS uses a 64-bit sequence number, which is not expected to wrap.

As you alluded to, RC4 is actually very vulnerable to related-key attacks, and your approach is very similar to WEP, which is completely insecure for this reason. The major difference here is that the nonce in WEP is appended to the key, and here it's prepended. Even with substantially less data, RC4 is still far from an ideal stream cipher and has known biases. It's just not a design that I'd be using for anything anymore.

However, there is good news. If you're looking for a way to conduct a symmetric verification of some data with a shared key, we have an easy way to do that: a MAC. HMAC-SHA256 with a 16-byte key is fine for this, but it does mean that typically you'll need to send more data to avoid attacks. Typically, you'd send the entire MAC, which is 32 bytes. AES-CMAC with a 16-byte key is also a fine choice and is 16 bytes.

If you're looking for a long-term key, your nonces should be much larger. We'd recommend at least 192 bits (24 bytes) if you're picking random nonces, but personally, I'd recommend 256 bits (32 bytes). If you're using a counter, it can be smaller, but many algorithms have weaknesses if a nonce is reused, so you must ensure that can't ever occur in your situation.

Also, some algorithms, like CBC, require unpredictable nonces for security, so you should be sure to verify what your algorithm requires. You can also take a nonce of any relevant size (including a counter) and a long-term key and use a key derivation function like HKDF to generate a new key and new nonce on each request, which avoids all of those problems.