[messaging] X25519 EC-EKE

[Mike Hamburg]

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> 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) I successfully add elligator2 to ASM Cortex M0 uNaCl library, without long multiplication  (https://munacl.cryptojedi.org/cortexm0.shtml) 
> and also to forx25519-cortexm4  ASM library with long multiplication  (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)  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)
> 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
> https://moderncrypto.org/mailman/listinfo/messaging