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

From: Feng Hao <[email-masked]>
Date: Mon, 14 Nov 2016 11:53:28 +0000

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

---

From: Watson Ladd <[email-masked]>
Date: Mon, 14 Nov 2016 07:14:17 -0800

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 <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Feng Hao <[email-masked]>
Date: Mon, 14 Nov 2016 22:56:22 +0000

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" <[email-masked]> wrote:

>> Recently I submitted J-PAKE and Schnorr NIZK to IETF for "informational
>>RFC". Both drafts are currently under review in the independent
>>submission stream.
>>
>>  * 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.
>>
>> URL:            
>>https://www.ietf.org/internet-drafts/draft-hao-schnorr-05.txt
>> URL:            
>>https://www.ietf.org/internet-drafts/draft-hao-jpake-05.txt

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 14 Nov 2016 16:55:35 -0800

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 <[email-masked]> wrote:
> 
> Hi Watson,
>

---

From: Feng Hao <[email-masked]>
Date: Tue, 15 Nov 2016 10:55:48 +0000

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

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

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? 

Cheers,
Feng

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

Let x := -A / (1+u*h^2).

— Mike

---

From: Feng Hao <[email-masked]>
Date: Tue, 15 Nov 2016 12:05:29 +0000

Hi Watson,

From: Watson Ladd [mailto:[email-masked]] 
Sent: 15 November 2016 07:25
To: Feng Hao <[email-masked]>
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

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

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

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

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

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

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

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Nov 2016 07:20:09 -0800

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

> 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 illust…

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.

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

> 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 ch…

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?

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

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.

---

From: Feng Hao <[email-masked]>
Date: Tue, 15 Nov 2016 17:49:50 +0000

Hi Watson,

>Sent: 15 November 2016 15:20
>Cc: [email-masked]
>>>> 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
>>>If only there existed one round PAKEs that could work on elliptic curves.
>Oh wait, there are several proposals, some with security proofs.
>>
>Let's just say SPAKE2 for specificity, but it's clear that Dragonfly has many of
>the same properties.
>>
>>>> 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.
>>
>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).
>
>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.

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

>>>> [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.
>>>>
>>>> [4] R. Gennaro, Y. Lindell, ³A framework for password-based
>>>> authenticated key exchange,² Eurucrypt¹03, LNCS, No. 2656, pp. 524-543,
>2003.
>>>>
>>>>
>>>> >On Mon, Nov 14, 2016 at 3:53 AM, Feng Hao
>>>> ><[email-masked]>
>>>> >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.
>>>> >>
>>>> >>  * 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.
>>>> >>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.
>>>> >>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 15 Nov 2016 11:14:58 -0800

Dear Feng,

Let me make this very clear, to avoid your misunderstandings: J-PAKE
is substantially less efficient than SPAKE2 over the same group.
SPAKE2 with M and N generated by hashing is secure, and the proofs
found in the SPAKE2 paper do work for this case. If we use a small
subgroup of a finite field group, then the necessary validations for
group membership double the cost of SPAKE2, but J-PAKE is still
slower. J-PAKE requires an additional round, while SPAKE2 fits into
the same flow as Diffie-Hellman. There is no relevance of KOY, or
Jiang-Gong, or any other paper that may or may not (I didn't bother to
look) present its own definitions and security model.

SPAKE2 requires exactly 4 exponentations in the subgroup if we do not
do anything smart about them. Two of these can be combined and
replaced with a dual base exponentiation via Strauss's algorithm.

Do you have anything to say to this?

Sincerely,
Watson

---

From: Feng Hao <[email-masked]>
Date: Wed, 16 Nov 2016 10:25:39 +0000

Hi Watson,

On your comments about comparing costs between SPAKE2 and J-PAKE
 
 * It's not a fair comparison as the setup assumptions are different. SPAKE2 requires a trusted setup, while J-PAKE doesn't. Instead, you should compare SPAKE2 with KOY, Jiang-Gong and GL protocols as they require the same trusted setup. J-PAKE should be compared with EKE, SPEKE and Dragonfly (which is based on SPEKE).

 * When you say "SPAKE2 with M and N generated by hashing is secure, and the proofs found in the SPAKE2 paper do work", it's best that you write up the full details how you do the hashing, proofs that why it's secure and why
it doesn't affect the original proofs in the SPAKE2 paper in any way. Then people can check and verify your proofs instead of having to take your word for it. I see you are always rigorous in asking "security proofs" from others for everything they do (which is good), so you should consider applying the same rigor to yourself.

 * The KOY, Jiang-Gong and GL papers are relevant as they are the same type of CRS-based designs as SPAKE2. These papers state that the setup needs to be done by a trusted party and they don't specify using a hash.
SPAKE2 is in the same model. It's appropriate you compare these protocols and definitions. This is necessary especially since you're doing something not specified in the original SPAKE2 paper and other related peer-reviewed papers.

 * You will need to convince IETF users that there is no possibility of trapdoor for M and N (which may prove a bit tricky). Knowledge (or partial knowledge) of the relation between M and N may allow one to
systematically break all instances of the protocol execution. 

 * Kindly note that if you can manage to convince IETF users that M and N are completely random, one might just plug M and N as the input of two random points to DUAL_EC and make it work?

 * What you say about the 4 exponentiations in the subgroup is correct (consistent with the original paper), but this hasn't included the validation of the public key (which is free in EC but takes one full exponentiation in the finite field setting). See my further comment below.

I read again the original SPAKE2 paper as well as your I-D. I have the following comments

 * I think SPAKE2 is underspecified in the original paper. It doesn't state the requirements for M and N, but it should be clear that they must be completely random. Also, it doesn't state if the discrete logarithm between M and g (and symmetrically between M and g) must be unknown. It's not immediately clear to me if knowledge of the discrete logarithm for M and g will break anything, but all these should have been explicitly specified in the paper.

 * I'm a bit worried that in the actual protocol specification in the original paper, there is no step to perform public key validation. This could be due to two reasons: 1) an inadvertent omission by the authors; 2) an intentional design choice. In case of ambiguity like this, one normally takes it as the latter. The reason is simple: if public key validation is considered essential, it MUST be clearly specified, which is the case with most key agreement protocols. However, from early 2000s, some researchers called for abandoning the public key validation, as long as the protocol has formal security proofs (HMQV is one notable example, but it backfired in the end).

 * The above observation reminds me of a paper " Multi-Factor Authenticated Key Exchange" by Poincheval and Zimmer in 2008 [1] where the protocol is specified in a similar manner as SPAKE2 without public key validation. We analysed the protocol and it took us a while to conclude that it is insecure without public key validation (despite the security proofs in the paper) [2]. We contacted authors of [1] and they kindly acknowledged the attack and also confirmed that public key validation needed to be added in their protocol. The attack can be traced to a subtle deficiency in their theoretical model which implicitly assumes that a server is trusted when it communicates with a client. This assumption is clearly invalid, but it is implicit in the model/proofs and it took 5 years for peer researchers to identify it!

 * At the moment, I don't see an obvious attack due to the missing public key validation in the SPAKE2 specification (as in the original paper), but it's a potential issue that needs some attention.

Cheers,
Feng

[1] D. Pointcheval and S. Zimmer, "Multi-Factor Authenticated Key Exchange," Proceedings of Applied Cryptography and Network Security (ACNS¹08), pp. 277-295, LNCS 5037, 2008.

[2] Security Analysis of a Multi-Factor Authenticated Key Exchange Protocol  https://eprint.iacr.org/2012/039.pdf

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 16 Nov 2016 22:12:34 +0900

Dear colleagues,

I don't quite understand, why ‎an alternative construction could be a problem, if it's security properties are explicitly stated and well-proven, and if it's description is clear and is not underspecified. 

I totally understand with Watson, that J-PAKE is slower than alternatives - but the performance issues are not secret for the developers who may want to choose it - so why should we harass it?

My opinion is when we have such a new area as PAKEs, diversity of constructions can be a good thing - in case all standardized constructions are proven and if their properties are clearly defined in the documents. 

So wouldn't it be a wise step to help the document become as clear as it can be (if Watson sees some problems in the current version)?

Best regards,
Stanislav Smyshlyaev
‎
  Исходное сообщение  
От: Feng Hao
Отправлено: среда, 16 ноября 2016 г., 19:26
Кому: Watson Ladd
Копия: [email-masked]
Тема: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

Hi Watson,

Cheers,
Feng

---

From: Michel Abdalla <[email-masked]>
Date: Wed, 16 Nov 2016 16:08:23 +0100

Dear Feng,

Since you’ve raised some questions about SPAKE2, I just wanted to clarify some of these issues below.

Regards,
Michel

> On Nov 16, 2016, at 11:25 AM, Feng Hao <[email-masked]> wrote:
> 
> Hi Watson,
> 

Since the security proof only requires that M and N are two random elements whose discrete logs with respect to g are unknown, the proof would go through even if M and N were chosen as the output of a random oracle on some fixed inputs, say M=H(0) and N=H(1), where H hashes into the the appropriate group.

> * Kindly note that if you can manage to convince IETF users that M and N are completely random, one might just plug M and N as the input of two random points to DUAL_EC and make it work?

The security of SPAKE2 requires that the discrete logs of M and N with respect to g should remain unknown to everybody so the generation of M and N has to enforce this aspect.

> * I think SPAKE2 is underspecified in the original paper. It doesn't state the requirements for M and N, but it should be clear that they must be completely random. Also, it doesn't state if the di…

If one knows the discrete log of M with respect to g (let’s call this value m), then one can perform an offline dictionary attack on SPAKE2 as follows. The adversary impersonates User A and sends a random element X'=g^x' to User B. After receiving Y* from User B, the adversary requests the session key associated with this session through a reveal query. Let SK be this session key.  Now guess pw and compute offline Y = Y* / N^pw, K_A = Y^{x’ - pw m}, and SK_A = H(A,B,X’,Y*,K_A).  Note that SK_A will match SK when pw is the correct pw.
 
> * I'm a bit worried that in the actual protocol specification in the original paper, there is no step to perform public key validation. This could be due to two reasons: 1) an inadvertent omission…

Our proof implicitly assumes membership tests for all the elements being exchanged. Hence, the actual explanation for the under specification is an inadvertent omission on our part.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Nov 2016 07:17:43 -0800

>  * It's not a fair comparison as the setup assumptions are different. SPAKE2 requires a trusted setup, while J-PAKE doesn't. Instead, you should compare SPAKE2 with KOY, Jiang-Gong and GL protocols…

Different setup assumptions do not make it impossible to compare
different protocols.

> it doesn't affect the original proofs in the SPAKE2 paper in any way. Then people can check and verify your proofs instead of having to take your word for it. I see you are always rigorous in askin…

This a) cannot be done with standard foundations and b) is a trivial
exercise with any kind of ideal hash/ROM model. I'll sit down and do
it, but while drafting this email someone went and did it.

> SPAKE2 is in the same model. It's appropriate you compare these protocols and definitions. This is necessary especially since you're doing something not specified in the original SPAKE2 paper and o…

Except I'm not interested in writing a review paper. I'm interested in
looking at all the proposals before us for PAKE, and determining which
should be promoted.

>  * Kindly note that if you can manage to convince IETF users that M and N are completely random, one might just plug M and N as the input of two random points to DUAL_EC and make it work?

Are you aware that DUAL_EC included a point generation mechanism that,
if used, would have completely avoided the backdoor? Do you think that
the hashing argument presented downthread is wrong.
>  * What you say about the 4 exponentiations in the subgroup is correct (consistent with the original paper), but this hasn't included the validation of the public key (which is free in EC but takes…

The next part of my email did describe the validation costs: 1
exponentiation per element to be validated. That is not a full
exponentation: if the subgroup is the unique subgroup of order q in
the finite field, we need only check x^q=1. I said the validation
doubled the cost of SPAKE2: this is not exactly right, as only one
point needs to be validated.

>  * I'm a bit worried that in the actual protocol specification in the original paper, there is no step to perform public key validation. This could be due to two reasons: 1) an inadvertent omission…

The draft completely specifies an equivalent protection. This is the
reason we use the cofactor. I believe I explicitly required on-curve
checks, but will make it more clear if you don't think so.

---

From: Feng Hao <[email-masked]>
Date: Wed, 16 Nov 2016 15:33:23 +0000

Dear Michel,

Thanks for the clarifications, which address the raised points pertinently. 

One small question: "M=H(0) and N=H(1), where H hashes into the appropriate group"

Can you give more details on the realization of H?

Cheers,
Feng

>From: Michel Abdalla [mailto:[email-masked]]
>Sent: 16 November 2016 15:08
>Cc: Watson Ladd <[email-masked]>; [email-masked]
>> * It's not a fair comparison as the setup assumptions are different. SPAKE2
>requires a trusted setup, while J-PAKE doesn't. Instead, you should compare
>SPAKE2 with KOY, Jiang-Gong and GL protocols as they require the same
>trusted setup. J-PAKE should be compared with EKE, SPEKE and Dragonfly
>(which is based on SPEKE).
>>
>> * When you say "SPAKE2 with M and N generated by hashing is secure,
>> and the proofs found in the SPAKE2 paper do work", it's best that you
>write up the full details how you do the hashing, proofs that why it's secure
>and why it doesn't affect the original proofs in the SPAKE2 paper in any way.
>Then people can check and verify your proofs instead of having to take your
>word for it. I see you are always rigorous in asking "security proofs" from
>others for everything they do (which is good), so you should consider
>applying the same rigor to yourself.
>>
>
>Since the security proof only requires that M and N are two random
>elements whose discrete logs with respect to g are unknown, the proof
>would go through even if M and N were chosen as the output of a random
>oracle on some fixed inputs, say M=H(0) and N=H(1), where H hashes into
>the the appropriate group.
>
>> * The KOY, Jiang-Gong and GL papers are relevant as they are the same
>type of CRS-based designs as SPAKE2. These papers state that the setup
>needs to be done by a trusted party and they don't specify using a hash.
>> SPAKE2 is in the same model. It's appropriate you compare these protocols
>and definitions. This is necessary especially since you're doing something not
>specified in the original SPAKE2 paper and other related peer-reviewed
>papers.
>>
>> * You will need to convince IETF users that there is no possibility of
>> trapdoor for M and N (which may prove a bit tricky). Knowledge (or partial
>knowledge) of the relation between M and N may allow one to
>> * Kindly note that if you can manage to convince IETF users that M and N
>are completely random, one might just plug M and N as the input of two
>random points to DUAL_EC and make it work?
>>
>
>The security of SPAKE2 requires that the discrete logs of M and N with
>respect to g should remain unknown to everybody so the generation of M
>and N has to enforce this aspect.
>
>> * What you say about the 4 exponentiations in the subgroup is correct
>(consistent with the original paper), but this hasn't included the validation
>of the public key (which is free in EC but takes one full exponentiation in the
>finite field setting). See my further comment below.
>>
>> * I think SPAKE2 is underspecified in the original paper. It doesn't state the
>requirements for M and N, but it should be clear that they must be
>completely random. Also, it doesn't state if the discrete logarithm between
>M and g (and symmetrically between M and g) must be unknown. It's not
>immediately clear to me if knowledge of the discrete logarithm for M and g
>will break anything, but all these should have been explicitly specified in the
>paper.
>
>If one knows the discrete log of M with respect to g (let’s call this value m),
>then one can perform an offline dictionary attack on SPAKE2 as follows. The
>adversary impersonates User A and sends a random element X'=g^x' to User
>B. After receiving Y* from User B, the adversary requests the session key
>associated with this session through a reveal query. Let SK be this session
>key.  Now guess pw and compute offline Y = Y* / N^pw, K_A = Y^{x’ - pw m},
>and SK_A = H(A,B,X’,Y*,K_A).  Note that SK_A will match SK when pw is the
>correct pw.
>
>>
>> * I'm a bit worried that in the actual protocol specification in the original
>paper, there is no step to perform public key validation. This could be due to
>two reasons: 1) an inadvertent omission by the authors; 2) an intentional
>design choice. In case of ambiguity like this, one normally takes it as the
>latter. The reason is simple: if public key validation is considered essential, it
>MUST be clearly specified, which is the case with most key agreement
>protocols. However, from early 2000s, some researchers called for
>abandoning the public key validation, as long as the protocol has formal
>security proofs (HMQV is one notable example, but it backfired in the end).
>
>Our proof implicitly assumes membership tests for all the elements being
>exchanged. Hence, the actual explanation for the under specification is an
>inadvertent omission on our part.
>>
>>
>> * The above observation reminds me of a paper " Multi-Factor
>Authenticated Key Exchange" by Poincheval and Zimmer in 2008 [1] where
>the protocol is specified in a similar manner as SPAKE2 without public key
>validation. We analysed the protocol and it took us a while to conclude that
>it is insecure without public key validation (despite the security proofs in the
>paper) [2]. We contacted authors of [1] and they kindly acknowledged the
>attack and also confirmed that public key validation needed to be added in
>their protocol. The attack can be traced to a subtle deficiency in their
>theoretical model which implicitly assumes that a server is trusted when it
>communicates with a client. This assumption is clearly invalid, but it is
>implicit in the model/proofs and it took 5 years for peer researchers to
>identify it!
>>
>> * At the moment, I don't see an obvious attack due to the missing public
>key validation in the SPAKE2 specification (as in the original paper), but it's a
>potential issue that needs some attention.
>>
>> Cheers,
>> Feng
>>
>> [1] D. Pointcheval and S. Zimmer, "Multi-Factor Authenticated Key
>Exchange," Proceedings of Applied Cryptography and Network Security
>(ACNS¹08), pp. 277-295, LNCS 5037, 2008.
>>
>> [2] Security Analysis of a Multi-Factor Authenticated Key Exchange
>> Protocol  https://eprint.iacr.org/2012/039.pdf
>>

---

From: Feng Hao <[email-masked]>
Date: Wed, 16 Nov 2016 15:49:50 +0000

Hi Watson,

>Sent: 16 November 2016 15:18
>Different setup assumptions do not make it impossible to compare different
>protocols.

OK. I said "fair", not "impossible".

>This a) cannot be done with standard foundations and b) is a trivial exercise
>with any kind of ideal hash/ROM model. I'll sit down and do it, but while
>drafting this email someone went and did it.

Cool. Btw, nothing is really "trivial" in the design of a protocol. Any small change may have profound effects. This is why I suggest you to write it down in full detail, and ideally get it in a peer-reviewed publication if that's possible so there is a fixed version of the spec as the basis for technical discussion.

>Except I'm not interested in writing a review paper. I'm interested in looking
>at all the proposals before us for PAKE, and determining which should be
>promoted.
>>
>>  * You will need to convince IETF users that there is no possibility
>> of trapdoor for M and N (which may prove a bit tricky). Knowledge (or
>partial knowledge) of the relation between M and N may allow one to
>Are you aware that DUAL_EC included a point generation mechanism that, if
>used, would have completely avoided the backdoor? Do you think that the
>hashing argument presented downthread is wrong.

If that works completely, why not reuse it instead of inventing your own?

>exponentation: if the subgroup is the unique subgroup of order q in the
>finite field, we need only check x^q=1. I said the validation doubled the cost
>of SPAKE2: this is not exactly right, as only one point needs to be validated.

OK. Michel just clarified.

>>  * I think SPAKE2 is underspecified in the original paper. It doesn't state
>the requirements for M and N, but it should be clear that they must be
>The draft completely specifies an equivalent protection. This is the reason
>we use the cofactor. I believe I explicitly required on-curve checks, but will
>make it more clear if you don't think so.
>
>>

---

From: Michel Abdalla <[email-masked]>
Date: Wed, 16 Nov 2016 17:23:08 +0100

Dear Feng,

It seems to me that Watson already proposes one such method in his specification of SPAKE2.

Other methods of realizing H can be found in the literature, such as in the instantiation of the Boneh-Franklin IBE scheme and the Boneh-Lynn-Shacham signature scheme. 

Regards,
Michel

> On Nov 16, 2016, at 4:33 PM, Feng Hao <[email-masked]> wrote:
> 
> Dear Michel,
>

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 15 Nov 2016 09:18:53 -0800

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 <[email-masked]> wrote:
> 
> Hi Mike,
> 

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 cons…

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.

> Feng

Cheers,
-- Mike

---

From: Feng Hao <[email-masked]>
Date: Tue, 15 Nov 2016 18:04:57 +0000

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:[email-masked]]
Sent: 15 November 2016 17:19
To: Feng Hao <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

Hi Feng,

On Nov 15, 2016, at 02:55, Feng Hao <[email-masked]<mailto:[email-masked]>> wrote:
Hi Mike,

Cheers,
Feng

Cheers,
-- Mike

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

Let x := -A / (1+u*h^2).

— Mike

On Nov 14, 2016, at 2:56 PM, Feng Hao <[email-masked]<mailto:[email-masked]>> wrote:

Hi Watson,

Regards,
Feng

On 14/11/2016 15:14, "Watson Ladd" <[email-masked]<mailto:[email-masked]>> wrote:

On Mon, Nov 14, 2016 at 3:53 AM, Feng Hao <[email-masked]<mailto:[email-masked]>>
wrote:
Hi,

As per the reviewers' comments, I've revised the drafts to clarify a
few points.

Schnorr draft

J-PAKE draft

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

Cheers,
Feng

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg