[prev in list] [next in list] [prev in thread] [next in thread] 

List:       moderncrypto-curves
Subject:    [curves] ECSRP
From:       mike () shiftleft ! org (Michael Hamburg)
Date:       2014-08-18 7:21:09
Message-ID: D27C8209-78A1-48B5-849D-D14366175DC4 () shiftleft ! org
[Download RAW message or body]

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


[prev in list] [next in list] [prev in thread] [next in thread]