Re: [Cfrg] Removing the magic constants from SPAKE2

[Michael Hamburg <[e-mail]>]

On Jan 8, 2014, at 6:23 PM, Watson Ladd <[e-mail]> wrote:

> On Wed, Jan 8, 2014 at 3:19 PM, Michael Hamburg <[e-mail]> wrote:
>> Hello CFRG,
>> 
>> <snip>
> 
>> 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.
> 
> 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.

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