MIME-Version: 1.0
In-Reply-To: <DB5PR0701MB192893EEFB5B57A72B70984ED4BF0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
References: <DB5PR0701MB19282BB2E03816405AF5DF91D4BC0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
 <CACsn0ck4uFHrKzX9EDGSADjv1BkpnGPA3v4ncR8R9dkTn5DWgg@mail.gmail.com>
 <D44FD9E6.186BF%feng.hao@newcastle.ac.uk>
 <CACsn0cngxnRjVPBDcC9HuNxbJV-VD1UPHOryWSjKBkf5+Mnz1w@mail.gmail.com>
 <DB5PR0701MB192893EEFB5B57A72B70984ED4BF0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
From: Watson Ladd <watsonbladd@gmail.com>
Date: Tue, 15 Nov 2016 07:20:09 -0800
Message-ID: <CACsn0ckQMFdLhFP_AhTaQPAmKpb8ZdxHBDGRRxvx8cEHC+vh7A@mail.gmail.com>
To: Feng Hao <feng.hao@newcastle.ac.uk>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/S447QEPIXHVXSEU9qtvziaKJM4c>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
Precedence: list

On Tue, Nov 15, 2016 at 4:05 AM, Feng Hao <feng.hao@newcastle.ac.uk> wrote:
> Hi Watson,
>
> From: Watson Ladd [mailto:watsonbladd@gmail.com]
> Sent: 15 November 2016 07:25
> To: Feng Hao <feng.hao@newcastle.ac.uk>
> Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
>
> On Nov 14, 2016 2:56 PM, "Feng Hao" <feng.hao@newcastle.ac.uk> 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 conside=
red
>>> the simplest and the most efficient balanced PAKEs. It is shown that th=
e
>>> computational efficiency of J-PAKE is about the same as EKE and SPEKE i=
n
>>> 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 poin=
t
>>> 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 pape=
rs
>>> in the literature that merely count the number of exponentiations as th=
e
>>> computational cost without considering the specific group settings
>>> required by the protocol (e.g., if the protocol accommodates short or l=
ong
>>> 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 l=
ost all the performance already.
>
> What do you mean by =E2=80=9Clost all the performance=E2=80=9D? Can you e=
laborate?

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=3D2q+1 ensures that a Jacobi symbol computation completely
protects people.

>
>> Furthermore, your section 2.2 of 1 is not a full discussion: an actual a=
nalysis of the exponentiations done by each party and the size of the value=
s they use would have been a good idea to include to model the cost in term=
s of group additions.
>
> Sorry, I don=E2=80=99t understand this. The analysis in the paper uses on=
e 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 expone=
ntiation in SPEKE (and EKE) is 6-7 times more expensive than one exponentia=
tions in J-PAKE.  It=E2=80=99s trivial to generalize that for other bit-len=
gth modulus (the cost difference is 2047/224 =3D 9 times for 2048-bit modul=
us).

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 set=
up
>>> to define the randomness in the group setting: in particular, to define=
 a
>>> pair of generators whose discrete logarithm must be unknown. SPAKE2 (wh=
ich
>>> I understand you=C2=B9re 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 com=
mon
>>> reference model if you=C2=B9re a fan of jargon) is a tricky task. The m=
ost
>>> concrete advice in terms of implementation that you may find is probabl=
y
>>> from Gennaro and Lindell [4]: =C2=B3An example of where it is reasonabl=
e to
>>> assume a common reference string is when a large organization wishes to
>>> implement secure login for its employees. In this case, the organizatio=
n
>>> is trusted to choose the common reference string properly, and this str=
ing
>>> can then be hardwired into the software code.=C2=B2 As an example we ca=
n have
>>> Google to define a trusted setup, which will be trusted by its employee=
s.
>>> 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 onl=
y of interest to theoreticians. I don=E2=80=99t think it=E2=80=99s an appro=
priate 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 S=
PAKE2 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: wil=
l do sometime.
>
> This is not specified in the original SPAKE2 paper. And this is not speci=
fied 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 ne=
ed to produce a proof to show it doesn=E2=80=99t contradict the original pr=
oofs.

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=C2=B9m not objecting PAKE protocols that rely on a common r=
eference
>>> string; they are one category of PAKE designs and are useful in
>>> specifically identified scenarios. I=C2=B9m merely highlighting that th=
ere are
>>> diversified PAKE designs with different assumptions and properties. Hav=
ing
>>> the diversity is a good thing in the research field. However, disparagi=
ng
>>> some without noting the weaknesses/merits of others in the context of t=
hat
>>> diversity is not fair.
>
>>The great thing about standards is there are so many to pick from. This h=
as doomed PAKEs forever.
>
> Again, I don=E2=80=99t understand. What=E2=80=99s 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 advantag=
es JPAKE provides, although its symmetry is occasionally useful for some pr=
otocols.
>
> By 1 round, 2 exponentiations, you mean SPEKE? Did you read Sec 2.2 befor=
e you respond to this? If you have any specific technical questions, doubts=
 or disagreement, I'm happy to discuss. However, criticisms that are too ge=
neral 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, =C2=B3Efficient password-authentica=
ted key
>>> exchange using human-memorable passwords=C2=B2, Advances in Cryptology,=
 LNCS
>>> 2045, pp. 475-494, 2001.
>>>
>>> [3] S.Q. Jiang, G. Gong, =C2=B3Password based key exchange with mutual
>>> authentication,=C2=B2 Selected Area in Cryptography, LNCS 3357, pp. 267=
-279,
>>> 2004
>>>
>>> [4] R. Gennaro, Y. Lindell, =C2=B3A framework for password-based authen=
ticated
>>> key exchange,=C2=B2 Eurucrypt=C2=B903, LNCS, No. 2656, pp. 524-543, 200=
3.
>>>
>>>
>>> On 14/11/2016 15:14, "Watson Ladd" <watsonbladd@gmail.com> 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 <feng.hao@newcastle.ac.uk>
>>> >wrote:
>>> >> Hi,
>>> >>
>>> >> Recently I submitted J-PAKE and Schnorr NIZK to IETF for "informatio=
nal
>>> >>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 al=
so
>>> >>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 th=
at
>>> >>explicit key confirmation is recommended in a practical implementatio=
n
>>> >>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=3Ddraft-hao-schnor=
r-05
>>> >>
>>> >> Name:           draft-hao-jpake
>>> >> Revision:       05
>>> >> Title:          J-PAKE: Password Authenticated Key Exchange by Juggl=
ing
>>> >> 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=3Ddraft-hao-jpake-=
05
>>> >>
>>> >> Your comments are most welcome!
>>> >>
>>> >> Cheers,
>>> >> Feng
>>> >>
>>> >> _______________________________________________
>>> >> Cfrg mailing list
>>> >> Cfrg@irtf.org
>>> >> https://www.irtf.org/mailman/listinfo/cfrg
>>> >
>>> >
>>> >
>>> >--
>>> >"Man is born free, but everywhere he is in chains".
>>> >--Rousseau.
>>>



--=20
"Man is born free, but everywhere he is in chains".
--Rousseau.