2015 - Philippe Arteau

### Overview In this presentation, Philippe Arteau examines the security weaknesses of non-cryptographic pseudo-random number generators (PRNGs), focusing specifically on linear congruential generators (LCGs). While PRNGs are designed for speed and uniform distribution in non-security contexts (like games), developers frequently misuse them for sensitive tasks like generating unique identifiers or password reset tokens. The talk explores the internal mechanics of LCGs, walks through how an attacker can recover internal states and predict tokens, and demonstrates exploitation tooling.

### Key Topics - **PRNG Categories & Implementations**: Broad comparison of PRNG types found across programming environments, contrasting LCGs with Mersenne Twister (e.g., PHP's `mt_rand`) and runtime-specific generators (such as Pearl or V8). Standard non-cryptographic APIs prioritize execution performance and even distribution, whereas cryptographic APIs (like Java's `SecureRandom` or C#'s `RNGCryptoServiceProvider` under the cryptography namespace) enforce unpredictability. - **Misconceptions in Framework Code**: A code pattern identified in Java frameworks such as Struts and Spring where developers attempt to harden randomness by initializing `java.util.Random` with a seed from `SecureRandom`. While the initial seed is strong, the subsequent state updates remain bound to the predictable LCG algorithm. - **LCG Mechanics and Weaknesses**: Explanation of standard LCG state transitions involving multiplication by large constants, addition of small constants, modular/overflow truncation, and discarding the least significant bits to produce output integers.

### Technical Details In Java's LCG implementation, each step updates a 48-bit internal state. The transition multiplies the state by a constant, adds a value (such as `0xBL`), and masks off bits to retain 48 bits. To output a 32-bit integer (`nextInt()`), the generator takes only the most significant 32 bits from the internal 48-bit state, discarding the lower 16 bits.

Because only 16 bits of internal state are truncated per generated integer: - An attacker observing two consecutive 32-bit integers can brute-force the missing 16 bits (65,536 possibilities) to determine the exact internal 48-bit seed. - If an API generates a 64-bit `long` (via `nextLong()`), it concatenates two sequential 32-bit outputs. A single observed 64-bit value or 8-byte token provides enough state to recover the generator's seed directly without needing multiple separate requests. - When values are mapped onto custom alphabets (such as alphanumeric strings for tokens), additional bits of information are lost, requiring more sample observations and additional brute-forcing.

### Practical Exploitation & Tooling The speaker demonstrates how to conduct state recovery during penetration testing using the tool **prankster** (contrasted with **untwister**, which targets Mersenne Twister): 1. **Sample Gathering**: An attacker requests password reset tokens for accounts they control, logging sequential token values into an input file (`input.txt`). 2. **Parameter Deduction**: The attacker determines or guesses the target PRNG algorithm (e.g., `prng_java` for JVM/Tomcat applications) and the character alphabet used to represent the token. 3. **Seed Recovery**: Running prankster with the recovery flag (`-r`), algorithm, alphabet, and input samples calculates the underlying internal PRNG state preceding the observations. 4. **Next-Value Prediction**: Using the recovered seed along with prankster's generation parameters, the attacker computes subsequent tokens, allowing them to predict sensitive values—such as a password reset token triggered for a victim's account.

### Takeaways Non-cryptographic PRNGs like LCGs cannot be retrofitted for security simply by seeding them securely. Penetration testers can reliably reconstruct generator states with few samples (as few as two integers or one long) using tools like prankster, reinforcing that cryptographically secure PRNGs must always be used when generating tokens, identifiers, and sensitive values.