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

[Watson Ladd <[e-mail]>]

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. 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.

>
>> 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.

>
>>> 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.

>
> 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?

>
>>> 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.

>
>>> 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.