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

[Björn Haase]

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?

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 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.

Yours,

Björn.

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
>