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

[Mike Hamburg <[e-mail]>]

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 <[e-mail]> 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" <[e-mail]> 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 <[e-mail]>
>> 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
>>> [e-mail]
>>> https://www.irtf.org/mailman/listinfo/cfrg
>> 
>> 
>> 
>> -- 
>> "Man is born free, but everywhere he is in chains".
>> --Rousseau.
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg