4
$\begingroup$

I am trying to understand how a cryptographic library works (for example, one that provides assymetric encryption such as RSA), but I'm running into a few problems about the key-generation. There are a lot of questions regarding the generation of random primes, but I'm interested in the generation of a random number. There seem to be some official guidelines by the government (for example, NIST FIPS 186-4 (PDF) is referred to in a couple of other answers to questions about random prime generation) for the generation of keys for certain protocols, but they are not an easy read and I don't think they answer my questions.

I think I understand the basic principles: Entropy is gathered by the operating system or a daemon to provided a small amount of unpredictable data that is used as a seed for a cryptographically secure pseudo-random number generator (CSPRNG). The CSPRNG generates the random numbers that are used to generate random primes (either a probable or provable prime).

What is a good CSPRNG? I couldn't find the algorithm that OpenSSL uses (it's very well possible that there are multiple). Wikipedia lists a bunch, but doesn't provide sufficient information on implementation and performance.

Also, are there any additional constraints on the prime or prime pair that is generated? I vaguely remember reading something about prime products of a certain form that are no good for use in cryptographic keys (because they are easy to factor with some tricks).

$\endgroup$
  • 1
    $\begingroup$ CSPENG: Fortuna. IIRC "big enough" means something around twice the length of the security level. You don't need strong primes, random primes are kina likely to be strong (enough) primes but you're on the safe side if you use them. $\endgroup$ – SEJPM Aug 9 '15 at 21:46
  • $\begingroup$ Ah, I should have read the wikipedia page more carefully. Shame I only read it after I posted the question. Apearently it is not useful to pick strong primes and one should pick large enough primes instead, see crypto.stackexchange.com/questions/1151/…. Can you provide a little more information about Fortuna? Why do you name that one? Is it the most commonly used CSPRNG, or the one that OpenSSL uses? $\endgroup$ – Ruben Aug 9 '15 at 22:39
  • $\begingroup$ That's the one for OpenSSL. Note that I've come to understand that - depending on the platform - OpenSSL's random functions may be tricky to trust. $\endgroup$ – Maarten Bodewes Aug 10 '15 at 0:15
  • $\begingroup$ Many cryptographic libraries utilize the operating system RNG, which you may or may not trust, I wrote a wrapper around the OS RNG specifically for key generation, under the assumption that it is possible to compromise the OS RNG to generate poor entropy or predictable values $\endgroup$ – Richie Frame Aug 10 '15 at 6:54
  • $\begingroup$ @RichieFrame very interesting. is your wrapper for your private use or free to use? $\endgroup$ – ddddavidee Aug 11 '15 at 11:44
1
$\begingroup$

There are many "cryptographically strong pseudorandom generators" and we know how to construct them well. If you have a strong 128-bit (or more) key $k$, then you can just use AES-CTR to get as much randomness as you need: $AES_k(0)||AES_k(1)||AES_k(2)||\cdots$. You can also do a similar thing with SHA256. The real problem that arises is where to get the key from in the first place. Typically, there is a source of entropy. This is turned into (almost) uniform randomness (a.k.a. a key) using a randomness extractor. In cryptographic applications, this is often achieved by just applying a hash function like SHA256 to the source.

When OpenSSL is run in Linux, it takes its initial random source from /dev/urandom. This is already a problem since /dev/urandom (unlike /dev/random) is not blocking, which means that it provides randomness even if the Linux entropy pool is empty. What makes it worse is that OpenSSL does not reseed if the entropy pool was originally low.

I just heard an interesting talk at BlackHat 2015 about this. The above claim about OpenSSL is based on their analysis of the code. You can see more information in their PPT and white paper (I don't agree with everything they say but it's very informative and good work).

I suggest that you reseed the OpenSSL generator yourself (using rand_seed) either by calling /dev/random yourself (you can query to see if the entropy pool has enough randomness in order to prevent blocking; use the command: # cat /proc/sys/kernel/random/entropy_avail), or by using RDSEED, which is a hardware generator inside all Intel chips from Ivy Bridge. See (https://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed for more info.)

It seems that due to Snowden fears, Linux does not use RDSEED. My opinion is that it should certainly be used, at least to add randomness to the OpenSSL generator.

One final note: if you generate a new process to check the available entropy, then you will modify the pool. It seems that the Linux operating system using 256 bits of randomness from the pool every time a process is generated (for random memory allocation etc.). This is huge overkill and means that the entropy sorely needed for crypto applications may be exhausted for things that don't need real randomness. Anyway, that's life. So, if you want to constantly poll, then generate a single process that will periodically check entropy_avail, and don't generate a new process every time.

$\endgroup$
  • $\begingroup$ What about RDSEED (since broadwell)? $\endgroup$ – SEJPM Aug 10 '15 at 14:59
  • $\begingroup$ @SEJPM Thanks; you are right and RDSEED should be used. The BlackHat people got this wrong. $\endgroup$ – Yehuda Lindell Aug 10 '15 at 16:30
  • $\begingroup$ Please note: I think RDRAND and RDSEED should be used. RdRand is Intel's HW-based AES-CTR-DRBG and RDSEED is Intel's HW-based TRNG. However you'll only have RdRand on Ivy+ and RDSEED only on Broadwell+. And the Linux guys indeed refused to use RDRAND because of Snowden. RDSEED seems to be too new (first Broadwells wee available in January '15) $\endgroup$ – SEJPM Aug 10 '15 at 17:39
  • $\begingroup$ I'm confused: various sources say that using /dev/urandom is perfectly fine... (You may have a point though; I don't know how /dev/urandom behaves if there's not enough entropy...) Thanks for your answer anyway! $\endgroup$ – Ruben Aug 12 '15 at 17:05
  • $\begingroup$ /dev/urandom does not block if there isn't enough entropy. So, if you seed your PRG straight after startup, then you may be in trouble. $\endgroup$ – Yehuda Lindell Aug 16 '15 at 21:25

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.