Relation between key size and PRNG state size

Question

Some (supposedly) cryptographically secure PRNGs have an internal state of only 160 bits or less. When the algorithm is otherwise properly designed, that seems like enough to generate a 128 bit key for e.g. AES.

Can the PRNG also be used for the generation of longer keys, e.g. RSA keys with 1024 bits?

My intuition is that it would take (on average) a brute force attack of 2^159 key generations to find the same key, which is probably harder than factoring the 1024 bit key (according to various key length comparisons).

Is there an easier way to crack an RSA key generated using such a PRNG? The OpenSSL PRNG documentation states that an internal state of at least 4096 bits is required to securely generate an RSA-4096 key; that would contradict my intuition.

Answer 1

Your intuition is correct.

While more bits of entropy is better when generating a key, attacking RSA through the key generation process is an independent attack of factoring the modulus, and is predicated on a different computational hardness assumption, search of the keyspace compared to the hidden subgroup problem for finite Abelian groups (for factoring or discrete logarithm.) Factoring at least seems subexponential but superpolynomial, so is significantly easier than search; Many search problems appear to be NP hard, with exponential time complexity in the average case.

The attack on the key generation process depends on the cryptographic strength of the PRNG, and is analogous to attacking a symmetric ciphers in many ways. Since the attacks against PRNG's are so similar to attacks against symmetric ciphers, you can use the guides at keylength for symmetric ciphers as guides to the minimum state for key generation as its entirely appropriate. If you're using RSA for key exchange, and your symmetric key length is smaller than the key length of your PRNG seed, they won't bother attacking the key generation process.

The question does highlight a very important concern about prudent cryptography however, and that is that key generation is highly vulnerable to attack by poor implementation. A cryptographically secure PRNG is essential if using a PRNG for key generation.

Answer 2

To generate an RSA key, you need lots of random bits – more than 4000 for a 4096-bit key (usually more than the key size, since you need to throw away and retest parts if the prime tests fail).

Now, to generate an RSA key, you would love to have the bits being uncorrelated. But if your PRNG has 160 bits of state, you cannot get even 200 uncorrelated entirely random bits out of it. Most of the time, you can get a bit more than the state size safely, but they will obviously not be entirely random, only oh point something random, and not necessarily uncorrelated. The quality of the output of a PRNG is debatable; for example, arc4random(3) is a “stretching RNG” which means that it distributes the entropy in its about 1696 bit of state mostly uniformly across the output (notwithstanding RC4 early keystream bias: the first 3072-plus-some aRC4 output bytes are thrown away), whereas others “exhaust” their full entropy in the first pool-sized read and then are merely pseudo-random (i.e. zero mathematical entropy afterwards); AFAICT the Linux/BSD /dev/urandom device belongs into this category except that reads cause stirs which increase entropy – more, the more consumers are using the RNG at the same time).

So, this is really a “depends” question. It depends on the security level you want (160 bits of state for an 4096-bit RSA key is really a bit few, but might work for an 1024-bit RSA key, but definitely not for an 1024-bit DSA key) and, to some extent, the properties of the RNG chosen. The general answer is: no, you cannot use a n-bit state RNG to generate an RSA key with n or more bits of size.

「Is there an easier way to crack an RSA key generated using such a PRNG?」 – Yes, but the details may or may not be worth it. For an extreme, see the Debian OpenSSL RAND_add fiasco, in which the entire key space was, IIRC, 32768 * 2 possible keys, for each key bit size, making it utterly easy to precompute them all (for a few given key bit sizes).