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

From: jonas weber <[email-masked]>
Date: Sun, 30 Oct 2016 22:13:54 -0400

Peter,

In your last post on this topic you write:

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.

Given the uncertainty over the RFC-5114 groups, I believe it would be helpful to have an RFC with a list of primes as you describe. Many of us use shorter exponents to save computation and having a list of verifiable primes would be useful, particularly if they could be registered for use in IKE and TLS.

Regards,

Jonas

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 31 Oct 2016 10:07:32 +0000

jonas weber <[email-masked]> writes:

>Given the uncertainty over the RFC-5114 groups, I believe it would be helpful
>to have an RFC with a list of primes as you describe. Many of us use shorter
>exponents to save computation and having a list of verifiable primes would be
>useful, particularly if they could be registered for use in IKE and TLS.

I've been having a discussion about this off-list, may as well make it public
if others are interested... the main issue is how to generate the values,
presumably you'd want safe primes (so p = 2q + 1), g = 2 for efficiency, and
some NUMS source for the primes.  One suggestion was PBKDF2( "DH 2048" ),
PBKDF2( "DH 1024" ), etc as the seed value and then some deterministic way to
get from there to the final prime.  And maybe pseudocode so anyone can
replicate it using whatever bignum library they prefer (rather than, say,
"plug the following formula into Mathematica").  How NUMS does it have to get?

Peter.

---

From: Michael StJohns <[email-masked]>
Date: Mon, 31 Oct 2016 13:04:04 -0400

On 10/31/2016 6:07 AM, Peter Gutmann wrote:
> get from there to the final prime.
Appendix A of FIPS 186-4 defines a method ( section A.1.2)to generate 
DSA/DH domain values from a seed using Shawe-Taylor.  I'm not sure it 
meets all of your requirements, but it may be a stepping off point.  One 
useful thing about this would be that the test harnesses already exist 
for validating an implementation provides the right answer.

Mike

>   And maybe pseudocode so anyone can
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 31 Oct 2016 14:45:18 -0400

The way I got suckered into RFC5441 is that it is the only RFC that appears
to be consistent with RFC2631 on how to do DH:

https://www.ietf.org/rfc/rfc2631.txt

I see the following ways forward:

1) Update RFC2631 to say use  of a short exponent is OK, and then kill
RFC5441.

2) Do a draft consistent with RFC2631 that has rigid construction and kill
5441.

3) Both.

I don't really mind which.

As far as the rigidity issue goes, I see the following hazards to avoid:

1) An attacker is one of a small circle that knows a set of parameters to
be weak and steers the group towards them.

2) An attacker constructs a set of parameters in such a way that they
contain what is in effect a backdoor that can only be used by a party that
knows the secret of the construction.

Our current approaches to rigidity are only designed to address the second
case. There really isn't a way to address the first. It is quite possible,
likely even that fast primes also speed up attacks They might even make
whole classes of attack possible or they might not.

A process that is based on H("DH2048") for a seed might or might not result
in a choice of weak parameters but it does mean that there isn't a hidden
backdoor.

Based on my conversations with NSA folk, the governing doctrine is 'NOBUS'
nobody but us. Introducing a weakness that only the NSA could exploit with
hidden knowledge nobody else could discover independently is one thing.
Developing a system with a hole anyone can find if they look long enough is
not acceptable.

---

From: Yoav Nir <[email-masked]>
Date: Mon, 31 Oct 2016 21:57:16 +0200

On 31 Oct 2016, at 20:45, Phillip Hallam-Baker <[email-masked]> wrote:

> Based on my conversations with NSA folk, the governing doctrine is 'NOBUS' nobody but us. Introducing a weakness that only the NSA could exploit with hidden knowledge nobody else could discover independently is one thing. Developing a system with a hole anyone can find if they look long enough is not acceptable.

Whatever else he may have accomplished, Edward Snowden proved that NSA hidden knowledge can and does get unhidden. At least to people who failed to learn that from PFC Manning.

So it’s best not to deploy a group that only the NSA can break, even if you are not concerned about the NSA monitoring your data. The next Snowden can make it so that the people that you are concerned about will also be doing it. 

Yoav

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 31 Oct 2016 17:24:52 -0400

On Mon, Oct 31, 2016 at 3:57 PM, Yoav Nir <[email-masked]> wrote:

> > Based on my conversations with NSA folk, the governing doctrine is
> 'NOBUS' nobody but us. Introducing a weakness that only the NSA could
> exploit with hidden knowledge nobody else could discover independently is
> one thing. Developing a system with a hole anyone can find if they look
> long enough is not acceptable.
>
> Whatever else he may have accomplished, Edward Snowden proved that NSA
> hidden knowledge can and does get unhidden. At least to people who failed
> to learn that from PFC Manning.
>
> So it’s best not to deploy a group that only the NSA can break, even if
> you are not concerned about the NSA monitoring your data. The next Snowden
> can make it so that the people that you are concerned about will also be
> doing it.

​Well it came up in a response to my complaint about BULLRUN...​

​​

​I think that point is now appreciated. And not just because of Snowden.
There was also the hacking tools dump that appears to have been finger
trouble without ​actual criminal intent.

It is useful to enumerate and distinguish the attacks we are avoiding and
the ones we are not. Especially when we have no way to avoid some pitfalls.
There is no deterministic procedure that is going to guarantee strong
parameters against unknown attacks. We have no way of knowing which
parameters are strong.

​We can nail down backdoor free and eliminate the NOBUS attacks. That does
not prevent some sociopath smurfing a set of weak parameters. But if they
did, the US govt would likely be among the biggest victims as a result.​

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 1 Nov 2016 00:57:24 +0000

>https://www.ietf.org/rfc/rfc2631.txt

Hmm, so going back one step in the chain, how did you get suckered into using
RFC 2631?  That's a spec that's used by, approximately, nothing...

(I'd have to check what IPsec does, but it's not used by TLS, SSH, S/MIME,
PGP, or any other protocol I'm familiar with.  If you need some sort of spec
for DH then I guess it's some sort of spec, but I think a better choice would
have been the TLS form, which means you get support in crypto libs, PKCS #11,
hardware, ...).

>I see the following ways forward:

Given that 5114 is unsafe and 2631 isn't used by anything that I'm aware of, I
think a better option would be:

4) Do a draft with values created in a generally-approved NUMS manner, g = 2
   for efficiency, safe primes, etc, whose generation is verified by two or
   more generally-trusted crypto people.

Peter.