0
$\begingroup$

So in OpenSSL you have the -engine tag for inputting your own entropy as a source for generating whatever.

  1. So if you wanted to generate a 2048-bit RSA certificate how much entropy would you need for it to be secure?
  2. Is 1 truly random byte or even one bit of entropy enough for generating a secure certificate?
  3. Do you need more entropy for bigger certificates?
  4. Is the entropy used raw or is it mixed with something else (in the case of openssl -engine)?
$\endgroup$
  • 1
    $\begingroup$ Are you asking how much entropy is necessary to generate a new key and its self-signed certificate? Or for generating a certificate for an existing key? The later might require no entropy at all (discounting that used for protection against side channels), depending on parameters. For the former, refer to Thomas Pornin's answer. Also: according to this and this, in openssl key generation, what follows the -engine parameter is not data used as raw entropy. $\endgroup$ – fgrieu Jun 13 '17 at 21:00
  • 1
    $\begingroup$ Note that the -engine flag can do more than just provide an entropy source, it can also be used to specify a cryptographic module to be used (ie a HSM or a smart card) which would maybe also handle key storage and carrying out of operations. $\endgroup$ – SEJPM Jun 13 '17 at 21:52
  • 1
    $\begingroup$ (@fgrieu) in particular when issuing a cert for someone else who may try to cause a signature collision and thereby forge a different and improper cert (google hashclash and shattered+cryptography) the issuing process must use sufficient entropy to block that. CABforum baseline reqts currently say 'at least 20 bits' in SerialNumber, which precedes all adversary/requester-chosen data. $\endgroup$ – dave_thompson_085 Jun 14 '17 at 0:05
  • $\begingroup$ @dave_thompson_085: yes, I'm also a supporter of unpredictable prefix (certificate serial number) to mitigate hash collision attacks; that was intended to be included in my depending on parameters :-) $\endgroup$ – fgrieu Jun 14 '17 at 9:41
  • $\begingroup$ new related question, maybe? crypto.stackexchange.com/questions/48292/rsa-size-of-n-p-and-q $\endgroup$ – daniel Jun 14 '17 at 20:28
11
$\begingroup$

The answer to "how much entropy" is always "128 bits".

The tricky point is that the term "entropy" is very often misused. In general terms, the situation is the following:

  • A computer is a deterministic machine. From knowledge of its complete state (contents of disk, RAM and CPU registers) at a time $T$, one can compute its behaviour and state at any time $T' > T$, as long as no new unknown information is injected. Conceptually, this is about simulating the machine.

  • The attacker's goal is to try to recover the state at the time of key generation, in order to be able to simulate the key generation process and thus obtain the private key. However, the attacker does not know everything about the state, so he will have to "guess", i.e. to try possible values for the information he lacks. This is known as "brute force".

  • "That which the attacker does not know" can be quantified into the notion of "entropy": we will say that the state has an entropy of $n$ bits if the best possible brute force strategy will require, on average, $2^{n-1}$ tries before hitting the right one.

    Note that this notion does not require that the unknown information is exactly a sequence of uniformly random bits. The definition is such that if the attacker knows everything except $n$ bits, which are (from the point of view of the attacker) exactly random, uniform, and independent of each other, then the entropy is $n$ bits. In a more practical setup, the "entropy bits" come from measures of physical events (e.g. precise timing of interrupts originating from the hardware); these measure will be encoded over a lot more than $n$ bits. This is not that much a problem since we can always somehow "concentrate" entropy bits by hashing all them together.

If the attacker-unknown data is a single byte, then the attacker will just have to try at most $256$ possible values (and on average $128$) to recover the private key. This is the same as saying that 8 bits cannot contain more than 8 bits of entropy (and may contain less if the attacker has some partial knowledge of the byte, e.g. he knows whether some values are more probable than other).

The amount of needed entropy is basically: "enough to make brute force stupidly expensive". "128 bits" are the traditional value for "way too much" (it's the new tradition; twenty years ago, we would have used 80 bits, but the relentless advances in technology and economics make an $2^{80}$ computation task less ludicrous than what it used to be). If your private key is generated with a cryptographically secure PRNG which is itself seeded with attacker-unknown data that cumulate at least 128 bits of entropy, then, by definition, brute-forcing that entropy is unfeasible (the attacker won't be able to try more than a negligibly small fraction of the space of possible values), and the job is done.

Note that an attacker gets to choose between trying to brute-force the generation seed, and trying to unravel the private key from the public key using its mathematical structure (e.g. trying to factorize the modulus, in the case of RSA keys). He will use the strategy that is easiest for him. In that sense, you "just" need enough entropy to make mathematical breaks easier than PRNG seed brute-force. In practice you inject enough entropy to make brute-forcing unfeasible, and you use asymmetric keys such that mathematically breaking them is not feasible either (e.g. with RSA, use 2048 bits or more).

Some people argue that if quantum computers ever come to fruition, then, in some sense (and with a lot of usually unspoken caveats), an attacker with a quantum computer could quantum-brute-force an $n$-bit PRNG seed with cost $2^{n/2}$ only (with a variant of Grover's algorithm); thus, "256 bits" would be needed to protect against that. On the other hand, a working quantum computer would break through the mathematics of a RSA, DSA, DH or elliptic curve key with extreme efficiency, making the point moot: as long as you use RSA, you are making the bet that quantum computers do not exist (and, for now, this is not that bad a bet).

$\endgroup$
  • $\begingroup$ I thought you'd need enough to make 2 random primes (that are nearly but not quite the same number of digits long), that multiply to make the key. So roughly 2 * sqrt (2048 bits) . $\endgroup$ – daniel Jun 13 '17 at 20:04
  • $\begingroup$ I am no mathematician or anything , I am just interested in the practical part . So is the entophy used raw ? and how muc is secure in !!!!OPENSSL!!!! $\endgroup$ – Richard R. Matthews Jun 13 '17 at 20:24
  • $\begingroup$ I can never understand why always 128 bits. Having typed this helpful comment, /dev/random can now spew out 1000 bits of pure entropy from it's pool. Why don't I just use all that? It's not as if I'm paying for the stuff bit by bit. I have nothing to lose and it makes this question entirely moot. $\endgroup$ – Paul Uszak Jun 14 '17 at 0:02
  • $\begingroup$ @PaulUszak 128 bits is how much entropy you need. If you have more, fine. $1000 \ge 128$ so 1000 bits of entropy is fine and you can use it. But 1000 bits of entropy from /dev/urandom is just as good except in very special circumstances involving a mint new machine that lacks a proper hardware RNG. $\endgroup$ – Gilles 'SO- stop being evil' Jun 14 '17 at 21:10
  • 1
    $\begingroup$ @RichardR.Matthews This is a cryptography site, so you got a theoretical answer. The practical answer is, forget about -engine and let openssl get entropy from the operating system, the operating system is better at it than you. $\endgroup$ – Gilles 'SO- stop being evil' Jun 14 '17 at 21:11
1
$\begingroup$

I feel like this is a trap, but don't you need 2 random prime numbers that are a 1024 bits long? So how much random data you consume depends on how you pick those primes, maybe without any optimization you use 1024 bits, pick a random number, then add 1 continuously until it passes your primality test, then use this as your P or Q.

$\endgroup$
  • $\begingroup$ The javascript in the Wikipedia example of RSA just keeps grabbing numbers until it finds a prime, so maybe my method for finding a prime is weak. But then for a 1024 bit number that means they only have a 0.14% chance to hit (1/ln(2^1024) *100 ) so it will chew through much more random data. $\endgroup$ – daniel Jun 14 '17 at 21:26
  • $\begingroup$ Actually the chance is different (lower?) than that as the range is limited to the top ~1/4 , and my 'add 1 continuously method' does not give uniform distribution of numbers, as it favors primes after a long run on non prime numbers. $\endgroup$ – daniel Jun 15 '17 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.