Return-Path:
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id C7D0912940C
for ; Wed, 16 Nov 2016 07:08:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.698
X-Spam-Level:
X-Spam-Status: No, score=-5.698 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-1.497,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id LpWWAVsX-euL for ;
Wed, 16 Nov 2016 07:08:31 -0800 (PST)
Received: from nef2.ens.fr (nef2.ens.fr [129.199.96.40])
by ietfa.amsl.com (Postfix) with ESMTP id 4265A129522
for ; Wed, 16 Nov 2016 07:08:30 -0800 (PST)
Received: from di.ens.fr (di.ens.fr [129.199.99.1])
by nef2.ens.fr (8.13.6/1.01.28121999) with ESMTP id uAGF8Ouq047206
; Wed, 16 Nov 2016 16:08:24 +0100 (CET)
Received: from dhcp205.dmi.ens.fr (dhcp205.dmi.ens.fr [129.199.97.205])
(authenticated bits=0) by di.ens.fr (8.14.4/jb-1.1)
id uAGF8Nj0027084 ; Wed, 16 Nov 2016 16:08:23 +0100
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 10.1 \(3251\))
From: Michel Abdalla
In-Reply-To:
Date: Wed, 16 Nov 2016 16:08:23 +0100
Content-Transfer-Encoding: quoted-printable
Message-Id: <1E393A35-FEF3-4205-B91B-D3DC2DE918A1@ens.fr>
References:
To: Feng Hao
X-Mailer: Apple Mail (2.3251)
X-Virus-Scanned: by amavisd-milter (http://amavis.org/)
X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.4.3
(nef2.ens.fr [129.199.96.32]); Wed, 16 Nov 2016 16:08:24 +0100 (CET)
Archived-At:
Cc: "cfrg@irtf.org"
Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Wed, 16 Nov 2016 15:08:35 -0000
Dear Feng,
Since you=E2=80=99ve 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 =
wrote:
>=20
> Hi Watson,
>=20
> On your comments about comparing costs between SPAKE2 and J-PAKE
>=20
> * 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).
>=20
> * 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.
>=20
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=3DH(0) and N=3DH(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.
>=20
> * 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.=20
>=20
> * 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?
>=20
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.
>=20
> I read again the original SPAKE2 paper as well as your I-D. I have the =
following comments
>=20
> * 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=E2=80=99s 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'=3Dg^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 =3D Y* / N^pw, K_A =3D Y^{x=E2=80=99 - pw m}, and SK_A =3D =
H(A,B,X=E2=80=99,Y*,K_A). Note that SK_A will match SK when pw is the =
correct pw.
=20
>=20
> * 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.=20
>=20
>=20
> * 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!
>=20
> * 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.
>=20
> Cheers,
> Feng
>=20
> [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.
>=20
> [2] Security Analysis of a Multi-Factor Authenticated Key Exchange =
Protocol https://eprint.iacr.org/2012/039.pdf
>=20
> On 15/11/2016 19:14, "Watson Ladd" wrote:
>=20
>> Dear Feng,
>>=20
>> 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.
>>=20
>> 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.
>>=20
>> Do you have anything to say to this?
>>=20
>> Sincerely,
>> Watson
>=20
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg