[OTR-dev] Fwd: Some DH groups found weak; is OTR vulnerable?

Taylor R Campbell campbell+otr at mumble.net
Tue May 26 11:07:46 EDT 2015


   Date: Mon, 25 May 2015 15:11:32 -0400 (EDT)
   From: Paul Wouters <paul at cypherpunks.ca>

   >> Using a larger DH group is totally reasonable - namely a 2048bit group
   >> or a larger one.

   Is it? Compared to the AES key size we use? Which I think is still 128bit?

If you compare the various public methods of estimating work factor at
<http://www.keylength.com/>, you'll see that to make the work factor
of finite field discrete log match that to guess a 128-bit secret, you
need at least a 2048-bit prime, in every method listed there.  I'm not
vouching for the accuracy of any one of those methods, but surely the
least conservative of them should set a lower bound on the size of the
prime needed.

So yes, using even a 2048-bit finite field DH group with AES-128 is
certainly reasonable.  It would also be reasonable to increase the AES
key size to 256 bits, in order to attain a security level of 128 bits
even against multi-target attacks.

   >> it is that whenever this topic comes up for discussion it ends with
   >> "lets just switch to ECC and do away with this problem entirely."

This is also a reasonable choice, particularly if

(a) bandwidth is a strong concern, or
(b) it's just as much trouble to replace finite field DH by elliptic
curve DH altogether as it is to change finite field DH groups.

   Don't we have to pick points on a curve, and than we run into a similar
   problem of which points are unsafe and how to do know? Isn't that why
   the NIST (or brainpool or djb) curves tell us which points to use?

No.  Choosing a prime for finite field DH is analogous to choosing a
curve for elliptic curve DH.

The analogue to picking points on a curve is picking a generator for
the group.  For DH over the Oakley groups, one uses the generator with
the smallest representative, 2.  For X25519 (DH over Curve25519), one
uses the generator with the smallest x coordinate, 9.

I don't know of any weaknesses in generator selection, either in
finite field DH or elliptic curve DH, provided it generates a subgroup
of sufficient size.  Any such weakness probably translates to a
weakness in the cryptosystem altogether.  So for this arbitrary
decision, the smallest value is a reasonable choice.

   I'm also always quite amused how people jump to curve25519. While
   people ask how NIST got their numbers, they just take djb's word on
   it for his choice of numbers ("I won't talk about speed but they
   are the fastest").

The curve shape and every parameter in Curve25519 are fully justified
in in the paper <http://cr.yp.to/ecdh/curve25519-20060209.pdf> to
provide the maximum performance for a prescribed security level, or to
be the smallest values for an arbitrary choice satisfying all security
criteria.  For example, the coefficient A = 486662 in the curve shape
y^2 = x^3 + Ax^2 + x is chosen to be the smallest value satisfying all
security criteria; smaller values obviously simplify the scalar
multiplication algorithm.

Not true of the NIST curves.  For NIST P-256, the constant b =
0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b in
the curve shape y^2 = x^3 - 3x + b is explained only as the 256-bit
truncation of

SHA-1(s) || SHA-1(s + 1) || SHA-1(s + 2) || ...

where s = 0xc49d360886e704936a6678e1139d26b7819f7e90 is completely
unexplained (see
<http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf>).

The same approach as yielded Curve25519 -- setting down security
criteria and finding the fastest/smallest parameters that support them
-- has yielded other curves with higher security levels, different
applications (e.g., Curve1174 admits the Elligator 1 map), &c.

One such curve, E-521, was independently found by three different
research groups at the same time searching for a curve with the
beyond-paranoid 256-bit security level, serving only as a hedge
against partial breakthroughs in elliptic curve cryptanalysis.  (The
prime, 2^521 - 1, is the same as in NIST P-521, but the curve shape
and coefficients are different.)


More information about the OTR-dev mailing list