DH Group Exchange Fallback

[Mark D. Baushke]

Hi Darren,

Darren Tucker <dtucker at zip.com.au> writes:

> Tangent: has any consideration been given to increasing the maximum
> allowed beyond 8192 bits (which is below the current NIST
> recommendation for 256 bits of security)? 

Actually, I have given this some thought. For really modern CPUs, this
is not completely out of question. However, to connect to the
Internet-of-Things, this is likely to be a proble.

> Last time I looked OpenSSL supported 10k bits out of the box so it
> probably wouldn't be hard to support that in OpenSSH.

With the group18 8192-bit MODP prime, we are getting just under 192-bits
of security... depending on how you calculate it.

(I think I read somewhere that, going to 16384 (2^14) will get us to
approximately 229-bits of security and 32768 (2^15) will get us to
almost 267-bits of security, but I am unable to find the reference right
now.... sigh.)

While I have no strong objections to supporting larger than 8192 bit DH
groups, I suspect that going for Diffie-Hellman groups that are not
based on safe primes would be a better next step.

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.

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.

And of course, using provable primes may not mean that one always uses
g=2. So, they can be slightly slower. Still, I think that is better than
assuming there is not a mathematical short cut for the safe primes we
are using today.

Right now, both TLS and SSH seem to only use Safe Primes. It would be
nice to understand what risks we are running if we move from probable
safe primes to provable primes for both q, and p as well as a proper
q-subset generator value g.

	Comments?
	-- Mark