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

Feng Hao <feng.hao@newcastle.ac.uk> Wed, 16 November 2016 15:34 UTC

Return-Path: <feng.hao@newcastle.ac.uk>
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 ABCE11296D6 for <cfrg@ietfa.amsl.com>; Wed, 16 Nov 2016 07:34:05 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.222
X-Spam-Level:
X-Spam-Status: No, score=-4.222 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=newcastle.onmicrosoft.com
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 JHp1VV7tMk7S for <cfrg@ietfa.amsl.com>; Wed, 16 Nov 2016 07:34:02 -0800 (PST)
Received: from cheviot12.ncl.ac.uk (cheviot12.ncl.ac.uk [128.240.234.12]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CF7B61294B7 for <cfrg@irtf.org>; Wed, 16 Nov 2016 07:33:59 -0800 (PST)
Received: from exhubvm02.ncl.ac.uk ([128.240.234.9] helo=EXHUBVM02.campus.ncl.ac.uk) by cheviot12.ncl.ac.uk with esmtp (Exim 4.63) (envelope-from <feng.hao@newcastle.ac.uk>) id 1c72Dl-0002mz-Cj; Wed, 16 Nov 2016 15:33:58 +0000
Received: from EUR01-DB5-obe.outbound.protection.outlook.com (213.199.154.182) by exhub.ncl.ac.uk (128.240.234.9) with Microsoft SMTP Server (TLS) id 14.3.266.1; Wed, 16 Nov 2016 15:33:25 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=newcastle.onmicrosoft.com; s=selector1-newcastle-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=PLj/3YJvfOZjDJFQjGl53zMBjMHCBJ4pMsRHmPX0zgU=; b=AGFY6+U2sgSDKFGpshe4axidL92I8BL1Cn4CY7L5C7D4Dy4p1ergJNMlUai1FrS5v+CThwAvX6zeemBQNmP9LBBvzmgp+WvtjKOfDus5kHSeTiR9bgyxgUfmV/6YBCxlVw6QkxhAhA4zrkl1WK++Nidihhy6nTb+W33i+1NWgt8=
Received: from DB5PR0701MB1928.eurprd07.prod.outlook.com (10.167.228.24) by DB5PR0701MB1925.eurprd07.prod.outlook.com (10.167.228.21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.2; Wed, 16 Nov 2016 15:33:23 +0000
Received: from DB5PR0701MB1928.eurprd07.prod.outlook.com ([10.167.228.24]) by DB5PR0701MB1928.eurprd07.prod.outlook.com ([10.167.228.24]) with mapi id 15.01.0734.004; Wed, 16 Nov 2016 15:33:23 +0000
From: Feng Hao <feng.hao@newcastle.ac.uk>
To: Michel Abdalla <michel.abdalla@ens.fr>
Thread-Topic: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
Thread-Index: AdI+bZzQZch4zeUeTNyFcWq6Y0INHQAHCdeAABAiwAAAEcC1gAAJS7QwAAdP5YAAAaRZ8AAGjxQAAAzy6gAAHLsQgAAAx7ow
Date: Wed, 16 Nov 2016 15:33:23 +0000
Message-ID: <DB5PR0701MB1928850E56E7BB9863FFE0CAD4BE0@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> <1E393A35-FEF3-4205-B91B-D3DC2DE918A1@ens.fr>
In-Reply-To: <1E393A35-FEF3-4205-B91B-D3DC2DE918A1@ens.fr>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=feng.hao@newcastle.ac.uk;
x-originating-ip: [128.240.225.103]
x-microsoft-exchange-diagnostics: 1; DB5PR0701MB1925; 7:KA51ttyCpPODb4Cj44yoyeBKKakdz4nkzJuN5uNUDODhnNL1zJ9UJT2yvqaCQFJn6oJliN6Gs20y+m1DEhYJ5vRFDDfjo1kSOPNp3bk+LW5apSZ7eb3Y/0uS3NBsTHb0sxFzKDuusttsjXWPIgVFu8APJp/0OJd/T4q/R2b65DzAiZs8Or3SsGgW5QeZSEzc+W3WihoZqfcET3gxgF7rpSYt9ZhNsSnrCN/SaPXEz4ZXCiWkRFA7rSwbFmIruk3pC5Ric4l30e5Dzj4PJS8e7j07CRRQgiZx768KnpX6Q3BT15eBdhVEp2Ey/9AmPdgWDcsn0anmJSXHH5X9x0A6BaAaFii+ypc2zbgk/O5CmTE=
x-ms-office365-filtering-correlation-id: cdce3bf6-a48d-4e85-1faf-08d40e35e6f6
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001); SRVR:DB5PR0701MB1925;
x-microsoft-antispam-prvs: <DB5PR0701MB192520F88D81122A5B67AF75D4BE0@DB5PR0701MB1925.eurprd07.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(158342451672863)(192374486261705)(131327999870524)(266576461109395);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6060326)(6040281)(601004)(2401047)(8121501046)(5005006)(3002001)(10201501046)(6041223)(6061324); SRVR:DB5PR0701MB1925; BCL:0; PCL:0; RULEID:; SRVR:DB5PR0701MB1925;
x-forefront-prvs: 01283822F8
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(7916002)(51694002)(51914003)(377454003)(13464003)(189002)(199003)(24454002)(122556002)(66066001)(3660700001)(2906002)(76576001)(105586002)(68736007)(76176999)(54356999)(4326007)(305945005)(7736002)(74316002)(86362001)(6506003)(50986999)(3280700002)(33656002)(8676002)(102836003)(7846002)(3846002)(6116002)(101416001)(106356001)(93886004)(77096005)(97736004)(92566002)(189998001)(2900100001)(2950100002)(9686002)(6916009)(87936001)(8936002)(81166006)(74482002)(42882006)(110136003)(229853002)(81156014)(7696004)(5660300001); DIR:OUT; SFP:1101; SCL:1; SRVR:DB5PR0701MB1925; H:DB5PR0701MB1928.eurprd07.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
received-spf: None (protection.outlook.com: newcastle.ac.uk does not designate permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 16 Nov 2016 15:33:23.4505 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 9c5012c9-b616-44c2-a917-66814fbe3e87
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB5PR0701MB1925
X-OriginatorOrg: newcastle.ac.uk
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/34LAmJ8CjSa7knYEqaeCQxhrrzg>
Cc: "cfrg@irtf.org" <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 <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 16 Nov 2016 15:34:05 -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

>-----Original Message-----
>From: Michel Abdalla [mailto:michel.abdalla@ens.fr]
>Sent: 16 November 2016 15:08
>To: Feng Hao <feng.hao@newcastle.ac.uk>
>Cc: Watson Ladd <watsonbladd@gmail.com>om>; cfrg@irtf.org
>Subject: Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs
>
>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 <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. 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
>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?
>>
>
>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 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.
>
>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
>>
>> 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