Re: [Cfrg] Review of (security of) remaining candidates
"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Fri, 06 March 2020 20:42 UTC
Return-Path: <smyshsv@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 A3FE43A0A42
for <cfrg@ietfa.amsl.com>; Fri, 6 Mar 2020 12:42:04 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Level:
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: 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 r8kiDQAknRfN for <cfrg@ietfa.amsl.com>;
Fri, 6 Mar 2020 12:42:01 -0800 (PST)
Received: from mail-lj1-x22c.google.com (mail-lj1-x22c.google.com
[IPv6:2a00:1450:4864:20::22c])
(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 DC7003A0A41
for <cfrg@irtf.org>; Fri, 6 Mar 2020 12:41:59 -0800 (PST)
Received: by mail-lj1-x22c.google.com with SMTP id j19so3630045lji.1
for <cfrg@irtf.org>; Fri, 06 Mar 2020 12:41:59 -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=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;
d=1e100.net; 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: =?utf-8?q?ADFU+vvlQ3EZXd7fNIkMxpTDfF+Pcu0utNkyaDSqBjtl?=
=?utf-8?q?d3V4TICpEtl/BQA4dfutFBQU8K7SjfY/ZPilf+6g0EiKeJ4=3D?=
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: <dee5db9a-bc30-fad9-44d5-799db11cea9d@gmail.com>
In-Reply-To: <dee5db9a-bc30-fad9-44d5-799db11cea9d@gmail.com>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
Date: Fri, 6 Mar 2020 23:41:46 +0300
Message-ID:
<CAMr0u6mp=39bP-XzOfT+BqQncB4rJbSyE7G+C=8FH2tSEDtW_A@mail.gmail.com>
To: Julia Hesse <juliahesse2@gmail.com>
Cc: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="0000000000004206d905a035afac"
Archived-At:
<https://mailarchive.ietf.org/arch/msg/cfrg/I1nR8uJ3pePsqPmeUW63QdOemwM>
Subject: Re: [Cfrg] Review of (security of) remaining candidates
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: Fri, 06 Mar 2020 20:42:05 -0000
Thanks a lot, Julia! Regards, Stanislav пт, 6 марта 2020 г. в 23:36, Julia Hesse <juliahesse2@gmail.com>om>: > 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. > > SPAKE2 > ====== > 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 https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf > (passive and MITM security) and https://eprint.iacr.org/2019/1194 > (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 > > https://github.com/BjoernMHaase/AuCPace/blob/master/aucpace_security_analysis_20200208.pdf > and the specification https://tools.ietf.org/html/draft-haase-cpace-01. > For details on how to implement Map2Point I looked at the most recent > version of the original CPace publication at > https://eprint.iacr.org/2018/286. > > 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 > > https://github.com/BjoernMHaase/AuCPace/blob/master/aucpace_security_analysis_20200208.pdf > . > > 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. > > OPAQUE > ====== > I reviewed the security analysis in https://eprint.iacr.org/2018/163.pdf > (rev of Oct 22) and the specification in > https://tools.ietf.org/html/draft-krawczyk-cfrg-opaque-03. > > 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 > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg >
- [Cfrg] Review of (security of) remaining candidat… Julia Hesse
- Re: [Cfrg] Review of (security of) remaining cand… Stanislav V. Smyshlyaev