Subject: [Cfrg] Removing the magic constants from SPAKE2

From: Michael Hamburg <[email-masked]>
Date: Wed, 8 Jan 2014 15:19:30 -0800

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

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Jan 2014 18:23:47 -0800

On Wed, Jan 8, 2014 at 3:19 PM, Michael Hamburg <[email-masked]> wrote:
><snip>

> 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 Elli…

But it unfortunately falls apart in the standard model, because I can
cook the hash. The obvious choice for original SPAKE2 is the M and N
with smallest x or y coordinates that are on the curve besides the
generator. I don't think M&N are the issue here.

Basically, I think derandomization is better than SHA3 being like a
random oracle in all the ways that matter as an assumption.

>
><snip>
> Cheers,
> — Mike Hamburg
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 8 Jan 2014 19:39:31 -0800

> random oracle in all the ways that matter as an assumption.

I believe we discussed this at BaySec.  SPAKE2 uses the random oracle model anyway, as does every fast-ish PAKE including J-PAKE (depending on the signature scheme used by J-PAKE, but the default is Schnorr IIRC).

But regardless, I don’t agree with your intuition here.  The derandomized case is probably impossible to break in real life, but once an attacker solves the discrete logs of M and N once, she can hack everyone forever.  It’s a class break.

For the Elligator version, for the attacker to try (p1,p2) with only one login attempt, she has to solve a CDH challenge derived from SHA3(p1) and SHA3(p2), ideally salted with the username and the server domain.  And then she still has to test all other passwords sequentially.  And this only works for one user and domain.  For there to be a practical attack, somehow points of the form Elligator(SHA3(password)) have to have easily computable relations a significant fraction of the time.  With non-pathologically-chosen hash functions (eg, SHA2 or SHA3), this seems extremely unlikely.

In other words, while an attacker could get a few free guesses with a cleverly “cooked" hash function, the hash function has to be truly pathologically related to the elliptic curve for it to actually break things.

So while the Elligator construction uses the ROM more pervasively, I think it’s theoretically more sound than the original SPAKE2.

Cheers,
— Mike

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 9 Jan 2014 10:11:41 +0100

>
>
> 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.
>

I like this idea.

For purposes of standardization, instead of generating those "magic" SPAKE2
base points randomly using unbiased US dollar coins in some other agency's
back room, I'd expect you'd be using "verifiably pseudorandom" points based
on some seed (which shouldn't be an unacceptable leap of faith if you're
already relying on the Random Oracle Model for your security proofs), but
using Elligator to obtain proper mask values more directly seems like a
good alternative.

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.
>

Note that there's also a SPAKE variant called SOKE, which only masks one of
the DH shares in the first place (
http://www.bmoeller.de/pdf/soke-asiaccs2006.pdf; this was *meant* for TLS,
but due to patent concerns at the time was soon replaced by a thoroughly
gimmicky protocol that you don't really want to know about, and hence the
I-D was never completed).

> * Is SRP-style augmentation desirable?  Should it be optional?

By "SRP-style" augmentation I think you mean a verifier-based PAKE in
general, right?  ("Verifier-based" = the password information as held by
the server cannot be used to impersonate the client to other server
instances, and is rather merely a verifier to check that the client holds
such information.  I don't like the term "augmented" for this because it
appear to refer to an implementation detail of certain solutions, notably
the original Bellovin-Merrit Augmented EKE.)

I think having a verifier-based protocol is highly desirable, but that this
can be optional if that's sufficiently justified by efficiency advantages.

Bodo