Subject: [saag] Possible backdoor in RFC 5114

From: Watson Ladd <[email-masked]>
Date: Thu, 6 Oct 2016 08:56:45 -0700

https://tools.ietf.org/html/rfc5114

Let's review some publicly known facts:

1) BBN is a defense contractor

2) The NSA subverts crypto standards

3) It is possible to design primes so the discrete log problem is easy

4) The primes in RFC 5114 are not generated in verifiable manner: it
is possible they
are hidden SNFS primes.

At minimum we should obsolete RFC 5114 in favor of primes generated in
a verifiable manner. The fact that there already were primes for IKE
use makes me wonder why this was even needed in the first place.

Sincerely,
Watson

---

From: Jeffrey Walton <[email-masked]>
Date: Thu, 6 Oct 2016 12:10:40 -0400

> use makes me wonder why this was even needed in the first place.

That gives me a sinking feeling because I have used them in
production. I want to say, "Oh f**k...".

If they are of special form, then how can it be tested or exposed. I'm
happy to purchase some Amazon compute time and run some extended
tests.

Jeff

---

From: Yoav Nir <[email-masked]>
Date: Thu, 6 Oct 2016 19:28:57 +0300

Hi, Watson.

> use makes me wonder why this was even needed in the first place.

RFC 5114 is an Informational document published by two employees (at the time) of BBN as individuals. As the boilerplate says, “it does not specify an Internet standard of any kind”.

IANA numbers have been assigned to them for IKE, but they have not seen widespread use.  In TLS they are all but unknown, and recent work is deprecating the use of DHE with explicit parameters anyway.

The soon-to-be published successor to RFC 4307 (algorithm guidance for IKE - [1]) makes them “SHOULD NOT”.

It has never been explained in what way a 2048-bit MODP Group with 224-bit Prime Order Subgroup is better than a 2048-bit MODP Group without one.  Consequently everyone uses the regular 2048-bit MODP from RFC 3526 ([2]) if they’re not using ECDHE groups.

The RFC is effectively not in use. I don’t see any value in obsoleting it by writing a new RFC with more MODP groups that nobody wants. We could move it to Historic.

Yoav
 
[1] https://tools.ietf.org/html/draft-ietf-ipsecme-rfc4307bis-14 <https://tools.ietf.org/html/draft-ietf-ipsecme-rfc4307bis-14>
[2] https://tools.ietf.org/html/rfc3526 <https://tools.ietf.org/html/rfc3526>

---

From: Jeffrey Walton <[email-masked]>
Date: Thu, 6 Oct 2016 13:06:54 -0400

> RFC 5114 is an Informational document published by two employees (at the
> time) of BBN as individuals. As the boilerplate says, “it does not specify
> an Internet standard of any kind”.

They were published by the IETF which established provenance and
provided attestation.

If the IETF is going to back pedal on 5114, then there are other
"Additional Group" documents it has published which may need to be
back pedaled too, like 3526.

(3526 is what I happened to use in the past due to the larger field
sizes; not 5114).

Jeff

---

From: Watson Ladd <[email-masked]>
Date: Thu, 6 Oct 2016 10:11:50 -0700

> (3526 is what I happened to use in the past due to the larger field

What in 3526 needs backpeddling? None of the primes there could be
backdoored without real surprises: they are generated by taking big
chunks of pi, and then adjusting the last digits to make them prime.
The backdoor requires two small polynomials whose resultant is the
prime, which is hard to do with the deterministic generation of 3526.

Sincerely,
Watson

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 6 Oct 2016 17:15:29 +0000

On Thu, Oct 06, 2016 at 07:28:57PM +0300, Yoav Nir wrote:

> time) of BBN as individuals. As the boilerplate says, �it does not specify
> an Internet standard of any kind�.
> 
> IANA numbers have been assigned to them for IKE, but they have not seen
> widespread use.  In TLS they are all but unknown, and recent work is
> deprecating the use of DHE with explicit parameters anyway.

Sadly, their use was facilitated by support for these groups being
added in OpenSSL 1.0.2, making it easier for users to stumble into
using them.  Thus, for example, these are in use in Exim, likely
because it seemed more convenient to use "standard" groups, than
to ask users to generate their own DH parameters, and "they're in
an RFC, so they must be better than just random...".

    http://www.exim.org/exim-html-current/doc/html/spec_html/ch-main_configuration.html#SECTalomo
    [ scroll down to the entry for tls_dhparams ]

    If Exim is using OpenSSL and this option is empty or unset,
    then Exim will load a default DH prime; the default is the 2048
    bit prime described in section 2.2 of RFC 5114, "2048-bit MODP
    Group with 224-bit Prime Order Subgroup", which in IKE is
    assigned number 23.

    Otherwise, the option must expand to the name used by Exim for
    any of a number of DH primes specified in RFC 2409, RFC 3526
    and RFC 5114. As names, Exim uses "ike" followed by the number
    used by IKE, of "default" which corresponds to "ike23".

    The available primes are: ike1, ike2, ike5, ike14, ike15, ike16,
    ike17, ike18, ike22, ike23 (aka default) and ike24.

Fortunately for some, the Postfix compiled-in default DHE parameters
use SG primes (that I generated in the usual way), but users are
encouraged to use their own.

    http://www.postfix.org/FORWARD_SECRECY_README.html

> The RFC is effectively not in use. I don�t see any value in obsoleting it
> by writing a new RFC with more MODP groups that nobody wants. We could
> move it to Historic.

Well, it is not in wide use, but it may be a stretch to say
"effectively not in use".

-- 
	Viktor.

P.S. What is the most effective known way to "cook" FFDHE parameters
(other than reduced prime size) to make DLP easier?

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 7 Oct 2016 02:42:50 +0000

Yoav Nir <[email-masked]> writes:

>It has never been explained in what way a 2048-bit MODP Group with 224-bit
>Prime Order Subgroup is better than a 2048-bit MODP Group without one.
>Consequently everyone uses the regular 2048-bit MODP from RFC 3526 ([2]) if
>they’re not using ECDHE groups.

My thoughts exactly.  Given that with sizeof( p ) == sizeof( g ) these are
probably the least efficient DH parameters ever published, the whole RFC just
screams "don't use me".  Does it even need to be actively deprecated?

Peter.

---

From: Jeremy Harris <[email-masked]>
Date: Fri, 7 Oct 2016 09:48:14 +0100

On 07/10/16 03:42, Peter Gutmann wrote:
>   Given that with sizeof( p ) == sizeof( g ) these are

For people who are not number-theoreticians, and have no clue on what
effect sizeof(random letter) might have, but nonetheless expect
active standards to be useful?
-- 
Jeremy

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 7 Oct 2016 12:45:31 +0100

So I'm not seeing anyone so far argue to not
deprecate these somehow.

We could just make 5114 historic as Yoav suggests,
or, if someone writes an I-D to explain why, we
could obsolete 5114. (Such an I-D would presumably
also say something about codepoints that point at
5114 from other registries.)

Assuming nobody shows up saying these are in
fact in widespread use I'd be supportive of us
getting rid of cruft.

So, someone wanna volunteer to write an I-D that'd
obsolete 5114? If so, say so here.

Or, if you want me to start the "mark it historic"
process (which doesn't need an I-D), please say
so here. (Note that even though this doesn't need
an I-D the status-change does get an IETF last
call.)

Or, if you wanna argue that none of the above are
right, then please do that.

Cheers,
S.

---

From: Tero Kivinen <[email-masked]>
Date: Fri, 7 Oct 2016 16:59:32 +0300

> fact in widespread use I'd be supportive of us

I think the NIST ECP groups are quite widely supported, and used.
RFC5114 includes both Nist ECP Groups (192, 224, 256, 384 and 521) and
3 MODP groups.

In IPsec, ECP groups are widely used, those MODP groups with subgroup
are not. On the other hand I think only those 192, 256 and 521 bit
groups are really used, and those are defined also in RFC5903 (which
obsoleted original 4753 which had serious bug in it).

> obsolete 5114? If so, say so here.

Or parts of it or something. 

> an I-D the status-change does get an IETF last

Marking NIST ECP groups as historic might be preferrable for some
people, but it might be good idea to wait before we have curve25519
etc published as rfc for all protocols that 5114 covers before we go
that far. In IPsec the curve25519 etc are now in the IESG, I do not
know what is the status for other protocls (X.509, TLS, SSH, SMIME). 

> right, then please do that.

I have no idea why we would want to mark the document as historic, or
obsolete it, especially as it does define things that are in use (ECP
groups).

It does not give any recommendations for using those groups, for
example in IPsec we do have separate documents which gives those
recommendations and for the 256-bit ECP we are saying SHOULD, and for
the MODP groups defined in the 5114 we are saying SHOULD NOT.

That is much better way to define the recommendations and how those
groups should or should not be used.
-- 
[email-masked]

---

From: Yoav Nir <[email-masked]>
Date: Fri, 7 Oct 2016 18:56:12 +0300

> On 7 Oct 2016, at 16:59, Tero Kivinen <[email-masked]> wrote:
> 
> Stephen Farrell writes:
>> 
> I think the NIST ECP groups are quite widely supportd, and used.

First, I think you meant 256, 384 and 521 bit, not the 192.

Second, 5114 did not fix the bug in 4753. It just referenced 4753 for formatting. You know this better than I do, but I don’t think the IANA registry ever referenced 5114 for these ECP groups.

So for the three useful groups in 5114 you didn’t need it (as 4753) already existed, and you don’t need it now, as 5903 exists. I don’t see anything standing in the way of moving to historic or obsoleting it.

Yoav

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Fri, 7 Oct 2016 21:12:20 +0000

> I have no idea why we would want to mark the document as historic, or obsolete it, especially as it does define things that are in use (ECP groups).
> It does not give any recommendations for using those groups, for example in IPsec we do have separate documents which gives those recommendations and for the 256-bit ECP we are saying SHOULD, and for the MODP groups defined in the 5114 we are saying SHOULD NOT.
> That is much better way to define the recommendations and how those groups should or should not be used.

Agreed. The ECP groups are widely used in IKE. "Historifying" will not add value especially before a 25519 group is defined.
Panos

-----Original Message-----
From: saag [mailto:[email-masked]] On Behalf Of Tero Kivinen
Sent: Friday, October 07, 2016 10:00 AM
To: Stephen Farrell <[email-masked]>
Cc: [email-masked]
Subject: Re: [saag] Possible backdoor in RFC 5114

Stephen Farrell writes:
> 
> So I'm not seeing anyone so far argue to not deprecate these somehow.
> 
> We could just make 5114 historic as Yoav suggests, or, if someone 
> writes an I-D to explain why, we could obsolete 5114. (Such an I-D 
> would presumably also say something about codepoints that point at
> Assuming nobody shows up saying these are in fact in widespread use 
> I'd be supportive of us getting rid of cruft.

In IPsec, ECP groups are widely used, those MODP groups with subgroup are not. On the other hand I think only those 192, 256 and 521 bit groups are really used, and those are defined also in RFC5903 (which obsoleted original 4753 which had serious bug in it).

> So, someone wanna volunteer to write an I-D that'd obsolete 5114? If 
> so, say so here.

> process (which doesn't need an I-D), please say so here. (Note that 
> even though this doesn't need an I-D the status-change does get an 
> IETF last
> call.)

Marking NIST ECP groups as historic might be preferrable for some people, but it might be good idea to wait before we have curve25519 etc published as rfc for all protocols that 5114 covers before we go that far. In IPsec the curve25519 etc are now in the IESG, I do not know what is the status for other protocls (X.509, TLS, SSH, SMIME). 

> Or, if you wanna argue that none of the above are right, then please 
> do that.

I have no idea why we would want to mark the document as historic, or obsolete it, especially as it does define things that are in use (ECP groups).

It does not give any recommendations for using those groups, for example in IPsec we do have separate documents which gives those recommendations and for the 256-bit ECP we are saying SHOULD, and for the MODP groups defined in the 5114 we are saying SHOULD NOT.

That is much better way to define the recommendations and how those groups should or should not be used.
--
[email-masked]

_______________________________________________
saag mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/saag

---

From: Watson Ladd <[email-masked]>
Date: Fri, 7 Oct 2016 14:50:06 -0700

>> That is much better way to define the recommendations and how those groups should or should not be used.

The IANA registry cites 5903, not 5114, for these groups, so
historifying 5114 would have no effect. I'm not entirely sure what
historifying does to registries in terms of marking DO NOT USE: maybe
a separate draft is required. I am not a process expert. Furthermore
in at least some cases the IKE registries get used by people hunting
for DH parameters. Do we need a draft here? What should that look
like?

It's not SHOULD NOT. It's "using these groups even outside of IKE will
result in pwnage". Do you agree we need a stronger warning about known
bad cryptographic constructions? What do you think that should look
like?

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Sat, 8 Oct 2016 12:30:27 +0000

Watson and all,

This paper would be a good (re)read: http://www.math.uwaterloo.ca/~ajmeneze/publications/pqc.pdf.

Quynh. 

________________________________________
From: saag <[email-masked]> on behalf of Watson Ladd <[email-masked]>
Sent: Thursday, October 6, 2016 11:56 AM
To: [email-masked]
Subject: [saag] Possible backdoor in RFC 5114

Sincerely,
Watson

---

From: Watson Ladd <[email-masked]>
Date: Sat, 8 Oct 2016 06:37:24 -0700

On Oct 8, 2016 5:30 AM, "Dang, Quynh (Fed)" <[email-masked]> wrote:
>
> Watson and all,
>
> This paper would be a good (re)read:
http://www.math.uwaterloo.ca/~ajmeneze/publications/pqc.pdf.

>From which you would have us conclude what?

The backdoor of Gordon in Diffie-Hellman is well-known.  There is no way to
know if these primes are backdoored.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Sat, 8 Oct 2016 14:40:28 +0000

Assuming the curves generator was a bad guy and he/she could do 2^80 computations (not simple computations: running the specified routine to find primes numbers which means he/she got to do more than 2^80 times of the routine by a factor) at that time in 1997, the class of weak curves must have been about 2^169 in 1997, only known to the NSA and have never been discovered by the public from 1997 until now.

Also, some of the curves are used for top secret security level information. If it was the case that the NSA knew the curves were weak curves, would they take that risky action by assuming that the rest of the world would not find that out for at least 20 years later.

Quynh.

________________________________
From: Watson Ladd <[email-masked]>
Sent: Saturday, October 8, 2016 9:37:24 AM
To: Dang, Quynh (Fed)
Cc: [email-masked]
Subject: Re: [saag] Possible backdoor in RFC 5114

>From which you would have us conclude what?

The backdoor of Gordon in Diffie-Hellman is well-known.  There is no way to know if these primes are backdoored.

> From: saag <[email-masked]<mailto:[email-masked]>> on behalf of Watson Ladd <[email-masked]<mailto:[email-masked]>>
> To: [email-masked]<mailto:[email-masked]>
> [email-masked]<mailto:[email-masked]>

---

From: Watson Ladd <[email-masked]>
Date: Sat, 8 Oct 2016 08:59:25 -0700

On Oct 8, 2016 7:40 AM, "Dang, Quynh (Fed)" <[email-masked]> wrote:
>
> Assuming the curves generator was a bad guy and he/she could do 2^80
computations (not simple computations: running the specified routine to
find primes numbers which means he/she got to do more than 2^80 times of
the routine by a factor) at that time in 1997, the class of weak curves
must have been about 2^169 in 1997, only known to the NSA and have never
been discovered by the public from 1997 until now.
>
>
> Also, some of the curves are used for top secret security level
information. If it was the case that the NSA knew the curves were weak
curves, would they take that risky action by assuming that the rest of the
world would not find that out for at least 20 years later.

Am I discussing ECC? No.

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 10 Oct 2016 14:57:20 +0300

> First, I think you meant 256, 384 and 521 bit, not the 192.

Yes, of course.

> So for the three useful groups in 5114 you didn’t need it (as 4753)
> already existed, and you don’t need it now, as 5903 exists. I don’t
> see anything standing in the way of moving to historic or obsoleting
> it. 

This is true for IPsec. I am not sure if it is true for TLS, SSH and
S/MIME.

RFC4753 and 5903 only covers the IKE and IKEv2 cases, RFC5114 also
covers other protocols, and I do not know what if they use 5114 or
not, and if the NIST ECP group references in there are to 5114 or to
something else.

For IPsec I think we are good, because we have separate document
specifying the mandatory to implement algorithms, and that some
document also specifies MUST NOTs and SHOULD NOTs.
-- 
[email-masked]

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 10 Oct 2016 15:21:52 +0300

Watson Ladd writes:
> a separate draft is required.

Moving document to historic does not change anything in the IANA
registries. To make changes to the IANA registries, you need separate
document, IESG action, or designated expert agreeing on change,
depending on the registry. And the IANA registries do not give
recommendations whether algorithm is good to use be used or not, and
adding such thing to IANA registries would be bad idea.

The IANA IKEv2 registry still includes algorithms like 768-bit MODP
Group, and single DES. It does not mean that you are fine using those. 

IANA registries are not saying that you should or should not implement
certiain algorithms, they provide mappings between numbers,
identifiers and specifications. 

> I am not a process expert. Furthermore in at least some cases the
> IKE registries get used by people hunting for DH parameters. Do we
> need a draft here? What should that look like?

IKE registries are supposed to be used for protocols related to IKE.
If other people use them for other reasons, there is nothing we can do
for that.

> bad cryptographic constructions? What do you think that should look

In IPsec we do publish warnings and recommendations in the separate
documents (rfc4307bis and rfc7321bis, work in progress). And
rfc4307bis do contain SHOULD NOT for those groups, and gives reason
for that.

If you think wider warning is really need, you can write document
saying rfc5114-die-die-die, and get that published. That will not
still remove RFC5114, at best it could be moved to historic if other
people agree with you, but that still does not affect the fact that
people still might use that rfc5114 as reference.

Regardless what we do we cannot protect people from making mistakes.
If they want to make weak crypto, there is nothing we can do. I am
pretty sure that even if they use RFC5114 groups, those groups are not
the weakest point in their protocol. 

Btw, can you point me the reference which says that those groups are
really backdoored? What I have seen is people saying that as those
might be backdoored, they must been backdoored, and I myself do not
find that very convincing argument. On the other hand as there is no
seed etc published on how those groups are generated, they might be
backdoored, and I think that is good reason for SHOULD NOT for IPsec.
-- 
[email-masked]

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 10 Oct 2016 08:14:45 -0700

> This is true for IPsec. I am not sure if it is true for TLS, SSH and

For SSH, the IANA document URL:

  http://www.iana.org/assignments/ssh-parameters/ssh-parameters.xhtml 

does not have any reference to RFC 5114.

To the best of my understanding, SSH has never really supported anything
other than safe-primes (Sophie Germain primes at that?) Diffie-Hellman
key exchange. Although it is possible to implement Lim-Lee primes with
RFC 4419, only g,p are sent over the wire. For ECDH, SSH has RFC 5656,
so once more there is no need to keep RFC 5114 for anything SSH uses.
I do not know of any other uses of ECP groups for SSH.

> document also specifies MUST NOTs and SHOULD NOTs.

For SSH, I have an IETF draft
https://datatracker.ietf.org/doc/draft-ietf-curdle-ssh-kex-sha2/
to cover the 'SHOULD NOT' values for key exchagne.

Perhaps we need to have a similar document for TLS and S/MIME as well?

	-- Mark

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 11 Oct 2016 04:14:28 +0000

>Perhaps we need to have a similar document for TLS and S/MIME as well?

The TLS one already exists:

https://www.ietf.org/id/draft-gutmann-tls-lts-05.txt

It's just hung up in the TLS WG, which is getting a bit annoying since there
are at least two vendors who have either shipped or are ready to ship
implementations based on it...

Peter.