Subject: [Cfrg] Curve25519 v Cheon ...

From: Dan Brown <[email-masked]>
Date: Fri, 3 Aug 2018 18:49:23 +0000

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 3 Aug 2018 23:16:55 +0300

> twist, though I am not sure which situation this applies to.

Note that if one is dealing with any kind of more complicated  operations
than ECDH, then one typically uses Edwards25519 instead of Curve25519 as
the latter has defined point addition. And with that curve, one must
check points.

Factorizing the order of Edwards448 +-1:

l+1=2*2*5*40426179255361943*117022176685990080317952907*1920512778107470297051284135413772115136848527535710350664567491939533123490247759565643789
l-1=2*3*19*19*97*227393*3009341*342682509629*6730519843040614479184435237013*547972593843380542316719287015009101629889568888367769396279985548530313239

I have not even tried to factorize the order of the twist of that
curve. Neither of those two factorizations was practicularly quick.

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Fri, 3 Aug 2018 20:59:43 +0000

-----Original Message-----
From: Cfrg <[email-masked]> On Behalf Of Ilari Liusvaara

<DB> In Ford-Kaliski OPRF, the operation is even simpler than ECDH, because
there is no hashing, just a raw scalar multiplication (but with a fixed
static secret key), in which case, it seems reasonable to use the Montgomery
form, no?</DB>

l+1=2*2*5*40426179255361943*117022176685990080317952907*19205127781074702970
51284135413772115136848527535710350664567491939533123490247759565643789
l-1=2*3*19*19*97*227393*3009341*342682509629*6730519843040614479184435237013
*547972593843380542316719287015009101629889568888367769396279985548530313239

<DB> Thanks, I didn't even bother to look at Curve448 at all.  Those
factorizations roughly fit the typical pattern (~ 2/3 of the bits in the
largest prime, and continuing downwards).  </DB>