[Cfrg] Curve25519 v Cheon ...

[Dan Brown <[e-mail]>]

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