Re: [Cfrg] Review of (security of) remaining candidates

"Stanislav V. Smyshlyaev" <> Fri, 06 March 2020 20:42 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id A3FE43A0A42 for <>; Fri, 6 Mar 2020 12:42:04 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id r8kiDQAknRfN for <>; Fri, 6 Mar 2020 12:42:01 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id DC7003A0A41 for <>; Fri, 6 Mar 2020 12:41:59 -0800 (PST)
Received: by with SMTP id j19so3630045lji.1 for <>; Fri, 06 Mar 2020 12:41:59 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=w5u20X+duGWqJTlhdJ4ualPkcyYhHh6R6XACFGKerRw=; b=KkvuYu1jLdElZVDj8SJDt02y+NNcynQIVxamqyPCgDQKkxTZHRre87CpdmIGU+QlXj sZtwQfUSE++cWULR2AFAYzWrzIEz/1CJbth5OF3rvxn6LtRcgItN1Dv1Tof0lEW8UWKr nuKTxzU/Frdun/FLF/DSEinpiOMtG+rcPfpk/5aUMc9iK2MxDJKod2x88Gnd1cfucEB0 Vw1GEDIDqf8ZcpA6tVJSr7hrB+P+rgVTIrWMLqZnqVkVAz7Ci+iBWv1Juw31NmbPDBDG OU14WNSVvMCnCltLvAINOH5FL0dkLUoktYSiJX7JEfkF9J1f4ggYTEkUNp8mnBcxBmCF xCkA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=w5u20X+duGWqJTlhdJ4ualPkcyYhHh6R6XACFGKerRw=; b=lUqrYbU+ayVTvj33N6OXL2AAXvz1ud5M8Ee5io2dT+YnQidohzCzt9Ldv14gcCuJVe dp1BwlngBpeTK2+h6eiucubojPVxCSbCItPSHFaBkiFMdYsdFVfhf+/xOaaiEFXN4Eco a6zDF1H7UoeEo07APuojmE3IAZ6uWEWOJJbK6KSa0N0VXnXBdiIBa72xC2ILm+fRAg3r +buwUzAzfGxmI+SHXgfT+5GxzF6Axz2JAdI4TdcjnshWavgjGYQsueno0Cr+1eav5ZP2 NDpCO0RnnVgurH3hM23cgdrXMjr4BkcPX6Ym+dvFefhtOkoe0tTxCOYxf29XD5q2q+n6 snWg==
X-Gm-Message-State: ANhLgQ2EYDvv68L/bDvdDawOy9wtzVhclpY/SzQ7mhXoq8tsNlTCwwlQ 1f28vWxb/VzgzkJtT1FniGKeQiT6DFpUNOEXp0I=
X-Google-Smtp-Source: ADFU+vvlQ3EZXd7fNIkMxpTDfF+Pcu0utNkyaDSqBjtld3V4TICpEtl/BQA4dfutFBQU8K7SjfY/ZPilf+6g0EiKeJ4=
X-Received: by 2002:a2e:9086:: with SMTP id l6mr2892899ljg.215.1583527317601; Fri, 06 Mar 2020 12:41:57 -0800 (PST)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: "Stanislav V. Smyshlyaev" <>
Date: Fri, 06 Mar 2020 23:41:46 +0300
Message-ID: <>
To: Julia Hesse <>
Content-Type: multipart/alternative; boundary="0000000000004206d905a035afac"
Archived-At: <>
Subject: Re: [Cfrg] Review of (security of) remaining candidates
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, 06 Mar 2020 20:42:05 -0000

Thanks a lot, Julia!


пт, 6 марта 2020 г. в 23:36, Julia Hesse <>:

> Apologies for the lengthy and late review. I looked at security aspects
> of the four remaining candidates, and the recommendations are not taking
> other properties such as efficiency or integration into standards into
> account.
> To summarize, security-wise I (conditionally) recommend SPAKE2 and OPAQUE.
> ======
> I reviewed the following documents: the candidate's specification as
> described in draft-irtf-cfrg-spake2-09, and proofs of (what they call)
> SPAKE2 in
> (passive and MITM security) and
> (adaptive corruption and forward secrecy).
> Security pro's and con's:
> + Existing security proofs require one programmable global RO and Gap-DH
> (needed for forward secrecy, passive/mitm proof requires CDH instead of
> Gap-DH)
> + SPAKE2 has forward secrecy
> + None of the proofs require key confirmation (draft-irtf-cfrg-spake2-09
> puts it as MUST = absolute requirement)
> + Security proofs cover multi-party & multi-session setting (including
> re-use of passwords)
> + Security proofs are tight (i.e., guarantees do not degrade with the
> number of users)
> + Security proof for passive/MITM security was published already in 2005
> and since today no issues have been found (see also notes on Scott's
> review below)
> - Security proofs cover only executions where users use passwords chosen
> uniformly random from the dictionary
> - draft-irtf-cfrg-spake2-09 adds a cofactor h to the protocol, but no
> security analysis exists for that
> - No quantum preparedness, no option to switch to it, limited crypto
> agility since not a modular protocol
> - No quantum annoyance if M,N generated system-wide
> Notes on SPAKE2's reliance on parameters M,N (both group elements):
> If the dlog of M or N is known, then SPAKE2 is offline attackable
> (meaning that attacking only one run of the protocol allows the attacker
> to later test arbitrarily many passwords). However, the protocol's
> security does not rely on M != N
> Notes regarding other reviews:
> Scott Fluhrer mentions an issue in the proof of passive and MITM
> security, which to me is not a concern. Namely, he indicates that there
> exists a distinguisher between Ext2 and Ext3. In this game hop, random
> self-reducibility of CDH is exploited to plant a CDH problem instance
> into hashed outputs of participants, such that any hash query of a
> distinguisher would contain a CDH solution. Scott's concern is that
> parts of the CDH problem instances could be adversarially generated (and
> thus self-reducibility does not help in replacing MITM-attacked
> instances). However, Ext3 only replaces outputs of sessions that are
> *not* attacked by a MITM (indicated by "for all sessions generated via
> an Execute oracle query"). Instead, those sessions are handled only in
> Ext4 where the analysis correctly concludes that the attacker can only
> distinguish replacement of the RO in case he guesses the correct
> password. Therefor I don't see any issue with the proof.
> Comments:
> Both security proofs seem sound to me. If possible,
> draft-irtf-cfrg-spake2-09 should demand a gap-DH group instead of a CDH
> group such that SPAKE2 is guaranteed to achieve forward secrecy. Since
> all variants discussed on the list of generating M,N will leave the
> proofs valid, security-wise the only concern is that system-wide M,N
> would hinder quantum annoyance, which seems already well-known to
> everybody.
> Clearly, a strong point in favor of SPAKE2 is that proofs show that only
> one RO suffices to obtain strong guarantees.
> My main concern is that the protocol in the RFC is not the one analyzed
> in the papers. Some modifications seem to add to its security (e.g.,
> using w=MHF(pw) mod p instead of pw partly mitigates the fact that
> security is only analysed wrt randomly distributed passwords), but for
> others it is less clear (e.g., usage of cofactor h, cf also Karthik's
> review) and more analysis needs to be carried out. I am also slightly
> worried that the authors of draft-irtf-cfrg-spake2-09 say that key
> confirmation is mandatory while security analysis clearly shows that it
> is not necessary. I am not an expert in implementing crypto protocols,
> but to me it seems desireable to state SPAKE2 without key confirmation
> and leave it up to the application protocol if/how key confirmation is
> implemented.
> CPace
> =====
> I reviewed the updated security analysis
> and the specification
> For details on how to implement Map2Point I looked at the most recent
> version of the original CPace publication at
> Security pro's and con's:
> + Strong security notion with adversarially-chosen passwords,
> composability, adaptive corruptions and forward secrecy
> + Security properties do not rely on key confirmation
> + CPace is quantum annoying
> + Security proof covers multi-party & multi-session setting (including
> re-use of passwords)
> - Security proof does not analyze distinguishing advantage, thus I also
> cannot say whether the proof is tight
> - Trusted setup required for Map2Point
> - Heavy use of random oracles (2, both are programmed)
> - Proof posted only in 2019 with several issues already discovered (and
> probably containing more, see below)
> - No quantum preparedness, no option to switch to it, limited crypto
> agility since not a modular protocol
> Note on sid handling:
> As clarified by Ran Canetti, the sid can be chosen by the initiator and
> transmitted to the responder. Security-wise let me note that the sid
> does *not* have to be randomly distributed, and it does *not* have to be
> kept secret. It only has to be unique system-wide (e.g., contains a
> nonce or counter and some addressing information of both initiator and
> responder, which needs to be unique anyway to correctly route the
> message). CPace is thus a 1-round protocol assuming that the application
> protocols allows transmitting the sid along with the initiator's first
> message.
> Comments:
> Even though the author(s) continuously improve the security analysis of
> CPace, I am still not able to follow. One reason is that it is a
> simulation-based proof without any formal indistinguishability
> arguments. Another reason is that, while the proof is written as a
> sequence of games, most non-trivial changes happen in the step Exp2 to
> Exp3. In this step it is shown how to simulate a CPace execution without
> knowledge of passwords. However, all possible corruption scenarios
> (corrupted initiator, corrupted sender, and different times where these
> corruptions can each happen) are handled simultaneously, resulting in so
> many different cases that, at least to me, it is impossible to say
> whether the simulation is complete.
> While the security definition in the UC framework originates from a
> paper of 2005 by Canetti et al, it had to be adapted to allow for proofs
> of implicit authenticated CPace. On the plus side, adaptation has been
> done in coordination with, among others, authors of OPAQUE who face the
> same problem since they use also the UC framework. However, it still
> seems to me that the changes made are not sufficient for CPace to
> realize the current version, called F_ipwKE. An attacker leaving both
> parties uncorrupted but injecting a self-chosen Y_b will observe the
> hashed output of the initiator (obtained from F_ipwKE, oblivious to the
> simulator). If he then afterwards queries the random oracle on the
> shared secret Y_a^y_b, the simulator can use the newly introduced
> DelayedTestPwd query to learn whether the attacker and the initiator
> used the same password. However, to program the random oracle H_2
> according to this answer, the simulator needs to learn the output given
> towards the honest initiator. This is not possible with F_ipwKE.
> This might seem nit-picky, and indeed I do not have any doubts that
> CPace UC-emulates a slightly revised but not crucially weakened version
> of F_ipwKE. However, the proof relies on heavy tools: two programmable
> random oracles and several properties of Map2Point (efficiently
> invertible such that dlogs of images can be chosen by the simulator
> etc.) which additionally require availability of a shared trusted setup
> among all protocol participants (called CRS in the paper). Let me stress
> that a UC secure balanced (!) PAKE protocol can be obtained *without*
> any idealized assumptions, although such a protocol would be less
> efficient than CPace. Still, the question remains what the current proof
> is worth: due to the heavy usage of idealized assumptions it is only a
> rudimentary sanity check of the protocol and it does not rule out a very
> large class of attacks exploiting properties of instantiations of any of
> the idealized building blocks.
> Recommendation balanced PAKE
> ============================
> While the proven guarantees for SPAKE2 are a bit weaker than for CPace,
> I do believe that they are sufficient for a widely deployed SPAKE2 not
> to have any serious security issues. For CPace, I unfortunately cannot
> state the same. Upon deployment and instantiation of Map2Point and the
> programmable random oracles, there are just too many things which could
> go wrong due to the strong/idealized assumptions on all of these
> components. In that sense, the analyzed protocol is too far away from
> what will be actually deployed. Security-wise I thus recommend SPAKE2,
> conditioned on a thorough analysis on usage of cofactors.
> AuCPace
> =======
> I reviewed the updated security analysis in
> .
> Security pro's and con's:
> + Strong security notion with adversarially-chosen passwords,
> composability, adaptive corruptions and forward secrecy
> + Security properties do not rely on key confirmation
> + Modular: AuCPace can be instantiated with any (implicit) UC-secure
> balanced PAKE
> + Minimal usage of idealized assumptions (1 programmable RO)
> - Proof not convincing without further analysis
> Comments:
> After thoroughly checking the proof of the implicit (not strongly
> secure) AuCPace I am unfortunately not convinced that AuCPace can be
> proven UC secure (i.e., to emulate F_aipwKE as stated in the paper).
> While the authors give a simulator for AuCPace, they do not give any
> arguments why this simulation is sufficient. Such arguments should be
> intelligible from the sequence of games they provide. Below is an
> incomplete list of issues with this sequence.
> * The first game is the real execution without F_aipwKE, and none of the
> games introduce (any part of) this ITI. But then, the last game suddenly
> contains F_aipwKE.
> * Games G_2,G_3(1),G_3(2) do not say how to formally change the
> execution, nor do they contain formal reductions to, e.g., CDH.
> * Game G_4 contains no indistinguishability arguments despite the fact
> that almost all changes happen from G_3(2) to G_4
> * The newly introduced interfaces are analyzed only rudimentary: G_4
> lets the simulator relay Interrupt and DelayedTestPwd queries towards
> F_ipwKE to F_aipwKE. According to the text, this should work because the
> interfaces in both functionalities are equal. However, whether F_aipwKE
> gives an answer that can be used to simulate F_ipwKE depends on the
> *values* set in the functionalities. To say the least, one has to prove
> that dPT=1 in F_aipwKE whenever dPT=1 in F_ipwKE.
> ======
> I reviewed the security analysis in
> (rev of Oct 22) and the specification in
> Security pro's and con's:
> + Strong security notion with adversarially-chosen passwords,
> composability, adaptive corruptions and forward secrecy
> + Security properties do not rely on key confirmation
> + Modular, good crypto agility
> + Security proof covers multi-party & multi-session setting (including
> re-use of passwords)
> + No idealized assumptions outside of building blocks required
> - No quantum preparedness and not quantum annoying
> Comments:
> OPAQUE's security proof is wrt the same strong model as AuCPace. OPAQUE
> is modular, using KCI-secure AKE and an OPRF as building blocks. OPAQUE
> is nowhere close to quantum prepared since it is a long way towards a
> quantum-safe OPRF that is efficient enough. The protocol comes with an
> impressive security analysis that does not leave a lot of wiggle room.
> Obvious downsides are the complexity of the current proof (~20 pages in
> the OPAQUE paper, plus one has to assemble the HMQV security proof from
> few other papers) and the fact that it is relatively new and thus
> presumably not checked by many people.
> I checked the (evolving) proof of OPAQUE already few times, and with the
> current version I find only one issue I could not (trivially) solve
> myself: the non-modular way in which HMQV is used. Namely, HMQV's
> security proof is wrt a protocol-internal key generation algorithm
> setting up a key pair for each user. When using HMQV modularly, those
> keys would never "leave" honest parties. However, in OPAQUE the keys are
> generated and used outside HMQV (they form the password file and are
> send, encrypted with the OPRFed password, from the server to the user).
> Still, the OPAQUE proof uses the HMQV simulator as a sub-algorithm. I am
> not convinced that this simulator can be run on externally-chosen keys.
> For example, in an honest execution the saPAKE adversary can, after a
> successful key exchange, try a late password guess by decrypting any
> ciphertext sent by the server. The adversary then learns the HMQV keys
> *without corrupting any party* and can compute the shared HMQV secret of
> those parties. It seems to me that this is not simulatable by the saPAKE
> simulator without learning the session key generated by honest protocol
> participants. (Note: this is a similar issue as described for CPace above.)
> Recommendation augmented PAKE
> =============================
> Both proofs come with similar pro's. The conducted analysis of OPAQUE is
> clearly superior to the one of AuCPace. Conditioned on me being wrong
> about the issue with HMQV's keys, or the authors being able to fix it, I
> thus recommend OPAQUE.
> _______________________________________________
> Cfrg mailing list