[Cfrg] Removing the magic constants from SPAKE2

Michael Hamburg <mike@shiftleft.org> Wed, 08 January 2014 23:19 UTC

From: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: quoted-printable
Message-Id: <333749FB-4D07-455E-9646-7A8C571E6226@shiftleft.org>
Date: Wed, 08 Jan 2014 15:19:30 -0800
To: cfrg@irtf.org
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
Subject: [Cfrg] Removing the magic constants from SPAKE2
Precedence: list

Hello CFRG,

There’s been a lot of discussion of PAKE here, and one of the contenders is SPAKE2.  The goal of this post is to suggest that a SPAKE2 variant might be a suitable standardized PAKE now that SPAKE2 itself is out of patent.  I believe that it can be as fast as Dragonfly, but with smaller messages, a security proof, and fewer flames from Trevor Perrin.  As a reminder, at a high level SPAKE2 uses 3 independent generators g,M,N on the curve, and does:

c->s: X = g^x M^h(password)
s->c: Y = g^y N^h(password), serverValidator(K)
c->s: clientValidator(K).

Here the session key K is h(password,X,Y,g^xy).  If there’s extra information that both sides understand from the connection (eg, user name, server domain, etc), it should be thrown into the hash as well, or salted into the password, to prevent rebinding.  This PAKE also supports a Dragonfly-style flow, where the client and server exchange X,Y, and then exchange their validators in a second round.

However, the protocol is considered problematic (and is out of favor with CFRG) in large part because of the magic curve points M,N.  The discrete logs of these points would be a backdoor in SPAKE2, so care must be taken to ensure that M,N are generated at random.

However, there’s another way to do SPAKE2, which doesn’t need magic curve points.  Instead, M^hash(password) and N^hash(password) can be replaced with Elligator(hash(“M to the”, password)) and Elligator(hash(“N to the", password)).  This obviously achieves the same bounds in the ROM.

Furthermore, if a completely symmetric PAKE is desired, there’s nothing really wrong with setting these two blinding factors to the same value.  That is, they can both be M^hash(password) or Elligator(hash(“M to the”, password)).  The disadvantage is in the proof: the proof will now be based on “CDH squaring” instead of regular CDH, i.e. computing g^(x^2) from (g,g^x).  Because of quarter-squares the two problems are equivalent, but it changes the epsilon^2 in SPAKE to an epsilon^4.  This isn’t a huge deal, and if you prefer stronger proof frameworks like Kudla-Patterson’s GapDH trick, then it doesn’t change the bounds at all.

One more important note!  Because Elligator only works on curves with a cofactor, care must be taken not to leak bits from the cofactor.  That is, either g needs to generate the whole group and not just the q-torsion, or else the parties should send (g^x Elligator(…))^4.  This could also be avoided by using a prime-order curve and SWU/BCIMRT instead of Elligator.

Does anyone on CFRG find this approach interesting?  If there’s enough interest, I’m willing to spec it, though I’d like to understand CFRG’s preference on the various options here:
* Which curve(s)?  Ed25519?  Safecurves?  Is NIST curve compatibility a requirement?
* How much metadata should be present (ASN.1 or fixed curves?)
* Is the completely symmetric PAKE desirable?
* Is SRP-style augmentation desirable?  Should it be optional?
* Are the flows being integrated into TLS or something?
* Should false start be in the spec?

Cheers,
— Mike Hamburg

[Cfrg] Removing the magic constants from SPAKE2 Michael Hamburg
Re: [Cfrg] Removing the magic constants from SPAK… Watson Ladd
Re: [Cfrg] Removing the magic constants from SPAK… Michael Hamburg
Re: [Cfrg] Removing the magic constants from SPAK… Bodo Moeller
Re: [Cfrg] Removing the magic constants from SPAK… Mike Hamburg