Subject: [Cfrg] ECDLP:ECDHP in Curve25519 [was RE: Curve25519 v Cheon ...]

From: Dan Brown <[email-masked]>
Date: Mon, 13 Aug 2018 15:20:07 +0000

Hi again,

This email concerns a "provable security" type result, a topic mostly for 
theorists.

My email below on the Cheon issue, jarred my memory about a(n _unreferreed_) 
reduction from DL to DH, that I wrote about a while back (Theorem 3.4, 
https://eprint.iacr.org/2014/877.pdf#lem.3.4 ).

Impact: _if_ the reduction is correct, and _if_ the ECDLP in Curve25519 costs 
at least ~ 2^126 group operations (a poor-precision estimate, of course), 
_then_ the ECDHP in Curve25519 costs at least ~ 2^(126-7) group operations (a 
worse precision estimate, but still quite high).  (The 2nd estimate glosses 
over some details, and might need a correction.)

Caveat: for weaker assumptions about the ECDLP in Curve25519, e.g. 2^63 groups 
operations, the theorem provides says very little about the cost of the ECDHP 
(it could drop to zero), i.e. the ration ECDLP:ECDHP is not constant.  Of 
course, such drastically weaker assumptions would only to be accommodate a 
disastrous breakthrough in the ECDLP, in which case, one should be using a 
larger curve (or some alternative to ECC).

Again: this reduction has not been confirmed by any other person.  Indeed, 
since writing that report, my confidence level in that part has fallen 
considerably, mostly due to forgetfulness.  I do recall being surprised very 
much by it, but I managed convince myself of its correctness, so I wrote it up 
and/or down.

Also, I have not carefully compared what this says about ECDHP to what 
Maurer-Wolf (MW) reduction would or could say about ECDHP.  For example: there 
exists an auxiliary MW curve of order 2^252 over the field of size n (where n 
is the prime order of non-twist base point).  Unfortunately, I don't know how 
to construct such a curve.  Regardless, this would imply the ECDHP solver 
could be used to build a ECDLP solver of some relative cost (again I would 
need to work out the details of this cost).  Unlike the result above, the 
ratio ECDLP:ECDHP in the MW reduction probably does not degrade under weaker 
assumptions about the hardness of ECDLP, etc.

Of course, a similar reduction should apply to NIST P-256, though maybe with a 
different ratio... (The eprint with reduction has its main topic being yet 
another curve, which I deemed to nearly optimize this ratio ...)

Finally, I am also aware of the reasonable conjecture ECDLP:ECDHP = 1, which 
in some sense supported by the reductions of the kinds above, but also 
supported by the fact that nobody has found a better way to solve ECDHP, than 
to solve ECDLP, and there is also support in generic groups, etc.

Best regards,

Dan

-----Original Message-----
From: Cfrg <[email-masked]> On Behalf Of Dan Brown
Sent: Friday, August 3, 2018 2:49 PM
To: [email-masked]
Cc: Hugo Krawczyk ([email-masked]) <[email-masked]>
Subject: [Cfrg] Curve25519 v Cheon ...

Hi,

I was asked off-list if I know the necessary parameter factorizations involved 
in the Cheon-type attack against Curve25519. This may be somewhat relevant for 
the Ford-Kaliski OPRF construct used in OPAQUE, recently proposed to CFRG.

I did not know the relevant factorizations, but was curious, so I used 
SageMath to find the factorizations.

TL;DR: Non-twist Curve25519 nearly fully resists Cheon attack; if twist points 
are allowed, then resistance is approximately typical for a curve of its size.

(Reminder: Cheon's attack is expensive, requires many queries, and does not 
affect hashed ECDH or ElGamal-style signatures, such as ECDSA or
EdDSA/Schnorr.)

More details:

Main curve, prime base point order n:
n = 2^252+27742317777372353535851937790883648493
n-1 = 2^2 * 3 * 11 * 198211423230930754013084525763697 *
276602624281642239937218680557139826668747
n+1 =  2 * 5 * 7 * 103 * 684245902131068969 *
1466936914520620440380580414586728830413895967152734051
Twist curve, prime base point order m:
m = 2^253 - 55484635554744707071703875581767296995
m-1 = 2^2 * 79 * 117223 * 6418733 * 2220636239 *
27413359092552162435694767700453926735143482401279781
m+1 = 2 * 3 * 25759 * 65239 * 84185933008598999 *
17051470131630101375531586771020539887753991037867

Caveat: I may have mis-pasted these numbers (they might be missing a digit
here or there).  Of course, if I mis-pasted n or m, then subsequent
factorization would be wrong and irrelevant.  (I factored m and n, and got
primes, a check against the chance I miscopied m or n.)

Aside: All these factorization were quite quick, just seconds on a PC, except
n-1, which took minutes (since it is RSA-like number with two big factors).

Recall that Cheon's attack has a narrow impact.   If a protocol provides an
oracle for a static scalar multiplier, which is usually only needed for
protocols that have a blinding or oblivious step, and does not include ECDH or
ElGamal signature, then Cheon's attack might reduce security slightly below
the usual 128-bit level, at the cost of very many queries to the oracle.  The
effectiveness of this attack depends on the factorization of the base point
order +/- 1.  The smaller factor indicate the query complexity of the attack,
while the square of the remaining factors indicates the off-line computation.
(I actually the forget the details to any greater precision than that.)

For Curve25519, numbers n+/-1 have either very small factors, or very large
factors.  The factorizations means that (non-twist) Cheon's attack has nearly
negligible reduction in security, or else requires an impractical (2^60)
number of queries.  By contrast, considering the twist case, the m+/-1 numbers
have more typical factorizations, with some medium size factors, so very
roughly the attack applies in a typical way (with a large number of queries,
and a huge computational cost, usually).  Many Curve25519 implementations do
not check for points on the twist, in which Cheon's attack on the twist might
be applicable.  I've heard that some proposal suggest reject points on the
twist, though I am not sure which situation this applies to.

I presume it is a pure fluke that non-twist-only Curve25519 nearly fully
resists Cheon's attack.  I don't recall if CFRG made this feature part of its
desirable list, when it was asked by TLS to recommend to new curves.

Brief side notes on other curves ...

NIST curves: R. Gallant and I long ago wrote a paper in which we discussed
this issue for NIST case in the n-1 case of the attack.  IIRC, the
factorizations were mostly typical (a mix of small, medium and large prime
factors).  We didn't do the n+1 case, pre-dating Cheon (who discovered the n+1
case).

2y^2=x^3+x/GF(8^91+5): the new curve I proposed in an I-D (and presented to
CFRG), has a typical vulnerability to Cheon.  I think the I-D recommends to
only use this curve in ephemeral ECDH (or signatures?).

Best regards,

Dan