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

Feng Hao <> Wed, 16 November 2016 15:50 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 1CC1B129607 for <>; Wed, 16 Nov 2016 07:50:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.221
X-Spam-Status: No, score=-4.221 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id vStSfx0O7hs5 for <>; Wed, 16 Nov 2016 07:50:14 -0800 (PST)
Received: from ( []) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 511C8126BF7 for <>; Wed, 16 Nov 2016 07:50:14 -0800 (PST)
Received: from ([] by with esmtp (Exim 4.63) (envelope-from <>) id 1c72TU-0006bF-FX; Wed, 16 Nov 2016 15:50:12 +0000
Received: from ( by ( with Microsoft SMTP Server (TLS) id; Wed, 16 Nov 2016 15:49:51 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=selector1-newcastle-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=r9vX3N0Mal+aAzIk4Y7qEdGHyEijO4mrg2YeYKBX7nI=; b=RvY8fkSl3WIi8DzD9uCLfyDGrMU50fKvBSOgc3Asd1iwpNl2mI6fyNJxytE4REmyTjCee1xstB/cCjaLsQkwkOFUd8pPd9MD1S9+IMtA8lzypIKxQW/gdtIs42+IGgXaaQjBrEV1O3KZzklV5o2rH84vEKh1W2Z8xPskVO12+8M=
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.2; Wed, 16 Nov 2016 15:49:50 +0000
Received: from ([]) by ([]) with mapi id 15.01.0734.004; Wed, 16 Nov 2016 15:49:50 +0000
From: Feng Hao <>
To: Watson Ladd <>
Thread-Topic: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
Date: Wed, 16 Nov 2016 15:49:50 +0000
Message-ID: <>
References: <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-GB, en-US
Content-Language: en-US
authentication-results: spf=none (sender IP is );
x-originating-ip: []
x-microsoft-exchange-diagnostics: 1; DB5PR0701MB1926; 7:hIX1tEjbPaBMJdmthEMsbB1WgmHYBMc8vvQSYxdDgjDcSbo7z6zbjWTurnekdjnF2WuSLfrpln9UMBc/UGMbLSLWGRp9AUd3AEJehcbWHlrz0sxNmAU02YQEk6Yzr1bgnvdY0dr2Nj/mh9vbrH4Qtsw9TV3n//wZF/zHHh0aciLejPi3r3WTKAW1o2XajtNSNzmztHb+0AM6rWkTyrdBpMLtpC6pWTYy7E2ccq7wvBpl2LOnfqi2WQso8xt6AnSiKLGhUbD5fnajztR3R6XKRfnTfv500LuCbNw3bSBMf1AmFecRgCEmy54VVe/Q+70j0GykDMj4Xxc3VKAwwSFydgO6KrqKQHTzLArNxi+/DgA=
x-ms-office365-filtering-correlation-id: e5661fd9-c9ff-476d-6683-08d40e38331e
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001); SRVR:DB5PR0701MB1926;
x-microsoft-antispam-prvs: <>
x-exchange-antispam-report-test: UriScan:(158342451672863)(192374486261705)(266576461109395);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6060326)(6040281)(601004)(2401047)(5005006)(8121501046)(10201501046)(3002001)(6041223)(6061324); SRVR:DB5PR0701MB1926; BCL:0; PCL:0; RULEID:; SRVR:DB5PR0701MB1926;
x-forefront-prvs: 01283822F8
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(7916002)(24454002)(199003)(13464003)(377454003)(189002)(8676002)(77096005)(4326007)(229853002)(2906002)(66066001)(93886004)(101416001)(2900100001)(97736004)(76176999)(9686002)(7696004)(2950100002)(42882006)(110136003)(8936002)(81156014)(7846002)(5660300001)(74316002)(3846002)(87936001)(81166006)(50986999)(6916009)(102836003)(6116002)(54356999)(7736002)(305945005)(122556002)(86362001)(33656002)(68736007)(92566002)(1411001)(189998001)(74482002)(3280700002)(76576001)(105586002)(3660700001)(6506003)(106356001); DIR:OUT; SFP:1101; SCL:1; SRVR:DB5PR0701MB1926;; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
received-spf: None ( does not designate permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 16 Nov 2016 15:49:50.2578 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 9c5012c9-b616-44c2-a917-66814fbe3e87
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB5PR0701MB1926
Archived-At: <>
Cc: "" <>
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 15:50:23 -0000

Hi Watson,

>-----Original Message-----
>From: Watson Ladd []
>Sent: 16 November 2016 15:18
>To: Feng Hao <>
>Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
>On Wed, Nov 16, 2016 at 2:25 AM, Feng Hao <>
>> 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).
>Different setup assumptions do not make it impossible to compare different

OK. I said "fair", not "impossible".

>>  * 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.
>This a) cannot be done with standard foundations and b) is a trivial exercise
>with any kind of ideal hash/ROM model. I'll sit down and do it, but while
>drafting this email someone went and did it.

Cool. Btw, nothing is really "trivial" in the design of a protocol. Any small change may have profound effects. This is why I suggest you to write it down in full detail, and ideally get it in a peer-reviewed publication if that's possible so there is a fixed version of the spec as the basis for technical discussion.

>>  * 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
>Except I'm not interested in writing a review paper. I'm interested in looking
>at all the proposals before us for PAKE, and determining which should be
>>  * 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?
>Are you aware that DUAL_EC included a point generation mechanism that, if
>used, would have completely avoided the backdoor? Do you think that the
>hashing argument presented downthread is wrong.

If that works completely, why not reuse it instead of inventing your own?

>>  * 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.
>The next part of my email did describe the validation costs: 1
>exponentiation per element to be validated. That is not a full
>exponentation: if the subgroup is the unique subgroup of order q in the
>finite field, we need only check x^q=1. I said the validation doubled the cost
>of SPAKE2: this is not exactly right, as only one point needs to be validated.

OK. Michel just clarified.

>> 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
>>  * 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 draft completely specifies an equivalent protection. This is the reason
>we use the cofactor. I believe I explicitly required on-curve checks, but will
>make it more clear if you don't think so.
>>  * 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
>> 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?
>"Man is born free, but everywhere he is in chains".