[curves] ECSRP

[Michael Hamburg]

Resent because I accidentally replied one.

> On Aug 17, 2014, at 9:22 PM, Steve Thomas <steve at tobtu.com> wrote:
> 
>> On August 17, 2014 at 3:14 AM Michael Hamburg <mike at shiftleft.org> wrote:
>> 
>> 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?
>> 
> 
> I must of messed up my generation script. These are the points I found from 1 <
> x < 102. Well then there's the negative points of these. Are these the same
> points you got?
> (0x9, 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9)
> (0x10, 0x36b20194b9ee7885e888642d2006d60cdcc836d17f615e8416989556b3941598)
> (0x22, 0x152e35c8284506cb11fdbb318bb870561d0432459377eaff7562f563cb542e0e)
> (0x2d, 0x4d3505de41c7a153a60b348256f53be887d3bee6c3f8fd5d6ff8ee823c4b12f5)
> (0x31, 0x1d2dc6a0c656a661d0bc2da640a8a7180491dfd068c199683a09fd0e75ee810c)
> (0x3a, 0x5d893740c2ac99a8d9599b6daf4c7f499c0d794aaff2c249e6d9a4521f840152)
> (0x3e, 0x7f1487c59a00c598bd6e82a12c8004483b34110ffb6836b237b3a9a5bb8fb263)
> (0x4e, 0x542406b37871a4b49fa476663a97b0f33c249f69bcd43de53919a05e367a015f)
> (0x64, 0x111601db00a700b9eb84d80f6e412baaf507e009882dbaf588202fc9367e26ab)

Try SAGE, it’s nice :-)

> E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
> q = 2^252 + 27742317777372353535851937790883648493

> [“(0x%x,0x%x)" % (x,E.lift_x(x)[1]) for x in xrange(102) if E.is_x_coord(x) and q*E.lift_x(x) == (0,1,0)]
['(0x9,0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9)',
'(0x10,0x36b20194b9ee7885e888642d2006d60cdcc836d17f615e8416989556b3941598)',
'(0x22,0x152e35c8284506cb11fdbb318bb870561d0432459377eaff7562f563cb542e0e)',
'(0x2d,0x32cafa21be385eac59f4cb7da90ac417782c41193c0702a29007117dc3b4ecf8)',
'(0x31,0x1d2dc6a0c656a661d0bc2da640a8a7180491dfd068c199683a09fd0e75ee810c)',
'(0x4e,0x2bdbf94c878e5b4b605b8999c5684f0cc3db6096432bc21ac6e65fa1c985fe8e)',
'(0x64,0x111601db00a700b9eb84d80f6e412baaf507e009882dbaf588202fc9367e26ab)’]> 

> q * E.lift_x(0x3a)
(0 : 0 : 1)

> (q * E.lift_x(0x3a)).order()
2

> 
>> 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.
> 
> Where is the specification for SPAKE2. All I found was SPAKE1's protocol with
> Diffie-Hellman and that SPAKE2 does a slightly different KDF.

http://www.di.ens.fr/~abdalla/papers/AbPo05a-letter.pdf

>> * 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.
>> 
> 
> Yeah I know I was just lazy and since there are several ways to do this I just
> deferred till later.
> 
> 
>> 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.
>> 
> 
> So I'm just going to guess how this works:
> P = Elligator(k)
> A->B: aP
> A<-B: bP
> A: key || v1 || v2 = H(abP, ...)
> B: key || v1 || v2 = H(abP, ...)
> A->B: v1
> A<-B: v2
> 
> Is this correct or am I completely off?

No, that would be SPEKE Elligator Edition, and it might infringe the SPEKE patent which IIRC hasn’t expired yet.

I was thinking something like:

k = slowHash(pw, username, salt, …)
Q = h * Elligator(k).  B knows Q.

A -> B: aP + Q, where h is the cofactor
B -> A: bP

key || v1 || v2 = H(hQ, all the messages exchanged, abP)
B -> A: v1
A -> B: v2

Q is thrown into the hash  for proof reasons; it might not be necessary.

To augment, instead set k1 || k2 <- slowHash(…).  Server knows (k2) P, and both sides additionally compute b (k2) P and throw it into the hash.

If you want simultaneous flows for some reason either both sides can add in Q, or B can blind with R where R = h * Elligator(k3).  Using Q has better performance, but using R gives a tighter proof.

The biggest issue with this sort of thing is that some additional magic (noise-style) is required to hide the user name.

Cheers,
— Mike