Re: [Cfrg] Comments on the CPace proof and the CFRG PAKE selection process

Björn Haase <Bjoern.M.Haase@web.de> Wed, 03 June 2020 07:28 UTC

Return-Path: <Bjoern.M.Haase@web.de>
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 2D8183A0CB2 for <cfrg@ietfa.amsl.com>; Wed, 3 Jun 2020 00:28:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.995
X-Spam-Level:
X-Spam-Status: No, score=-1.995 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, MIME_HTML_ONLY=0.1, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=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 (1024-bit key) header.d=web.de
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 8GBM_FOna3c2 for <cfrg@ietfa.amsl.com>; Wed, 3 Jun 2020 00:28:01 -0700 (PDT)
Received: from mout.web.de (mout.web.de [212.227.17.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B8C2C3A0CB1 for <cfrg@irtf.org>; Wed, 3 Jun 2020 00:28:00 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1591169275; bh=3+O/w85nhEfze91OEi8nydro+JcqHp1D1mKTVzWcMrQ=; h=X-UI-Sender-Class:From:To:Subject:Date; b=BeLRA+0B/jp5xXVd0oyAhCrgH2NR7JJUjvY5BdxnUelsO1qf3vUaDqLv4HUWeNI8M YUjQO5gDCz8Spuuk7yabTk6Bz+dfrXkOK//MOvMFErHt8QxKiM++rUNEnyjo3L2u1V IiBHzrk8IFwNmpYzqiFo1c3lxEc/VnG1Kfz4Qkuo=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [2.247.251.178] ([2.247.251.178]) by msvc-mesg-web002.server.lan (via HTTP); Wed, 3 Jun 2020 09:27:55 +0200
MIME-Version: 1.0
Message-ID: <trinity-5db6ff60-69f9-4268-96f0-76dd717d138b-1591169275728@msvc-mesg-web002>
From: Björn Haase <Bjoern.M.Haase@web.de>
To: cfrg@irtf.org, Michel Abdalla <michel.abdalla@ens.fr>
Content-Type: text/html; charset="UTF-8"
Importance: normal
Date: Wed, 03 Jun 2020 09:27:55 +0200
Content-Transfer-Encoding: quoted-printable
X-Priority: 3
X-Provags-ID: V03:K1:iNK4LOF8old3sJXKJau2NGtdqSi2w38bcZE4l+MJpXR7k9Z2+AgXnRC884kg27jPn6k9b oXGOKkiQlbMso8HN3gsyzcWNBe1xMukcEoDPVbuUu4i6qJcLj/GaRggnfLUVZuO9STTIjxYxbSaD 6aY3SvEegNS6sYhljXyi0/0QmPR2MwWBi7oYaCR80ogkQ7aa0YfkP2wff6azhrinuS+774MFtD3s acBUr9FLaP87pPnieXbyhTCgByJ4gdWvrhXcSHSbZ5we+Qpcf2MkNTLQOWCiqZevxBPO1S8ub6wt ZA=
X-UI-Out-Filterresults: notjunk:1;V03:K0:oMuiv/4PglI=:e97sDkMD6vOiB/maupl/Qt t/pnRO8uAdDUn0RNg3gOWALQZPMtX/Gzy+yRg/aMhuzgLG0CHIMaw+GnbAYvDNwY1LdxGXyXx TSPeZLvnh/oLa2puIs9EHIyP7yoky6nMMg/mqgP/EijZgkzvPshuKjideozxwLerMWLrCB0PZ YFYRuqNjCI1XfkHlmuNEPRMC7Ej10XLD79RDRk/U/59UUXDA9JS2TcXnr274toGf7waz7vqQd YjEWRC428YPhxDKxcVZfH6sfDrrNEVCBjS+DQXN6i1P1UBk1lWDfY/x/Uqd7hCupa61kh80Gl vJSc07vXPTZOXV9RWltN3FE2ouQfmDDYJdEla1673cpTsh3Tud4XOfkCBUIAQ4rpYkiFzvp0b kPrhSvREwt/MEkzuH7pis26je0xqYvR+rgCazuJvzOJJKnJJeK5de7tkwuNuflRi4YJiARB6r 8OMZtsmTWftkyfvzdxP4eN8Kw3ajr9HJw3NiK9mui5UCRJRMx8ilIYrkbJ0T98ltz4kOwbFiw aBouXp/9BDq84iVKQid8F5+ErkEjpio3DB+/BIIh3R00KVTHAnCosry0gLAzmGISEBE6KO6yd CNxZL3uzSp/eRPvC1HA6kMrnfLsn8kxKrSatK122Ggjet5/Q64IBRrGfN+r3NJtPa0eGjZAMC TUFuJRtJ8m6xST8jrxgQEH7Ru2RYhcR0p4whrgE/Nn+FbldRHRHdk8C55arakLE7UUAMhp9+7 98B6jyIw17FiOCyzpVDOcM+Y1/KioPAzYFKc7A==
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/YqWjc0dEM9BS5tiMmwUs3AOhR8Q>
Subject: Re: [Cfrg] Comments on the CPace proof and the CFRG PAKE selection process
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: Wed, 03 Jun 2020 07:28:04 -0000

Dear Michel,

thank you for your Analysis. I will be responding top your feedback soon, probably next week, just after having returned from vacation.

Yours, Bjoern


--
Diese Nachricht wurde von meinem Android Mobiltelefon mit http://WEB.DE" rel="nofollow">WEB.DE Mail gesendet.
Am 02.06.20, 00:42 schrieb Michel Abdalla <michel.abdalla@ens.fr>:
Hi everybody,

Given that CPace has been selected as the balanced PAKE option, I believe it is important to make a few comments about its security as well as the CFRG PAKE selection process.  

1) Inclusion of the protocol transcript in the key derivation function

Although the latest RFC for CPace ( https://datatracker.ietf.org/doc/draft-haase-cpace/" class="" rel="nofollow">link) includes the protocol transcript in the key derivation function (suggested by Bjoern Tackmann), the security analysis in the corresponding paper ( https://github.com/BjoernMHaase/AuCPace/blob/master/aucpace_security_analysis_20200208.pdf" class="" rel="nofollow">link) does not clearly state the reasons for it. In particular, when examining the proof, the inclusion of the transcript during the computation of ISK has not been applied consistently throughout the paper and the analysis does not seem to make use of this fact.  

Here I would like to point out that this requirement is a hard one. Without it, the protocol would be insecure. To see why, just consider the following man-in-the-middle attack during an execution between a server and a client having the same password.

(a) When the server sends Y_a, the attacker forwards Y_a^2 = G^{2 y_a c_j} to the client
(b) When the client sends Y_b, the attacker forwards Y_b^2 = G^{2 y_b c_j} to the server
(c) The client and the server would compute the same ISK despite seeing different messages, since the key used to derive it would be the same: G^{2 y_a y_b c_j^2}.

2) Trivial malleability attacks

When introducing the protocol transcript in the key derivation function, the current RFC for CPace does not use the actual values of Y_a and Y_b to compute ISK. Instead, the input of the key derivation function uses strip_sign_information(Y_a) and strip_sign_information(Y_b).

One problem with this is that trivial modifications of the messages (for instance by changing Y_a to -Y_a) by a MITM attacker would not be detected by honest parties since the final key derivation does not properly bind the session keys to the transcript.

Although such an issue can be easily fixed by avoiding the use of strip_sign_information(), it clearly shows an important gap in the current proof.   

3) Reduction to SDH

The reduction to the SDH problem in the latest version of the Haase’s paper is still not given explicitly. Hence, right now, the security analysis only shows that the SDH is a necessary assumption but not necessarily sufficient.  Though such a reduction might be possible, I still don’t see exactly how it can be done so it would be nice if the Haase and Labrique could address this gap in the proof.  

In a separate paper currently available on ePrint ( https://eprint.iacr.org/2020/320" class="" rel="nofollow">link), we provide proofs in the UC model for SPAKE2, TBPEKE, and SPEKE. Our results for TBPEKE and SPEKE can also be extended to CPace but only in the case where the key derivation includes the transcript of the communication (which is required) and the password (we may be able to remove this requirement with further analysis).

As stated in the paper, our proofs for SPAKE2 and TBPEKE rely on the gap versions of the CDH and SDH assumptions. In particular, the Decision Diffie-Hellman oracle is used throughout these proofs to maintain consistency of answers to RO queries, and that this is needed even to deal with sessions in which the adversary is passive: the reduction still needs to be able to consistently deal with the sessions where the attacker is active and the attacker may adaptively decide to launch an active attack after seeing one of the protocol messages. In the case of SPAKE2, removing the need of a gap assumption might be possible given the recent result by Shoup ( https://eprint.iacr.org/2020/313" class="" rel="nofollow">link).  


4) Static versus adaptive UC security

Our proofs of security for SPAKE2, TBPEKE, and SPEKE in https://eprint.iacr.org/2020/320" class="" rel="nofollow">https://eprint.iacr.org/2020/320 only assume static corruptions and it would be interesting to extend them to deal with adaptive corruptions, but doing so does not seem straightforward.

The current security claim for CPace in https://github.com/BjoernMHaase/AuCPace/blob/master/aucpace_security_analysis_20200208.pdf" class="" rel="nofollow">https://github.com/BjoernMHaase/AuCPace/blob/master/aucpace_security_analysis_20200208.pdf still claims adaptive security. Unfortunately, since the reductions to the SDH problem are not explicitly given, one cannot verify how corruptions can be handled during these reductions. Note that, when reducing to the SDH problem, the reduction would not know the discrete log of some of the values being exchanged and, hence, it might be hard to know how to properly answer adaptive corruption queries.


5) Perfect forward secrecy vs weak forward secrecy

The UC relaxations used in the proofs of security of CPace, TBPEKE, SPEKE, and SPAKE2 are not known to imply perfect forward secrecy without an additional key confirmation step. In particular, the notion of lazy-extraction UC PAKE in https://eprint.iacr.org/2020/320" class="" rel="nofollow">https://eprint.iacr.org/2020/320 is only known to imply weak forward secrecy. Interestingly, proving perfect forward secrecy without the key confirmation step seems to be significantly harder. In the case of SPAKE2, we were able to provide a game-based proof for it under gap CDH (see https://eprint.iacr.org/2019/1194" class="" rel="nofollow">https://eprint.iacr.org/2019/1194), but the reduction is not tight and requires an intermediate assumption previously used in the proof of SPAKE1. A similar result is currently not known for CPace, TBPEKE, and SPEKE.


6) Comment on the CFRG PAKE selection process

Since the selection process is now over and I no longer have a conflict of interest, I would like to end this email by commenting on the CFRG PAKE selection process.

On the one hand, the selection process highlighted several important security aspects for real-world PAKE schemes, such as side-channel resistance and quantum annoyance. The notion of quantum annoyance is actually quite interesting and something which we never considered when designing SPAKE2 back in 2005. Nevertheless, I also find it hard to argue that a protocol can satisfy it, since this property was never formally defined, let alone formally proved to hold for any of the candidates.

On the other hand, I was a bit surprised to see that concerns about security proofs were often ignored in the process. Among the 4 candidates for balanced PAKE, CPace seems to be the one for which nobody was ever able to verify its proofs. Yet, its theorems and strong security claims were mostly taken for granted because people seemed to believe that a correct proof for it could be given (me included) and this seemed to have played an important role in the process. However, what the different MITM attacks given above show is that the security of CPace is still not very well understood. In particular, the current version of CPace still lacks appropriate verifiable proofs and all the versions of the CPace scheme in https://eprint.iacr.org/2018/286" class="" rel="nofollow">https://eprint.iacr.org/2018/286 and TCHES are insecure.

As a result, moving forward, I would strongly recommend against taking security statements for granted if they cannot be verified. Moreover, I also believe that the issues with the security proof of CPace should be fully addressed before proceeding with any formal specification of the latter. 

Regards,
Michel

PS: I would like to acknowledge the help of Manuel Barbosa with whom I discussed the security issues mentioned above.

_______________________________________________ Cfrg mailing list Cfrg@irtf.org https://www.irtf.org/mailman/listinfo/cfrg