3

I know in light of logjam there have been recommendations to generate your own DH group (https://weakdh.org/sysadmin.html). It seems to me that leaving this task up to the end user is much more likely to be problematic than someone precalculating an attack against a large group (like group #14 with 2048-bits or even group #16 with 4096-bits if you are paranoid).

Further, the generation of those standard groups is obviously not maliciously created (it is based on pi expansion). However, a random group provides me no guarantee it hasn't been created with ill intent.

What gives with this common recommendation?

Standard groups: https://tools.ietf.org/html/rfc3526#page-4

1

You use tools to generate safe DH groups for you, so you don't generate them entirely randomly. These tools put them through strict tests which ensure they do not have properties which make them unsafe. The tests are so accurate that the probability that one of the chosen parameters will be insecure is exceptionally low. There are two types of generators, called 2 and 5. The default is 2, but you can read about the differences here. The generation goes roughly like this:

  • The DH group generator creates a list of random candidates. They are all completely random, taken from your system's entropy pool so you can be sure that they are not maliciously selected.
  • The generator puts each candidate through extensive tests and discards the majority, leaving only a few which have special properties that make them safe for use.

What NIST did is use the pi for the first step, because obviously you would not trust them if they told you that they used their own randomness, because they could theoretically backdoor it otherwise. This safely turns the first step into a deterministic one.

Now, you don't have to worry about you creating the groups your self, because the generator gets entropy from your own system's entropy. This stage is non-deterministic, which makes the pre-computation attacks which weaken DH no longer a problem.

The reason you should use your own DH groups is because it makes you more secure from attacks involving pre-computation. The reason you should not use your own DH groups is because generating them is computationally heavy and if you are using a very very old computer, it may take a long time to create them. But as long as you generate them using openssl dhparam, then you will not need to worry about bad DH groups.

  • (1) if you're talking about OpenSSH ssh-keygen (which is not the only SSH much less only DH) the -G step is not completely random; it sieves a large block whose start is random, and then -T M-R filters them (although the man page is not at all clear on this; check the code). Later choice among the moduli file is random. (2) nondeterministic generation has no effect on precomputation attacks, only on preventing backdoor (3) NIST has nothing to do with rfc3526 (4) openssl can generate Schnorr groups (kq+1 not 2q+1) for DH much faster, see other Qs on that – dave_thompson_085 May 12 '18 at 6:14
0

Don't discourage these arguments :

  • A quantum computer prototype is already working and making something. Guess what?
  • A GPU farm is very affordable nowdays, even for a private researchers. And, yes - 10xGeForce Titan Z can make A GOOD KICK-ASS
  • There's no actual problem generating/calculating groups "on-site", it's a way faster nowdays

So I do agree with the article you provided as a reference.

  • 1
    Actually, no cryptoanalytic quantum computers are in a working state yet. The best one running Shor's algorithm can only factor the number 21 into 7 and 3. As for a GPU farm, using Titans is a stupid idea because they are designed for accuracy, not speed. Using any NVidia GPUs at all is not a good idea. AMD is always traditionally better for raw computation due to having more individual cores. – forest Apr 24 '16 at 5:47
  • @forest NVidia provides a good or near-perfect parallelism to the task, remember. And - there's no officially announced quantum algo in work. Do you think, that NSA and them-alike will immediately, clearly and honestly state : We have a way to illegally interfere into your cryptogramms ? Really? – Alexey Vesnin Apr 24 '16 at 14:06
  • It's pretty much agreed upon that the NSA now days has roughly the same level of mathematical expertise as academia. That's rarely disputed. In the past, they were a decade or so ahead. Not so much anymore. They no longer employ vastly higher number of mathematicians. As a result, you can relatively accurately approximate their progress by comparing them against what has been done in academia. Of course, even academic work can be classified, but it is classified for a far shorter time period. As a result, I'd say it's foolish to assume that the NSA has a working QC. – forest Apr 24 '16 at 23:44
  • @forest I think that they don't have a fully-featured and working QC now, but I'm pretty sure that some parts of QC that are working as prototypes today are aimed to crypto breach as for one of the primary tasks. And remember DES fiasco: yes, the actual researches were classified. Not for a long time, but it was enough to make a huge ripple – Alexey Vesnin Apr 25 '16 at 1:34

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.