Return-Path: 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 ; 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 ; 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 ; 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 In-Reply-To: Date: Wed, 16 Nov 2016 17:23:08 +0100 Content-Transfer-Encoding: quoted-printable Message-Id: <7E91D778-0094-43CD-A0AF-3B0D0B8F6209@ens.fr> References: <1E393A35-FEF3-4205-B91B-D3DC2DE918A1@ens.fr> To: Feng Hao 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: Cc: "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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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.=20 Regards, Michel > On Nov 16, 2016, at 4:33 PM, Feng Hao = wrote: >=20 > Dear Michel, >=20 > Thanks for the clarifications, which address the raised points = pertinently.=20 >=20 > One small question: "M=3DH(0) and N=3DH(1), where H hashes into the = appropriate group" >=20 > Can you give more details on the realization of H? >=20 > Cheers, > Feng >=20 >> -----Original Message----- >> From: Michel Abdalla [mailto:michel.abdalla@ens.fr] >> Sent: 16 November 2016 15:08 >> To: Feng Hao >> Cc: Watson Ladd ; cfrg@irtf.org >> Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs >>=20 >> Dear Feng, >>=20 >> Since you=E2=80=99ve raised some questions about SPAKE2, I just = wanted to clarify >> some of these issues below. >>=20 >> Regards, >> Michel >>=20 >>> On Nov 16, 2016, at 11:25 AM, Feng Hao >> wrote: >>>=20 >>> Hi Watson, >>>=20 >>> On your comments about comparing costs between SPAKE2 and J-PAKE >>>=20 >>> * 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). >>>=20 >>> * 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. >>>=20 >>=20 >> 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=3DH(0) and N=3DH(1), where H = hashes into >> the the appropriate group. >>=20 >>> * 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. >>>=20 >>> * 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. >>>=20 >>> * 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? >>>=20 >>=20 >> 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. >>=20 >>> * 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. >>>=20 >>> I read again the original SPAKE2 paper as well as your I-D. I have = the >>> following comments >>>=20 >>> * 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. >>=20 >> If one knows the discrete log of M with respect to g (let=E2=80=99s = 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'=3Dg^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 =3D Y* / N^pw, K_A =3D = Y^{x=E2=80=99 - pw m}, >> and SK_A =3D H(A,B,X=E2=80=99,Y*,K_A). Note that SK_A will match SK = when pw is the >> correct pw. >>=20 >>>=20 >>> * 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). >>=20 >> 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. >>>=20 >>>=20 >>> * 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! >>>=20 >>> * 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. >>>=20 >>> Cheers, >>> Feng >>>=20 >>> [1] D. Pointcheval and S. Zimmer, "Multi-Factor Authenticated Key >> Exchange," Proceedings of Applied Cryptography and Network Security >> (ACNS=C2=B908), pp. 277-295, LNCS 5037, 2008. >>>=20 >>> [2] Security Analysis of a Multi-Factor Authenticated Key Exchange >>> Protocol https://eprint.iacr.org/2012/039.pdf >>>=20 >>> On 15/11/2016 19:14, "Watson Ladd" wrote: >>>=20 >>>> Dear Feng, >>>>=20 >>>> 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. >>>>=20 >>>> 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. >>>>=20 >>>> Do you have anything to say to this? >>>>=20 >>>> Sincerely, >>>> Watson >>>=20 >>> _______________________________________________ >>> Cfrg mailing list >>> Cfrg@irtf.org >>> https://www.irtf.org/mailman/listinfo/cfrg >=20