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

"Stanislav V. Smyshlyaev" <> Wed, 16 November 2016 13:12 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id C3A541295AA for <>; Wed, 16 Nov 2016 05:12:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id xPFp228_RY7p for <>; Wed, 16 Nov 2016 05:12:39 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:400e:c05::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 7B272129480 for <>; Wed, 16 Nov 2016 05:12:39 -0800 (PST)
Received: by with SMTP id p66so79168838pga.2 for <>; Wed, 16 Nov 2016 05:12:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:content-transfer-encoding:message-id:date:subject:from :in-reply-to:references:to:cc; bh=Oj6Ieky5N6gzHqNy3zS4xJl3kU1bftQLV17Lj8ExUGk=; b=dbVYp+EFP+QXIyAZEwNVBsxoPL9aRH18RFTHccoadJMBMIYBgOEfiE3e9g7F2ulkEh f+SyYP8cODyM4RfhQvu5nyUMpc29fRNEDOUuCtCREfL65sPQlIv9G8mRT9maDWEyxdhX i1GLo3Rpodf5uB/Q7cMVEUP41u0dKOfkU0FO96Epvk7rQDjSUaUBhAOkkgCmh9y7szFj AjfxsmgnYSgw8PlmcPFeqYNZChgNhUz86u9EOMT0q3pUtO7SbXlHNU/fQP0jznuEbslk enVt3OSjw/p3k0QhcRubU3rGK4U3xjyvw1m3TU8Szfv9NDpVilUU6ByZMjC69hbpdTfN cX5Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=x-gm-message-state:mime-version:content-transfer-encoding :message-id:date:subject:from:in-reply-to:references:to:cc; bh=Oj6Ieky5N6gzHqNy3zS4xJl3kU1bftQLV17Lj8ExUGk=; b=S3uAVChB5SqUGR8RzOiMpY5788C1gmrlRW17WHvQfpXyj0OFIm7tr9lMZIbnukyNZ4 bKwsmPBBxDxBmRjJLoV7Q8YLTByz0RmMF1Sb9UoBGC4wucrRkzJmstMS63sY777lpM1R Pf1I415Ye028q07KdfgcLiyVYt/1B5WLaAXzsSXfLR4DJbTVKdb6zWRMsyJLhB7qQGwQ vOcMZ1hHR3q2MeSbVy3QrZ3UH1qMfY11GxL1MgI1h+D2R8Pm2keh2Ttg/Q0Slk2/c/DK j0Ns3leE+xdXmi4bUi/FfOHfZ1jOS0NT4vaIaPMFbYq7PaZ3zErN4xMjYpiubGXqmJTH y9dA==
X-Gm-Message-State: ABUngvcTNI06GJwqNskkqfZqwHUBJWpqKD9Fxus0b7UY0GQAwBcRPR4zMyBiw4WZbojkfg==
X-Received: by with SMTP id s66mr4348631pfj.146.1479301958939; Wed, 16 Nov 2016 05:12:38 -0800 (PST)
Received: from [] ([]) by with ESMTPSA id 65sm53910778pfn.12.2016. (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 16 Nov 2016 05:12:38 -0800 (PST)
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
X-Mailer: BlackBerry Email (
Message-ID: <>
Date: Wed, 16 Nov 2016 22:12:34 +0900
From: "Stanislav V. Smyshlyaev" <>
In-Reply-To: <>
References: <> <> <> <> <> <> <> <> <>
To: Feng Hao <>, Watson Ladd <>
Archived-At: <>
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
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 13:12:42 -0000

Dear colleagues,

I don't quite understand, why ‎an alternative construction could be a problem, if it's security properties are explicitly stated and well-proven, and if it's description is clear and is not underspecified. 

I totally understand with Watson, that J-PAKE is slower than alternatives - but the performance issues are not secret for the developers who may want to choose it - so why should we harass it?

My opinion is when we have such a new area as PAKEs, diversity of constructions can be a good thing - in case all standardized constructions are proven and if their properties are clearly defined in the documents. 

So wouldn't it be a wise step to help the document become as clear as it can be (if Watson sees some problems in the current version)?

Best regards,
Stanislav Smyshlyaev
  Исходное сообщение  
От: Feng Hao
Отправлено: среда, 16 ноября 2016 г., 19:26
Кому: Watson Ladd
Тема: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

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.

* 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?

* 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.

* 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).

* 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.


[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

On 15/11/2016 19:14, "Watson Ladd" <> 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?

Cfrg mailing list