DH Group Exchange Fallback

[Daniel Kahn Gillmor]

On Sun 2017-09-24 22:54:12 -0700, Mark D. Baushke wrote:
> The whole point of using ephemeral safe primes a la RFC 4419, is to make
> it too difficult to use pre-calculatation tables. It seems reasonable to
> suppose that there are less safe primes in a bit range than other
> primes, including provable primes.
>
> To be honest, I am uneasy about continuing to use Sophie-Germain and
> safe primes exclusively.

I don't understand this part.  you want to defend against an attacker
with cryptanalytic capabilities by *not* using safe primes?  Are you
expecting everyone operating a server to choose their own random
parameters, and to generate primality proofs for them?  what's stopping
time-starved admins from just copying someone else's group parameters and the
associated proofs, thereby creating a de facto common group that's worth
mounting a pre-calculation attack for?

How are you expecting clients to verify that the groups they're
using, while maybe not safe primes, are not in wide use elsewhere?  are they
supposed to track a list of of parameters they've seen and reject them
once they start seeing "too many" of them?

> For my effort, I would find it 'better' to consider moving to provable
> primes. Of course, that would mean sending all three of g,p,q to the
> client for them to validate that the primes are safe using something
> like Pocklington's Theorem. This should be fairly quick as such things
> go. It does mandate a change to the protocol to send q over the wire
> too.

are you talking about shipping the proofs in addition to shipping the
group parameters?  The sizes of the primality proofs of even a 2048-bit
prime is about 50KB:

  https://dkg.fifthhorseman.net/ffdhe-primality-proofs/

They get *much* larger as the size of the primes grows.

And verifying them (while not nearly as expensive as generating them) is
not something i can imagine any ssh client actually doing before making
a connection -- i mean, why should they, when it's cheaper and quicker
to just "trust the server" ?  (and that's to say nothing about the
efficiency gains for the defenders of having pre-computed tables for a
known group that can accellerate the fixed-base exponentiation part of
DH)

Using an a-priori-known, well-vetted, strong group parameters seems like
a more reliable approach for the ecosystem as a whole.

The proposal being explored in this thread does not seem like a good
idea.

  --dkg