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

[Antonio Sanso <[e-mail]>]

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

On Oct 20, 2016, at 2:13 AM, Peter Gutmann <[e-mail]> wrote:

> 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.
> 
> _______________________________________________
> saag mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/saag