07. Pseudorandom Numbers and Stream Ciphers

Random Numbers

Randomness: want any specific string of bits is exactly as random as any other string.

True random number generator (TRNG): physical process which outputs each valid string independently with equal probability.

Pseudorandom number generator (PRNG): deterministic algorithm which approximates a TRNG.

For practically, TRNGs are often used to provide a seed for a PRNG.

Pseudorandom Number Generator (PRNG)/Deterministic Random Bit Generator (DRBG)

Entropy source includes:

• Physical noise source
• Digitization process
• Post-processing stages

Periodic health tests required to ensure reliable operation.

Each generator takes a seed as an input, outputting a bit string before updating its state.

The seed should be updated after some number of calls.

DRBGs expose some functions:

• Instantiate: set the initial state using a seed
• Generate: provide bit string for each request
• Reseed: input new random seed and update the state
• Test: check correct operation
• Uninstantiate: delete/zeroising the state

The DDRBG should prevent an attacker from being able to reliably distinguish between its output and a truly random string. There are two types of resistance:

• Backtracking resistance: attacker with access to current state of DRBG should not be able to distinguish between the output of earlier calls and random strings
• Forward prediction resistance: attacker with access to current state of DRBG should not be able to distinguish between output of later calls and random strings

CTR_DRBG

Block cipher in counter (CTR) mode - AES with 128-bit keys recommended.

DRBG initialized with seed whose length is equal to key length PLUS block length.

Seed defines a key $K$ and counter value $ctr$ (no separate nonce).

CTR run iteratively with no plaintext.

Update Function

Each request to the DRBG generates up to $2^{19}$ bits.

State $(K, ctr)$ must be updated after each Generate request by generating two blocks using the current key to obtain a new key and counter; provides backtracking resistance.

Up to $2^{48}$ requests to the Generate function are allowed before re-seeding is required; provides forwards prediction and backtracking resistance.

Dual_EC_DRBG

Older standard based on elliptic curve discrete logarithm problem and with many flaws.

Much slower than other DRBGs.

Secret deal between NSA and RSA Security to use this as the default PRNG in their software was reported in 2013.

Stream Ciphers

Generates keystream using a short key and initialization vector $IV$.

Each element of the keystream is used to successively encrypt one or more ciphertext characters.

Stream ciphers are usually symmetric.

Synchronous Stream Ciphers

Keystream is generated independently of the plaintext; both the sender and receiver need to generate the same keystream and be synchronized.

Keystream and plaintext are XORed together, so receiver simply needs to XOR the ciphertext with the keystream to decrypt.

Vigenère cipher can be seen as a periodic synchronous stream cipher where each shift is defined by a key letter.

CTR mode of operation for a block cipher can be used to generate a keystream.

Binary Synchronous Stream Ciphers

For each time interval $t$:

• $s(t)$ is the binary keystream
• $p(t)$ is the binary plaintext
• $c(t)$ is the binary ciphertext

Encryption: $c(t) = p(t) \oplus s(t)$.

Decryption: $p(t) = c(t) \oplus s(t)$.

One-Time Pad

Key is random sequence of characters such that each is independently generated.

Each character in the key is only used once; this provides perfect secrecy.

Alphabet can be of any length but is usually either binary or a natural language alphabet.

Perfect Secrecy

Shannon’s definition:

• Message set $\{ M_1, \dots, M_k \}$

• Ciphertext set $\{ C_1, \dots, C_k \}$

• $\mathrm{Pr}(M_i | C_j)$; probability that $M_i$ is encrypted given that $C_j$ is observed

  • In most cases, messages $M_i$ are not equally likely; that is, given a ciphertext, some messages are more likely than others

• For all messages $M_i$ and ciphertexts $C_i$:

  $$\mathrm{Pr}(M_i | C_j) = \mathrm{Pr}(M_i)$$

The ciphertext should be independent of the plaintext

One-Time Pad Perfect Secrecy

Let a ciphertext $C_j$ be observed.

The probability that $M_i$ was sent given that $C_j$ is observed is the probability that $M_i$ is chosen, weighted by the probability that the right keystream is chosen.

As each keystream is chosen with equal probability, $\mathrm{Pr}(M_i | C_j) = \mathrm{Pr}(M_i)$.

Any keystream is possible and so given any plaintext, every possible ciphertext is generated with equal probability.

Vernam Binary One-Time Pad

• Plaintext : binary sequence $b_1, \dots, b_r$
• Ciphertext: binary sequence $c_1, \dots, c_r$
• Keystream : binary sequence $k_1, \dots, k_r$
  • Must be same length as the plaintext
• Encryption: $c_i \equiv p_i \oplus k_i$
• Decryption: $p_i \equiv c_i \oplus k_i$

Properties

Shannon showed that any ciphertext with perfect secrecy must have as many keys as there are messages. Hence, one-time pad is the only unbreakable cipher.

However, this requires secure communication between fixed parties and secure key generation, transportation, synchronization, and destruction which are all difficult due to the size of the keys.

Visual Cryptography

Encryption splits an image into two shares, each pixel being shared in a random way (similar to splitting a bit in a one-time pad).

Each share alone reveals no information about the image, but the two images can be overlayed to reveal the plaintext.

Prominent Stream Ciphers

A5 Cipher

Binary synchronous stream cipher applied in most GSM communications. Three variants:

• A5/1 is the original algorithm defined in 1987
• A5/2 is the weakened version intended for deployment outside Europe
• A5/3 (KASUMI) used in 3G systems

A5/1 Design

Three linear feedback shift registers (LFSRs) whose outputs are combined.

The LFSRs are irregularly clocked, making the overall output non-linear.

It has a 64-bit keystream such that 10 bits are fixed to zero; hence, the effective key length is 54 bits.

RC4 Cipher

Ron’s code #4 . Originally owned by RSA but leaked in 1994. Too weak to use in real systems nowadays, but was was widely deployed in TLS before 2013.

ChaCha Algorithm

Possible replacement of RC4 designed in 2008.

Faster than AES; as few as 4 cycles/byte on x84 processors.