[Cfrg] What groups to use for Diffie Hellman?

[Phillip Hallam-Baker <[e-mail]>]

I am currently working on a set of APIs to support the use of proxy
recryption within a cryptography application. Recryption solves many
problems in designing end-to-end secure messaging applications.

The following draft shows where I am headed:
https://datatracker.ietf.org/doc/draft-hallambaker-mesh-recrypt/

Links to the code libraries and API documentation can be found here:
http://www.prismproof.org/code.html

The beginnings of the recryption API are to be found here:
http://www.prismproof.org/code/portable/html/1a1794fd-cbe8-6e8b-9868-64028331fad8.htm

[All the code is under MIT license]

The API does not change much for recryption. The first step is identical,
the only difference being that instead of putting the key agreement
BigInteger result through a hash function, you send it on to the recipient
who then calls an agreement method that takes it as an additional parameter.


For ease of debugging, I would prefer to have as few moving parts to debug
at one time. So even though the intention is to us ECDH with curves x25519
and x448 for production, I am developing using straight DH with the
parameters in RFC 5114. (DH might also turn out to be necessary in
deployment if quantum resistance becomes an issue though I suspect if
people can build a 64 QBit quantum computer they will have solved most of
the problems they need to solve to go to several thousand)

The reason I am using this is that I don't want to spend time debugging
Miller-Rabin primality tests and getting them to run fast enough to be
useful. And that is the only RFC with DH parameters I could find that
specifies p and q values.

While finding it, I also found a lot of people complaining that RFC5114 is
not rigidly constructed. And there are good reasons for concern.


While writing 5114 die die die might be a good idea. A precondition for
having people take notice is to propose a set of alternative shared
parameters that have been constructed in a form that is 'sufficiently
rigid'.

One thing that seems to be a source of confusion is what the boundary
between the public and the shared parameters is. And this is different in
different protocols and while there are vast volumes of opinion on the
subject, it is hard to get a reading.


DH has the following parameters:

The modulus prime - p
The sub group prime - q
The generator - g = h^{(p-1)/q} mod p
The private key - x
The public key - g^x mod p

>From my point of view as a protocol designer, the shared parameters are
anything that is common between all the users and the public key is
anything that isn't a shared parameter and isn't part of the private key.
So there are multiple choices for the boundary between public and shared:

1) Share nothing
2) Share p
3) Share p, q
4) Share p, q, g

There are two reasons to share a parameter

1) The parameter is expensive to generate.
2) The parameter might introduce a weakness if it isn't generated correctly.

There is one good reason not to

1) Using a shared parameter may allow an attacker to attack multiple
private keys in parallel.


Generating p and q is costly. I don't want to do that on a constrained
device. So the choice comes down to g. And here I have a few choices.

1) Use fixed h and thus g.
2) Include h in the public key parameters.
3) Include g in the public key parameters.

The reason to include h rather than g is that it ensures that the generator
has been correctly generated. The reason not to is that this takes extra
time and knowing h might reduce the work factor for an attacker.


Any ideas?