Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Message-ID: <20161116131234.5943378.4618.9736@gmail.com>
Date: Wed, 16 Nov 2016 22:12:34 +0900
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
In-Reply-To: <DB5PR0701MB1928AEBDA2833976F543C1EAD4BE0@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>
 <CACsn0ckQMFdLhFP_AhTaQPAmKpb8ZdxHBDGRRxvx8cEHC+vh7A@mail.gmail.com>
 <DB5PR0701MB192892E1DAF20517AE2D032CD4BF0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
 <CACsn0c=2OHcGtb3AADZoZt4FpVr76_1O70Cf9rM3E1DWnaK-ng@mail.gmail.com>
 <DB5PR0701MB1928AEBDA2833976F543C1EAD4BE0@DB5PR0701MB1928.eurprd07.prod.outlook.com>
To: Feng Hao <feng.hao@newcastle.ac.uk>, Watson Ladd <watsonbladd@gmail.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/MwsxdMxSfsCYN6NUGof2VgUMZjY>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
Precedence: list

Dear colleagues,

I don't quite understand, why =E2=80=8Ean alternative construction could be=
 a problem, if it's security properties are explicitly stated and well-prov=
en, and if it's description is clear and is not underspecified.=C2=A0

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 construct=
ions can be a good thing - in case all standardized constructions are prove=
n and if their properties are clearly defined in the documents.=C2=A0

So wouldn't it be a wise step to help the document become as clear as it ca=
n be (if Watson sees some problems in the current version)?

Best regards,
Stanislav Smyshlyaev
=E2=80=8E
=C2=A0 =D0=98=D1=81=D1=85=D0=BE=D0=B4=D0=BD=D0=BE=D0=B5 =D1=81=D0=BE=D0=BE=
=D0=B1=D1=89=D0=B5=D0=BD=D0=B8=D0=B5 =C2=A0
=D0=9E=D1=82: Feng Hao
=D0=9E=D1=82=D0=BF=D1=80=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=BE: =D1=81=D1=80=
=D0=B5=D0=B4=D0=B0, 16 =D0=BD=D0=BE=D1=8F=D0=B1=D1=80=D1=8F 2016=C2=A0=D0=
=B3., 19:26
=D0=9A=D0=BE=D0=BC=D1=83: Watson Ladd
=D0=9A=D0=BE=D0=BF=D0=B8=D1=8F: cfrg@irtf.org
=D0=A2=D0=B5=D0=BC=D0=B0: Re: [Cfrg] J-PAKE and Schnorr NIZK for informatio=
nal RFCs

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 compar=
e SPAKE2 with KOY, Jiang-Gong and GL protocols as they require the same tru=
sted 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 oth=
ers 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 a=
nd definitions. This is necessary especially since you're doing something n=
ot specified in the original SPAKE2 paper and other related peer-reviewed p=
apers.

* You will need to convince IETF users that there is no possibility of trap=
door for M and N (which may prove a bit tricky). Knowledge (or partial know=
ledge) of the relation between M and N may allow one to
systematically break all instances of the protocol execution.=20

* Kindly note that if you can manage to convince IETF users that M and N ar=
e 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 (cons=
istent 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 t=
he finite field setting). See my further comment below.

I read again the original SPAKE2 paper as well as your I-D. I have the foll=
owing 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 comp=
letely random. Also, it doesn't state if the discrete logarithm between M a=
nd g (and symmetrically between M and g) must be unknown. It's not immediat=
ely clear to me if knowledge of the discrete logarithm for M and g will bre=
ak anything, but all these should have been explicitly specified in the pap=
er.

* I'm a bit worried that in the actual protocol specification in the origin=
al 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 intent=
ional 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 a=
greement protocols. However, from early 2000s, some researchers called for =
abandoning the public key validation, as long as the protocol has formal se=
curity 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 sp=
ecified in a similar manner as SPAKE2 without public key validation. We ana=
lysed the protocol and it took us a while to conclude that it is insecure w=
ithout public key validation (despite the security proofs in the paper) [2]=
. We contacted authors of [1] and they kindly acknowledged the attack and a=
lso confirmed that public key validation needed to be added in their protoc=
ol. The attack can be traced to a subtle deficiency in their theoretical mo=
del which implicitly assumes that a server is trusted when it communicates =
with a client. This assumption is clearly invalid, but it is implicit in th=
e 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 ke=
y 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=C2=B908), =
pp. 277-295, LNCS 5037, 2008.

[2] Security Analysis of a Multi-Factor Authenticated Key Exchange Protocol=
 https://eprint.iacr.org/2012/039.pdf

On 15/11/2016 19:14, "Watson Ladd" <watsonbladd@gmail.com> wrote:

>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

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg