Re: [Cfrg] PAKE review // CPace without the session-id round / Brian Warner's use-case requiring perfectly symmetric balanced PAKE

Björn Haase <> Fri, 01 November 2019 16:45 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 76DDB120096 for <>; Fri, 1 Nov 2019 09:45:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id avddrUysIi6y for <>; Fri, 1 Nov 2019 09:45:19 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 1720D120019 for <>; Fri, 1 Nov 2019 09:45:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;; s=dbaedf251592; t=1572626714; bh=dhP/ozE/23kHXFzGRzxtJS23CRPXZVoAAArqUz0rr3s=; h=X-UI-Sender-Class:Subject:To:References:From:Date:In-Reply-To; b=W03DapsGH1PLsVihZ67lZPjQ1lzcKSGp8MvLk2mdrM7IDuz2MTMFjzS3KB4y+2ZjT HY+3kUM3gFkLffJNj+77Zhn3C9bPfyUaiS1CR9SFJUYsSSoc/Y3hEk2OuE7bl7F4+1 gr7+2dJCywB7QzILYc+HIg+D6JH4T+BLTyZ5bVbU=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [] ([]) by (mrweb102 []) with ESMTPSA (Nemesis) id 0Lp71s-1hm2hB2Cxg-00exaF for <>; Fri, 01 Nov 2019 17:45:14 +0100
To: cfrg <>
References: <>
From: =?UTF-8?Q?Bj=c3=b6rn_Haase?= <>
Message-ID: <>
Date: Fri, 1 Nov 2019 17:45:11 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
X-Provags-ID: V03:K1:kn1snuzMun/Jc08Lompl/sQSkKxYuSpcRERzDqQZ25RglFYTQDB LTV+QM87soqrgu2xNCj4ti69/lUPiBmMgJg8eGPR93X/Br2NzR1YSUIwP9sh7gr/j5gJiBD I5reuFslYNbCu49sOomveJY3AJ2Nwc3ek4z7aJ2Sv+Mf8gVkdjNbGTCZ/m3jUR/dY/FGrAp cwo0dTZGZLRPp7S5oIKZQ==
X-UI-Out-Filterresults: notjunk:1;V03:K0:sxWIhw/lgTM=:XyWjU7PHzO1z/FDpa65k4c eXAFTQOo9flcL005S6TYl+V2I4eaehVAGBP3iplAc5fzLrAzGNUytAJV+/ILv7ox374JPrmt9 t47iRhYFYGsOrrHpOAsZkikKXCho86eS2+fMhi4k1HbIg4CSiYDYcmUTisxQ1fiYkbj5Ef15L +Jv0PhYdm4HCvQ5a2t1SQiGB+F3RO+wJ3PGN56jFqJYiuAxHFqU15a51RRoDZCeuTNU6AWE3Y chHIJ/c8r0LeDYRWzU16B6MpDCzzsBX0UFDPyFqBN8ZNcmdLryzEg1+Q6BvG0LfgjBoQ9WJL1 QJ/uuKbxvAlTGK8xKaYzuD9boD4PV4rw3reO6S8zlDI0ShAP2qPjEbP8WSSJ5zf0/FEdn3OD+ QL+QfzEVeyiPu706h7m1dMI1F0kdu+qTgN0SyNsXRzZck57dMsx+ncceU64rJOb9ZuqVoAyqe dhQDY/XM8YhENG+CPBSEsmzXE8qM7YakviQZaW0oxEhOg8y9IwH3q4boCs1KjyCP/sBv3qRn0 /N4N0JyToiv3njWCdXEGJSb2Miwi6JURar38RvbrlH2A9IlZn5Opjzu1VIyS31dAS44r0R9Bt ArYz5I9R3T7vKdQ/tdzAXVDS5OjPDMOOHFQa1gHnUFxaeYn9PFoNTLYzaDMBVJbQRl+XlsgcQ pJARmpZbCTIwUbRo/BWxdSmcMaBp8S3GBlmzyaQ0akBpLNPh8yG5PpiR5ZJcS0IOpt6GXvIqC 1Xw5xvOckZRqXiiFxJ677XY35+Z9cmr6OH5dB0v2GTVKFyncgBzLlhWQuY0wL+MZHBEpHZhnw dVjPBVw+wTIVlvRMHV/cBq8GO8L8ig42ZCX8UaYf3wCrJw04Z2+AWlsYxFXjFzTp+Itma2Dz4 FtTtBaCet/PkGMigeAIMh+RI6FwHFG3HUTjXVuOTVPOUqUIRgMhUIj+S/RnzN6NbVJvA4zOCJ Yprs5Jdn5NTBzxcPAkTZpYIDiRWkRYV+2JbdvCi8IhjCEVUlp7uESuzVc9J2aNnn4CNq/ZOls seH1/IaIlKA8Nf8u+0fNZJGpaDoefglDD+iLjAriKf4WBCN3irHi0t3Md0VkQpr6GpDOvxr3Q ATCSQtmmSHKtUlUyiwv3xpwOF1j7/OPD3590EN5+h/pLG+vhNZlTjs1xp8I8NRVW1agRC34Wo 5UkhKH+/Gn5ZmhzuuTd3COf89vcPYbHYFytlsSVu3hZk4j2+AHTe6ydydsCH/xVZr3MckUxtT 8XLdtVdy/0rIDXn02pzvzZR5pq5NWumvnY5Rlv37h8lr6LLPjs/PKAII4My8=
Archived-At: <>
Subject: Re: [Cfrg] PAKE review // CPace without the session-id round / Brian Warner's use-case requiring perfectly symmetric balanced PAKE
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 01 Nov 2019 16:45:23 -0000

 > Björn Tackmann wrote:
 >As balanced scheme, CPACE seems best, with SPAKE2 coming in somewhat
close second.
 > [...]
 > The following is under the assumption, which has been discussed on
the CFRG list recently and seems
 > plausible to me, that CPACE can be implemented without the additional
session ID round.

After some additional analysis, the statement of Ran Canetti and after
studying the recent eprint of
Julia Hesse I also conclude that we could let the initiator party alone
choose the session id.
This will result in CPace having only one single message round.

There is only one aspect that needs special consideration when doing
this, in my opinion: When calculating
the CPace session key sk1 = h(sid || K) from the DH result group element
K, we did intentionally prepend
the session id and relied on having both parties contribute to it's value.

The simulator needs to program the an externally chosen input value to
an already known and defined sk1 value
under some conditions. Of course this programming would fail if the
externally chosen input value *is* already
programmed to another value. This would result in distinguishable
behaviour between ideal and real world
and invalidate the proof.

When having the separate sid round, entropy from both parties did
contribute to the sid value, thus ruling out
a collision problem if at least one party is not honest.

Now that the session id would be provided by the initiator only, i.e.
without involving
entropy generated by the responder, I'd see the need to choose a
construction where it is guaranteed that
entropy from both sides enters any sk1 hash calculation that needs to be
programmed during the proof for an
external input. We could argue that K does include entropy from both
sides, but this argument would require
possibly complicated reasoning in the proof.
For this reason, for the calculation of sk1, I'd switch to sk1 = h(sid
|| Y_a || Y_b || K), i.e. including the transcripts.
This way, it is guaranteed (without the need of further reasoning) that
entropy generated
by the responder is entering this calculation and no "collision" problem
needs to be considered
when the simulator needs to program the hash for sk1. This change also
resolves the malleability issues
that did concern Stanislav and Björn Tackmann in their reviews.

Brian Warner's use-case and perfectly symmetric CPace:

In our paper, we also did prepend the sid to the hash query that we used
for calculating the generator G,
however in this case in the proof the input value for the random-oracle
hash is chosen by the simulator,
and we would not be facing such a"collision" issue. In my opinion
letting the initiator choosing sid is no
problem here.

Removing the sid also for the hash operation used for calculating the
generator G would make the protocol
perfectly symmetric. This would be desirable in Brian Warner's use case.
My gut feeling is that this should not
at all be a problem security-wise. We would be ending up fairly close or
identical with SPEKE. However, I fear
that then there might be some technical difficulties with the UC
framework which invalidate part of the proof and the
composability guarantees. We would be having some state (within the RO
implementation) which would be shared
and used in several concurrent sessions and in my understanding the
abscence of shared state is one important
component for meaningfully defining and prooving composability in UC.

So as a general rule I would not recommend CPace without session ID for
calculating the generator.
When considering Brian's use case, however, I don't see any real problem
since if I recall correctly, Brian
did use low-entropy passwords that were to be used exactly one single
time in his application.
This would mean that we probably could disregard the case of the same
password being used in several sessions by honest parties in this
application. So here the outer protocol construction
would guarantee that a specific generator is used only in one single