Subject: [IPsec] trapdoor'ed DH (and RFC-5114 again)

From: Paul Wouters <[email-masked]>
Date: Sun, 9 Oct 2016 17:26:02 -0400 (EDT)

Released a few days ago:

 	http://eprint.iacr.org/2016/961

 	A kilobit hidden SNFS discrete logarithm computation
 	Joshua Fried and Pierrick Gaudry and Nadia Heninger and Emmanuel Thomé

 	We perform a special number field sieve discrete logarithm
 	computation in a 1024-bit prime field. To our knowledge, this
 	is the first kilobit-sized discrete logarithm computation ever
 	reported for prime fields. This computation took a little over
 	two months of calendar time on an academic cluster using the
 	open-source CADO-NFS software.

Basically, this paper shows how to make a DH group of 1024 modp
with a backdoor, in two months of academic computing resources,

The paper mentions 5114 a few times:

 	RFC 5114 [33] specifies a number of groups for use with
 	Diffie-Hellman, and states that the parameters were drawn
 	from NIST test data, but neither the NIST test data [39] nor
 	RFC 5114 itself contain the seeds used to generate the finite
 	field parameters

And concludes:

 	Both from this perspective, and from our more modern one, dismissing the
 	risk of trapdoored primes in real usage appears to have been a mistake,
 	as the apparent difficulties encountered by the trapdoor designer in 1992
 	turn out to be easily circumvented. A more conservative design decision
 	for FIPS 186 would have required mandatory seed publication instead of
 	making it optional.  As a result, there are opaque, standardized 1024-bit
 	and 2048-bit primes in wide use today that cannot be properly verified.

This is the strongest statement yet that I've seen to not trust any
of the RFC-5114 groups.

The latest 4307bis document has these groups (22-24) as SHOULD NOT,
stating:

 	Group 22, 23 and 24 or 1024-bit MODP Group with 160-bit, and
 	2048-bit MODP Group with 224-bit and 256-bit Prime Order Subgroup
 	have small subgroups, which means that checks specified in the
 	"Additional Diffie-Hellman Test for the IKEv2" [RFC6989] section
 	2.2 first bullet point MUST be done when these groups are used.
 	These groups are also not safe-primes.	The seeds for these groups
 	have not been publicly released, resulting in reduced trust in
 	these groups.  These groups were proposed as alternatives for
 	group 2 and 14 but never saw wide deployment.  It is expected
 	in the near future to be further downgraded to MUST NOT.

I'm proposing it is time to change this to MUST NOT for 4307bis.

Possibly, we should do this via SAAG in general, and then follow SAAG's
advise in IPSECME.

Is there _any_ reason why group 22-24 should not be MUST NOT ?

Paul

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Mon, 10 Oct 2016 13:18:00 +0000

Hi Paul,

Thank you for sharing the paper.

A conclusion of the paper was "Our results are yet another reminder that 1024-bit primes should be considered insecure for the security of cryptosystems based on the hardness of discrete logarithms. The discrete logarithm computation for our backdoored prime was only feasible because of the 1024-bit size, and the most effective protection against any backdoor of this type has always been to use key sizes for which any computation is infeasible. NIST recommended transitioning away from 1024-bit key sizes for DSA, RSA, and Diffie-Hellman in 2010 [6]."

NIST has been urging users to move away from groups with 1024- bit p and 160-bit q  for many years now.

In our document, we stated that group generators "should" provide their seeds. The reason for having "should" instead of "shall (must)" was that anyone could run our suggested method to generate their own group. A user who generates his/her own group for her/his own application could have a choice of publishing the seed or not.  If a user had a contractor/third party to generate a group for him/her, he or she could ask for all documentation about the whole process.

Quynh.

________________________________
From: IPsec <[email-masked]> on behalf of Paul Wouters <[email-masked]>
Sent: Sunday, October 9, 2016 5:26 PM
To: [email-masked] WG
Cc: [email-masked]
Subject: [IPsec] trapdoor'ed DH (and RFC-5114 again)

Released a few days ago:

And concludes:

Paul

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

---

From: Paul Wouters <[email-masked]>
Date: Mon, 10 Oct 2016 11:33:26 -0400 (EDT)

On Mon, 10 Oct 2016, Dang, Quynh (Fed) wrote:

> A conclusion of the paper was "Our results are yet another reminder that 1024-bit primes should be considered insecure for the security of cryptosystems based on the hardness of discrete
> logarithms. The discrete logarithm computation for our backdoored prime was only feasible because of the 1024-bit size, and the most effective protection against any backdoor of this
> type has always been to use key sizes for which any computation is infeasible. NIST recommended transitioning away from 1024-bit key sizes for DSA, RSA, and Diffie-Hellman in 2010 [6]."
> 

Sure.

> In our document, we stated that group generators "should" provide their seeds. The reason for having "should" instead of "shall (must)" was that anyone could run our suggested method to
> generate their own group. A user who generates his/her own group for her/his own application could have a choice of publishing the seed or not.  If a user had a contractor/third party to
> generate a group for him/her, he or she could ask for all documentation about the whole process. 

But why should I trust the RFC-5114 2048-bit MODP Group with 256-bit
Prime Order Subgroup? The problem of not knowing the seed remains the
same. We just think the NSA does not have a mathemathical advantage over
academia, but that's still a big unknown.

And for IKE, you cannot just generate your own groups.

Paul

---

From: John Mattsson <[email-masked]>
Date: Mon, 17 Oct 2016 15:30:49 +0000

> I'm proposing it is time to change this to MUST NOT for 4307bis.

+1

---

From: Daniel Migault <[email-masked]>
Date: Mon, 17 Oct 2016 11:54:19 -0400

In fact is there anyone opposing their status becomes MUST NOT in
rfc4307bis.

On Mon, Oct 17, 2016 at 11:30 AM, John Mattsson <[email-masked]>
wrote:

> >       as the apparent difficulties encountered by the trapdoor designer
> in
> >1992
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag
>

---

From: Yoav Nir <[email-masked]>
Date: Mon, 17 Oct 2016 19:05:18 +0300

I’m not entirely comfortable with calling something a MUST NOT when all we have is conjecture, but I have no love and no need of those DH groups.

I don’t believe anyone else depends on these groups (at least in IPsec), so I’m fine with such a change.

Yoav

> On 17 Oct 2016, at 18:54, Daniel Migault <[email-masked]> wrote:
> 
> In fact is there anyone opposing their status becomes MUST NOT in rfc4307bis.
> 
> On Mon, Oct 17, 2016 at 11:30 AM, John Mattsson <[email-masked] <mailto:[email-masked]>> wrote:
> <[email-masked] <mailto:[email-masked]> on behalf of [email-masked] <mailto:[email-masked]>> wrote:
> 
> >
> >Released a few days ago:
> >
> >       http://eprint.iacr.org/2016/961 <http://eprint.iacr.org/2016/961>
> >
> >[email-masked] <mailto:[email-masked]>
> >https://www.ietf.org/mailman/listinfo/ipsec <https://www.ietf.org/mailman/listinfo/ipsec>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/saag <https://www.ietf.org/mailman/listinfo/saag>
>

---

From: Paul Wouters <[email-masked]>
Date: Mon, 17 Oct 2016 12:19:26 -0400 (EDT)

On Mon, 17 Oct 2016, Yoav Nir wrote:

> I’m not entirely comfortable with calling something a MUST NOT when all we have is conjecture,

It's a little more than conjecture.

1) It has been proven that malicious 1024 bit DH values can be generated
    by academia that cannot be independantly discovered. Therefore any
    nationstate with access to the same theory and more CPU power could
    have done this years ago.

2) We have the RFC 5114 values who'se original authors/sponsors are not
    disclosing how these were generated.

1) + 2) means we cannot know if these values were trapdoor'ed.

If BBN/NIST/NSA wants to share how they seeded these values, we can all
publicly decide if we can keep using these or not. Without such
information, it just becomes an unnecessary risk to take.

Adding Steve Kent, co-author of RFC-5114, to the CC: so that he has
the opportunity to share what he knows about the origins of these
values and their seeds.

>  but I have no love and no need of those DH groups.

Thanks,

Paul

> On Mon, Oct 17, 2016 at 11:30 AM, John Mattsson <[email-masked]> wrote:

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 18 Oct 2016 13:33:28 +0300

Yoav Nir writes:
> I’m not entirely comfortable with calling something a MUST NOT when all we
> have is conjecture, but I have no love and no need of those DH groups.

Same here, and it also makes it so that we cannot say our
implementation is conforming rfc4307bis, even when we do already have
support for AES, SHA2, 2048-bit DH, i.e. all the mandatory to
implement algorithms in the new document, but we do also have code to
propose the RFC5114 MODP groups, if user configures them to be used.

Changing that is of course is very easy to do in implementation, but
before this is deployed etc will take some time, and there is change,
that some customer has explictly configure RFC5114 2048-bit MODP group
in use, and by removing that we suddenly break their existing
configuration.

It is always annoying to explain to customer why we explictly broke
their existing configurations unless there is real security reason for
it. Looking that the paper, this only applies to the 1024-bit MODP
group in RFC5114, even the paper says that 2048-bit MODP groups are
safe, even if they would have same backdoor.

We are already downgrading normal 1024-bit MODP group to SHOULD NOT,
and this would make it two reasons to make RFC5114 1024-bit MODP group
to SHOULD NOT (too short, and might be backdoored), so perhaps the
compromize can be to make RFC5114 1024-bit MODP group number 22 to
MUST NOT, and keep the groups 23-24 as SHOULD NOTs.

Anyways we need to modify the rfc4307bis text and add reference to
this paper, as one more reason why groups 22-24 MUST NOT/SHOULD NOT be
used.

> IPsec), so I’m fine with such a change.

I do not think people depend on them, but I assume there is quite a
lot of implementations there that can be configured to use them if
explictly asked, thus making them MUST NOT will make it so that those
implementations will not be conforming rfc4307bis.
-- 
[email-masked]

---

From: Yoav Nir <[email-masked]>
Date: Tue, 18 Oct 2016 15:47:34 +0300

> On 17 Oct 2016, at 19:19, Paul Wouters <[email-masked]> wrote:
> 

Someone can trapdoor 1024-bit values, therefore someone else can trapdoor 2048-bit values.

> 1) + 2) means we cannot know if these values were trapdoor’ed.

Yeah, we cannot know. That’s why it’s conjecture.

Yoav

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 18 Oct 2016 12:50:24 +0000

>Someone can trapdoor 1024-bit values, therefore someone else can trapdoor

Yep, space aliens.  However I'm really not too worried about those at the
moment.

Peter.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 18 Oct 2016 15:51:45 +0300

> On 18 Oct 2016, at 13:33, Tero Kivinen <[email-masked]> wrote:
> 
> Yoav Nir writes:

I don’t think that’s the right way to interpret compliance with RFC4307bis. If you can configure your implementation to support only algorithms that are MUST, SHOULD, or MAY in the document, then you can configure your implementation to comply with 4307bis. I don’t think implementation compliance requires pulling out code.

Our implementation allows the user to key in long hex strings to construct MODP groups that are not available out of the box. With your interpretation we can never be compliant because they can always make up their own 512-bit group and add that to the available groups.

Yoav

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 18 Oct 2016 16:24:34 +0300

Yoav Nir writes:
> I don’t think that’s the right way to interpret compliance with
> RFC4307bis. If you can configure your implementation to support only
> algorithms that are MUST, SHOULD, or MAY in the document, then you
> can configure your implementation to comply with 4307bis. I don’t
> think implementation compliance requires pulling out code. 

When rfc4307bis says MUST NOT do DES, and MUST NOT do 768-bit MODP, I
assume that to be conforming to that document, user is not able to
configure DES with 768-bit MODP group.

Of course MUST NOTs are difficult as it is really hard to show where
in your code you implement this specific MUST NOT (yes, there was one
customer asking us to point out where in code we implement each MUST
NOTs).

> Our implementation allows the user to key in long hex strings to
> construct MODP groups that are not available out of the box. With
> your interpretation we can never be compliant because they can
> always make up their own 512-bit group and add that to the available
> groups. 

That is different issue, as this is SHOULD feature in the RFC7296:

   parameters, up to certain size limits.  In support of this goal, all
   implementations of IKEv2 SHOULD include a management facility that
   allows specification (by a user or system administrator) of Diffie-
   Hellman parameters (the generator, modulus, and exponent lengths and
   values) for new Diffie-Hellman groups.  Implementations SHOULD
   provide a management interface through which these parameters and the
   associated Transform IDs may be entered (by a user or system
   administrator), to enable negotiating such groups.

Also there is nothing in the rfc4307bis saying that that is MUST
NOT...

On the otherhand if someone uses that interface to configure the
768-bit MODP group 1, then he is going against MUST NOT in rfc4307bis,
and his system is longer conforming... It might be good idea to limit
that interface so it will not allow any groups which are shorter than
1024-bits, just so users cannot do stupid things... 
-- 
[email-masked]

---

From: Watson Ladd <[email-masked]>
Date: Tue, 18 Oct 2016 07:31:10 -0700

> in use, and by removing that we suddenly break their existing

In sane protocols the default MTI ciphersuite is always ready to be
used for exactly this reason. IKE's extensively flexible configuration
knobset was not a good idea for this reason.

> MUST NOT, and keep the groups 23-24 as SHOULD NOTs.

This seems reasonable to me.

> implementations will not be conforming rfc4307bis.

That's sort of the point. We want these implementations to NOT support
these groups, just as RC4 die-die-die meant TLS implementations no
longer support RC4.

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

---

From: Paul Wouters <[email-masked]>
Date: Tue, 18 Oct 2016 10:38:52 -0400 (EDT)

> Yeah, we cannot know. That’s why it’s conjecture.

 	conjecture: 1. an opinion or conclusion formed on the basis of incomplete information.

I have complete information for "one cannot detect trapdoors without knowing seed"

Paul

---

From: Stephen Kent <[email-masked]>
Date: Tue, 18 Oct 2016 10:47:00 -0400

Paul,

It's  been over 8 years since this RFC was published, and I have not 
looked at it since then. My recollection is that we wrote 5114 because 
an IPsec developer approached me and said that he wanted to support 
these groups in a product. He said that he wanted test vectors for the 
groups, consistent with what we have done for many other algs. I 
persuaded Matt to generate the RFC because it was a relatively easy task 
a good way for Matt to get acquainted with the RFC process.

As to your question, I have no info about how the NIST DH values were 
generated. However, I do agree with Yoav and Tero that it seems unduly 
prejudicial to declare these to be a MUST NOT. The fact that one can 
generate trap-doored DH values that cannot be detected is not the same 
as having proof that a given set of values have been generated in that 
fashion. Moreover, if one interprets a MUST NOT in this context to mean 
that an implementation supporting any of these groups is non-compliant, 
then that unfairly penalizes existing implementations, as Tero noted. 
Moreover, if the concern raised by the paper (which I have read) is with 
MODP groups of size 1024 (or smaller), only 1 of the groups in 5114 fits 
that criteria (section 2.1).

I have not tracked the status of these NIST groups re evaluation 
criteria like FIPS 140-2. If these groups are approved for use in 
products evaluated under that FIPS (I don't know if they are), 
deprecating them creates a possible conundrum for vendors who want to 
comply with RFCs and with FIPS evaluation criteria. Thus I suggest a 
less dramatic response than declaring all of the groups in 5114 to be 
MUST NOT.

I'm not a vendor of any crypto products (these days), and I've never 
been a crypto mathematician. So my views are based only on what I recall 
about the creation of 5114 and about IETF crytpo standards practices in 
general.

Steve

---

From: John Mattsson <[email-masked]>
Date: Tue, 18 Oct 2016 18:46:29 +0000

New paper “Measuring small subgroup attacks against Diffie-Hellman”

https://eprint.iacr.org/2016/995.pdf

“Cryptographic recommendations from standards committees are often too
weak or vague”

“However, the tangle of RFCs and standards attempting to define current
best practices in key generation and parameter sizing do not paint a clear
picture, and instead describe complex combinations of approaches and
parameters, exposing the fragility of the cryptographic ecosystem. As a
result, developers often forget or ignore edge cases, leaving many
implementations of Diffie-Hellman too close to vulnerable"

“As we show in this paper, finite-field based Diffie-Hellman has many edge
cases that make its correct use difficult, and which occasionally arise as
bugs at the protocol level.”

“As a concrete recommendation, modern Diffie-Hellman implementations
should prefer elliptic curve groups over safe curves with proper point
validation.”

/John

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 19 Oct 2016 09:36:01 +0200

> should prefer elliptic curve groups over safe curves with proper point

I am not sure that the recommendations of this paper should be blindly
trusted. There are some inaccurate facts about a library I work on
[0], but a part of the abstract is also concerning:
"We examine over 20 open-source cryptographic libraries and
applications and observe that until January 2016, not a single one
validated subgroup orders by default."

That's objectively accurate, but the authors do not attempt to find
out the actual issue behind it. Are all implementations bad, or there
are obstacles in doing that? I am aware that TLS client
implementations do not validate subgroup orders by default, because
the group information provided by TLS is not sufficient to validate
the subgroup order. It is simply impossible for them to do any
validation.

regards,
Nikos

[0]. https://lists.gnupg.org/pipermail/gnutls-devel/2016-October/008198.html

---

From: John Mattsson <[email-masked]>
Date: Wed, 19 Oct 2016 08:13:12 +0000

I have not read the paper in detail, but I agree with the high level
conclusions. If it were not for quantum computers, I think IETF should
move to curve25519 as quickly as possible. With quantum computers the
picture is more complicated as ECC would anyway need to be replaced with
PQC in the not to distant future.

Cheers,

John

On 19/10/16 09:36, "[email-masked] on behalf of Nikos
Mavrogiannopoulos" <[email-masked] on behalf of
[email-masked]> wrote:

>[0]. 
>https://lists.gnupg.org/pipermail/gnutls-devel/2016-October/008198.html

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 20 Oct 2016 00:13:46 +0000

Nikos Mavrogiannopoulos <[email-masked]> writes:

>trusted. There are some inaccurate facts about a library I work on [0], but a
>part of the abstract is also concerning: "We examine over 20 open-source
>cryptographic libraries and applications and observe that until January 2016,
>not a single one validated subgroup orders by default."

I've got some comments on it as well, are any of the authors on this list?
There are no email addresses given in the paper and I'm not sure that I should
be spamming them all, or at least the ones I know... in any case the comments
may be of interest to others, so I've posted them here.

  Using shorter private exponents yields faster exponentiation times, and is a
  commonly implemented optimization. The justification for matching the order
  of the subgroup q to the exponent size rather than making subgroup order as
  large as possible is not documented anywhere in the standards documents.

It's not in any standards doc, but it's in HAC AFAIK, and originally came from
a paper by van Oorschot and Wiener.  My code uses a curve-fitting mechanism to
choose the appropriate-size exponent for a given prime (implementation
provided by Colin Plumb many years ago).  Calling it a quadratic curve
calculation is probably over-selling it a bit, it's just a way of matching the
exponent size to the prime size without having to include a large lookup
table.

  For protocols like TLS and SSH that allow a server to unilaterally specify
  the group to use, this validation step is not possible for clients to
  perform for non-safe primes: there is no way for the server to communicate
  to the client the intended order of the group

Actually it is for TLS, anything implementing the TLS-LTS draft [1] will
communicate the group order and the client can then verify it.

  We observe that no implementation that we examined validated group order for
  subgroups of order larger than two

That's kind of a tautology there, both TLS and SSH make this impossible to do.
At the moment there's at least one implementation that does this, and possibly
more (there are some proprietary vendor stacks doing -LTS, but since they're
for embedded devices and tend to be as minimalistic as possible - the most
popular ASN.1 library there is memcpy() - I wouldn't be surprised if they
skipped this particular check).  So there's a minimum of one, and a maximum of
n.

  In addition, we observed that nearly every implementation uses short
  exponents by default,

Yep, because they're the most efficient.  This is what killed RFC 5114,
they're the most inefficient (random) DH domain parameters ever published.
Which, in the long run, was probably a good thing since it strongly
discouraged their use.

  They have been widely implemented in IPsec and TLS

Not in TLS they ain't, for the reason given above.  I realise there are
oddball implementations out there that use or enable their use, but I wouldn't
say that counts as "widely used".

  This means a client has no feasible way to validate that the group sent by
  the server has the desired level of security or that a server’s key exchange
  value is in the correct group for a non-safe prime.

See the previous note, TLS-LTS provides this capability.  If you're using the
RFC 3526 DH params then you can also pretty easily recreate q from them, so
it's a simple change to apply this fix.

(TLS-LTS also fixes a number of other issues in TLS 1.2 and earlier, it's not
only the DH fix that's in there).

  TABLE II: TLS Library Behavior

I assume this was the item that Nikos was grumbling about :-).  The two issues
are that the "Reuses exponent" entries are rather unclear and "Validates
Subgroup" is somewhat tautological since standard TLS (without -LTS) doesn't
allow you to do this, so the anwer is always "No".  I assume for "Reuses
exponent" the entry "Application dependent" means "it's not very clear from
the code", because my code certainly never reuses DH exponents.  However, to
see that you need to know that although each DH instance uses an { x, y } pair
that's fixed at the time of creation, no DH instance is ever reused in a TLS
or SSH session,

(Nikos, if you want to do the subgroup checking with GnuTLS and interop-test
an implementation that provides subgroup info and does the required checking,
let me know and I'll put up a server.  Same for anyone else, e.g. the OpenSSL
guys).

  implementations should follow the guidelines outlined in RFC 7919 for
  selecting finite field Diffie-Hellman primes

Uh, no.  7919 is a my-way-or-the-highway spec, or more accurately my-way-or-
no-way.  You can't say "I'd like to do DH-2048" as with SSH, you can only use
the one value that 7919 specifies and if either side chooses some other
DH-2048 value you're required to fall back to RSA.  When this was discussed on
the TLS list, the general response, from those who commented, was that they
weren't going to use it because of this and other problems it had.  Some of
these issues were brought up long ago (e.g. [2]), but ignored.  So 7919 is
pretty much a non-starter.

  implementations should prefer “safe” primes of documented provenance of at
  least 2048 bit

This is unfortunately easier to recommend than to do.  For example my code
(and some other implementations I know of) recognise and fastpath known-good
values like the RFC 3526 ones, but you can't restrict yourself to only using
known-good values because too many sites use who-knows-what sort of values,
and you'd lose the ability to connect to a significant chunk of the net if you
get too exclusive.

The real solution, and obviously I'm a bit biased here because I'm the author
(but then it was also an obvious problem that needed fixing), is to use -LTS,
which provides what you need to validate the DH parameters.

Peter.

[0] Not my footnote.
[1] https://datatracker.ietf.org/doc/draft-gutmann-tls-lts.
[2] https://www.ietf.org/mail-archive/web/tls/current/msg18697.html.

---

From: Antonio Sanso <[email-masked]>
Date: Thu, 20 Oct 2016 08:18:19 +0000

hi Peter, (one of the authors here)
thanks a lot for you comments.
As for the case with Nikos we take on board and well appreciate comments/feedbacks.
Will pass the message.

Thanks a lot and regards

antonio