6

I stumbled upon this website which provides a service to generate Diffie-Hellman parameters online for free to the public.

Surely using a website like this would be a bad idea to use in a production environment to generate the DH parameters instead of generating them yourself? Or does it actually make no difference where they come from?

2
  • I'd just use standardized DH parameters. Oct 12, 2017 at 11:28
  • DH parameters are not secret. But you should generate themself to avoid some attacks. Using a generator on a website may or may not be a risk, as they may give all users the same parameters to make it easier to try the same key on different servers. This is exactly the same reason why you should regenerate the dh parameters instead of using the preinstalled ones.
    – allo
    Oct 12, 2017 at 14:44

1 Answer 1

9

How DH parameters are generated

There are two types of generators for DH parameters. Each generator has two steps: a step that requires random input, and a deterministic step. The two steps are the same between the two types of generators:

  • Your system supplies entropy to the generator, which uses it to generate candidate primes.
  • A deterministic algorithm goes and discards any prime that has unsafe properties.

This second step is designed to avoid generating moduli which have accidentally unsafe mathematical properties. This step is not designed to detect intentionally malicious candidates, only accidental ones that will naturally pop up. The result of these computationally difficult steps is a list of moduli suitable for use in DH key exchange and which do not have accidental weaknesses.

Malicious parameters

It is possible to create backdoored Diffie-Hellman parameters which are still validated as safe. For example, certain primes compatible with SNFV or primes vulnerable to the small-subgroup attack. There are far more issues. This means that trusting a service which provides these parameters can be risky, since you have no way to know if the moduli have actually used a random number generator to select the primes or not, as you do not have access to the seed they are using. The deterministic validation step is designed only to catch the accidental unsafe primes that come about due to the large number of candidates that are created. It is not meant to be hard to "trick".

Nothing-up-my-sleeve numbers

A nothing-up-my-sleeve number is a value with suitable mathematical properties which is well-known, alleviating the question "why did you choose those constants?". Some examples used in cryptography are π, e, or even the Declaration of Independence. This would allow anyone to validate both that the primes are safe and that they were generated in a completely deterministic and reproducible process. If they were do this, it would be significantly more difficult for them to generate malicious moduli. For example, all moduli from RFC 3526 use π as a nothing-up-my-sleeve number, so all primes are in the form of:

moduli

Where n is the number of bits in the modulus and c is the smallest positive integer that makes p a safe prime. This makes it apparent that there are no unexplained values used in generating any of these standard moduli.

This is not a panacea. For an algorithm where a significant number of randomly chosen constants lead to weakness, the number of adjustable elements in the selection procedure may make it such that apparently simple constants are vast enough that one which inserts a backdoor can be searched for. Luckily, it seems that DH is picky enough about its primes that this becomes a bit harder. Still, it's better to simply use π than it is to use the binary representation of a well-known document, or a more obscure but still irrational number, or something personal like your family's dates of birth. π provides uniform random distribution and is irrational, so it is suitable for all constants which do not need to be in a specific range and do not need to be secret.

Unpredictable public randomness

If the fact that this deterministic generation would allow an adversary to be able to precompute future moduli for themselves (and thus predict future output) is problematic, then a distributed shared randomness protocol that ensures future output will not be predictable would be desired. This has been done by Tor Project, under the name Shared Randomness Protocol. Values cannot be predicted in advance, but can be verified as having been published in the past. The Tor protocol releases a new value every day at 00:00 UTC in its consensus document. These values can be used for generating new DH moduli, for example by feeding it into a DRNG.


A diagram showing a comparison between the properties provided by their method, safe numbers (nothing-up-my-sleeve numbers), and shared randomness (like Tor's protocol) is shown here:

+---------------+-------------+--------------+-------------+----------------+
|               | Value known | Reproducible | Predictable | Trust required |
+---------------+-------------+--------------+-------------+----------------+
| Their method  | no          | no           | no          | yes            |
| Safe numbers  | yes         | yes          | yes         | no             |
| Shared random | yes         | with value   | no          | low            |
+---------------+-------------+--------------+-------------+----------------+

The candidate prime generation process can be described in this way:

  1. Seed a deterministic random number generator (DRNG) with a value, k.
  2. Extract an n bit integer, p, from the DRNG, where n is the desired modulus size.
  3. If p is not an odd integer, increment or decrement it by one.
  4. If p is not a prime or (p-1)/2 is not a prime, jump to step 2.
  5. Consider p a candidate. If sufficient candidates have not been found, jump to step 2.

The first method selects k from an internal entropy source, such as the Linux kernel's entropy pool. The second method selects k from a nothing-up-my-sleeve number, such as π. The third method selects k from an unpredictable public random value, such as Tor's current shared random value. It's up to you to determine which of these provide properties which satisfy your threat model. You may just be better off generating your own parameters locally, as that does not hide the initial seed for you, is reproducible with the seed, is unpredictable, and requires no trust.

0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .