Cryptography Fundamentals - Chapter 8 (Real World Cryptography)

Core Concepts of Randomness and Entropy

• The Ubiquity of Randomness: Randomness is essential to nearly all cryptographic algorithms, including secret keys, nonces, Initialization Vectors (IVs), prime numbers, and challenges. The only major exception is hash functions.

• Entropy in Information Theory: Information theory suggests the term "entropy" to quantify the degree of randomness in a string. This concept originates from the work of $\text{Claude Shannon}$.     * High Entropy: Corresponds to high randomness and low information. High entropy strings are less predictable.     * Low Entropy: Corresponds to low randomness and high information. Low entropy strings are more predictable.

• Cryptography Requirement: For security purposes, randomness must be fundamentally unpredictable.

Distribution Types and Probability

• Uniform Randomness: Occurs when all possible values within a set are equally likely to be selected.     * Bit String Definition: Unless otherwise defined, the set of "all possible values" refers to the bit strings of the size of the variable being considered.     * Probability Calculation: For an $8$-bit variable, there are $2^8 = 256$ combinations. The probability of picking any specific number in a uniform distribution is $\frac{1}{256}$.

• Non-Uniform Randomness: Occurs when all possible values within the set are not equally likely to be selected. Different combinations have different chances of being picked.

Types of Random Number Generators

• True Random Number Generators (TRNGs):     * Nondeterminism: True randomness implies nondeterminism. If a process is deterministic, it can be predicted, meaning it is not truly random.     * Definition: True random can be defined as having "infinite unknown variables."     * Physical Phenomena: TRNGs often use unpredictable physical phenomena, such as thermal noise, to extract randomness.     * Performance Bottleneck: Extracting randomness from physical noise is a slow process. This can become a bottleneck for applications requiring high volumes of random numbers quickly.

• Pseudorandom Number Generators (PRNGs):     * Definition: Pseudorandom can be defined as having "too many unknown variables to predict."     * Architecture: A PRNG starts with an initial secret called a seed, which is created by mixing various entropy sources.     * Functionality: PRNGs can produce large volumes of random numbers very quickly from the initial seed.     * Alternative Terminology:         * CSPRNGs: Cryptographically Secure PRNGs.         * DRBGs: Deterministic Random Bit Generators (nomenclature used specifically by $\text{NIST}$).

Technical Mechanics and Security Properties of PRNGs

• PRNG Workflow Model:     1. Seed Initialize: The seed sets the initial state.     2. Update State: The generator transitions from one state to the next.     3. Generate Output: The "next" function produces a random number based on the state.

• Core Properties:     * Deterministic Nature: Using the same seed twice will produce the exact same sequence of random numbers. If the seed is known, the output is completely predictable.     * Indistinguishability: In practice, outputs must be indistinguishable from a uniform random distribution. Observing random numbers alone should not allow an attacker to recover the internal state.     * Prediction Resistance: It should be impossible to observe produced random numbers and predict future numbers or recover previously generated ones.

• Specific Security Guarantees:     * Forward Secrecy: If an attacker compromises the internal state at a specific time, they cannot use that state to retrieve previously generated random numbers.     * Backward Secrecy (Healing): This property ensures that obtaining the current state does not allow an attacker to determine all future numbers. This is achieved by "healing" the PRNG through periodic re-seeding/re-injecting new entropy.

Randomness in Practical Operating Systems

• The OS Bundle: Operating Systems generally bundle three components to provide randomness interfaces to developers:     1. Noise Sources: Raw randomness from thermal levels or mouse movements.     2. Cleaning and Mixing: Processes to improve the quality of raw randomness, which may be biased.     3. PRNGs: High-speed generators seeded by the cleaned/mixed values.

• Unix-like Systems (/dev/random vs /dev/urandom):     * $/dev/random$: Blocks the system until initial seeding is complete. Generally used for legacy or highly sensitive early-boot requirements.     * $/dev/urandom$: Never blocks. It is considered secure after the initial boot phase and offers high speed with unlimited output. It is used for standard cryptographic needs.     * Entropy Warning: $/dev/urandom$ may not provide enough entropy if used too early after a device boots.

• Modern System Calls:     * getrandom: Available on Linux and $\text{FreeBSD}$. It functions similarly to $/dev/urandom$ but will block if the PRNG has not been properly initialized with enough entropy. It is the recommended method.     * BCryptGenRandom: The system call provided by Windows for generating randomness.

• Programming Language Abstractions:     * It is recommended to use standard libraries (e.g., $\text{Golang's}$ $crypto/rand$ package) rather than insecure versions (e.g., $math/rand$).     * Note: The $getrandom$ call returns a maximum of $256$ bytes per call.

Operational Pitfalls and Edge Cases

• Forking Processes: In userland PRNGs, a program that forks creates a child process with the same state as the parent. Both will produce identical random sequences unless they are re-seeded with different values.

• Virtual Machines (VMs): If a VM state is saved and restarted multiple times (cloning), every instance might produce the exact same sequence of random numbers from that state onward.

• Early Boot Entropy: Embedded or headless systems lack user-driven noise. They may boot in a similar fashion and end up with identical initial noise, resulting in identical seeds and identical random sequences across different devices.

Public Randomness and Verifiable Random Functions (VRFs)

• Concept: While private randomness (keys) is most common, public randomness is used when privacy is not required but verifiability/unpredictability is.     * One-to-Many: One producer generates randomness for many participants to verify.     * Many-to-Many: A set of participants produces randomness together.

• Verifiable Random Function (VRF) Implementation:     1. A signer generates a key pair and publishes the verifying key and a fixed public seed.     2. The signer signs the public seed and hashes the signature to create a random number.     3. The signature is published as proof.     4. Validators hash the signature to check if it matches the random number and use the verifying key/public seed to confirm the signature is correct.

• Security of VRFs: Because the signature is unique (using schemes like $\text{BLS}$) and the seed is fixed, the signer cannot alter the random number without being detected. Multiple numbers can be generated by using the seed as a counter.

Key Derivation Functions (KDFs)

• Definition: KDFs are used for "key stretching"—deriving several secrets from a single initial secret.

• Differences from PRNGs:     * Input Tolerance: KDFs do not require uniformly random secrets as input; they can handle biased results (like key exchange outputs) as long as entropy is high.     * Output Output: KDFs are generally deterministic (to allow participants to re-derive keys) and are not intended to produce a large volume of data.

• HMAC-based Key Derivation Function (HKDF): Defined in $\text{RFC 5869}$, it is commonly used with $\text{SHA-2}$.     * HKDF-Extract: Removes biases from the input to produce a uniformly random secret. Uses a salt (an optional, non-secret value) to differentiate usage within a protocol.     * HKDF-Expand: Produces arbitrary length output from the uniform secret. It uses an info argument to differentiate between protocols.     * Output Limits: HKDF is limited by the hash function size. For $\text{SHA-512}$ ($512$ bits) over $255$ HMAC iterations, the limit is $512 \times 255 = 16,320$ bytes.     * Related Outputs: Calling HKDF-Expand with identical parameters but different requested lengths results in the same output truncated to different lengths.

• SHA-3 Alternatives: Extended Output Functions (XOFs) like $\text{SHAKE}$ and $\text{cSHAKE}$ can serve as KDFs. $\text{KMAC}$ avoids "related output" issues because its length argument acts as a customizer.

Principles of Key Management

• Goal: Managing the storage and protection of sensitive secrets and preparing for potential compromise.

• Key Rotation: Associating expiration dates with keys and replacing them periodically to "heal" from eventual compromise.

• Key Revocation: The ability to cancel a key immediately once it is known to be compromised, often requiring a system to check revocation status before use.

Questions & Discussion

• Interaction: The presentation concludes with a slide reserved for audience questions (Slide 33).