MIME-Version: 1.0
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>
From: Watson Ladd <watsonbladd@gmail.com>
Date: Wed, 16 Nov 2016 07:17:43 -0800
Message-ID: <CACsn0cnde6E8XAcebRh0kbxcdZUBRo2W6Yx5W+dMVs99PhPraw@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/gBvwaArscnMF4HT2bYYP2S1BEWo>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
Precedence: list

On Wed, Nov 16, 2016 at 2:25 AM, Feng Hao <feng.hao@newcastle.ac.uk> wrote:
> 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. SPA=
KE2 requires a trusted setup, while J-PAKE doesn't. Instead, you should com=
pare 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 (whi=
ch is based on SPEKE).

Different setup assumptions do not make it impossible to compare
different protocols.

>
>  * 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 wh=
y
> it doesn't affect the original proofs in the SPAKE2 paper in any way. The=
n people can check and verify your proofs instead of having to take your wo=
rd for it. I see you are always rigorous in asking "security proofs" from o=
thers for everything they do (which is good), so you should consider applyi=
ng the same rigor to yourself.

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.

>
>  * The KOY, Jiang-Gong and GL papers are relevant as they are the same ty=
pe 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.

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 t=
rapdoor for M and N (which may prove a bit tricky). Knowledge (or partial k=
nowledge) 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 ran=
dom 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 (c=
onsistent 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 i=
n the finite field setting). See my further comment below.

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=3D1. I said the validation
doubled the cost of SPAKE2: this is not exactly right, as only one
point needs to be validated.

>
> I read again the original SPAKE2 paper as well as your I-D. I have the fo=
llowing comments
>
>  * I think SPAKE2 is underspecified in the original paper. It doesn't sta=
te the requirements for M and N, but it should be clear that they must be c=
ompletely 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 immed=
iately 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 ori=
ginal 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 int=
entional design choice. In case of ambiguity like this, one normally takes =
it as the latter. The reason is simple: if public key validation is conside=
red essential, it MUST be clearly specified, which is the case with most ke=
y agreement protocols. However, from early 2000s, some researchers called f=
or 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 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.

>
>  * The above observation reminds me of a paper " Multi-Factor Authenticat=
ed 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 insecur=
e without public key validation (despite the security proofs in the paper) =
[2]. We contacted authors of [1] and they kindly acknowledged the attack an=
d also confirmed that public key validation needed to be added in their pro=
tocol. The attack can be traced to a subtle deficiency in their theoretical=
 model which implicitly assumes that a server is trusted when it communicat=
es 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 Exchang=
e," 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 Protoc=
ol  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
>



--=20
"Man is born free, but everywhere he is in chains".
--Rousseau.