Chapter 6: Randomness Flashcards
Why and where do we need random numbers?
- Challenges (nonces) used in challenge-response protocols
- Initialization vector (IV) for block cipher modes of operation (CBC, OTF, CTR)
- Secret keys for symmetric ciphers
- Secret keys for Message Authentication Codes
- Generation of asymmetric keys used by SSH, in X.509 or S/MIME certificates
- Session keys in cookies to identify web sessions
- “Randomness” can be described by unpredictability…
- … and unpredictability is good for security, as an attacker, e.g., cannot predict a secret key.
- A measure for “unpredictability” is “entropy”
- Let X be a random variable which outputs a sequence of n bits, e.g. X = {0,1} or X = {00,01,10,11}, etc.
Entropy of a 128 Bit Vector
* A key of 128 Bit (=16 Byte) should have an entropy of 128
* Let us assume we obtained a key from a random variable.
* What is the entropy of this key?
Collecting Entropy
* Hardware-based (Approach: observe physical non-predictable phenomena)
* …
* Thermal noise from a semiconductor diode or resistor
* …
* The amount a metal insulator semiconductor capacitor is charged during a fixed period of time
*
* Lava lamps
Time between emission of particles during radioactive decay
Frequency instability of a free running oscillator
Noise of microphone or camera
- Software-based collection of entropy
- The system clock (Caution: …)
- …
- …
- Content of buffers
- In practice: use /dev/random and combine sources!
low entropy → attacker might guess correct time)
User input (mouse movement, keystrokes, time between keystrokes, etc.)
OS stats, e.g. network or CPU load
Attacker must not be able to guess/influence the collected values
Pseudo-Random Number Generator (PRNG)
- Getting entropy is expensive
- Pseudo-Random Number Generator (PRNG):
- ‘Cheap’ randomness
- Deterministic algorithm
- Input: Small amount of initial entropy, ideally from a hardware RNG (Seed)
- Output: Sequence of random-looking numbers calculated using the seed as input
Pseudo-Random Number Generator – Example
Cryptographically Secure Pseudo Random Number Generator (CSPRNG)
- Important: The length of the seed should be large enough to make brute-force search over all seeds infeasible
- The output should be indistinguishable from truly random sequences:: …
- The output should be unpredictable for an attacker with limited resources, without knowledge of the seed::…
- No polynomial-time algorithm can correctly distinguish between an output sequence of the generator and a truly
random sequence - No polynomial-time algorithm can predict the next bit of the generator with probability > 0.5 (“next-bit test”)
Cryptographically Secure Pseudo Random Number Generator (CSPRNG)
- Mathematically proven CSPRNG:
- Used in practice:
- A CSPRNG produces a bitstring of 2048 bit
- What is the max. possible entropy of this string?
- min(Length of the seed, 2048)
- usually: Length of the seed
