### [Cfrg] some notes on OPAQUE and AuCPace

Hugo Krawczyk <hugokraw@gmail.com> Mon, 18 November 2019 17:24 UTC

Return-Path: <hugokraw@gmail.com>

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 9115112018B
for <cfrg@ietfa.amsl.com>; Mon, 18 Nov 2019 09:24:17 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.998

X-Spam-Level:

X-Spam-Status: No, score=-1.998 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, HTML_MESSAGE=0.001,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no

Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key)
header.d=gmail.com

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 Gb03g1OJ0aff for <cfrg@ietfa.amsl.com>;
Mon, 18 Nov 2019 09:24:15 -0800 (PST)

Received: from mail-il1-x12b.google.com (mail-il1-x12b.google.com
[IPv6:2607:f8b0:4864:20::12b])
(using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 9B8DB12013D
for <cfrg@irtf.org>; Mon, 18 Nov 2019 09:24:15 -0800 (PST)

Received: by mail-il1-x12b.google.com with SMTP id d83so16712317ilk.7
for <cfrg@irtf.org>; Mon, 18 Nov 2019 09:24:15 -0800 (PST)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=5G841Gfr1sEgmwT6jaO5Z4n9PxZSMEyQQuglDDhf1rw=;
b=AJb7uIjwhwBVNNwu5hsWD34Pk+M9aUsMdGl527QdaGWi8u3T6hj2oB2AFrNf/v0ilY
w4NX7gUfGlpVoZzjhSDb2jUlsZD+TXh5YPjWsWiOgCcIzzo78nPYrj8M3TbY/Ou5ZDc3
rS7eC6TC0usDX8T/N1z98N7X74oX5kwbc3CX/eeD2WKuBuJOuKk+8DRkmASukE8jJGdn
YvgX3Bolovr7bv86o7Gx48Am0N/Rnm0nSaSz6MyjXoc9LRWjNDgLuRJNx3l6DT/T7dFf
7uElpM15ZOWq7cBwFXmautvJDY4QCrWljqUgEGLdObdRY97oBAA7uZxAkYRm/7q9gR2e
mvSw==

X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc;
bh=5G841Gfr1sEgmwT6jaO5Z4n9PxZSMEyQQuglDDhf1rw=;
b=db+plHBViIE8UCGKiTkJNniXCybnD58VZJ4+EVzLz/37QJoslQB4Wd2SO5OI4Jo7Vt
fJUGD/o3QpoBvmW2afEGPlXqnwSXPe57AR1Kh7PPrsoRK12EcswcMRJhzF58J2U17u9w
JU5YBgcIob5+KgGinKe+SDwSLBdnuNcQtBIYEEA2/ZrICvHd2Xrc3ZjJLEOQhNPA12NN
Ga3EF985E4aLrKkJphXnVCOCpgC1DJZx1fVCUd43YmycfFmk6cr4YGZnTwtdlEWrAs25
26EWGakfyh7+pgwmiW4ku8Drhl266w15Una8cxhl6504hNXdgAApe7GdV4PNIhJa4KaV
I3fw==

X-Gm-Message-State: APjAAAVd81uyvoIaWYeehzfi/zY+psXqOxkB84YQHOFvYN32A6ASg87A
2AoAiUSfG38Jrsn9Obei4CEOgGLw0X1h7UQpizLq8g==

X-Google-Smtp-Source: APXvYqzR/O60TW/D+XCHNFJae2zWl+D/DIpwNviCVker0jzLXnRecxSAt3fxjLqJPfFIslxBh/ouLi9YWhWRVRU4w8Y=

X-Received: by 2002:a92:d80e:: with SMTP id y14mr17671727ilm.267.1574097854103;
Mon, 18 Nov 2019 09:24:14 -0800 (PST)

MIME-Version: 1.0

References: <CADi0yUO6vDBt_1EvKkZp23+cHqOyFJw9cT0LBbu4hrx2SBEvAA@mail.gmail.com>

In-Reply-To: <CADi0yUO6vDBt_1EvKkZp23+cHqOyFJw9cT0LBbu4hrx2SBEvAA@mail.gmail.com>

From: Hugo Krawczyk <hugokraw@gmail.com>

Date: Mon, 18 Nov 2019 12:23:50 -0500

Message-ID: <CADi0yUN5zwnw-8qajdP3CRK7ZsUibBoTdvSVBtJo-=tHMbAX3w@mail.gmail.com>

To: CFRG <cfrg@irtf.org>

Cc: Stanislaw Jarecki <stanislawjarecki@gmail.com>

Content-Type: multipart/alternative; boundary="0000000000006f87fb0597a237cf"

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/qbTnjasSsYerOkztSgEK-2ByRJ8>

Subject: [Cfrg] some notes on OPAQUE and AuCPace

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: Mon, 18 Nov 2019 17:24:17 -0000

I would like to address some questions that we received off-list from several people and may be of more general interest, this includes some comments on the proof of AuCPace. 3-message OPAQUE: In a previous email I said that OPAQUE must provide full forward secrecy (i.e., forward secrecy against active attackers) and this implies that OPAQUE must have 3 messages. This is a property of any aPAKE protocols where the first message from the client can be produced without knowledge of the password (which is the case for OPAQUE). In principle, aPAKE protocols where the first message depends on the password may use just two messages. This clarification may be important since my observation in the HMQV paper that implicitly authenticated protocols (i.e., where the messages of the protocol do not depend on the parties' private keys) cannot ensure full forward secrecy with only two messages, was misinterpreted to say that NO forward-secure AKE protocol can use two messages (even though in the same paper I gave examples of full AKEs with two messages). I hope this clarification will help avoiding such misunderstanding in the aPAKE setting. Equivocable encryption: The proof of OPAQUE models the encryption that produces the envelope EnvU as equivocable encryption. This means that there exists a simulator (of the type used in cryptographic proofs) that can generate a ciphertext before it knows the corresponding plaintext. This is an abstract property needed in the proof but IT DOES NOT MEAN that the encryption has such property in the real world. This is similar to the use of "rewinding" in zero-knowledge proofs - no one expects to rewind proofs in the real world, it's just a proof technique. In particular, equivocable encryption can be modeled via programmable random oracles or ideal ciphers. Moreover, the proof of OPAQUE can work with regular semantically secure encryption assuming "non-information oracles" as used for proving UC secure channels in https://eprint.iacr.org/2002/059. See also the next paragraph for an encryption-less variant. Optimizing EnvU and server state size: OPAQUE can be built so that the envelope EnvU only contains the server's public key and a MAC value on it, and the server's state only contains the user's public key and a MAC on it (in addition to protocol-independent user account information). The current OPAQUE internet draft (v 03) contains a note on this. An additional property of such OPAQUE variant is that it completely dispenses with the above issue of equivocable encryption. Adaptive security of OPAQUE: The current proof of the DH-OPRF function works for non-adaptive adversaries only (we do not know of any adaptive attack but the existing proof works for static adversaries). This translates into non-adaptiveness in the proof of OPAQUE. Adaptive security of AuCPace. The AuCPace presents a proof against adaptive adversaries. We have no reason to believe the protocol is not secure against such adversaries but we do believe that an adaptive proof would need much more detail and completeness than the current proof to be convincing (these proofs are very delicate and adaptiveness makes them more so). Regardless, note that when one considers Strong AuCPace, the proof is already non-adaptive because of the same reason as above, namely, the proof of DH-OPRF on which Strong AuCPace would be based is non-adaptive. On cryptographic assumptions (OPAQUE and AuCPace). Currently the proof of OPAQUE depends on the Gap One-More DH (G-OMDH) Assumption on which DH-OPRF builds plus any assumption the specific AKE in use requires. The current AuCPace security claim only assumes CDH. However, this seems too optimistic as CPace itself requires a stronger assumption (*). Moreover, Strong AuCPace also requires G-OMDH as this comes from the DH-OPRF function that Strong AuCPace uses. We also believe that the UC modeling of aPAKE in AuCPace needs to be updated along the lines of the updates in the latest eprint version of OPAQUE eprint.iacr.org/2018/163. The AuCPace proofs would need to be updated and expanded accordingly. (*) CPace requires the following 2-CDH assumption (if the attacker can break the assumption, it can actually break the security of the protocol). Assumption 2-CDH: Given input (G1,G2,X) of random group elements, output values (Y,K1,K2) such that Y is a group element other than 1 and K1=DH(G1,X,Y) and K2=DH(G2,X,Y). The DH function is defined as DH(G,G^x,Y)=Y^x. Clearly, solving CDH solves 2-CDH. Showing the other direction (to prove equivalence with CDH) would be very surprising. Has this assumption been used/analyzed earlier?

- [Cfrg] some notes on OPAQUE and AuCPace Hugo Krawczyk