[curves] ECSRP

[Michael Hamburg]

The points look good to me, and I’m getting the right fraction of 1/16.  Maybe you’re accepting points with qX = (0,0), which is why you’re getting 1/8?

The protocol looks reasonable, but you’d want a proof.  It actually looks a lot like augmented SPAKE2, so the proof might just go through.
* You’re just canceling out the 1/k Q, so it serves the same function as kQ in SPAKE2.
* The 1/k on P is used for augmentation, which works as basically the opposite of SPAKE2’s augmentation (basically send bP, check kbP).  I think they’re about equally efficient.
* SPAKE2 throws more stuff into the hash function.
* Usually PAKE protocols also create a key shared between the two parties, eg key || v1 || v2 = H(X(ap) || X(bp) || X(abp)), then exchange v1 and v2.

I’ve been meaning to write up “SPAKE2 Elligator Edition” where you replace (1/k)Q here with cofactor * Elligator(k).  This could work here too.  Dunno if that would be better than the SPAKE2EE I’ve been cooking up.  The advantage is that if someone somehow comes up with log base P of Q, it doesn’t instantly hack everyone.  That is, it doesn’t rely on static DH.

Cheers,
— Mike

> On Aug 16, 2014, at 11:04 PM, Steve Thomas <steve at tobtu.com> wrote:
> 
> Can you take a look at this: https://github.com/Sc00bz/ECSRP
> 
> P and Q are points on the curve in the same cyclical group (ie aP = Q for some
> unknown a)
> k is the key derived from the password
> 1/k is done by modular inverse for the cyclical group order
> Server has (1/k)P and (1/k)Q
> a and b are random private keys
> X(P) returns the x coordinate of a point
> || is concatenation
> 
> C->S: Identity
> C<-S: b(1/k)P + (1/k)Q, salt, password KDF settings
> C:    k(b(1/k)P + (1/k)Q) - Q = bP
> C->S: X(aP), H(X(bP) || X(abP))
> S:    Verify
> C<-S: H(X(aP) || X(bP) || X(abP))
> C:    Verify
> 
> -----------------
> 
> I am having problems with point Q. For Curve25519, I picked Q as (16, ...), but
> I do not know if that is a good choice. It appears that there are two cyclical
> groups of the same order (2^252+27742317777372353535851937790883648493) on that
> curve, but I do not know if there is an issue with adding two points on the same
> curve but in different cyclical groups. I have not found any problems but
> obviously I can only test a very small fraction of them. I'm thinking that any
> point that is on this curve and has the same order as point P is fine for point
> Q, but I am not positive. (Well obviously P = Q is a bad choice or really any aP
> = Q for a known a.)
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves