[messaging] X25519 EC-EKE

[Mike Hamburg]

The check should be simple-ish.  In fact, you can have both sides compute habX instead of abX, where h is the cofactor, check that it’s not the identity point, and then use it.

Suppose Rob is trying to impersonate Bob.  Rob sends bG and/or bJ in a small subgroup.  Then abG or abJ is also in the small subgroup, so Rob can guess it and use this to create his authenticator.  This enables him to authenticate with Alice without knowing the password, and simultaneously to gain information about the password for an offline dictionary attack.

You could also try to thwart this by additionally hashing the password into the authenticator.

I’m not sure what the best defense is.  That’s why security proofs are helpful.

— Mike

> On Mar 9, 2018, at 1:04 AM, Van Gegel <torfone at ukr.net> wrote:
> 
> 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. 
> 
> 
> --- Original message ---
> From: "Mike Hamburg" <mike at shiftleft.org>
> Date: 8 March 2018, 21:11:42
> 
> 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 <torfone at ukr.net <mailto:torfone at ukr.net>> 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 (https://github.com/bernedogit/amber <https://github.com/bernedogit/amber>) I successfully add elligator2 to ASM Cortex M0 uNaCl library, without long multiplication  (https://munacl.cryptojedi.org/cortexm0.shtml <https://munacl.cryptojedi.org/cortexm0.shtml>) 
> > and also to forx25519-cortexm4  ASM library with long multiplication  (https://github.com/weedegee/x25519-cortexm4 <https://github.com/weedegee/x25519-cortexm4> ).
> > 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 (http://elligator.cr.yp.to/elligator-20130828.pdf <http://elligator.cr.yp.to/elligator-20130828.pdf>)  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) 
> > (http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CC0144B723B43385A22CA617D53FEF15?doi=10.1.1.10.6273&rep=rep1&type=pdf <http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CC0144B723B43385A22CA617D53FEF15?doi=10.1.1.10.6273&rep=rep1&type=pdf>)
> > 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
> > Messaging at moderncrypto.org <mailto:Messaging at moderncrypto.org>
> > https://moderncrypto.org/mailman/listinfo/messaging <https://moderncrypto.org/mailman/listinfo/messaging>
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180309/f49dbcc1/attachment.html>