[CFRG] Symmetric SPAKE2

Filippo Valsorda <filippo@ml.filippo.io> Tue, 27 April 2021 01:20 UTC

Return-Path: <filippo@ml.filippo.io>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6BCC83A09BB for <cfrg@ietfa.amsl.com>; Mon, 26 Apr 2021 18:20:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.02
X-Spam-Level:
X-Spam-Status: No, score=-2.02 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=filippo.io header.b=BwhFNpD+; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=Awxr4GSO
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EkGFSHaRJYBI for <cfrg@ietfa.amsl.com>; Mon, 26 Apr 2021 18:20:32 -0700 (PDT)
Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com [66.111.4.25]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 397EE3A09B9 for <cfrg@irtf.org>; Mon, 26 Apr 2021 18:20:31 -0700 (PDT)
Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.nyi.internal (Postfix) with ESMTP id CB0525C019E; Mon, 26 Apr 2021 21:20:29 -0400 (EDT)
Received: from imap1 ([10.202.2.51]) by compute3.internal (MEProxy); Mon, 26 Apr 2021 21:20:29 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h= mime-version:message-id:date:from:to:cc:subject:content-type; s= fm3; bh=DTIGfwsfMYssBJzM0vR5v4D+JgYgo/eKDG/QXJ02Xdk=; b=BwhFNpD+ VtQOgtM83N+XIjGSXAy+hy2GOXGthCEcSM5xr3LqQqeHU+LdmQcNvhwXwitb9MsK Cf3gpx7m9TYAQ/TRJtN3I7yjNZ2cfnn97DPMJgG9rrCz8IheGWSPT+QnDFmSwNVg +b11aT/mFoWIuREjoArVaJZnszMl2ZTBg6QoXxwpD7YnW0H2qVJIKB9XLwt5ptCW ng1/ycmXkFr3GpjpCD2z9hCkn02zOUg5tsrawQwwb4kJPulDVDYzSCB3xFaFZOIH bAtm34oiwyzrKoVZVSWmg3dqw0ChQWEjsXGDQZBnxR7zkvFYr5S0REPgHztWUlY4 oukuB6iugJtTzw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:from:message-id :mime-version:subject:to:x-me-proxy:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm2; bh=DTIGfwsfMYssBJzM0vR5v4D+JgYgo /eKDG/QXJ02Xdk=; b=Awxr4GSOuyzy8Y+FQMvidimD0UjNKhjJ9eYDPJOWiyG2e SmH6y9LIMct6ROIIoLJCA1o+xWiY/xDlE0LtdPcSCnB1Uyf5GUvLl+FpKUKgnPsv DR38pa25/8OyktqyDYfSEwIb+EY/liiPDINuEjXqa7EdlUTSJ24nlbuB71qz1VsQ qJx8DCbtHVDxK83SIbJl59p+1hb/ilxJdGusutBsOz9loSnUmP1PzhC/qtCLptFG jSjdea+BugVMIu8KhyckZX1pTJMlstR/jBikUwKxRof+i3V3sxD9vt20OSwnnsOM lwlwY3JSo5hSum7D6sXwgjuU/jIPivBw1qBhbOSvQ==
X-ME-Sender: <xms:3GaHYL6eoSMiRv9aVWuU7e2k0JrUEzf3kQtFaPwiMquwz8Id3pDzCg> <xme:3GaHYA5njcPpL7l2ITlFTo1cItqIcESgI8p1V0QFBNcg9iLskZQemSHX2NII9bT4v c0lwlM7PVDF3whm0w>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrvdduledgjeehucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepofgfggfkfffhvffutgesthdtredtreertdenucfhrhhomhepfdfhihhlihhp phhoucggrghlshhorhgurgdfuceofhhilhhiphhpohesmhhlrdhfihhlihhpphhordhioh eqnecuggftrfgrthhtvghrnhepjeeuueffuefggeekjeffueekudeuleeljeekgeduieei geffieelleegtedttdffnecuffhomhgrihhnpehivghtfhdrohhrghdpmhhouggvrhhntg hrhihpthhordhorhhgpdhirggtrhdrohhrghenucevlhhushhtvghrufhiiigvpedtnecu rfgrrhgrmhepmhgrihhlfhhrohhmpehfihhlihhpphhosehmlhdrfhhilhhiphhpohdrih ho
X-ME-Proxy: <xmx:3GaHYCfNE2qBiEJGVW1ZHG1ZDfMNltwQzuc2AtRZS6XJXbwDuriOMA> <xmx:3GaHYMLPlivpFfZd9Py61au_7RUn-TQ_I6p8ab9dTQl1na2wn2-MXw> <xmx:3GaHYPKF-gwKTEx0eXIoQ1ASra6pib1kVShRvybnBSN87H87ghNHJA> <xmx:3WaHYH2lQOONhWUVRv2mY8v6c1KSt02j1dBxmsfI_UoipdUJcH3AzQ>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 096E5130005F; Mon, 26 Apr 2021 21:20:28 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.5.0-alpha0-403-gbc3c488b23-fm-20210419.005-gbc3c488b
Mime-Version: 1.0
Message-Id: <272c789a-afa2-4cef-869d-980f4e0df1e8@www.fastmail.com>
Date: Mon, 26 Apr 2021 21:19:45 -0400
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: cfrg@irtf.org
Cc: "Brian Warner" <warner@lothar.com>, "Hao, Feng" <Feng.Hao@warwick.ac.uk>, "Mike Hamburg" <mike@shiftleft.org>, "Watson Ladd" <watsonbladd@gmail.com>, "Benjamin Kaduk" <kaduk@mit.edu>
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/zgOg68OxJREtawyHm5q-o199RJ4>
Subject: [CFRG] Symmetric SPAKE2
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 27 Apr 2021 01:20:38 -0000

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 curves@moderncrypto.org 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