Random Number Generation

Needs of Random Numbers

• Nonces
• Secret key generation
• Public key generation
• Keystream for a one-time pad

Requirements

• Randomness
  • uniform distribution
  • independence
• Unpredictability
  • cannot infer future sequence on previous values
    • randomness is a specific type of unpredictability characterized by equal probabilities

Random Number Generators

• TRNG (True Random Number Generator)
  • 利用自然現象來產生隨機數
• PRNG (Pseudorandom Number Generator)
• PRF (Pseudorandom Function)

PRNG Requirements

• Randomness (NIST SP 800-22)
  
  • Required Characteristics of Randomness Test
    • Uniformity
    • Scalability
    • Consistency
  • Randomness Tests
    • Frequency test
    • Runs test
    • Maurer’s universal statistical test
• Unpredictability
  • Forward unpredictability
  • Backward unpredictability
• Seed Requirements
  • For cryptographic applications, the seed that serves as input to the PRNG must be secure
  • Because the PRNG is a deterministic algorithm, if the attacker can deduce the seed, then the output can also be determined
  • The seed must be a random or pseudorandom number
  • Typically, the seed is generated by a TRNG recommended by SP 800-90A
    

Pseudorandom Number Generators (PRNG)

• Linear Congruential Generators (LCG)
  • Iterative technique
    
    $$\begin{array}{rlr}m& \text{the modulus}& m>0\\ a& \text{the multiplier}& 0<a<m\\ c& \text{the increment}& 0\le c<m\\ X_0& \text{the starting value, or seed}& 0\le X_0<m\end{array}$$
  • Iterative equation
    
    $$X_{n+1}=(a{X}_n+c)\text{ mod m}$$
    can produce a sequence of integers in the range 0
    $\le$ X_n
    $\le$ m
• Suitable criteria
  • generates a full-period (i.e., [0, m −1])
  • generated sequence should appear random
  • efficient implementation with 32-bit arithmetic

• Weakness
  • an attacker can reconstruct sequence given a small number of values

Blum Blum Shub (BBS) Generator

• take LSB (B_i) from iterative equation:
  
• Features
  • passes next-bit test
    • given the first k bits of the sequence, there is not a practical algorithm that can even allow you to state that the next bit will be 1 (or 0) with probability greater than 1/2
  • security rests on difficulty of factoring n

PRNG Using Block Ciphers

• OFB Mode (for AES-128)
  
  • recommended in X9.82 and RFC 4086
  • Input: 256-bit seed
    • 128-bit encryption key (K)
    • 128-bit initial value (V)
  • Output: 128-bit output block
    
• CTR Mode (for AES-128)
  
  • recommended in NIST SP 800-90A, X9.82, and RFC 4086.
    • implemented on many processor chips
  • Input: 256-bit seed
    • 128-bit encryption key (K)
    • 128-bit initial value (V)
  • Output: 128-bit output block
  • Example
    
• ANSI X9.17 PRNG
  • Input: 56-bit
    $K_1$, 56-bit
    $K_2$, 64-bit
    $D{T}_i$, 64-bit
    $Vi$
    • $D{T}_i$: the i-th date-time value
    • $V_i$: the i-th seed value
  • Output: 64-bit
    $R_i$, 64-bit
    $V_{i+1}$
  • Using 3 Triple-DES encryptions
    

TRNG (True Random Number Generator)

Introduction

• A TRNG uses a nondeterministic source to produce randomness
• Measuring unpredictable natural processes such as pulse detectors of ionizing radiation events, gas discharge tubes, and leaky capacitors

Comparison of PRNGs and TRNGs

Possible Sources of Randomness

• Sound/video input
  • Many computers are built with inputs that digitize some real-world analog source, such as sound from a microphone or video input from a camera.
  • The “input” from a sound digitizer with no source plugged in or from a camera with the lens cap on is essentially thermal noise.
• Disk drives
  • Disk drives have small random fluctuations in their rotational speed due to chaotic air turbulence.
  • The addition of low-level disk seek-time instrumentation produces a series of measurements that contain this randomness.
    • Such data is usually highly correlated, so significant processing is needed.
• Thermal noise
  • Intel has developed a commercially available chip that samples thermal noise by amplifying the voltage measured across undriven resistors

LavaRnd

• LavaRnd is an open source project for creating truly random numbers using
  • inexpensive cameras
  • open source code
  • inexpensive hardware
• taking pictures of the patterns made by the floating material in lava lamps
• using a saturated CCD (Charge Coupled Device) in a light-tight can as a chaotic source to produce the true random numbers

Conditioning

• A TRNG may produce an output that is biased in some way, such as having more ones than zeros or vice versa
• NIST SP 800-90B defines a random process as biased with respect to an assumed discrete set of potential outcomes if some of those outcomes have a greater probability of occurring than do others.
  • Deskewing Algorithms (Conditioning Algorithms)
  • Methods of modifying a bit stream to eliminate the bias
• One approach is to pass the bit stream through a hash function

Linux built-in mechanism for generating random numbers

• Linux uses four entropy sources
  • mouse
  • keyboard activity
  • disk I/O operations
  • specific interrupts
• Bits are generated from these four sources and combined in a pooled buffer
• When random bits are needed the appropriate number of bits are read from the buffer and passed through the hash function

Intel Digital Random Number Generator

• TRNGs have traditionally been used only for key generation and other applications where only a small number of random bits were required
  • This is because TRNGs have generally been inefficient with a low bit rate of random bit production
• The first commercially available TRNG that achieves bit production rates comparable with that of PRNGs is the Intel Digital Random Number Generator (DRNG) offered on new multicore chips since May 2012
  • It is implemented entirely in hardware
  • The entire DRNG is on the same multicore chip as the processors
• Intel Processor Chip with Random Number Generator
  
• Intel DRNG Logical Structure
  
  • Hardware Entropy Source
    • The heart is a pair of inverters that feed each other.
    • Two transistors, driven by the same clock, force the inputs and outputs of both inverters to the logical 1 state.
    • Because this is an unstable state, thermal noise will cause the configuration to settle randomly into a stable state with either Node A at logical 1 and Node B at logical 0, or the reverse.
  • Conditioner Stage
    • The output of the Entropy Source is collected 512 bits at a time and used to feed to two CBC hardware implementations using AES encryption.
    • Each CBC module takes two blocks of 128 bits of “plaintext”
    • For both CBC modules, an all-zeros key is used initially.
      • the output of the PRNG stage is fed back to become the key for the conditioner stage.
      • The output of the conditioner stage consists of 256 bits.
  • PRNG Stage
    • The update function is initialized with all-zeros key and counter = 0.
      • The update function is iterated twice to produce a 256-bit block, which is then XORed with the output of the conditioner stage.
      • The results are used as the 128-bit key and the 128-bit seed for the generate function, which produces 128-bit pseudorandom output.
    • The output is also fed back to be the key for the conditioner stage.

Stream Ciphers

Features

• Can be viewed a pseudorandom equivalent of a one-time pad.
  • The one-time pad uses a long random key, of length equal to the plaintext message.
  • A stream cipher uses a short secret key and a pseudorandomly generated stream of bits
• Encrypt plaintext one byte at a time
• Usually faster than Block Ciphers

Simplified Structure of a Typical Stream Cipher

Generic Structure of a Typical Stream Cipher

• Well-known stream ciphers: RC4, A5, Salsa20, ChaCha20.

RC4

Introduction

• Rivest Cipher 4 (or Ron’s Code 4)
• Stream Cipher designed by Ron Rivest (RSA Data Security Inc.) in 1987
• ARC4 (Alleged RC4): an implementation of RC4
• Widely used Stream Cipher in the Past
• Used in Lotus Notes, Oracle Secure SQL, CDPD (Cellular Digital Packet Data), web SSL/TLS, wireless WEP.
• Variable-length key: up to 2048 bits
• Techniques
  • $8\times 8$ S-box:
    $S_0,S_1,\dots ,S255$ (each has 1 byte)

Something about RC4

• For 7 years it was proprietary (trade secret), and its details were only available after signing a nondisclosure agreement.
• In 1994/9, someone anonymously posted it to the Cypherpunks mailing list (then be spread out widely).
  • However, RSADSI claims that RC4 was still a trade secret even though it was published.
• In the past
  • An agreement between the Software Publishers Association (SPA) and the U.S. gives RC2 and RC4 special status by means of which the export approval process is simpler and quicker than the usual cryptographic export process.
  • To qualify for quick export approval a product must limit the RC2 and RC4 keys size to 40 bits; 56 bits is allowed for foreign subsidiaries and overseas offices of U.S. companies.
• RC Family (by Ron Rivest of RSA Data Security Inc.)
  • RC1: only in notebook
  • RC2
    • Block Cipher
    • Initially, it is a trade secret; later, it is published.
  • RC3: has been broken in development
  • RC4
    • Stream Cipher
    • Initially, it is a trade secret; later, it is posted on the Internet by someone.
  • RC5
    • Block Cipher
    • Its details are published
  • RC6
    • Block Cipher
    • A modified version of RC5 as the proposal for AES

Algorithm

• Initialization of S
  ​​/* Initialization */
  ​​for i = 0 to 255 do
  ​​  s[i] = i;
  ​​  T[i] = K[i mod keylen]
  

  
  ​​/* Initial Permutation of S */
  ​​j = 0;
  ​​for i = 0 to 255 do
  ​​  j = (j + S[i] + T[i]) mod 256;
  ​​  swap(S[i], S[j]);
  

  
• Stream Generation
  ​​/* Stream Generation */
  ​​i, j = 0;
  ​​while (true)
  ​​  i = (i + 1) mod 256;
  ​​  j = (j + S[i]) mod 256;
  ​​  swap(S[i], S[j]);
  ​​  t = (S[i] + S[j]) mod 256;
  ​​  k = S[t];
  

  
• Encryption
  • $P[r]$ denotes the byte of P being encrypted
  • $C[r]$ denotes the corresponding cipher (byte) of
    $P[r]$
    
    $$C[r]=P[r]\oplus k$$
• Decryption
  • $C[v]$ denotes the byte of C being decrypted
  • $P[v]$ denotes the corresponding plaintext (byte) of
    $C[v]$
    
    $$P[r]=C[r]\oplus k$$

Speed Comparison

Security Strength

• Many vulnerabilities have been found
  • The IETF issued RFC 7465 prohibiting the use of RC4 in TLS
  • NIST prohibited the use of RC4 for government use

Salsa20

• Stream Cipher designed by Daniel J. Bernstein in 200
• Features
  • Key sizes: 128 bits, 256 bits.
  • 20 rounds
• Structure: ARX (add-rotate-xor) operations
  • 32-bit addition mod
    $2^{32}⊞$（模加法）
  • constant-distance rotation operations (
    $⋘$)
  • bitwise addition
    $\oplus$ on an internal state of sixteen 32-bit words
  • avoids the possibility of timing attacks in software implementations
• The core function maps a 256-bit key, a 64-bit nonce, a 64-bit counter, and a 128-bit constant to a 512-bit block of the key stream

Internal State

• 16 “32-bit words” arranged as a
  $4\times 4$ matrix.
  
• 8 words (256 bits) Key, 2 words (64 bits) Position/Counter, 2 words (64 bits) Nonce, and 4 words (128 bits) Constant.
  
  • The constant words spell “expand 32-byte k” in ASCII 4 words: “expa”, “nd 3”, “2-by”, and “te k”.

The quarter-round function − QR(a, b, c, d)

• 4-word input
• 4-word output
• 依序運算

b ^= (a + d) <<< 7;
c ^= (b + a) <<< 9;
d ^= (c + b) <<< 13;
a ^= (d + c) <<< 18;

Double-Round

• Odd round
  ​​QR(0, 4, 8, 12)    // column 1
  ​​QR(5, 9, 13, 1)    // column 1
  ​​QR(10, 14, 2, 6)   // column 1
  ​​QR(15, 3, 7, 11)   // column 1
  

• Even round
  ​​QR(0, 1, 2, 3)      // row 1
  ​​QR(5, 6, 7, 4)      // row 1
  ​​QR(10, 11, 8, 9)    // row 1
  ​​QR(15, 12, 13, 14)  // row 1
  

不是 block cipher，block cipher 要整個 block 到齊才會繼續。

ChaCha20

• The Most Widely used Stream Cipher
• 作者與 Salsa 20 相同
• Features
  • A modification of Salsa20
  • New Round Function: increasing Diffusion and Performance
  • Key size: 256 bits.
  • 20 rounds
  • Structure: ARX (add-rotate-xor) operations（跟 Salsa 20 相同）
  • The core function maps a 256-bit key, a 64-bit nonce, a 64-bit counter, and a 128-bit constant to a 512-bit block of the key stream
  • Google has selected ChaCha20 along with Bernstein’s Poly1305 message authentication code as a replacement for RC4 in TLS.
  • ChaCha20 is also used for the arc4random random number generator, instead of the broken RC4, in FreeBSD, OpenBSD, and NetBSD operating systems

ChaCha20 Internal State

• 16 32-bit words arranged as a 4x4 matrix.
  

New Initial State

• 4 words (128 bits) CONSTANT, 8 words (256 bits) KEY, 2 words (64 bits) COUNTER, 2 words (64 bits) IV (Nonce)
  
  • CONSTANT words spell “expand 32-byte k” in ASCII 4 words: “expa”, “nd 3”, “2-by”, and “te k”.
• The original ChaCha20 cipher with a 64-bit nonce and a 64-bit counter, allowing a practically unlimited amount of data to be encrypted with the same (key, nonce) pair.
• The IETF variant increases the nonce size to 96 bits, but reduces the counter size down to 32 bits, allowing only up to 256 GB of data to be safely encrypted with a given (key, nonce) pair.

New quarter-round function − QR(a, b, c, d)

• 4-word input
• 4-word output

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

New Double-Round