Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Sun, 08 September 2019 16:13 UTC

Return-Path: <Feng.Hao@warwick.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 E0E2C12003F for <cfrg@ietfa.amsl.com>; Sun, 8 Sep 2019 09:13:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0
X-Spam-Level:
X-Spam-Status: No, score=0 tagged_above=-999 required=5 tests=[HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 Tv84lYu-toJe for <cfrg@ietfa.amsl.com>; Sun, 8 Sep 2019 09:13:26 -0700 (PDT)
Received: from EUR03-AM5-obe.outbound.protection.outlook.com (mail-eopbgr30044.outbound.protection.outlook.com [40.107.3.44]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 069F7120018 for <cfrg@ietf.org>; Sun, 8 Sep 2019 09:13:25 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=YZZxXSee4wN7Pi8RGQi/P319OCe1KprQlQ2L7rlLxZJEgRnD5z2BBBAhj2hQhq0nmaosfNnJLD4x8Mzpm08FCQVOExSEX04lrwLgKOtC9p7HFBWWerG7RPAUrNRP8Mnpb+4doBqGlZhNMqsUsihO/R1tDRieB+1NA85U5EnKCzyAvgg4O0Esf4rzckXI0jktMK322a8OScJN+s8Yt4X/mrErWripnwL250ZwD8xuMlNWM1bX4w1EXTpnsKtwS6YFlyNV49YNhwzSQBp+VmvxZv0r8+AnWbLhaO7YM4qfv4+HyOo6n+ZOBiDd1twPGamzHIWuQT1fj9+8HhP916J9ag==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=OrUmZeNzZTM7dR6REkBidy92vdynTbKz4kyvyegcC5M=; b=nhF7mi18Hucm4L8Eb0rDV7sL6+INKIk04OvZqULiJsClQ4/Lx+/XD0qKUJRDb/FLvmyWxcpoTY8zO8qdgDFcQtl6vpfHs3XyXZRouytpEibj4VqP07x16IlPgGVspVxBb472ztQ5CMl1sUiCsbfowfqwNIFLGphC4V0Dgz2tQWL3Fm7AIMrOUTfytUyR0JVkXIS3vgn0NdzCd721idVV5UgxGWr0JDLjjCKP0K/mPd4cpPdKFTmvm8ESd2al+hnRep1bKF/uCs/kpic3JEz9K7MMEIGKlI1i7e6gUjSDB9zIQdjGFkvnHr/iv+NzSwzO677RvaRIV3RzczK5dYQN6A==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=warwick.ac.uk; dmarc=pass action=none header.from=warwick.ac.uk; dkim=pass header.d=warwick.ac.uk; arc=none
Received: from DB7PR01MB5435.eurprd01.prod.exchangelabs.com (20.178.104.28) by DB7PR01MB4917.eurprd01.prod.exchangelabs.com (20.177.194.221) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2241.18; Sun, 8 Sep 2019 16:13:23 +0000
Received: from DB7PR01MB5435.eurprd01.prod.exchangelabs.com ([fe80::55eb:f0c1:7e8e:3af5]) by DB7PR01MB5435.eurprd01.prod.exchangelabs.com ([fe80::55eb:f0c1:7e8e:3af5%7]) with mapi id 15.20.2241.018; Sun, 8 Sep 2019 16:13:23 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
CC: "cfrg@ietf.org" <cfrg@ietf.org>
Thread-Topic: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)
Thread-Index: AdVkF1zGWxIvxhLkQ1maNFJa+34IlAAsvhCAAAC+NlAAZtcAgA==
Date: Sun, 08 Sep 2019 16:13:02 +0000
Message-ID: <D99AE3CC.47787%u1775114@live.warwick.ac.uk>
References: <BL0PR11MB31728AF40F9C9B7B65472AC1C1BB0@BL0PR11MB3172.namprd11.prod.outlook.com> <CACsn0cmmxgSGumm-tPG52F4zs6jxFNcKTp1ERyAmwxdahxFCvg@mail.gmail.com> <BL0PR11MB317269CF9E51B182387B92E8C1BA0@BL0PR11MB3172.namprd11.prod.outlook.com>
In-Reply-To: <BL0PR11MB317269CF9E51B182387B92E8C1BA0@BL0PR11MB3172.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.7.7.170905
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Feng.Hao@warwick.ac.uk;
x-originating-ip: [86.1.47.16]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 7302ada9-fd40-4e2e-78c3-08d734777913
x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600166)(711020)(4605104)(1401327)(2017052603328)(7193020); SRVR:DB7PR01MB4917;
x-ms-traffictypediagnostic: DB7PR01MB4917:
x-microsoft-antispam-prvs: <DB7PR01MB491749F03393824A57D12E16D6B40@DB7PR01MB4917.eurprd01.prod.exchangelabs.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-forefront-prvs: 0154C61618
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(4636009)(346002)(39860400002)(366004)(376002)(136003)(396003)(199004)(189003)(19623405002)(71190400001)(81166006)(81156014)(229853002)(186003)(66066001)(6506007)(6486002)(478600001)(8676002)(14454004)(8936002)(6246003)(6512007)(6306002)(6436002)(26005)(11346002)(53936002)(7736002)(256004)(6116002)(3846002)(54896002)(6916009)(102836004)(86362001)(446003)(64756008)(25786009)(66446008)(4326008)(66946007)(2906002)(66556008)(66476007)(486006)(476003)(99286004)(71200400001)(5660300002)(6666004)(786003)(58126008)(316002)(76176011)(91956017)(76116006); DIR:OUT; SFP:1101; SCL:1; SRVR:DB7PR01MB4917; H:DB7PR01MB5435.eurprd01.prod.exchangelabs.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1;
received-spf: None (protection.outlook.com: warwick.ac.uk does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam-message-info: yc2WONHYbijHy+PqSFdx45G9ifhns06LcgJ/fUeni4rJ1cCin2KvaTjmtpKNvnpkOYttfCcrSpvqxIxPh1Pw1HdA4xICb6Iap5UlMNsKXj9VMwcrvdA5jr1ptEPQUfxEW/WYgeV9r8fn/sgY3NmUP7LnIB9n7hNmu7W3oStESHO+cTmFbHLoqRHZRj94ql7NCG6JYrMXmMohEa87iC38CUGbYoKeyDUT7S9KPkxzG9P2+SK71I+KFLhP6GmhOPlCpGvewXwV5vm63Lu8lINFlVUx1Bs6I6RQRKNvnvrAsW0mdQedcvHDuUOSnEkOZfyCvjFlnVTStOiZSG5YQIIfcmW1YaMSmNYeryPxYFb1t4CBS6d+Fx5YWq29/EJYQX3Aw6ypj7KKQ8AAvi0508LxZE5lwF7Fbcy5Jlf6V7jThDg=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_D99AE3CC47787u1775114livewarwickacuk_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-Network-Message-Id: 7302ada9-fd40-4e2e-78c3-08d734777913
X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Sep 2019 16:13:02.0588 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 09bacfbd-47ef-4465-9265-3546f2eaf6bc
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: wjDN2aVwJlkX5dnBdLACh5pQJRPwLq+p9NTLBmN4pjM6kR2bMbPJ0/sdycTGXXcsKwajyT07bXhMV8PdVTRQ5XTGfpk5T2MFttm2ArnzBfo=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB7PR01MB4917
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/s28wVWribJ-OgyKm8WFT47ou_ho>
Subject: Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
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: Sun, 08 Sep 2019 16:13:28 -0000


How much harder are many logs then one on a quantum computer? Not very.

I believe that it is about one million times harder to do one million discrete logs than it is to do one (given that Shor’s algorithm doesn’t generate any side information from one run that would help you with the next; I also can’t think of any way to combine N points, and solve fewer than N discrete logs in a way that would allow you to recover the DLogs of the original N points).

Looking at the likely progression of Quantum Computers, it appears probable that, once someone creates a real one (as opposed to the toys that exist now), they could break a ECDLog problem, but it may take weeks to do so (and there are not likely to be a number of them available).  Hence, one a TLA gets one, it might gain the capability to solve dozens of ECDlog problems a year, but no more than that; hence this vulnerability of SPAKE2 might be relevant.  Now, this is entirely speculation, and also it would be reasonable to suspect that the speed/cost of QCs would rise/drop fairly rapidly, and so a few years after that it might be feasible to attack the other schemes as well (at least for their high-value targets).  This scenario did seem plausible enough for me to mention it.

In addition, for most other methods, it may be that a single discrete log might not be sufficient to break a single instance of the other schemes; however that really is currently speculation, as I have not seriously studied the issue, nor do I know anyone else who has


IMHO, the threat is not so much a quantum computer, but a state actor (a three-letter agency) who breaks one instance of DL simply by brute-force, which will be justified if this single attack allows the adversary to break everywhere.