Subject: [CFRG] Symmetric SPAKE2

From: "Filippo Valsorda" <[email-masked]>
Date: Mon, 26 Apr 2021 21:19:45 -0400

Hi all,

I am trying to figure out the properties of symmetric SPAKE2, where there is no
ordering and M = N.

The only note I can find in draft-irtf-cfrg-spake2-18 is this in Section 5.

   In addition M and N may be equal to have a symmetric variant.  The
   security of these variants is examined in [MNVAR].  This variant may
   not be suitable for protocols that require the messages to be
   exchanged symmetrically and do not know the exact identity of the
   parties before the flow begins.

https://tools.ietf.org/html/draft-irtf-cfrg-spake2-18#section-5

I interpret "these variants" as the ones with M = N, and "This variant" as the
"Per-User M and N" one, meaning this paragraph is saying that you can't do
per-user M and N if M = N, which tracks.

However, the spec is hardcoding M and N to different values, so it doesn't
actually seem to allow M = N variants at all. Should that be addressed?

I looked at [MNVAR] for a proof of the security of M = N, but I noticed its
proofs involve UC and a sid. Does that sid have uniqueness requirements that can
only be satisfied with a full round-trip, like the one involved in the CPace
proof we discussed a couple weeks ago? In that case I think it wouldn't apply to
deployed uses of symmetric SPAKE2 like Magic Wormhole.

(I resisted titling this thread "On the properties of sid in symmetric SPAKE2".)

George Tankersley pointed me at a 2015 thread on [email-masked] where
Mike Hamburg is pretty confident a proof exists.

    More-symmetric and less-symmetric PAKE:

    It's not very important that M != N.  I'm pretty sure the proof Trevor 
    cited of this is wrong, but I'm also pretty sure that a proof exists 
    under slightly worse assumptions than the original.

    [...]

    These are both provable under some CDH variant (eg, GapDH if you like 
    shorter proofs with unrealistic assumptions, otherwise straight CDH with 
    tightness loss) in the random oracle model.

https://moderncrypto.org/mail-archive/curves/2015/000424.html

Following the Magic Worhole trail also led me to a thread from 2019, where Feng
Hao said they are not aware of a proof in the literature.

    If you set the two blinding factors equal (M=N), that will effectively turn
    it into a different protocol, which is very similar to Kobara-Imai's
    Pretty-Simple Password-Authenticated Key Exchange at
    https://eprint.iacr.org/2003/038.

    Both protocols rely on a trusted setup, but the main difference is below:
    * In SPAKE2: the protocol uses three generators, g, M, N. It's assumed that
    the discrete logarithm between any of these two must be unknow.
    * In Kobara-Imai, the protocol uses two generators, and it's assumed the DL
    between these two must be unknown.
    
    I don't know if anyone has studied whether the proofs in SPAKE2 are still
    applicable when only two random generators are used. The use of 2 generators
    is certainly simpler than 3.

https://mailarchive.ietf.org/arch/msg/cfrg/BBQ2gwCECu5ouTJjE_CE6d9Rg-0/

Is [MNVAR] the best published proof for symmetric SPAKE2? Does it apply to
single-roundtrip SPAKE2? If not, is anyone working on a proof that does?

Thank you,
Filippo

---

From: Watson Ladd <[email-masked]>
Date: Mon, 26 Apr 2021 21:04:39 -0700

> actually seem to allow M = N variants at all. Should that be addressed?

"These variants" is supposed to be M=N where you pick the point or the
per user one.
> deployed uses of symmetric SPAKE2 like Magic Wormhole.

Look in the Supplemental Material, Game Based Proofs for SPAKE2.

Sincerely,
Watson Ladd

-- 
Astra mortemque praestare gradatim