
Date: Wed, 20 Jan 2016 10:25:42 0700 From: Kurt Seifried <kseifried@...hat.com> To: Daniel Kahn Gillmor <dkg@...thhorseman.net> Cc: osssecurity <osssecurity@...ts.openwall.com> Subject: Re: Prime example of a can of worms On Wed, Jan 20, 2016 at 10:20 AM, Daniel Kahn Gillmor <dkg@...thhorseman.net > wrote: > 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". > Sorry yes, although this also applies equally to keys/etc. > > > 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? > I looked at this a bit and quite honestly the computational time involved is just to much to be useful, unless we're talking about generating a small set of highly trusted primes. For normal people, this just isn't feasible (witness prime generation taking between less then a second, and more than 10 minutes, nobody wants to wait 10 minutes...). > > 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. > Yup, that was a lesson learned. > > 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. > Agreed, I listed the diversity more as a stopgap for the cases where people have older hard/software (e.g. Java) that will never support larger primes/keys. At least then you don't get caught in dragnets for the default/commonly used primes. > > Thanks very much for your analysis. > > Regards, > > dkg >   Kurt Seifried  Red Hat  Product Security  Cloud PGP A90B F995 7350 148F 66BF 7554 160D 4553 5E26 7993 Red Hat Product Security contact: secalert@...hat.com
Powered by blists  more mailing lists
Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.