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

[Peter Gutmann <[e-mail]>]

Nikos Mavrogiannopoulos <[e-mail]> writes:

>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."

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.