> On Jul 28, 2017, at 8:50 AM, Björn Haase <bjoern.m.ha...@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.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
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves
