Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

Michel Abdalla <michel.abdalla@ens.fr> Wed, 16 November 2016 15:08 UTC

Return-Path: <michel.abdalla@ens.fr>
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 C7D0912940C for <cfrg@ietfa.amsl.com>; Wed, 16 Nov 2016 07:08:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.698
X-Spam-Level:
X-Spam-Status: No, score=-5.698 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-1.497, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
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 LpWWAVsX-euL for <cfrg@ietfa.amsl.com>; Wed, 16 Nov 2016 07:08:31 -0800 (PST)
Received: from nef2.ens.fr (nef2.ens.fr [129.199.96.40]) by ietfa.amsl.com (Postfix) with ESMTP id 4265A129522 for <cfrg@irtf.org>; Wed, 16 Nov 2016 07:08:30 -0800 (PST)
Received: from di.ens.fr (di.ens.fr [129.199.99.1]) by nef2.ens.fr (8.13.6/1.01.28121999) with ESMTP id uAGF8Ouq047206 ; Wed, 16 Nov 2016 16:08:24 +0100 (CET)
Received: from dhcp205.dmi.ens.fr (dhcp205.dmi.ens.fr [129.199.97.205]) (authenticated bits=0) by di.ens.fr (8.14.4/jb-1.1) id uAGF8Nj0027084 ; Wed, 16 Nov 2016 16:08:23 +0100
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 10.1 \(3251\))
From: Michel Abdalla <michel.abdalla@ens.fr>
In-Reply-To: <DB5PR0701MB1928AEBDA2833976F543C1EAD4BE0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
Date: Wed, 16 Nov 2016 16:08:23 +0100
Content-Transfer-Encoding: quoted-printable
Message-Id: <1E393A35-FEF3-4205-B91B-D3DC2DE918A1@ens.fr>
References: <DB5PR0701MB19282BB2E03816405AF5DF91D4BC0@DB5PR0701MB1928.eurprd07.prod.outlook.com> <CACsn0ck4uFHrKzX9EDGSADjv1BkpnGPA3v4ncR8R9dkTn5DWgg@mail.gmail.com> <D44FD9E6.186BF%feng.hao@newcastle.ac.uk> <CACsn0cngxnRjVPBDcC9HuNxbJV-VD1UPHOryWSjKBkf5+Mnz1w@mail.gmail.com> <DB5PR0701MB192893EEFB5B57A72B70984ED4BF0@DB5PR0701MB1928.eurprd07.prod.outlook.com> <CACsn0ckQMFdLhFP_AhTaQPAmKpb8ZdxHBDGRRxvx8cEHC+vh7A@mail.gmail.com> <DB5PR0701MB192892E1DAF20517AE2D032CD4BF0@DB5PR0701MB1928.eurprd07.prod.outlook.com> <CACsn0c=2OHcGtb3AADZoZt4FpVr76_1O70Cf9rM3E1DWnaK-ng@mail.gmail.com> <DB5PR0701MB1928AEBDA2833976F543C1EAD4BE0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
To: Feng Hao <feng.hao@newcastle.ac.uk>
X-Mailer: Apple Mail (2.3251)
X-Virus-Scanned: by amavisd-milter (http://amavis.org/)
X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.4.3 (nef2.ens.fr [129.199.96.32]); Wed, 16 Nov 2016 16:08:24 +0100 (CET)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/m_pIR94ylSSKWcxqIVJgOG37y9Y>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
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, 16 Nov 2016 15:08:35 -0000

Dear Feng,

Since you’ve raised some questions about SPAKE2, I just wanted to clarify some of these issues below.

Regards,
Michel

> On Nov 16, 2016, at 11:25 AM, Feng Hao <feng.hao@newcastle.ac.uk> wrote:
> 
> Hi Watson,
> 
> On your comments about comparing costs between SPAKE2 and J-PAKE
> 
> * It's not a fair comparison as the setup assumptions are different. SPAKE2 requires a trusted setup, while J-PAKE doesn't. Instead, you should compare SPAKE2 with KOY, Jiang-Gong and GL protocols as they require the same trusted setup. J-PAKE should be compared with EKE, SPEKE and Dragonfly (which is based on SPEKE).
> 
> * When you say "SPAKE2 with M and N generated by hashing is secure, and the proofs found in the SPAKE2 paper do work", it's best that you write up the full details how you do the hashing, proofs that why it's secure and why
> it doesn't affect the original proofs in the SPAKE2 paper in any way. Then people can check and verify your proofs instead of having to take your word for it. I see you are always rigorous in asking "security proofs" from others for everything they do (which is good), so you should consider applying the same rigor to yourself.
> 

Since the security proof only requires that M and N are two random elements whose discrete logs with respect to g are unknown, the proof would go through even if M and N were chosen as the output of a random oracle on some fixed inputs, say M=H(0) and N=H(1), where H hashes into the the appropriate group.

> * The KOY, Jiang-Gong and GL papers are relevant as they are the same type of CRS-based designs as SPAKE2. These papers state that the setup needs to be done by a trusted party and they don't specify using a hash.
> SPAKE2 is in the same model. It's appropriate you compare these protocols and definitions. This is necessary especially since you're doing something not specified in the original SPAKE2 paper and other related peer-reviewed papers.
> 
> * You will need to convince IETF users that there is no possibility of trapdoor for M and N (which may prove a bit tricky). Knowledge (or partial knowledge) of the relation between M and N may allow one to
> systematically break all instances of the protocol execution. 
> 
> * Kindly note that if you can manage to convince IETF users that M and N are completely random, one might just plug M and N as the input of two random points to DUAL_EC and make it work?
> 

The security of SPAKE2 requires that the discrete logs of M and N with respect to g should remain unknown to everybody so the generation of M and N has to enforce this aspect.

> * What you say about the 4 exponentiations in the subgroup is correct (consistent with the original paper), but this hasn't included the validation of the public key (which is free in EC but takes one full exponentiation in the finite field setting). See my further comment below.
> 
> I read again the original SPAKE2 paper as well as your I-D. I have the following comments
> 
> * I think SPAKE2 is underspecified in the original paper. It doesn't state the requirements for M and N, but it should be clear that they must be completely random. Also, it doesn't state if the discrete logarithm between M and g (and symmetrically between M and g) must be unknown. It's not immediately clear to me if knowledge of the discrete logarithm for M and g will break anything, but all these should have been explicitly specified in the paper.

If one knows the discrete log of M with respect to g (let’s call this value m), then one can perform an offline dictionary attack on SPAKE2 as follows. The adversary impersonates User A and sends a random element X'=g^x' to User B. After receiving Y* from User B, the adversary requests the session key associated with this session through a reveal query. Let SK be this session key.  Now guess pw and compute offline Y = Y* / N^pw, K_A = Y^{x’ - pw m}, and SK_A = H(A,B,X’,Y*,K_A).  Note that SK_A will match SK when pw is the correct pw.
 
> 
> * I'm a bit worried that in the actual protocol specification in the original paper, there is no step to perform public key validation. This could be due to two reasons: 1) an inadvertent omission by the authors; 2) an intentional design choice. In case of ambiguity like this, one normally takes it as the latter. The reason is simple: if public key validation is considered essential, it MUST be clearly specified, which is the case with most key agreement protocols. However, from early 2000s, some researchers called for abandoning the public key validation, as long as the protocol has formal security proofs (HMQV is one notable example, but it backfired in the end).

Our proof implicitly assumes membership tests for all the elements being exchanged. Hence, the actual explanation for the under specification is an inadvertent omission on our part. 
> 
> 
> * The above observation reminds me of a paper " Multi-Factor Authenticated Key Exchange" by Poincheval and Zimmer in 2008 [1] where the protocol is specified in a similar manner as SPAKE2 without public key validation. We analysed the protocol and it took us a while to conclude that it is insecure without public key validation (despite the security proofs in the paper) [2]. We contacted authors of [1] and they kindly acknowledged the attack and also confirmed that public key validation needed to be added in their protocol. The attack can be traced to a subtle deficiency in their theoretical model which implicitly assumes that a server is trusted when it communicates with a client. This assumption is clearly invalid, but it is implicit in the model/proofs and it took 5 years for peer researchers to identify it!
> 
> * At the moment, I don't see an obvious attack due to the missing public key validation in the SPAKE2 specification (as in the original paper), but it's a potential issue that needs some attention.
> 
> Cheers,
> Feng
> 
> [1] D. Pointcheval and S. Zimmer, "Multi-Factor Authenticated Key Exchange," Proceedings of Applied Cryptography and Network Security (ACNS¹08), pp. 277-295, LNCS 5037, 2008.
> 
> [2] Security Analysis of a Multi-Factor Authenticated Key Exchange Protocol  https://eprint.iacr.org/2012/039.pdf
> 
> On 15/11/2016 19:14, "Watson Ladd" <watsonbladd@gmail.com> wrote:
> 
>> Dear Feng,
>> 
>> Let me make this very clear, to avoid your misunderstandings: J-PAKE
>> is substantially less efficient than SPAKE2 over the same group.
>> SPAKE2 with M and N generated by hashing is secure, and the proofs
>> found in the SPAKE2 paper do work for this case. If we use a small
>> subgroup of a finite field group, then the necessary validations for
>> group membership double the cost of SPAKE2, but J-PAKE is still
>> slower. J-PAKE requires an additional round, while SPAKE2 fits into
>> the same flow as Diffie-Hellman. There is no relevance of KOY, or
>> Jiang-Gong, or any other paper that may or may not (I didn't bother to
>> look) present its own definitions and security model.
>> 
>> SPAKE2 requires exactly 4 exponentations in the subgroup if we do not
>> do anything smart about them. Two of these can be combined and
>> replaced with a dual base exponentiation via Strauss's algorithm.
>> 
>> Do you have anything to say to this?
>> 
>> Sincerely,
>> Watson
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg