[curves] Curve19119: A legacy-level little brother of Curve25519

[Mike Hamburg]

> On Jul 28, 2017, at 8:50 AM, Björn Haase <bjoern.m.haase at web.de> wrote:
> 
> Hi Trevor,
> 
>> * Did you give any thought to FourQ, which claims similar speedups
>> with respect to 25519 but also a similar security level? [1]
> 
> Not so far. Actually I have more closely looked at FourQ only this week after a discussion with Diego Aranha.
> My (very preliminary) assessment after 3h of reading is, that the field arithmetic for the extension field
> should be somewhat slower than for Curve25519's prime field (at least on small microcontrollers).
> The main benefit that I did identify is that by using the curve endomorphisms allows for speedups on the DH algorithm level.
> 
> Regarding FourQ: Most efficient PAKE protocols, I am aware of want an efficient mapping algorithm. I didn't yet assess whether Elligator or Elligator2 may be applied also to the FourQ point group. Finally it seems also be constructed over an Edwards curve, so one of the two reptiles might very well be available?

Elligator 2 works for any elliptic curve (over a field of odd characteristic IIRC) with at least one point of order 2.  So you can use it on FourQ.

Elligator 1 works on a strict subset of these curves and is more complicated, so as far as I’m concerned it should never be used.

In addition to FourQ and Curve19119, other fast-ish options include 2^252-2^232-1 (but maybe not on tiny micros); NIST’s 2^192-2^64-1 (but again maybe not on the M0?); and the Goldi-like 2^216-2^108-1.  But I agree that you should stick with Curve25519 if you can afford it.

> Apart of that: I feel quite save using Curve25519 for production use. For FourQ on the other hand, my gut feeling is that FourQ might not be sufficiently well-established and mature for using it in production code. At least we would probably be facing many questions from external security-reviewers and/or customers.
> 
> * For the PAKE, since you have Elligator, did you consider anything
> like the "SPAKE2-Elligator Edition" approach of [2] - basically,
> DH-EKE where the DH public values are masked by adding
> Elligator(password)?
> 
> EKE used to be patented until this year, IIRC. This had scared us away from using EKE and EKE variants so far. When comparing SPAKE2 with our PACE variant, I believe that our implementation has slightly better execution time and a smaller memory-footprint as a trade-off for more message exchanges.

> Note that for SPAKE2 you would need either point compression or point verification IIUC, which we also tried to avoid due to patent issues: One nice feature of our PACE variant is that we could operate on a X-Coordinate-only ladder on a montgomery ladder and curve which is not the case with SPAKE2-Elligator Edition. The Hisil-Wong-Dawson formulas actually are also very fast, however we would probably need some table-based precomputation (IIUC) in order to reach the same efficiency level as for, e.g. x-coordinate-only X25519. On our resource-constrained target table-based precomputation is not a good idea in my opinion (both regarding RAM consumption, fault injection and side-channel issues).

I realized at some point that “SPAKE2-EE” is actually an existing protocol called “PAK”, which is why I didn’t ever write it up.

On a constrained device, a SPEKE variant (like PACE) is a faster and simpler choice.  Also I thought the SPEKE patent expired, so why not use that?  SPAKE2 (-EE and otherwise) has a stronger security proof, supports augmentation, and is potentially faster with precomputation. I don’t know if there is an augmented version of SPEKE.

> I found an interresting aspect in the 2015 thread about SPAKE2 EE that I did not consider yet: We actually don't need to generate an affine point with the elligator, but for PACE and SPAKE2 EE we might have a more efficient solution when taking it in projective coordinates. Maybe we could get rid of one of the exponentiations in the elligator calculation (v, epsilon) at the cost of slightly less optimal differential addition formulas for the montgomery ladder with a projective difference point x0 ... Don't know yet which variant would come out faster.

It is possible to compute Elligator straight to affine with only one exponentiation, using the inverse square root trick.

You want x = -A/(1+ur^2), or -A-that, so you need to simultaneously divide by 1+ur^2 and compute the Legendre symbol of the putative y^2 = x(x^2+Ax+1).  If you compute that projectively to get y^2 = a/b, then L(a/b) = L(ab), so you don’t need to do the division first.  Let c=ab, d=1+ur^2.  Then you can compute

s := (cd^2) ^ ((p-3)/2)

Then (s^2 * cd^2) = (cd^2)^(p-2) = 1/cd^2, so that 1/d = (s^2 * cd^2) * cd unless c=0 or d=0.  But if c=0 then the point is (0,0) or infinity, and if d=0 then it’s infinity, so in either case you should return 0 anyway.  At the same time, (s * cd^2) = (cd^2)^((p-1)/2) = L(cd^2) = L(c) unless d=0.  So that gives you the inverse and Legendre symbol at the same time.  A similar trick with (cd^2)^((p-5)/8) can give you the square root, but you don’t actually need that here if you’re using an x-only ladder.

If you don’t do this, then compared to dividing, the projective ladder requires one more register (Z0) and is slower if you have a dedicated squaring algorithm.  It’s faster if you’re using multiply as square.

> Yours,
> 
> Björn.

Cheers,
— Mike


> Am 28.07.2017 um 00:32 schrieb Trevor Perrin:
>> On Thu, Jul 27, 2017 at 4:27 PM, Björn Haase <bjoern.m.haase at web.de> wrote:
>>> "Making Password Authenticated Key Exchange Suitable For
>>> Resource-Constrained Industrial Control Devices"
>>> https://eprint.iacr.org/2017/562
>>> 
>>> We observe a speedup factor of roughly 1.9 in comparison to our X25519
>>> implementation on a Cortex M0+ microcontroller.
>> 
>> Hi Björn,
>> 
>> Thanks, that's a good read.  Couple Qs:
>> 
>>  * Did you give any thought to FourQ, which claims similar speedups
>> with respect to 25519 but also a similar security level? [1]
>> 
>>  * For the PAKE, since you have Elligator, did you consider anything
>> like the "SPAKE2-Elligator Edition" approach of [2] - basically,
>> DH-EKE where the DH public values are masked by adding
>> Elligator(password)?
>> 
>> Trevor
>> 
>> [1] https://eprint.iacr.org/2017/434.pdf
>> 
>> [2]
>> https://moderncrypto.org/mail-archive/curves/2015/000424.html
>> https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf
>> 
> 
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170728/d880a287/attachment.bin>