Relation between key size and PRNG state size

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.

-
+1 interesting question. "bits" in RSA and symmetric crypto mean vastly different things. 4096 bits in RSA means the size of the semiprime, while 160 bits in symmetric crypto means a keyspace with $2^{160}$ elements. Do you really need a keyspace of 4096 bits in RSA to achieve 4096 bits of security in RSA, or is say 128 bits enough, assuming that you use that keyspace to generate 4096 bit semiprimes? – orlp Sep 10 '13 at 5:38
I'd use a pool size twice the security level to avoid collisions during the one-way function step. The trickier part are the additional accumulator pools a fortuna like construction needs. – CodesInChaos Sep 10 '13 at 7:28
@nightcracker Generating an RSA 1024 key from a 128 bit seed is completely fine. For 4096 bit RSA I'd use a 256 bit seeds. – CodesInChaos Sep 10 '13 at 7:31
Then again, generating a 1024 key in itself is not fine, that key size should no longer be used. – Maarten Bodewes Apr 19 '14 at 20:51

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.

-

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).

-
@downvote: care to comment? – mirabilos Jan 6 '14 at 23:50
I didn't give the downvote, but I suspect whoever did downvoted because your answer swerves between correct statements and total nonsense. Statements like "the quality of the output of the PRNG is debatable" is questionable; there exist high quality CSPRNGs that are effectively indistinguishable from random given 160 bits of seed. I have also no idea why you say "160 bits of state is definitely not (enough) for a 1024-bit DSA key". And, your general answer of "no, you cannot use a n-bit state RNG to generate an RSA key with n or more bits of size" is wrong. – poncho Jan 7 '14 at 1:32
“Statements like "the quality of the output of the PRNG is debatable" is questionable; there exist high quality CSPRNGs” yes, but not all PRNGs are “high quality CSPRNGs”, that's what I meant, that the choice of RNG affects the answer. – mirabilos Jan 7 '14 at 1:34
“that are effectively indistinguishable from random” does not mean that every bit is fully (1.000000) random – mirabilos Jan 7 '14 at 1:35
“I have also no idea why you say "160 bits of state is definitely not (enough) for a 1024-bit DSA key".” ← That is because DSA is weak in the face of bad entropy. – mirabilos Jan 7 '14 at 1:35