Diffie Hellman parameters still calculating after 24 hours

  • 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?

  • Tom Leek

    Tom Leek Correct answer

    6 years ago

    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.

    Good tip about the -dsaparam

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

    Could do the generation on some other beefier computer then `scp` the param file.

    Could you provide a citation for the DSA-like parameters are "equally secure"?

    Note to those who aren't interested in the actual security: Adding -dsaparam made it many, many, many times faster.

    "Beware that with such DSA-style DH parameters, a fresh DH key should be created for each use to avoid small-subgroup attacks that may be possible otherwise." -- any idea how to be sure your TLS implementation is doing that?

    There is an OpenSSL security advisory regarding "-dsaparam"-style dhparams: https://www.openssl.org/news/secadv/20160128.txt (CVE-2016-0701). So to my understanding you need to use (EC)DHE (PFS) ciphers when using these dhparams. Using standard DH ciphers is not safe.

License under CC-BY-SA with attribution

Content dated before 7/24/2021 11:53 AM