Resent because I accidentally replied one. > On Aug 17, 2014, at 9:22 PM, Steve Thomas <[email protected]> wrote: > >> On August 17, 2014 at 3:14 AM Michael Hamburg <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
