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

Feng Hao <feng.hao@newcastle.ac.uk> Tue, 15 November 2016 12:05 UTC

Return-Path: <feng.hao@newcastle.ac.uk>
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 9B498124281 for <cfrg@ietfa.amsl.com>; Tue, 15 Nov 2016 04:05:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.221
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=newcastle.onmicrosoft.com
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 zl_EvXPnmbtI for <cfrg@ietfa.amsl.com>; Tue, 15 Nov 2016 04:05:55 -0800 (PST)
Received: from cheviot22.ncl.ac.uk (cheviot22.ncl.ac.uk [128.240.234.22]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 22C761294B3 for <cfrg@irtf.org>; Tue, 15 Nov 2016 04:05:55 -0800 (PST)
Received: from exhubvm01.ncl.ac.uk ([128.240.234.5] helo=EXHUBVM01.campus.ncl.ac.uk) by cheviot22.ncl.ac.uk with esmtp (Exim 4.63) (envelope-from <feng.hao@newcastle.ac.uk>) id 1c6cUr-0004Is-F3; Tue, 15 Nov 2016 12:05:53 +0000
Received: from EUR01-VE1-obe.outbound.protection.outlook.com (213.199.154.246) by exhub.ncl.ac.uk (128.240.234.5) with Microsoft SMTP Server (TLS) id 14.3.266.1; Tue, 15 Nov 2016 12:05:32 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=newcastle.onmicrosoft.com; s=selector1-newcastle-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=5nD/7Fpna8lgv4W1onhn/icUOinbOeFXrI2iPt/8r4o=; b=kVYIIar4hGbH3aPtFhdG6snNsvjJ62/bYy2MUl6iMyn3an1kePBP+CDze6WS8M75VtOuommg8W3cjZzmRvUndFrj99Z+GeoaNMgC8EghIjsaeGSOQyHcWOuLOL3nL/idFkYLGueWUHxf7HiRrtEe2WKMobZ2m/OHB2PG+rZIbrE=
Received: from DB5PR0701MB1928.eurprd07.prod.outlook.com (10.167.228.24) by DB5PR0701MB1927.eurprd07.prod.outlook.com (10.167.228.23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.2; Tue, 15 Nov 2016 12:05:29 +0000
Received: from DB5PR0701MB1928.eurprd07.prod.outlook.com ([10.167.228.24]) by DB5PR0701MB1928.eurprd07.prod.outlook.com ([10.167.228.24]) with mapi id 15.01.0734.004; Tue, 15 Nov 2016 12:05:29 +0000
From: Feng Hao <feng.hao@newcastle.ac.uk>
To: Watson Ladd <watsonbladd@gmail.com>
Thread-Topic: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
Thread-Index: AdI+bZzQZch4zeUeTNyFcWq6Y0INHQAHCdeAABAiwAAAEcC1gAAJS7Qw
Date: Tue, 15 Nov 2016 12:05:29 +0000
Message-ID: <DB5PR0701MB192893EEFB5B57A72B70984ED4BF0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
References: <DB5PR0701MB19282BB2E03816405AF5DF91D4BC0@DB5PR0701MB1928.eurprd07.prod.outlook.com> <CACsn0ck4uFHrKzX9EDGSADjv1BkpnGPA3v4ncR8R9dkTn5DWgg@mail.gmail.com> <D44FD9E6.186BF%feng.hao@newcastle.ac.uk> <CACsn0cngxnRjVPBDcC9HuNxbJV-VD1UPHOryWSjKBkf5+Mnz1w@mail.gmail.com>
In-Reply-To: <CACsn0cngxnRjVPBDcC9HuNxbJV-VD1UPHOryWSjKBkf5+Mnz1w@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=feng.hao@newcastle.ac.uk;
x-originating-ip: [128.240.225.103]
x-microsoft-exchange-diagnostics: 1; DB5PR0701MB1927; 7:VF6ImoGRm/Og5fTdJtyCWEV263WiK55I4cKBwfepxBXYMq1DvnRimGMOTefYCX7fwwVJSQA7tnG/kwKzaaIVtcWZZEQiNvQ6B6QaRgV4c37TB8tbqcUb2L4xQLCrt8vSZ+KwuXCC+BfIP+KKDVYtAtye9D5pY/tYuqMkCggbdecLBGpstxkbhyClbQ3dLoEvIrt1zZWxn2TVci6B9q/qM0xOq7L8wWkKpc+SAQM2Y7f0RJmdotYi6gTMb25sS+V9jeM9Bfu0w922+MGCJZWY0JOuNCGLFLgwui2UQnyX0X3+yMbljuRslgvzRHzM0ud7atL4LZHJmg+zszAq6ckcrORhKZlbAPJ0fBr9RcUo4eU=
x-ms-office365-filtering-correlation-id: 7be9aeae-fd53-40f2-5a97-08d40d4fb19f
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001); SRVR:DB5PR0701MB1927;
x-microsoft-antispam-prvs: <DB5PR0701MB19270A86E20D1ACB8000FCBED4BF0@DB5PR0701MB1927.eurprd07.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(120809045254105)(192374486261705)(266576461109395);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6060326)(601004)(2401047)(5005006)(8121501046)(10201501046)(3002001)(6061324); SRVR:DB5PR0701MB1927; BCL:0; PCL:0; RULEID:; SRVR:DB5PR0701MB1927;
x-forefront-prvs: 012792EC17
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(7916002)(377424004)(189002)(199003)(377454003)(69234005)(24454002)(6116002)(50986999)(76176999)(66066001)(86362001)(76576001)(551544002)(3846002)(102836003)(2906002)(4326007)(33656002)(74482002)(189998001)(101416001)(54356999)(4001150100001)(3660700001)(97736004)(3280700002)(74316002)(93886004)(1411001)(122556002)(305945005)(7846002)(229853002)(7736002)(7696004)(2950100002)(110136003)(6916009)(42882006)(5660300001)(105586002)(106356001)(8676002)(87936001)(81156014)(2900100001)(81166006)(68736007)(92566002)(77096005)(8936002)(9686002); DIR:OUT; SFP:1101; SCL:1; SRVR:DB5PR0701MB1927; H:DB5PR0701MB1928.eurprd07.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
received-spf: None (protection.outlook.com: newcastle.ac.uk 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: 15 Nov 2016 12:05:29.6057 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 9c5012c9-b616-44c2-a917-66814fbe3e87
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB5PR0701MB1927
X-OriginatorOrg: newcastle.ac.uk
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/K6on0U7CDZj-cmfFd_yYjnGIvf4>
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: Tue, 15 Nov 2016 12:05:58 -0000

Hi Watson,

From: Watson Ladd [mailto:watsonbladd@gmail.com] 
Sent: 15 November 2016 07:25
To: Feng Hao <feng.hao@newcastle.ac.uk>
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

On Nov 14, 2016 2:56 PM, "Feng Hao" <feng.hao@newcastle.ac.uk> wrote:
>>
>> Hi Watson,
>>
>> Can you be specific what alternative you are talking about?
>>
>> In [1], J-PAKE is compared with EKE and SPEKE, which are widely considered
>> the simplest and the most efficient balanced PAKEs. It is shown that the
>> computational efficiency of J-PAKE is about the same as EKE and SPEKE in
>> the finite field setting. J-PAKE is better in the EC setting because: 1)
>> EKE in EC is unspecified (a straightforward implementation of EKE in EC
>> will trivially leak information about the password); 2) SPEKE in EC
>> requires an additional primitive of hashing a password to a random point
>> on the curve (which is a non-trivial problem on its own). J-PAKE needs 2
>> rounds instead of one, which is a downside and is acknowledged in the
>> paper. But security is never perfect; it is always a trade-off.

>If only there existed one round PAKEs that could work on elliptic curves. Oh wait, there are several proposals, some with security proofs.

Again, can you be specific what PAKEs you are talking about? We can then have a concrete side-by-side comparison.

>> Two points are worth reminding:
>>
>> 1. There is an unfortunate misconception in quite a number of PAKE papers
>> in the literature that merely count the number of exponentiations as the
>> computational cost without considering the specific group settings
>> required by the protocol (e.g., if the protocol accommodates short or long
>> exponents). See Section 2.2 in [1] for a full discussion.

>This cost model is correct for ECC. In the finite field we have already lost all the performance already. 

What do you mean by “lost all the performance”? Can you elaborate?

> Furthermore, your section 2.2 of 1 is not a full discussion: an actual analysis of the exponentiations done by each party and the size of the values they use would have been a good idea to include to model the cost in terms of group additions. 

Sorry, I don’t understand this. The analysis in the paper uses one specific example of 1024-bit modulus since this is the parameter used in the EKE and SPEKE papers. The example is mainly to illustrate the different cost of performing exponentiation with long/short exponent that one exponentiation in SPEKE (and EKE) is 6-7 times more expensive than one exponentiations in J-PAKE.  It’s trivial to generalize that for other bit-length modulus (the cost difference is 2047/224 = 9 times for 2048-bit modulus).

>> 2. There is also a category of PAKE protocols that assume a trusted setup
>> to define the randomness in the group setting: in particular, to define a
>> pair of generators whose discrete logarithm must be unknown. SPAKE2 (which
>> I understand you¹re working on for an IEFT submission) is only one
>> example. Other examples include KOY [2], Jiang-Gong [3] and
>> Gennaro-Lindell [4]. Implementing such as trusted set up (i.e., the common
>> reference model if you¹re a fan of jargon) is a tricky task. The most
>> concrete advice in terms of implementation that you may find is probably
>> from Gennaro and Lindell [4]: ³An example of where it is reasonable to
>> assume a common reference string is when a large organization wishes to
>> implement secure login for its employees. In this case, the organization
>> is trusted to choose the common reference string properly, and this string
>> can then be hardwired into the software code.² As an example we can have
>> Google to define a trusted setup, which will be trusted by its employees.
>> However, it will limit the PAKE application to the internal use within
>> that organization. EKE, SPEKE and SPEKE do not have this issue.

> Some readers would interpret the above to say JPAKE doesn't depend on a CRS. It depends on a stronger (in some sense) random oracle assumption. 

This CRS vs random oracle is one of the ideological arguments that is only of interest to theoreticians. I don’t think it’s an appropriate place to discuss that here.

FYI - the original Abdalla-Poincheval paper states that the security of SPAKE2 is in the random oracle model; it also depends on a CRS of course.

> In practice the CRS for SPAKE2 can be computed no problem from a random oracle. The draft has lagged in part due to accurately specifying this: will do sometime.

This is not specified in the original SPAKE2 paper. And this is not specified in any of the KOY, Jiang-Gong and Gennaro-Lindell papers (that assume a CRS) which I sent earlier. If you propose to change specification, you need to produce a proof to show it doesn’t contradict the original proofs.

>> Note that I¹m not objecting PAKE protocols that rely on a common reference
>> string; they are one category of PAKE designs and are useful in
>> specifically identified scenarios. I¹m merely highlighting that there are
>> diversified PAKE designs with different assumptions and properties. Having
>> the diversity is a good thing in the research field. However, disparaging
>> some without noting the weaknesses/merits of others in the context of that
>> diversity is not fair.

>The great thing about standards is there are so many to pick from. This has doomed PAKEs forever. 

Again, I don’t understand. What’s your argument?

> At some point we have to realize that a protocol with 14 exponentations and two rounds is not competitive with a 1 round, 2 exponentiation protocol, and this holds regardless of the group. I do not understand what advantages JPAKE provides, although its symmetry is occasionally useful for some protocols.

By 1 round, 2 exponentiations, you mean SPEKE? Did you read Sec 2.2 before you respond to this? If you have any specific technical questions, doubts or disagreement, I'm happy to discuss. However, criticisms that are too general and abstract don't help.

>> Regards,
>> Feng
>>
>>
>> [1] J-PAE: http://eprint.iacr.org/2010/190.pdf
>>
>> [2] J. Katz, R. Ostrovsky, M. Yung, ³Efficient password-authenticated key
>> exchange using human-memorable passwords², Advances in Cryptology, LNCS
>> 2045, pp. 475-494, 2001.
>>
>> [3] S.Q. Jiang, G. Gong, ³Password based key exchange with mutual
>> authentication,² Selected Area in Cryptography, LNCS 3357, pp. 267-279,
>> 2004
>>
>> [4] R. Gennaro, Y. Lindell, ³A framework for password-based authenticated
>> key exchange,² Eurucrypt¹03, LNCS, No. 2656, pp. 524-543, 2003.
>>
>>
>> On 14/11/2016 15:14, "Watson Ladd" <watsonbladd@gmail.com> wrote:
>>
>> >I'm sad to see J-PAKE continue to have legs given its terrible
>> >performance compared to alternatives. What's the point?
>> >
>> >On Mon, Nov 14, 2016 at 3:53 AM, Feng Hao <feng.hao@newcastle.ac.uk>
>> >wrote:
>> >> Hi,
>> >>
>> >> Recently I submitted J-PAKE and Schnorr NIZK to IETF for "informational
>> >>RFC". Both drafts are currently under review in the independent
>> >>submission stream.
>> >>
>> >> As per the reviewers' comments, I've revised the drafts to clarify a
>> >>few points.
>> >>
>> >> Schnorr draft
>> >>  * Clarify the parameters for the finite field and elliptic curves. The
>> >>DSA/ECDSA parameters are used only as an example; other groups can also
>> >>be used.
>> >>  * Clarify the requirement for the hash function. It needs to be
>> >>collision-resistant in a practical realisation with recommended hash
>> >>functions given.
>> >>
>> >> J-PAKE draft
>> >>  * Clarify that key confirmation can be implicit or explicit, and that
>> >>explicit key confirmation is recommended in a practical implementation
>> >>of J-PAKE.
>> >>
>> >> The latest drafts are below:
>> >>
>> >> Name:           draft-hao-schnorr
>> >> Revision:       05
>> >> Title:          Schnorr NIZK Proof: Non-interactive Zero Knowledge
>> >>Proof for Discrete Logarithm
>> >> Document date:  2016-11-14
>> >> Group:          Individual Submission
>> >> Pages:          11
>> >> URL:
>> >>https://www.ietf.org/internet-drafts/draft-hao-schnorr-05.txt
>> >> Status:         https://datatracker.ietf.org/doc/draft-hao-schnorr/
>> >> Htmlized:       https://tools.ietf.org/html/draft-hao-schnorr-05
>> >> Diff:           https://www.ietf.org/rfcdiff?url2=draft-hao-schnorr-05
>> >>
>> >> Name:           draft-hao-jpake
>> >> Revision:       05
>> >> Title:          J-PAKE: Password Authenticated Key Exchange by Juggling
>> >> Document date:  2016-11-14
>> >> Group:          Individual Submission
>> >> Pages:          14
>> >> URL:
>> >>https://www.ietf.org/internet-drafts/draft-hao-jpake-05.txt
>> >> Status:         https://datatracker.ietf.org/doc/draft-hao-jpake/
>> >> Htmlized:       https://tools.ietf.org/html/draft-hao-jpake-05
>> >> Diff:           https://www.ietf.org/rfcdiff?url2=draft-hao-jpake-05
>> >>
>> >> Your comments are most welcome!
>> >>
>> >> Cheers,
>> >> Feng
>> >>
>> >> _______________________________________________
>> >> Cfrg mailing list
>> >> Cfrg@irtf.org
>> >> https://www.irtf.org/mailman/listinfo/cfrg
>> >
>> >
>> >
>> >--
>> >"Man is born free, but everywhere he is in chains".
>> >--Rousseau.
>>