Comment by dragontamer
7 years ago
> Attacking a single 256 bit key is exactly as equally impossible as attacking a 256 bit RNG pool used to generate 100 keys.
But both are strictly easier than attacking 100x independently created 256-bit keys. The /dev/random case.
> If you're trying to prove that Aleph-one is greater than Aleph-0
I mean, yeah, that's basically the argument I have. 256-bits of entropy are probably enough for your application, but you cannot under any circumstances tell me that its the same as 25,600 bits of entropy. That's what /dev/random vs /dev/urandom comes down to. For most people in most situations, its almost inconceivable to imagine an application that needs more than 256-bits of true high quality entropy.
EDIT: A POTENTIAL case, which I admit I haven't though too much about... is a 2048-bit RSA key. I assume the RSA key needs to be generated with 2048-bits of true entropy (please correct me if I'm wrong), but the bits-of-security are far less than that, because RSA doesn't scale like other encryption schemes. So your 2048-bits of entropy RSA-key only scales to 128-bits of security.
If your 2048-bits of entropy RSA-key ended up to only have 256-bits of entropy generating it, you're possibly in bad luck (only 16-bits of entropy assuming a similar scaling factor). I'm not a specialist in the math, but... not all cryptographic primitives scale 1-to-1 with the input entropy source.
> > Attacking a single 256 bit key is exactly as equally impossible as attacking a 256 bit RNG pool used to generate 100 keys.
> But both are strictly easier than attacking 100x independently created 256-bit keys. The /dev/random case.
Both are impossible. Like, 'Solar System turned into thermodynamically optimal computronium fails' impossible. (seriously - '((mass of solar system * (speed of light)^2) / 0.0172 electronvolts ) / (2^256)' for calculations performed at 20C [0], and that evaluates to 5*10^-10. Drop the assumed temperature to 2.75K - the cosmic background temperature - and the energy per computation drops by a factor of several hundred, but that's still not nearly enough)
Or, put another way - if you can bruteforce 2^256, you can do that 100 times. (Even if you encrypt an object 100 times, you'll still only need to do ~2^264 work - not 2^25600)
0: https://en.wikipedia.org/wiki/Landauer%27s_principle
RSA-2048 is only about 112 bits of security because index calculus methods of breaking RSA-2048 (and DHE-2048) have an algorithm with ~2^112 steps to break it, not because of the amount of entropy used to generate the key [4].
An RSA-2048 keypair is generated by taking a CSPRNG like the one I proposed, generating 1024 bit numbers, checking them for being a prime number using Miller Rabin [1] until the chance of the number not being prime is below 2^-128 (generating new candidate primes if the current one turns out to be not prime), and then doing it all over again for the other prime. The two 1024 bit probably-primes "p" and "q" are the private key, their product "n" (with the public exponent e=65537) is the public key. Most systems precalculate some derived values used to speed up operations and store them with p and q, but you don't have to [2][3].
The RNG I proposed is absolutely good enough to generate RSA key pairs. There is no benefit to using "true hardware randomness" for generating candidate primes, after the initial pool of 256 bits of entropy has been generated.
1 - https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...
2 - https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generat...
3 - https://tools.ietf.org/html/rfc8017#section-3.2
4 - https://crypto.stackexchange.com/a/8692/24949