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

[Feng Hao <[e-mail]>]

Hi Watson,

>-----Original Message-----
>From: Watson Ladd [mailto:[e-mail]]
>Sent: 15 November 2016 15:20
>To: Feng Hao <[e-mail]>
>Cc: [e-mail]
>Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
>
>On Tue, Nov 15, 2016 at 4:05 AM, Feng Hao <[e-mail]>
>wrote:
>> Hi Watson,
>>
>> From: Watson Ladd [mailto:[e-mail]]
>> Sent: 15 November 2016 07:25
>> To: Feng Hao <[e-mail]>
>> Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
>>
>> On Nov 14, 2016 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.
>>
>>>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.
>
>Let's just say SPAKE2 for specificity, but it's clear that Dragonfly has many of
>the same properties.
>>
>>>> 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?
>
>Easy: if you care about performance, don't use finite field Diffie-Hellman.

How is the finite field Diffie-Hellman relevant to this discussion? It's a different protocol and has different requirements for implementation.

Also note that finite field is just one choice for implementing a cryptographic protocol, so is the ECC. Not every device supports ECC.

>People who actually care about performance are going to use efficient
>groups. It is not the case that a small subgroup of a large prime order-field's
>multiplicative group has a faster exponentiation then an elliptic curve group
>of the same size. That's on top of the fact that the IETF has mostly not
>standardized these subgroups due to the risk of small subgroup confinement
>attacks: the use of p=2q+1 ensures that a Jacobi symbol computation
>completely protects people.

First, small subgroup confinement can be prevented if you have proper validation in place. This is part of the protocol specification if you design it properly.

Second, even with the use of p=2q+1, small subgroups still exist and you still need to watch out for the small subgroup confinement attack. The use of safe prime makes the exponentiation significantly more expensive. 

I think you may have mixed your understanding of costs for Diffie-Hellman key exchange and J-PAKE. 

>>> 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).
>
>It doesn't go ahead and discuss the cost of JPAKE in comparison. By my
>calculation they come out comparable, but that might be wrong.  Of course,
>this conversation ignores the fact that you need groups to be used which are
>not.

If you read on, the comparison is presented in Section 5 of the J-PAKE paper [1].

>>>> 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.
>
>You are saying that the CRS is a problem for SPAKE2, when in actual fact it
>isn't. Anyone reading your email would conclude that SPAKE2 is like an IBE
>scheme which necessarily has a trusted setup phase. This is wrong.

I don't know how one would draw that conclusion - IBE is a completely different thing

The suggested implementation of CRS is quoted from the GL paper [4]. You may want to check with the original authors if you think that's incorrect.

>> 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.
>
>The CRS in SPAKE2 is two points on an elliptic curve. I don't understand this
>last sentence. What needs to be checked is that the setup satisfies the
>conditions on the points M and N, which it does.
>Are you asserting that it doesn't in fact?

OK. I meant to say the proofs in this kind CRS-based designs are motivated by removing random oracle. This is why those papers don't specify using hash to generate the CRS. If you propose to use random oracle to set CRS, you need to prove that your change doesn't contradict the original proofs, or to produce new proofs.

In practical terms, when you use hash to generate M and N. You have the freedom to decide what's the input to the hash and in what format (in effect there are endless possibilities). There is an implied trust that whoever defines this setup doesn't precompute M and N such that it gives him an advantage in knowing some relationship between M and N. This is why in CRS-based PAKE papers, the authors state that the setup should be done by "a trusted party". 

>>>> 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?
>
>We need to chop out many of the proposals that are in the air. This
>multiplicity of choices is one of the reason no one uses PAKES.
>>
>>> 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.
>
>Yes I did. Here is the very specific criticism that I think anyone could have
>read in the previous email: On elliptic curve groups J-PAKE is far less
>performant than alternatives like SPAKE2 or Dragonfly, does not have better
>security, requires more shoehorning into protocols then the alternatives,
>and is just not attractive for IETF use as a result.

OK. Previously you used J-PAKE as an example to go against Dragonfly, and now you do it in the reverse order?

https://www.ietf.org/mail-archive/web/cfrg/current/msg04181.html

All these PAKE techniques, EKE, SPEKE, Dragonfly, SPAKE2, J-PAKE etc, are examples of the diversity in the research field. They are designed with different considerations and have different trade-offs. It's important to understand the differences, but also the differences should be tolerated and respected. There is no need to use some to trump others. A developer can choose what suits their application requirements best. 

>>
>>>> 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.
>>>>
>
>
>
>--
>"Man is born free, but everywhere he is in chains".
>--Rousseau.