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.ha...@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@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
