<html><body><div style="height:1px;"></div>Hello, Mike Hamburg! Thank you, now I understand this problem better. So, I understand that G and J must generate the entire group and also that p must be negligibly-close to a power of 2. But I don't understand that Alice must check that Gb and Jb aren’t in the small subgroup for preventing an active dictionary attack. In original EC-EKE Alice abort if Mb not valid, and in rewritten version Alice send Ma as random instead. What is the possibility for active dictionary attack for Bob while he don't know password? And, if this check is still mandatory, how complicated is it? Van Gegel. <div style="font-size:0.9em;font-style:italic;"> --- Original message --- From: "Mike Hamburg" <mike@shiftleft.org> Date: 8 March 2018, 21:11:42 </div> <blockquote class="xfmc1" style="border-left:1px solid rgb(204, 204, 204);margin:0px 0px 0px 0.8ex;padding-left:1ex;"><pre>Hello Van Gegel, This seems reasonable, but it’s worth the exercise to prove security in order to make sure there aren’t subtle attacks. For example, G and J must generate the entire group and not just the subgroup (unlikely the canonical Curve25519 G), or else there is a passive dictionary attack. Also, Alice must check that Gb and Jb aren’t in the small subgroup, or else there is an active dictionary attack. Also, p must be negligibly-close to a power of 2 (which it is for Curve25519). The proof is likely to be somewhat tricky though, because you will need Enc to be an ideal cipher, and you will have a somewhat unusual CDH assumption because (Gb, Jb) is equivalent to a point on E_Fp^2 instead of E_Fp. Cheers, — Mike > On Mar 7, 2018, at 1:57 AM, Van Gegel <<a href="mailto:torfone@ukr.net" target="_blank" rel="noreferrer noopener">torfone@ukr.net</a>> wrote: > > Hello all! > > I searches simple solution for PAKE using only X25519 library. > Unfortunately mostly all protocols requires group addition or/and elligator. > Thanks Mike Humburg refers to inverse square root code and also AMBER Cryptography library (<a href="https://github.com/bernedogit/amber" target="_blank" rel="noreferrer noopener">https://github.com/bernedogit/amber</a>) I successfully add elligator2 to ASM Cortex M0 uNaCl library, without long multiplication (<a href="https://munacl.cryptojedi.org/cortexm0.shtml" target="_blank" rel="noreferrer noopener">https://munacl.cryptojedi.org/cortexm0.shtml</a>) > and also to forx25519-cortexm4 ASM library with long multiplication (<a href="https://github.com/weedegee/x25519-cortexm4" target="_blank" rel="noreferrer noopener">https://github.com/weedegee/x25519-cortexm4</a> ). > M0 code of isr() is about 400 bytes. This solve my problem. > > But recently I re-read paper of Daniel J. Bernstein, Mike Hamburg, Anna Krasnova, Tanja Lange Elligator: Elliptic-curve points indistinguishable from uniform random strings (<a href="http://elligator.cr.yp.to/elligator-20130828.pdf" target="_blank" rel="noreferrer noopener">http://elligator.cr.yp.to/elligator-20130828.pdf</a>) and find interest moment. > On "2.7 Active attacks" authors refers to old paper of Colin Boyd , Paul Montague , Khanh Nguyen Elliptic Curve Based Password Authenticated Key Exchange Protocols (2001) > (<a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CC0144B723B43385A22CA617D53FEF15?doi=10.1.1.10.6273&rep=rep1&type=pdf" target="_blank" rel="noreferrer noopener">http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CC0144B723B43385A22CA617D53FEF15?doi=10.1.1.10.6273&rep=rep1&type=pdf</a>) > described EC-EKE protocol with compressed Edwards points. > > DJB at all. said: "Our attack is to actively rerandomize one of the two points sent by Bob. If this point is on the same curve then Alice aborts; if this point is not on the same curve then Alice does not notice and communication continues." > > I'm not sure, but this attack can be completely solved including all public values under hash: if Eva will modifies any value the authentificator will be wrong so Eva can not obtain was this work or dummy point. > > I tried to rewrite Boyd at all. EC-EKE for Montgomery X25519, now it is not require any checking of point is on curve or on twist (so not need square root): > > Let G is Montgomery generator on EC25519 curve and J - on it's twist. All multiplications are with standard X25519 procedure (i.e. *8). H is PRF (Keccak). > > Alice is initiate and randomly select G or J for this session. > Alice generate random a and compute X*a = G*a or J*a depends selecting, set bit 255 randomly. Now it is completely random string. > Alice encrypt X*a by password, and send Enc(X*a) to Bob. > > Bob decrypt Enc(X*a) to X*a by password. > Bob generate random b and compute both G*b and J*b > Bob compute secret Sb=X*a*b > Bob compute authentificator Mb=H(Sb || Enc(X*a) || G*b || J*b) > Bob sends to Alice: Mb, G*b, J*b > > Alice compute two secrets S1=G*b*a and S2=J*b*a > Alice compute two authentificators: M1=H(S1 || Enc(X*a) || G*b || J*b) and M2=H(S1 || Enc(X*a) || G*b || J*b) > Alice checks either Mb ?= M1 or Mb ?= M2 > Alice compute her authentificator Ma=(S1 || G*b || J*b || Enc(X*a)) or Ma=(S2 || G*b || J*b || Enc(X*a)) depends M1 or M2 matched or set Ma as random if not matched > Alice send Ma to Bob > > Bob check Ma ?= H(Sb || G*b || J*b || Enc(X*a)) > > This seems safe against partition attack but I'm not sure... > Van Gegel > _______________________________________________ > Messaging mailing list > <a href="mailto:Messaging@moderncrypto.org" target="_blank" rel="noreferrer noopener">Messaging@moderncrypto.org</a> > <a href="https://moderncrypto.org/mailman/listinfo/messaging" target="_blank" rel="noreferrer noopener">https://moderncrypto.org/mailman/listinfo/messaging</a> </pre></blockquote> </body></html>