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

Mike Hamburg <mike@shiftleft.org> Tue, 15 November 2016 00:55 UTC

Return-Path: <mike@shiftleft.org>
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 11006129593 for <cfrg@ietfa.amsl.com>; Mon, 14 Nov 2016 16:55:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.499
X-Spam-Level:
X-Spam-Status: No, score=-3.499 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RP_MATCHES_RCVD=-1.497, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=shiftleft.org
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 fMhHFKATtVUW for <cfrg@ietfa.amsl.com>; Mon, 14 Nov 2016 16:55:38 -0800 (PST)
Received: from astral.shiftleft.org (vpn.shiftleft.org [52.40.228.30]) by ietfa.amsl.com (Postfix) with ESMTP id 10EA6129452 for <cfrg@irtf.org>; Mon, 14 Nov 2016 16:55:38 -0800 (PST)
Received: from [10.184.148.249] (unknown [209.36.6.242]) (Authenticated sender: mike) by astral.shiftleft.org (Postfix) with ESMTPSA id 36F569FCB3; Mon, 14 Nov 2016 16:55:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shiftleft.org; s=sldo; t=1479171320; bh=QQZc6zas8vrVVHS4ARIe4hxLPpvT23i4KGF+M9+lao8=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=i+GcO6Wpade00yzjn1VbC2BFAStJ7VmoRV7mTqvB/7CgGUW256wxlouQlDb9anqk5 mbIPp4ZPfbiU1q+Z1kKAAhNePxWpmuS+R/WzBpk/lALnfFK/7oOIs74ikTU4Sj+wjv h8O2TYPJjt2wAE5o8NGzADRylLDE6Co+P1J6C3Qo=
From: Mike Hamburg <mike@shiftleft.org>
Message-Id: <1B6B7B9F-F166-42EE-A35E-4D899CA1BAFE@shiftleft.org>
Content-Type: multipart/signed; boundary="Apple-Mail=_23E1982E-7673-4458-873E-526F958275D1"; protocol="application/pkcs7-signature"; micalg=sha1
Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3254\))
Date: Mon, 14 Nov 2016 16:55:35 -0800
In-Reply-To: <D44FD9E6.186BF%feng.hao@newcastle.ac.uk>
To: Feng Hao <feng.hao@newcastle.ac.uk>
References: <DB5PR0701MB19282BB2E03816405AF5DF91D4BC0@DB5PR0701MB1928.eurprd07.prod.outlook.com> <CACsn0ck4uFHrKzX9EDGSADjv1BkpnGPA3v4ncR8R9dkTn5DWgg@mail.gmail.com> <D44FD9E6.186BF%feng.hao@newcastle.ac.uk>
X-Mailer: Apple Mail (2.3254)
X-Virus-Scanned: clamav-milter 0.99.2 at astral
X-Virus-Status: Clean
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/r-P3lNmuGYKgLHgVx40fKTk6moY>
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 00:55:41 -0000

I’d like to note that for both SPEKE and SPAKE2-EE, the encoding to the curve doesn’t need to be uniform.  It just needs to be inverse-sampleable and within some reasonable factor of uniform.  This means that either SWU or Elligator can be used for this purpose.

If you’re doing SPEKE on a Montgomery curve y^2 = x(x^2+Ax+1), such as X25519, then Elligator2 is actually pretty simple to specify:



Let u be a fixed quadratic non-residue.  For example, u=-1 for 3mod4, or u=2 for 5mod 8.  (The other reasonable choice is u=sqrt(-1) for 5mod 8.)

Take as input a sequence of bytes to be encoded, eg h=really_slow_hash(salt,password).  Convert it to a field element using a little-endian convention, because Montgomery curves are Bernstein country.

Let x := -A / (1+u*h^2).

if x*(x^2+A*x+1) isn’t square, then change x := -A-x, which is also equal to x*u*h^2 by construction.

Now x is the x-coordinate of a point on the curve.  In the unlikely event that 1+uh^2=0, then the output is 0, or the point at infinity, or 0/0, or whatever.  These are all equivalent for SPEKE-X25519.  It doesn’t matter whether the point is in the subgroup or not, because you’ll multiply by the cofactor during the scalar mul.

For SPAKE2-EE, the specification is more complicated, but not by much.



Efficiency-wise, this can be implemented in constant time, in approximately the same amount of time as a single square root operation.  So can SWU, if you aren’t on a Montgomery or Edwards curve.

— Mike


> On Nov 14, 2016, at 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.
> 
> 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.
> 
> 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.
> 
> 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.
> 
> 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.
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg