Random Bit Generation and Stream Ciphers

Lecturer:

Prof. Dr. Michael Eichberg

Version:
2023-10-19
Based on:

Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Random Numbers

There are two distinct requirements for a sequence of random numbers:

Randomness

Visualization of a Bad Random Number Generator (RNG)

Expected distribution of random values in 3D space.

Distribution of values in 3D space

Distribution of supposedly random values of a bad rng in 3D space.

Bad distribution of values in 3D space

Unpredictability

Pseudorandom Numbers

Cryptographic applications typically make use of algorithmic techniques for random number generation.

Random and Pseudorandom Number Generators

RNGs

True Random Number Generator (TRNG)

Pseudorandom Number Generator (PRNG) and Pseudorandom Function (PRF)

Two different forms of PRNG

Pseudorandom number generator

  • An algorithm that is used to produce an open-ended sequence of bits.

  • Input to a symmetric stream cipher is a common application for an open-ended sequence of bits.

Pseudorandom function (PRF)

  • Used to produce a pseudorandom string of bits of some fixed length.

  • Examples are symmetric encryption keys and nonces.

Pseudorandom Number Generator (PRNG) and Pseudorandom Function (PRF)

PRNG Requirements

Randomness

NIST SP 800-22 specifies that the tests should seek to establish three characteristics: (1) Uniformity, (2) Scalability, (3) Consistency

Randomness Tests

SP 800-22 lists 15 separate tests of randomness

Frequency test:
  • The most basic test and must be included in any test suite

  • Purpose is to determine whether the number of ones and zeros in a sequence is approximately the same as would be expected for a truly random sequence

Runs test:
  • Focus of this test is the total number of runs in the sequence, where a run is an uninterrupted sequence of identical bits bounded before and after with a bit of the opposite value

  • Purpose is to determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence

Maurer’s universal statistical test:
  • Focus is the number of bits between matching patterns.

  • Purpose is to detect whether or not the sequence can be significantly compressed without loss of information. A significantly compressible sequence is considered to be non-random.

Unpredictability

A stream of pseudorandom numbers should exhibit two forms of unpredictability:

Forward unpredictability:

If the seed is unknown, the next output bit in the sequence should be unpredictable in spite of any knowledge of previous bits in the sequence

Backward unpredictability:
  • It should not be feasible to determine the seed from knowledge of any generated values.

  • No correlation between a seed and any value generated from that seed should be evident.

  • Each element of the sequence should appear to be the outcome of an independent random event whose probability is 1/2

The same set of tests for randomness also provides a test of unpredictability: A random sequence will have no correlation with a fixed value (the seed).

Seed Requirements

Generation of seeds

Algorithm Design

Algorithms fall into two categories:

  1. Purpose-built algorithms

    Algorithms designed specifically and solely for the purpose of generating pseudorandom bit streams.

  2. Algorithms based on existing cryptographic algorithms.

    Have the effect of randomizing input data.

    Three broad categories of cryptographic algorithms are commonly used to create PRNGs:

    • Symmetric block ciphers

    • Asymmetric ciphers

    • Hash functions and message authentication codes

Linear Congruential Generator

An algorithm first proposed by Lehmer that is parameterized with four numbers:

\(m\)

the modulus

\(m > 0\)

\(a\)

the multiplier

\(0 < a< m\)

\(c\)

the increment

\(0\leq c < m\)

\(X_0\)

the starting value, or seed

\(0 \leq X0 < m\)

The sequence of random numbers \(\lbrace{X_n}\rbrace\) is obtained via the following iterative equation: \(X_{n+1} = (aX_n + c)\; mod\; m\)

If \(m\) , \(a\) , \(c\) , and \(X_0\) are integers, then this technique will produce a sequence of integers with each integer in the range \(0 \leq X_n < m\)

The selection of values for \(a\) , \(c\) , and \(m\) is critical in developing a good random number generator.

Blum Blum Shub (BBS) Generator

Blum Blum Shub Block Diagram

Blum Blum Shub Block Diagram

\(n\) is the product of two (very large) primes \(n = pq\).

The seed s should be an integer that is co-prime to \(n\) (i.e. \(p\) and \(q\) are not factors of \(s\)) and not 1 or 0.

Example - Blum Blum Shub (BBS) Generator

i

x_i

B_i

0

20749

1

143135

1

2

177671

1

3

97048

0

4

89992

0

5

174051

1

6

80649

1

7

45663

1

8

69442

0

9

186894

0

10

177046

0

PRNG Using Block Cipher Modes of Operation

Two approaches that use a block cipher to build a PNRG have gained widespread acceptance:

Generic Structure of a Typical Stream Cipher

Typical Stream Cipher

plaintext \(p_i\)

ciphertext \(c_i\)

keystream \(z_i\)

key K

Initialization Value IV

state \(\sigma_i\) next-state function f keystream function g

Stream Cipher Design Considerations

The encryption sequence should have a large period:

A pseudorandom number generator uses a function that produces a deterministic stream of bits that eventually repeats; the longer the period of repeat the more difficult it will be to do cryptanalysis

The keystream should approximate the properties of a true random number stream as close as possible:

There should be an approximately equal number of 1s and 0s

If the keystream is treated as a stream of bytes, then all of the 256 possible byte values should appear approximately equally often

A key length of at least 128 bits is desirable:

The output of the pseudorandom number generator is conditioned on the value of the input key

The same considerations that apply to block ciphers are valid

With a properly designed pseudorandom number generator a stream cipher can be as secure as a block cipher of comparable key length:

A potential advantage is that stream ciphers that do not use block ciphers as a building block are typically faster and use far less code than block ciphers.

Entropy Sources

Comparison of PRNGs and TRNGs

Pseudorandom Number Generators

True Random Number Generators

Efficiency

Very efficient

Generally inefficient

Determinism

Deterministic

Nondeterministic

Periodicity

Periodic

Aperiodic

Conditioning