[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 []) 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-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 ([]) by localhost (ietfa.amsl.com []) (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

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
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?