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

[Feng Hao <[e-mail]>]

Hi Mike,

Thanks for the clarification. I’m still not entirely sure when the point falls into a small subgroup, simply multiplying a co-factor will resolve it and everything will still be in constant time. It would become clearer if you have a complete specification, and then we can see how the EC parameters interact with the protocol.

As said, this is a non-trivial problem as far as I understand. In IEEE P1363.2 and ISO/IEC 11770-4, there lacks a clean solution. The existing hashing-to-curve algorithm as defined in ISO/IEC 11770-4 is basically search then trial and error, which is not strictly constant time.

Hence I would recommend you consider writing this up and get a peer-reviewed publication. It will be a good contribution to the community as well as to standards such as ISO/IEC 11770-4. (I’m happy to be your contact for ISO/IEC if you go this route).

Cheers,
Feng

From: Mike Hamburg [mailto:[e-mail]]
Sent: 15 November 2016 17:19
To: Feng Hao <[e-mail]>
Cc: [e-mail]
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

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]<mailto:[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]<mailto:[e-mail]>>
Cc: Watson Bernard Ladd <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[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]<mailto:[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]<mailto:[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]<mailto:[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]<mailto:[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]<mailto:[e-mail]>
https://www.irtf.org/mailman/listinfo/cfrg