How to generate the Keystream from IV+Key in RC4

Question

So I understand that a keystream is generating from a key and is the length of the message you want to send, so that you can properly XOR every bit. But I'm having trouble finding and understanding the algorithm for creating the keystream from the IV and key.

One idea I had is if you have a message of length 100 and key of length 10, then your IV is 90 bits to cover the rest of the message, and then the key string is just the concatination of IV + key.

Answer 1

The length of Key and length of IV bear no relationship with the length of the message.

RC4 is deprecated. The way it was supposed to be used is:

1. Generate a random IV, wide enough that it will remain unique (e.g. 32 bytes), and emit that as header of the ciphertext since the receiver will need it.
2. Concatenate Key (limited to 256 minus IV size in bytes) and IV
3. Initialize the cipher with that (there are 256 steps that cycle on the concatenated Key and IV).
4. Generate as much output a there is plaintext, and use it as keystream to XOR with plaintext, yielding ciphertext.

But various attacks exist. If for some reason one is locked with that cipher from the past (rather than e.g. ChaCha which is safer, faster, and less RAM-intensive), and nevertheless wants to be secure, it's advisable to at least discard some of the initial keystream (e.g. the first 1024 bytes) in an intermediary step before 4.

And of course if one is locked with a particular protocol, it must be done as in that protocol.

---

Note: if the key is derived from a passphrase memorized by a user, then it is highly advisable to use some form of stretching for the password-to-key conversion:

• The best would be a modern and well parametrized password hash function such as Argon2 or Scrypt.
• If not, we can use RC4 itself by using the amount of keystream skipped as the workfactor parameter (e.g. 2²² bytes). Also, we need to limit the password length to be sure that there remains room for the IV.

Independently, the character set of the password must be well-defined (e.g. UTF-8).

Answer 2

Just in case this is your goal: if you want to examine the keystream of an arbitrary RC4 key, but all you have is a black-box library that takes a key and a message and encrypts (or decrypts) that message, you can get the keystream simply by passing a message composed entirely of zeros (null bytes). Any value XORed with 0 is just itself, and RC4 encryption (and decryption) are done by XORing the message with the keystream.

---

RC4 - like all stream ciphers - is essentially just a (theoretically cryprographically secure) pseudo-random number generator. The "seed" of the PRNG is just its key (in practice, usually a public portion to form an initialization vector / nonce that changes for each message, and a secret key that is pre-shared or exchanged via some other mechanism, concatenated together and possibly hashed). From such a "seed", the keystream is produced in a deterministic fashion, but the length of the key/seed is such that brute-forcing it is effectively impossible.

The actual algorithm by which the "seed" is processed and then used to generate bits (the keystream) is a sequence of basic mathematical operations, particularly addition, modulus, and bit swaps. The full algorithm is published on Wikipedia.

---

In theory, a secure PRNG / stream cipher has the following security features:

• Knowing only part of this seed (the IV, which is public, but not the secret key) does not allow recovery of the keystream with any likelihood greater than 1/(2^n), where n is the number of bits not known.
• Changing even a single bit of the "seed" - that is, even one bit of the key or IV - will produce a keystream that has no detectable relationship to any other (that is, it appears not only random by itself, but random compared to the output of any other seed).
• The keystream will not repeat (it contains no cycles, at least not within a length that could ever be computed or stored using current or forseeable-future hardware).
• Each bit of the keystream should appear totally independent of all other bits; you should be able to know every single proceeding bit of the keystream and still have no better than a 50/50 chance of guessing the next bit (or better than 1/256 chance of guessing the next byte [octet]). Same for knowing all the following bits, or indeed every single bit save one.
• Even knowing any practical number of bits of the keystream shouldn't allow anybody to predict the value of even a single bit of the "seed" with better than 50/50 chance.

Most non-cryptographically-secure PRNGs miss some or all of these properties (for example, they might loop after 2^32 bytes of output, or allow working forward or backward, deriving future or past outputs from some set). RC4, unfortunately, also fails to live up to these ideals; it was found to be vulnerable to multiple attacks that reveal at least partial message contents, or even the key, under common uses that occurred in the real world. For this reason, it is now a deprecated cipher / CSPRNG. If you want to examine a modern stream cipher / CSPRNG, consider the Salsa20/ChaCha family; as with RC4, the internal mathematical operations are fairly simple and described on the Wikipedia page (and, of course, in formal publications).