I have a fresh install of Arch Linux on a RaspberryPi model B. I'm setting up OpenVPN and using easy-rsa with OpenSSL 1.0.2d to generate initial keys and certificates. All went fine until I ran ./build-dh(script here). It was 24 hours later when I wrote this.

I have previously configured OpenVPN on other devices and the same RaspberryPi, but under Raspbian. And I don't remember this command ever taking so long. Last time I used 2048 bit key and it took about an hour. Now I'm trying with a 4096 bit key and it's been more than a day. In fact it's been another 12 hours since I reinitiated all my settings, enabled the build-it hardware random number generator and tried again. But it's still ongoing.

cat /proc/sys/kernel/random/entropy_avail returns values in the range of 3000-3100.

Does anyone have any previous experience with this? How do I check if it's just not executing in a loop?

up vote 78 down vote accepted

If openssl uses a lot of CPU then it is not blocked waiting for "entropy". OpenSSL is actually sane in that respect, and uses a cryptographically secure PRNG to extend an initial seed into as many bits as it needs.

When you use dhparam, OpenSSL not only generates DH parameters; it also wants to assert his social status by taking care to use for the modulus a so-called "strong prime", which is useless for security but requires an awful lot more computational effort. A "strong prime" is a prime p such that (p-1)/2 is also prime. The prime generation algorithm looks like this:

  • Generate a random odd integer p.
  • Test whether p is prime. If not, loop.
  • Test whether (p-1)/2 is prime. If not, loop.

Random odd 4096-bit integers are probability about 1/2000 to be prime, and since both p and (p-1)/2 must be prime, this will need on average generating and testing for primality about 4 millions of odd primes. This is bound to take some time.

When going from 2048-bit to 4096-bit, the density of strong primes is divided by 4, and the primality tests will also be about 4 times slower, so if generating a 2048-bit DH modulus takes 1 hour on average, the same machine with the same software will use an average of 16 hours for a 4096-bit DH modulus. This is only averages; each individual generation may be faster or slower, depending on your luck.


The reasonable solution would be to add the -dsaparam option.

openssl dhparam -dsaparam -out /etc/ssl/private/dhparam.pem 4096

This option instructs OpenSSL to produce "DSA-like" DH parameters (p is such that p-1 is a multiple of a smaller prime q, and the generator has multiplicative order q). This is considerably faster because it does not need to nest the primality tests, and thus only thousands, not millions, of candidates will be generated and tested.

As far as academics know, DSA-like parameters for DH are equally secure; there is no actual advantage to using "strong primes" (the terminology is traditional and does not actually imply some extra strength).

Similarly, you may also use a 2048-bit modulus, which is already very far into the "cannot break it zone". The 4096-bit modulus will make DH computations slower (which is not a real problem for a VPN; these occur only at the start of the connection), but won't actually improve security.

To some extent, a 4096-bit modulus may woo auditors, but auditors are unlikely to be much impressed by a Raspberry-Pi, which is way too cheap anyway.

  • You are exactly right. It's done now. – kgizdov Jul 29 '15 at 23:16
  • 7
    Good tip about the -dsaparam – tofutim Feb 10 '16 at 19:24
  • Nice! This is why my Synology NAS DS213j (1.2 GHz MARVELL Armada 370 ARM single core) freshly updated to "DSM 6.0-7321" is now burning 25% CPU on /usr/bin/openssl dhparam -outform pem -rand /dev/urandom -out /usr/syno/etc/ssl/dh2048.pem 2048. I will take bets in the office on time-to-end-of-computation :-) – David Tonhofer Apr 4 '16 at 9:49
  • 3
    Could do the generation on some other beefier computer then scp the param file. – Nick T Jun 4 '16 at 8:30
  • 32
    Could you provide a citation for the DSA-like parameters are "equally secure"? – Tully Nov 22 '16 at 19:52

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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