[messaging] X25519 EC-EKE

[Van Gegel]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180307/b10f18d9/attachment.html>