[CFRG] On the properties of sid in CPace

Filippo Valsorda <filippo@ml.filippo.io> Sun, 11 April 2021 23:43 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 B431E3A23E9 for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 16:43:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.019
X-Spam-Level:
X-Spam-Status: No, score=-2.019 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H4=-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=GgK/MxEo; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=Si9u0LCU
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 i9KYQaqylzoW for <cfrg@ietfa.amsl.com>; Sun, 11 Apr 2021 16:43:24 -0700 (PDT)
Received: from out3-smtp.messagingengine.com (out3-smtp.messagingengine.com [66.111.4.27]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7A56B3A23E7 for <cfrg@irtf.org>; Sun, 11 Apr 2021 16:43:24 -0700 (PDT)
Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.nyi.internal (Postfix) with ESMTP id C18D25C0093 for <cfrg@irtf.org>; Sun, 11 Apr 2021 19:43:22 -0400 (EDT)
Received: from imap1 ([10.202.2.51]) by compute3.internal (MEProxy); Sun, 11 Apr 2021 19:43:22 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h= mime-version:message-id:date:from:to:subject:content-type; s= fm3; bh=fysehOgKqiaKBNHyzyr/4pStBHikn2lUWh5ZrrawMTM=; b=GgK/MxEo 8XnR3ayFb2EN7QK9xZNBmJeqic8/Fcup/xlj98ElME14zF0q0f2C84nlaVM/bxH3 DtL6UvXBRMu7+zUDG0PFxGTBCnGngBu5TOh4kCvm1GHPV59uWKdH4EO/aUfZR18j tJRgjhP6C2qQ20mDeSZN3cqW1d9Rxjf1OSoqazsKjTK0BoyWg5RoHon7lhKc+XZb nGXwFRV1t3p2y3UE12+D4C+R4LBi0GsD9Wv0mcahMh6DAgF03Rcfez7QtVjUrE9U TFLKDmAjtcTifYymB5KhLAtvKG0dhoJnRjRbJwTfO5Zyw4mTKNqe+cdbGv+jHX7t 8ogEYTt3BP3V0g==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=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=fysehOgKqiaKBNHyzyr/4pStBHikn 2lUWh5ZrrawMTM=; b=Si9u0LCUqZs6wWOVmYyOmisr13o9k/AetnKFDluClMX+A v95Z93+rCPSVRX/nT1u8kbgM49i3M3n3WHQKLEJHDoXRo3MdmWnkbIey1zQrHFna i+xX30QrLPNrAIo7+wwHsqJiCTo5rbj7VRo54vKqXJuJz7N83fF7Fgw9LgtovQN3 d5xP7S4zRCyMk6YcJ4iHD+emipHbMe49zmb2E+NHQO4/uHDCmCMCfJ39UV0Y31mK UjR3UPUr9mRVzwBfSunQ1G3oDF/B9bL9OaKZveasIyzb0CI+QtjSQN878rMXsRDT dAyBqSi/9CGohYqG50WxOUu1e8erRI4fGHxdH4oXA==
X-ME-Sender: <xms:molzYJqmOcT3_6wntHxe54rW_dwNVphITGUjMyziuIq3y7-t02gOfQ> <xme:molzYLpnKMJ5lHDKks8LLw5do-636ZFj4p7qeJQNdSe66mitLmEtSeWcoEMj98-aR c1FPozP-1FYuJhrsA>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrudekiedgvdduucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfffhffvufgtsegrtderre erredtnecuhfhrohhmpedfhfhilhhiphhpohcugggrlhhsohhruggrfdcuoehfihhlihhp phhosehmlhdrfhhilhhiphhpohdrihhoqeenucggtffrrghtthgvrhhnpeeijeefjeetvd duueehgeffffffffduhfetleefkeeigeekteetieegfedtvedvveenucevlhhushhtvghr ufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehfihhlihhpphhosehmlhdrfh hilhhiphhpohdrihho
X-ME-Proxy: <xmx:molzYGOePdv7FDZ14lnPfbxvcZ1kCXj7xm_eoK8UZuevRRcczZJySw> <xmx:molzYE7OsNeGKs-Hp98UF9v6t-5DIXLpyP18HFL1DgXNZgulbhfTJg> <xmx:molzYI6vzb_4cu8PKhGqMB8IodnnZ2kJwz6ErvnoA9m2IHGRoh0l0w> <xmx:molzYKGKemCyIWwbCBNZQPsU7LzZTx6aD3qteiXtHhuAxr0qU9gQCQ>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 3D543130005F; Sun, 11 Apr 2021 19:43:22 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.5.0-alpha0-273-g8500d2492d-fm-20210323.002-g8500d249
Mime-Version: 1.0
Message-Id: <03a81355-32e2-465e-b08a-e33d02112ab8@www.fastmail.com>
Date: Mon, 12 Apr 2021 01:43:00 +0200
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary=0e3bce9b507b412d8d08d3dde5a40b65
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/T-lCHjwAXfG17E4HZpu67eAlJNo>
Subject: [CFRG] On the properties of sid in CPace
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: Sun, 11 Apr 2021 23:43:30 -0000

Hi all,

I am trying to figure out the required properties of sid in CPace, and what
happens in various attack and misuse scenarios.

This is what draft-irtf-cfrg-cpace-01 says about sid, if I didn't miss anything:

   Let sid be a session id byte string chosen for each protocol session
   before protocol execution; The length len(sid) SHOULD be larger or
   equal to 16 bytes.

   Prior to entering the protocol, A and B agree on a sid string. sid is
   typically pre-established by a higher-level protocol invocing CPace.
   If no such sid is available from a higher-level protocol, a suitable
   approach is to let A choose a fresh random sid string and send it to
   B together with Ya.

   Upon completion of this protocol, the session key ISK returned by A
   and B will be identical by both parties if and only if the supplied
   input parameters sid, PRS and CI match on both sides and the
   information on the public elements in J were not modified by an
   adversary.

Overall, it's not described as particularly different from CI (it's public, and
the output is tied to it), but sid is hashed into both the generator and into
the key material, while CI is not:

   G = map_to_group_mod_neg(DSI1 || PRS || ZPAD || sid || CI)

   ISK = H(DSI2 || sid || Ks || Yas || Ybs)

Last year there was a brief but very useful discussion about the sid ([Cfrg]
CPACE: what the "session id" is for?) with arguments for its importance, but I
still have a few questions. (Some excerpts from that thread below.)

First, how does the security of CPace degrade upon sid reuse? If it were to
happen due to birthday bounds, how catastrophic would it be?

What happens if the sid can be attacker-controlled between two otherwise honest
peers which both know the password?

Is uniqueness its only requirement, or does it also have to be unpredictable?

> the sid could be considered as to form some sort of "glue" linking the
> individual subblocks of the composed protocol

Isn't that what the additional data in CI is for? Is placing binding values in
CI less effective than placing them in the sid?

If I were to use CPace in a network protocol such as TLS, my instinct would be
to use a transcript hash as CI. Assuming the protocol negotiated random values
and identities, would that be enough or would I also need to hoist sid and
identities out and into the explicit CPace parameters?

> The sid also serves for making each generator ephemeral for each session and
> this could be useful for mitigating side-channel analysis since the adversary
> has essentially only one single trace available.

Does this work with an A-generated sid? It looks like an attacker could force B
to keep operating on the same generator in that case.

> This "ephemeral generator G" feature that comes with the inclusion of the sid
> is IMO also relevant for the "quantum annoying" property.

Is "quantum annoyingness" lost if only one side contributes to the sid? Is it
lost upon a single sid reuse?

I'm not arguing for removing the sid at all, but I think CPace as a low-level
primitive should provide a tool that is easy to reason about with clear rules
and properties, so documenting the expectations for the sid would help.

Thank you,
Filippo

P.S. This is the first time I see UTF-8 used as a general purpose variable
length integer encoding. I think I love it. However, it's likely UTF-8 libraries
will behave weirdly and most importantly differently around 0xFFFD, invalid
encodings, and surrogate pairs, which I can see causing trouble.