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

[Taylor R Campbell]

   Date: Mon, 1 Jun 2015 21:19:20 +0000
   From: Gregory Maxwell <gmaxwell at gmail.com>

   On Mon, Jun 1, 2015 at 8:32 PM, Paul Wouters <paul at cypherpunks.ca> wrote:
   > On Tue, 26 May 2015, Taylor R Campbell wrote:
   >> 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.
   >
   > But how do you know those arguments aren't cherry-picked ?

   Curve25519 is quite nice; but the arguments on SafeCurves, at least,
   are somewhat cherry-picked; and many of the discussions about it
   conflate curve choices with implementation details.

Many discussions about it also conflate curve choice (`Curve25519')
with DH function choice (`X25519', following the nomenclature of
<https://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html>).
This thread is about choosing a DH function, under the supposition
that finite-field DH over group 5 may provide a smaller security
margin than we would like.

Indistinguishability is not relevant to OTR [1], and while OTR's use
of DSA-1024 has long concerned me, it is not the subject of this
thread.  The paper I cited is also concerned with a DH function, and
not with indistinguishability or signature schemes [2].

If you insist on defining DH(s, P) = s*P for arbitrary secret 256-bit
strings s and public curve points P, then yes, the curve had better
have cofactor 1 to defend against small-subgroup attacks.

But there's no rule that requires you to define DH that way.  You can
instead define DH(s, P) = s*c*P where c is the cofactor, or prescribe
that secrets be divisible by c.  X25519 does exactly that, and test
vectors easily ensure that applications won't fail to do it.

I think it is a stretch to call it cherry-picking when one makes
practical defence against known small-subgroup attacks be a criterion
for a DH function, rather than making cofactor 1 be a criterion for
the curve underlying a DH function [3].

Similar remarks apply to the implementation issues you mentioned: a DH
function had better be easily and efficiently implementable in time
independent of the secret (and, e.g., DH over NIST P-256 is not), but
for most protocols including OTR it doesn't matter if signature
verification runs in time dependent on the signature and public key.


[1] The surrounding data already has ?OTR? markers revealing it is an
OTR conversation, and presumably headers identifying the sender and
receiver for the sake of XMPP routing or whatnot.

[2] By happy coincidence, the curve underlying X25519 also turned out
to work for indistinguishability (Elligator 2) and signature schemes
(Ed25519).

[3] SafeCurves addresses this in <http://safecurves.cr.yp.to/twist.html>:

  `A curve designer can protect against [small-subgroup attacks] by
   choosing curves with [cofactor 1].  A protocol designer can protect
   against [small-subgroup attacks] for any curve by [multiplying
   secrets by the cofactor].  Even without any defences, the impact is
   limited to sqrt(cofactor).'

SafeCurves doesn't fail to constrain the curve cofactor.  It doesn't
directly constrain the cofactor to be 1: instead it constrains the
practical security consequences of cofactor and twist cofactor against
known small-subgroup and invalid-curve attacks.