Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Randomness Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### Uses for Randomness in Cryptography

• Large primes
• Random numbers to test for primality
• Random bases in probabilistic primality tests

• RSA encryption, RSA digital signatures
• Random large primes p and q
• Random seed in PKCS #1 Optimal Asymmetric Encryption Padding (OAEP)
• Random salt in PKCS #1 Probabilistic Signature Scheme (PSS)

• Diffie-Hellman key exchange, El Gamal encryption, El Gamal digital signatures, DSA
• Random large prime modulus p and generator g
• Secret random exponents

• Elliptic curve versions of the above
• Elliptic curve group parameters p, a, b, g (e.g. NIST curves)
• Secret random multipliers

• Kerberos
• Random nonces and subkeys

• Transport Layer Security
• Random nonces R1 and R2

### True Random Sources

• A.k.a. entropy sources

• Manual — flipping coins, rolling dice

• The OS kernel's entropy source
• Linux: /dev/random
• Collects entropy from keyboard timings, mouse movements, and I/O device timings

• Hardware random number generators
• I have a TectroLabs TL200 unit
• Many other vendors sell similar units

• Random.org
• Measures radio frequency atmospheric noise and turns it into random numbers

• These generate "true" randomness — not repeatable

### Pseudorandom Number Generators

• Pseudorandom number generator (PRNG) operation
• Initialize PRNG algorithm with a seed
• Use the PRNG to generate an arbitrarily-long random-looking sequence of bits
• Two instances of a PRNG algorithm initialized with the same seed will generate the same bit sequence
• Two instances of a PRNG algorithm initialized with different seeds will generate different bit sequences

• Motivation for PRNGs
• True random sources are typically much slower than PRNG algorithms
• True random sources are not practical if large quantities of random data are needed
• True random sources cannot generate repeatable bit sequences — as might be needed for testing, for example
• Solution: Initialize a PRNG with a seed obtained from a true random source

• Requirements for cryptographically strong PRNGs
• After observing any subset of the output sequence, an adversary must not be able to:
• Deduce any earlier part of the output sequence
• Deduce any later part of the output sequence
• Deduce the internal state of the PRNG algorithm
• Deduce the seed
• Many standard PRNG algorithms (e.g., class java.util.Random) do not meet these requirements

• Bernstein's Fast-Key-Erasure Random Number Generator (RNG)
• https://blog.cr.yp.to/20170723-random.html
• Uses a block cipher, e.g. AES with a 256-bit key, in counter mode
• Initialize the key K from a true random source
• Thereafter, run this algorithm (quoting Bernstein):
• "Starting from the 256-bit key K, generate (say) 48 blocks B0 = AESK(0), B1 = AESK(1), ..., B47 = AESK(47). This is a total of 768 bytes of AES output.
• "Immediately overwrite the key K with the first two blocks B0, B1.
• "Use the other blocks B2, ..., B47 as 736 bytes of RNG output, of course erasing each byte as soon as it is consumed.
• "Start over with the new key."

• NIST standard for deterministic random bit generators (DRBGs)

• NIST's Hash_DRBG algorithm • Hash_DRBG initialization
• seed_material = entropy_input || nonce || personalization_string
• seed = Hash_df (seed_material, seedlen)
• V = seed
• C = Hash_df ((0x00 || V), seedlen)
• reseed_counter = 1

• Additional DRBG algorithms in Special Publication 800-90A
• HMAC_DRBG — based on a keyed hash (MAC) algorithm
• CTR_DRBG — based on a block cipher in counter mode

• NIST is working on additional Special Publications for:
• Entropy sources
• Random bit generator (RBG) constructions

### Statistical Test Suites

• Try to distinguish the output of a PRNG from a true random source

• NIST Statistical Test Suite
• A. Rukhin et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800-22, Revision 1a, April 2010. http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf
• Was used to evaluate the randomness of AES with various modes of operation
• Many authors of published cryptographic algorithms run the NIST Statistical Test Suite on their algorithms

• The NIST Statistical Test Suite is well suited for testing:
• Stream ciphers
• Pseudorandom number generators
• Algorithms producing arbitrary-length bit sequences

• The NIST Statistical Test Suite is not well suited for testing:
• Block ciphers
• Hash functions
• Message authentication codes
• Algorithms producing fixed-length bit sequences
• The outputs of such algorithms are typically too short for the statistical test results to be valid

• Alternative: Kaminsky's CryptoStat test suite

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005