Subject: [Cfrg] What groups to use for Diffie Hellman?

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 27 Oct 2016 10:47:21 -0400

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?

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 28 Oct 2016 01:56:07 +0000

Phillip Hallam-Baker <[email-masked]> writes:

>I am developing using straight DH with the parameters in RFC 5114. 

And there's your problem.  Apart from the fact that the 5114 groups are,
excluding carefully-selected pathologically-bad parameter sets, the least
efficient DH parameters ever published (in other words why would anyone want
to use them in the first place), there are also concerns about the fact that
they're created in an unverifiable manner.  Just use the 3526 parameters like
everyone else and you're fine.

>Any ideas?

Use the 3526 values, or generate your own, if you're really worried about
provenance, although the 3526 ones are pretty NUMS, and have been
independently verified.

Peter.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 28 Oct 2016 16:24:04 +1100

RFC 7919 (and RFC 3526, as Peter points out) haven't been called into question.

On 28 October 2016 at 01:47, Phillip Hallam-Baker <[email-masked]> wrote:
> 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)
>
> 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
>
> 1) Using a shared parameter may allow an attacker to attack multiple private
> keys in parallel.
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 28 Oct 2016 08:37:07 +0000

>RFC 7919 (and RFC 3526, as Peter points out) haven't been called into question.

Yup, 7919 is fine too, as long as you just use the values and not the rest of
the RFC (as it applies to TLS).  So you could, for example, use the DH-2048's
from either RFC, switching at random, in case one of the two has a problem.

One caveat with 7919 is that the values aren't as widely-used as 3526, so if
you've got something that whitelists/fastpaths 3526 then you'll take a slight
performance hit with the 7919 values.

On a related subject, is there any interest in an RFC that just lists, say,
ten DH parameter sets of various sizes with their generation machanism to
allow replication?  So no list of things you can and can't do, just the
parameters to use wherever you want.  My code uses Lim-Lee, as long as people
don't object to that I can generate them by that process, it'd just mean you'd
need another implementation that can handle verifying primes of the form
'p = 2 * q * ( prime[1] * ... prime[n] ) + 1'.

I'd also supply them as bignums of 32- and 64-bit words, since that's how
they're going to end up in people's code and it'll save lots of developers
having to manually reformat them from whatever form they're otherwise
published in.

Peter.