Re: Prime example of a can of worms

[Kurt Seifried <kseifried () redhat com>]

On Wed, Jan 20, 2016 at 10:20 AM, Daniel Kahn Gillmor <dkg () fifthhorseman net
> wrote:

> Hi Kurt--
>
> On Wed 2016-01-20 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/primes-parameters-and-moduli/
>
> Thanks for this writeup!
>
> the chart at
>
> https://securityblog.redhat.com/wp-content/uploads/2015/12/DH-Param-Compromise-300x269.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 Miller-Rabin 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 miller-rabin 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
> unknown-key-share 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 < p-1 to avoid the small-subgroup 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 finite-field 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 (generically-specified) curves, pretty much no one uses them in
> practice, and the custom-curve implementations are likely to be both
> inefficient and leaky (to say nothing of the difficulty of verifying
> that the offered curve is well-structured 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
> finite-field DH seems likely to be slow (additional runtime checks, no
> optimized implementations), buggy (missing or inadequate runtime checks,
> side-channel leakage), and bandwidth-heavy (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 believed-weak, widely-shared groups, and to introduce new
> widely-shared 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 stop-gap 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 () redhat com