
Date: Wed, 20 Jan 2016 12:20:09 0500 From: Daniel Kahn Gillmor <dkg@...thhorseman.net> To: Kurt Seifried <kseifried@...hat.com>, osssecurity@...ts.openwall.com Subject: Re: Prime example of a can of worms Hi Kurt On Wed 20160120 10:45:07 0500, Kurt Seifried wrote: > I finally got the article written and published, it's at: > > https://securityblog.redhat.com/2016/01/20/primesparametersandmoduli/ Thanks for this writeup! the chart at https://securityblog.redhat.com/wpcontent/uploads/2015/12/DHParamCompromise300x269.jpg uses the terms "keys" in the axis labels, but i think you mean "primes" or "moduli". > TL;DR: I found a lot of messy problems and no really good solutions. But > ultimately we need to start using bigger keys/primes or this is all just a > waste of compute time (might as well go back to clear text). yes, larger primes are clearly needed. The discussion gets a little ways into the issue of negotiating primes between peers, but doesn't address some underlying issues. For one, the writeup addresses probabilistic primality tests, but doesn't describe proofs of primality, which are significantly more expensive to generate (and still probably more expensive to verify than a short MillerRabin test). But these proofs provide certainty in a way that probabilistic tests might not. If we're talking about runtime primality checking when communicating with a potential adversary, are there proofs about the (im)possibility of generating a pseudoprime that is more or less likely to pass a millerrabin test? Additionally, the fact that the modulus is prime is an insufficient test  it needs to be a prime of a certain structure, or else the remote peer can force the user into a small subgroup, which can lead to unknownkeyshare attacks, key factorization, or other problems. One approach is to require that moduli be safe primes (p = (q*2) + 1, where q is also prime) and to verify that the peer's public share k is in the range 1 < k < p1 to avoid the smallsubgroup attack of size 2. This appears to be the best we know how to do with diffie hellman over finite fields, but it limits the range of acceptable moduli even further, and requires two primality tests for the peer seeing the primes for the first time. It's also worth noting that we have a similar concern with elliptic curve DH (ECDH)  the structure of the curve itself (which is the equivalent of the generator and the modulus for finitefield diffie hellman) is relevant to the security of the key exchange. In the ECDH space, there appears to be little argument about trying to use a diversity of groups: while many specifications provide ways to use custom (genericallyspecified) curves, pretty much no one uses them in practice, and the customcurve implementations are likely to be both inefficient and leaky (to say nothing of the difficulty of verifying that the offered curve is wellstructured at runtime). Indeed, the bulk of the discussion around ECDH is about picking a small handful of good curves that we can publicly vet, and then using those specific curves everywhere (see curve 25519 and goldilocks 448, the CFRG's upcoming recommendations). Encouraging peers to select a diversity of large custom groups in for finitefield DH seems likely to be slow (additional runtime checks, no optimized implementations), buggy (missing or inadequate runtime checks, sidechannel leakage), and bandwidthheavy (the moduli themselves must be transmitted in addition to the public keys), and as you say, the diversity of groups doesn't win you as much as just switching to larger groups in the first place. I agree that we need machinery in place to be able to relatively easily drop believedweak, widelyshared groups, and to introduce new widelyshared groups. But i'm not convinced that encouraging the use of a diversity of groups is really the "Best Default/Operational" tradeoff, as it is indicated in your chart, given the concerns above. Thanks very much for your analysis. Regards, dkg
Powered by blists  more mailing lists
Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.