
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.
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.