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

Michel Abdalla <michel.abdalla@ens.fr> Wed, 16 November 2016 16:23 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 6B3D91279EB for <cfrg@ietfa.amsl.com>; Wed, 16 Nov 2016 08:23:12 -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 5x_JuWeCuUJH for <cfrg@ietfa.amsl.com>; Wed, 16 Nov 2016 08:23:10 -0800 (PST)
Received: from nef2.ens.fr (nef2.ens.fr [129.199.96.40]) by ietfa.amsl.com (Postfix) with ESMTP id 2358E129423 for <cfrg@irtf.org>; Wed, 16 Nov 2016 08:23:09 -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 uAGGN8CW077258 ; Wed, 16 Nov 2016 17:23:09 +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 uAGGN8IR001412 ; Wed, 16 Nov 2016 17:23:08 +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: <DB5PR0701MB1928850E56E7BB9863FFE0CAD4BE0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
Date: Wed, 16 Nov 2016 17:23:08 +0100
Content-Transfer-Encoding: quoted-printable
Message-Id: <7E91D778-0094-43CD-A0AF-3B0D0B8F6209@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> <1E393A35-FEF3-4205-B91B-D3DC2DE918A1@ens.fr> <DB5PR0701MB1928850E56E7BB9863FFE0CAD4BE0@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 17:23:09 +0100 (CET)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/CXKpD17oWMoEel1VUdO7MSFsEak>
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 16:23:12 -0000

Dear Feng,

It seems to me that Watson already proposes one such method in his specification of SPAKE2.

Other methods of realizing H can be found in the literature, such as in the instantiation of the Boneh-Franklin IBE scheme and the Boneh-Lynn-Shacham signature scheme. 

Regards,
Michel

> On Nov 16, 2016, at 4:33 PM, Feng Hao <feng.hao@newcastle.ac.uk> wrote:
> 
> Dear Michel,
> 
> Thanks for the clarifications, which address the raised points pertinently. 
> 
> One small question: "M=H(0) and N=H(1), where H hashes into the appropriate group"
> 
> Can you give more details on the realization of H?
> 
> Cheers,
> Feng
> 
>> -----Original Message-----
>> From: Michel Abdalla [mailto:michel.abdalla@ens.fr]
>> Sent: 16 November 2016 15:08
>> To: Feng Hao <feng.hao@newcastle.ac.uk>
>> Cc: Watson Ladd <watsonbladd@gmail.com>om>; cfrg@irtf.org
>> Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
>> 
>> 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
>