This is a study note of “Understanding Cryptography” ch02. It covers the stream ciphers.

1 Introudction

Stream ciphers, also referred to as Vernam ciphers, encrypt bits individually. There are synchronous stream ciphers where the key stream depends only on the key, and asynchronous ones where the key stream also depends on the ciphertext. Because stream ciphers tend to be small and fast, they are particularly relevant for applications with little computational resources, e.g., for cell phones or other small embedded devices.

Each bit xi is encrypted/decrypted by adding a secret key stream bit si modulo 2. There are two reasons XOR function is used in stream ciphers:

  • It is perfectly balanced, i.e., by observing an output value, there is exactly a 50% chance for any value of the input bits.
  • The encryption and decryption use the same reversible function.

The generation of the values si, which are called the key stream, is the central issue for the security of stream ciphers. In fact, the security of a stream cipher completely depends on the key stream. The key stream bits si are not the key bits themselves.

2 Random Numbers and an Unbreakable Stream Cipher

True random number generators (TRNGs) are characterized by the fact that their output cannot be reproduced.

Pseudorandom number generators (PRNGs) generate sequences which are computed from an initial seed value. They are deterministic and not truely random. A common requirement of PRNGs is that they possess good statistical properties, meaning their output approximates a sequence of true random numbers.

In ANSI C rand(), it is:

1
2
s = seed = 12345
s = (1103415245 * s + seed) % 2 ^ 31

Cryptographically secure pseudorandom number generators (CSPRNGs) are a special type of PRNG which possess the following additional property: A CSPRNG is PRNG which is unpredictable. It means that given n consecutive bits of the key stream, there is no polynomial time algorithm that can predict the next bit with better than 50% chance of success. Another property of CSPRNG is that given the i, i+1, i+n-1 bit sequence, it should be computationallyinfeasible to compute any preceding bits i-1, i-2,…

The unpredicttability is unique to cryptography. Most other applications of PRNG don’t need this.

The number of atoms in the known universe is about 2^266, about 10^80.

In One-Time Pad (OTP), one key bit from TRNG is used for one bit of plaintext. OTP is perfectly secure but hard to use in practice because of its key length.

The ANSI C rand() has good statistical properties but can be attacked easily with some known some plaintext.

3 Shift Register-Based Stream Ciphers

There are software-based, hardware-based and block-cipher-based methods to create a CSPRNG. Linear feedback shift registers (LFSRs) is a popular hardware solution. LFSR is weak but combinations of LFSRs such as A5/1 or Trivium can make secure stream ciphers.

An LFSR consists of clocked storage elements (flip-flops) linearly connected and a feedback path. The number of storage elements is the degree of the LFSR. Let’s assume the LFSR is initially loaded with the values s_0, . . . , s_(m−1). The next output bit of the LFSR sm, which is also the input to the leftmost flip-flop, can be computed by the XOR-sum of the products of flip-flop outputs and corresponding feedback coefficient: s_m = s_(m-1) * p_(m-1) + ... + s_1 * p_1 + s_0 * p_0. The coefficient p_i can be 0 (closed) or 1 (open). It controls if the flip-flop i is used in feedback or not. The coefficent vector is the secret key of an LFSR.

The maximum sequence length generated by an LFSR of degree m is 2^m − 1. Note that only certain configurations yield maximum lenght LFSR.

As soon as an attacker knows 2m output bits of an LFSR of degree m, it is easy to calcualte the key because LFSRs are linear.

Trivium is a stream cipher that uses an 80-bit key. It uses a combination of three shift registers and nonlinear components to dereive the output of each reigster.

Almost all modern stream ciphers have two input parameters: a key k and an initialization vector IV . The former is the regular key that is used in every symmetric crypto system. The IV serves as a randomizer and should take a new value for every encryption session. It is important to note that the IV does not have to be kept secret, it merely must change for every session. Such values are often referred to as nonces, which stands for “number used once”. Its main purpose is that two key streams produced by the cipher should be different, even though the key has not changed. Without a changing IV, stream cipher encryption is highly deterministic.

4 Discussion

Many ciphers and modes of operation rely on initial values that are often generated from TRNGs. Also, many protocols require nonces (numbers used only once), which may stem from a TRNG.

All TRNGs need to exploit some entropy source, i.e., some process which behaves truly randomly.

Stream ciphers are less popular than block ciphers in most domains such as Internet security. There are exceptions, for instance, the popular stream cipher RC4.