Making Sense of the way Open SSL generates Diffie-Hellman Parameters.
This one is for the cryptography lovers and the curious…
Diffie-Hellman key exchange, also known as DH or DHE, is one of the less popular key exchange methods used in the SSL/TLS protocol (you may know the most widely used key exchange method: RSA). Though DH is much more commonly used in the SSH and IPsec protocols.
Key exchange algorithms are designed to allow two different parties to safely create an encryption key that can be used to communicate securely, and do so over an unsecured (or open) network, like the internet.
Every key exchange method uses different math to achieve this. Without getting into the specifics, Diffie-Hellman uses a set of numbers known as “DH parameters” that kick off the whole key exchange process. These parameters include a very large prime number which is pre-computed. This means they are generated by the server before it starts forming connections. Properly supporting Diffie-Hellman requires that you generate unique DH parameters for your server.
If you have used OpenSSL to generate Diffie-Hellman parameters, you may have noticed the console chugging along outputting “dots”(.) and “pluses” (+). Generating these parameters takes some time, so showing some sort of indicator that your server is still running is helpful. But these symbols are more than just a primitive “loading bar.”
The dots and pluses tell you every time your server has generated a number that it thinks may be a “safe prime” which can be used as the cryptographic underpinning for Diffie-Hellman SSL/TLS connections.
Each dot represents a generated number that might be a prime, and each plus represents a number that was tested and found not to be a prime. Proving large numbers are prime is a rather intensive task, so a mathematical shortcut (the Miller-Rabin primality test) is used to more quickly estimate if a number if prime. While it is not a 100% guarantee, it gets nearly as close with a lot less effort.
There is a third symbol as well: an asterisk (*). This indicates that a safe prime was found. You will only see the asterisk at the end of the output when your server has found the suitable prime it will use for your Diffie-Hellman parameters.
You will see in the screenshot above, that the output from generating DH parameters will end with sets of “++*” Planetbeing, a user over at StackExchange, explained why that is. They wrote, “The first + means the prime p itself has passed one iteration of the Miller-Rabin primality test. The second + means the (p-1)/2 also has passed one iteration of the Miller-Rabin primality test. The first * indicates both p and (p-1)/2 has passed an iteration of the Miller-Rabin primality test.”
This process is then repeated because OpenSSL wants to be very sure that this number is likely a prime, and therefore safe. The number of times this is repeated depends on the bit-size of the parameters.
I generated 4096-bit parameters on a standard VPS to see how many dots and pluses would be outputted and how long it would take. It took just over 20 minutes and generated 26090 dots and 164 pluses, before finally finding a suitable prime.
April King, an engineer at Mozilla, recently generated a truly massive 32kb Diffie-Hellman group for badssl.com, a test-bed website for different SSL errors. It took nearly 20 days and generated one million numbers in search for a suitable prime of that size!
The way Diffie-Hellman is implemented in most server OSs makes it a security vulnerability, and browsers like Chrome have recently removed support for these ciphers, so we are likely to see less and less of it. Diffie-Hellman exists in other forms that are still safe to use, such as ECDHE, which incorporates Elliptic Curve Cryptography.