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

Gregory Maxwell gmaxwell at gmail.com
Mon Jun 1 17:19:20 EDT 2015


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 ?
>
> It's like saying, "I picked red because it is provably the most prominent
> warning colour in nature, and the fastest" while hiding a "I have a back
> door for red" in my pocket.

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.

By cherry picked, e.g. it lists as a top level criteria
"indistinguisability" which they define as the known-existence
("elligator) of a cheap bijective mapping from a subset of points to
uniform byte-strings; which is an interest but very niche criteria
only really applicable to some stegnographic encoding applications;
but it doesn't constrain the curve co-factor.  By having a non-prime
order, there is an immediate (well known) reduction in discrete-log
security, and an increase in complexity of applications-- they have to
be sure to multiply by the cofactor,  a failure to handle this has
lead actual certificational vulnerabilities in real password based key
agreement protocols.  (But the shape used and some of the other
characteristics require that there is a cofactor of at least 2). So--
"prime order" is a criteria others have used (e.g. brainpool) that is
excluded here and which curve25519 fails-- this doesn't prevent it
from being an excellent choice though-- but if the comparison were
neutral it would list this criteria, and note that the Twisted Edwards
curves fail it.

For, the implementation-conflating; e.g. points are made about
constant time operation but this is an implementation detail; the
curve choice angle on this is purely on points like the "fastest
possible is easy to make constant time", which is a weak argument:
non-constant time is still considerably faster (and existing ed25519
implementations are very much non-constant time for non-secret-key
operations like verification for speed reasons)... the differences for
constant time in other curve choices are only a few percent, and
anyone worrying about the simplest possible implementation is likely
playing with fire to begin with.


More information about the OTR-dev mailing list