# How can a stream cipher encrypt one bit at a time and still be secure?

I was reading the differences between stream ciphers and block ciphers, noticing that block ciphers, encrypted blocks of 64 bits or so at a time. But, stream ciphers encrypt 1 bit at a time, and to me it seems it would be easily reverse-able? If the stream cipher's algorithm isn't changing then what stops the adversary from easily decrypting the ciphertext generated by the stream cipher?

• Critical: a good stream cipher generates fresh keystream for each new plaintext. That's why there is a (typically public and random) IV.
– fgrieu
Jan 24, 2018 at 16:25
• How does the adversary do that? Jan 24, 2018 at 17:50

TL;DR that bit relies on a large state and a lot of calculations that cannot be easily reversed, as you seem to believe.

A stream cipher creates a key stream that depends on the input key material (key seed). Although the stream cipher outputs one bit at a time (usually one byte at a time in implementations for obvious reasons) that doesn't mean that the internal state is of that size. The internal state will generally be larger than the security strength of the cipher.

Before even a single bit is output the state must be updated so that the output is indistinguishable from random to an adversary. Sometimes this is not entirely the case if the stream cipher is (partially) broken: the initial output stream of RC4 is distinguishable from random; it is required to first remove the head of the key stream to create a - relatively - secure cipher.

It should not be possible to calculate any significant part of the state or any part of the key by an adversary.

To use a stream cipher it is of high importance that the key / nonce combination for each encryption remains unique. If this isn't the case then a lot of information can be retrieved from the messages encrypted with the same combination.

Simply put, a stream cipher uses a cryptographically secure psuedorandom number generator (CSPRNG) to produce a key stream of arbitrary length, and then uses the resultant psuedorandom information to encrypt the plaintext by combining the two.

The security of the construction basically relies upon the output of the CSPRNG being unpredictable.

The length of the message has no bearing on the generation of the random numbers: The CSPRNG is designed with an adequate state size and complexity to ensure that future outputs remain unpredictable, regardless of how many past outputs one may possess.

For example, Salsa20 outputs 512 bits of random information per invocation of the function. If your message is only 1 bit long, then you would simply use the first bit of the output and discard the unused bits.

But, stream ciphers encrypt 1 bit at a time, and to me it seems it would be easily reverse-able?

Without knowing what the key stream generated by the CSPRNG was, the encryption of a single bit (or any number of bits) is not easily reversible, given only the ciphertext and the initialization vector/seed for the CSPRNG.

The only way to undo the operation is to generate the same key stream, and then remove the random information from the ciphertext. The CSPRNG is keyed, and it requires the key to generate the key stream.

If the stream cipher's algorithm isn't changing then what stops the adversary from easily decrypting the ciphertext generated by the stream cipher?

It is not clear what is meant by "the stream cipher's algorithm isn't changing". I am guessing this means "the stream cipher always outputs the same key stream".

As long as a unique seed is used to encrypt each message, the generated key stream will be both unique and unpredictable.

If the same seed was re-used for multiple messages, then the adversary can (possibly/probably) recover some of the key stream from a known plaintext/ciphertext pair, and then use the recovered key stream to decrypt other ciphertexts.

Using a unique seed for each message is standard practice for these reasons.

disclaimer: Details have been omitted to simplify this explanation, i.e. it assumes that the CSPRNG is secure, there's no mention of probabilities of success, etc...