Would knowing the random seed help to break AES or similar?

Question

Consider I knew the seed of the random number generator that Bob uses to send encrypted emails to Alice. Would I have an advantage in deciphering the message? Also, how does, for example, openssl generate a completely random seed so the rest of the generated sequence isn't discovered? Am I missing something here?

Answer 1

Yes, it can hugely help. There are many examples, but the DUHK attack is as good as any. This allows you to passively attack cryptosystems with the following characteristics:

• It uses the X9.31 random number generator

• The seed key used by the generator is hard-coded into the implementation

• The output from the random number generator is directly used to generate cryptographic keys

• At least some of the random numbers before or after those used to make the keys are transmitted unencrypted. This is typically the case for SSL/TLS and IPsec.

The reason it is specific to the X9.31 PRNG can be found here (in short, X9.31 has a "long term seed key"). The idea is that if you know the long term seed key, and see some direct output (the 4th assumption), you could recover the state of the PRNG, which is then sufficient (via the 3rd point) to recover the generated cryptographic keys.

Heuristically, if your PRNG starts with too little entropy, the outputs of it are "less random" than other parts of the protocol assume, which can break the other parts of the protocol.

---

As for how devices generate random seeds, they typically poll a system RNG (typically /dev/urandom/ on UNIX devices). How does /dev/urandom/ generate random numbers? From the environment (see here for some discussion). I do not know what is currently used in each device/OS, but generally (theoretical) cryptographers mention things like:

• Measuring temperature fluctuations on the CPU
• Measuring timings on various input devices (keyboards/mice), and in general other "random" information from external devices

These may not all be used in practice, but give some intuition for what "random sources" a device may have available to it. Note that certain devices (say embedded devices) may have less sources available --- this has led to attacks on embedded systems. A followup paper to an attack. This paper includes the following motivation of their work:

Motivation: Our work is inspired by the recent paper of Heninger, Durumeric, Wustrow, and Halderman [16], which uncovered serious flaws in the design and implementation of the Linux kernel’s randomness subsystem. This subsystem exposes a blocking interface (/dev/random) and a nonblocking interface (/dev/urandom); in practice, nearly all software uses the nonblocking interface. Heninger et al. observe

1. that entropy gathered by the system is not made available to the nonblocking interface until Linux estimates that 192 bits of entropy have been gathered, and

2. that Linux is unnecessarily conservative in estimating the entropy in events, and in particular that on embedded systems no observed events are credited with entropy.

These two facts combine to create a “boot-time entropy hole,” during which the output of /dev/urandom is predictable.

The Linux maintainers overhauled the randomness subsystem in response to Heninger et al.’s paper. The timing of every IRQ is now an entropy source, not just IRQs for hard disks, keyboards, and mice. Entropy is first applied to the nonblocking pool, in the hope of supplying randomness to clients soon after boot. (Clients waiting on the blocking interface can block a bit longer.)

Note that the Heninger et al attack mentioned was the Mining your P's and Q's attack, which was an attack on RSA. RSA has a public key which contains $n_i = p_iq_i$, the product of two semiprimes. The attack essentially collected many $n_1,\dots, n_k$ RSA moduli, then searches (pairwise) for common divisors among all of them (which can be made quite efficient). Any such common divisor allows you to factor two moduli. If PRNGs were working properly then the theory behind this predicts this will fail. This attack exposed that the PRNGs were not working properly, due to insufficient entropy early in the boot process in embedded devices.

Note that "insufficient entropy" can be viewed as "having some partial information about the seed". Knowing the seed completely is an extreme example of this, and while this won't necessarily mean every cryptosystem breaks, many break from weaker assumptions.