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

[Mike Hamburg <[e-mail]>]

Hi Feng,

Thanks for your reply. My comments are inline. 

Sent from my phone.  Please excuse brevity and typos.

> On Nov 15, 2016, at 02:55, Feng Hao <[e-mail]> wrote:
> 
> Hi Mike,
> 
> Thanks for the thoughtful comments.
> 
> There indeed exist encoding algorithms that can hash an input to a (somehow random) point on the curve in constant time. One of them (based on the icart method) is used by PACE in the implementation of e-passport.
> 
> But these algorithms have very specific requirements on the parameters of the curve (e.g., the modulus needs to be in some form etc). I'm not aware of any general algorithm that can flexibly and efficiently do the hashing-to-curve for general elliptic curves which are suitable for cryptography (i.e., where ECDLP is hard). 

The Shallue-vanDeWoestijne-Ulas algorithm (SWU) meets these requirements on any elliptic curve over a large-characteristic field.  See
https://eprint.iacr.org/2009/340.pdf
Section 2.1.  I don't remember if there is a known solution for small-characteristic.

> With regard to the algorithm you specify below, I'm not sure it's a constant algorithm though. There is a conditional check for the square root (which needs some care in the implementation).

Right. You can compute the Legendre symbol z^((p-1)/2) in constant time easily.  Then you have to conditionally select between the two options based on whether the symbol is -1; or else use arithmetic based on the fact that the symbol is necessarily in {-1,0,1}.

> Also, if the point falls into the subgroup, you say it doesn't matter because it will be multiplied by a co-factor. Are u sure?

I should have been more clear because this is security-critical.

The most natural choice of DH algorithm for SPEKE on a Montgomery curve is X25519, or maybe X448. These algorithms both multiply by the cofactor.  In this case, it doesn't matter whether P is in the subgroup.

For SPAKE2-EE, and for SPEKE with an algorithm that doesn't multiply by the cofactor, this would be a security hole. In that case, you need to multiply the encoded point by the cofactor before using it.

> On a side note, if this algorithm works as it says, then one should be able to easily apply it to Dragonfly? There were a lot discussion on this list on how to do efficient hashing-to-curve in constant time for the Dragonfly protocol (RFC 7664). I don't recall there is a consensus. Maybe there is an easy solution to that problem? 

I'm pretty sure SWU works for Dragonfly.  The one I presented requires a Montgomery curve, or at least a curve with a 2-torsion point, and I don't recall if Dragonfly uses those.

Of course, if you're respeccing Dragonfly, you might as well change it to some other PAKE, maybe one with a security proof.

> 
> Cheers,
> Feng

Cheers,
-- Mike

> -----Original Message-----
> From: Mike Hamburg [mailto:[e-mail]] 
> Sent: 15 November 2016 00:56
> To: Feng Hao <[e-mail]>
> Cc: Watson Bernard Ladd <[e-mail]>; [e-mail]
> Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
> 
> 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
>