Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt

"Paterson Kenneth" <kenny.paterson@inf.ethz.ch> Wed, 13 March 2019 11:01 UTC

Return-Path: <kenny.paterson@inf.ethz.ch>
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 A9398130EED for <cfrg@ietfa.amsl.com>; Wed, 13 Mar 2019 04:01:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.199
X-Spam-Level:
X-Spam-Status: No, score=-4.199 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, URIBL_BLOCKED=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 8pwnuxG61d6l for <cfrg@ietfa.amsl.com>; Wed, 13 Mar 2019 04:01:18 -0700 (PDT)
Received: from edge10.ethz.ch (edge10.ethz.ch [82.130.75.186]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CB2C1130EBF for <cfrg@ietf.org>; Wed, 13 Mar 2019 04:01:16 -0700 (PDT)
Received: from CAS12.d.ethz.ch (172.31.38.212) by edge10.ethz.ch (82.130.75.186) with Microsoft SMTP Server (TLS) id 14.3.439.0; Wed, 13 Mar 2019 11:59:32 +0100
Received: from MBX117.d.ethz.ch ([fe80::c1d4:d225:fabf:1974]) by CAS12.d.ethz.ch ([fe80::7861:4ecb:7c42:cad4%10]) with mapi id 14.03.0439.000; Wed, 13 Mar 2019 11:59:32 +0100
From: "Paterson Kenneth" <kenny.paterson@inf.ethz.ch>
To: Greg Hudson <ghudson@mit.edu>, Benjamin Kaduk <kaduk@mit.edu>
CC: "cfrg@ietf.org" <cfrg@ietf.org>, "cawood@apple.com" <cawood@apple.com>
Thread-Topic: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt
Thread-Index: AQHU2Cx0BfbR89M7N02t2s+AosM+i6YHVDEAgAGIp4CAAA91gIAAakKA
Date: Wed, 13 Mar 2019 10:59:31 +0000
Message-ID: <135A8573-53DF-4B51-A9F2-E3783DD6A0D0@inf.ethz.ch>
References: <155232379553.23186.8764563590660883823@ietfa.amsl.com> <884f593b-0753-16ff-e68c-990acd0e8d68@mit.edu> <20190313034352.GE8182@kduck.mit.edu> <7fa7713b-94da-da7b-bf9e-465627a8f030@mit.edu>
In-Reply-To: <7fa7713b-94da-da7b-bf9e-465627a8f030@mit.edu>
Accept-Language: de-CH, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [129.132.139.40]
Content-Type: text/plain; charset="utf-8"
Content-ID: <8895876C209E154A9CD9456FD8A2455D@intern.ethz.ch>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Wyd9cNfRX6wWt7H0s4_Uo92NlPk>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt
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: Wed, 13 Mar 2019 11:01:21 -0000

Hi Greg,

In-line...

-----Original Message-----
From: Cfrg <cfrg-bounces@irtf.org> on behalf of Greg Hudson <ghudson@mit.edu>
Date: Wednesday, 13 March 2019 at 04:40
To: Benjamin Kaduk <kaduk@mit.edu>
Cc: "cfrg@ietf.org" <cfrg@ietf.org>rg>, "cawood@apple.com" <cawood@apple.com>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt

    On 3/12/19 11:43 PM, Benjamin Kaduk wrote:
    > Perhaps the most drastic change is the switch from multiplying by the
    > cofactor before transmission and recipients verifying that points are on
    > the curve (but in essence trusting the peer on prime subgroup membership),
    
    In the old draft, each side chooses a multiple of the cofactor as its
    private coefficient, and multiplies that coefficient by the unmasked
    point, points of order greater than p (p times a divisor of h) will
    become points of order p.  This is the same strategy as X25519 uses.
    
    Points of small order (after unmasking) become I after multiplication by
    the scaled coefficient.  I recall some debate around whether X25519
    should require a check for whether the result is the identity point,
    with the conclusion that it is not necessary.  I believe the same
    applies here.
    

I don't think it's so simple here as it is for a simple DH protocol on a non-prime order curve like X25519.

The point is that all the original security analysis for SPAKE simply assumes everything happens in a prime order group.  But (quoting from my earlier review):

		page 3:  "B stores L=w1*g and w0." (In the context of SPAKE2+.)

		[...]

	-- Assuming g is the generator of G of order p*h, notice that this element L is not necessarily in the order p subgroup of G, since w1 (and w0) are not necessarily multiples of h. Later in the protocol, 	A computes V = w1(Y-w0*N) where Y should have been received from B. If Y is chosen adversarially, then V may also not be in the order p subgroup of G. This may not have any negative 	consequences for protocol security because of the manner in which key derivation is performed, with both Z and V being involved in key derivation and V not being exposed to an adversary 	impersonating B (this another reason to mandate how key derivation is done). But this sits uncomfortably with the following remark in the security considerations (page 7):

	        "It is not necessary to validate membership in the prime
   	order subgroup: the multiplication by cofactors eliminates the
   	potential for mebership [sic] in a small-order subgroup."

	-- It's certainly hard for an attacker to arrange for V to be in the order h (small) subgroup, but it can arrange for V NOT to be in the prime-order subgroup, and L need not be either (without any 	adversarial behaviour) while the presentation of SPAKE2+ in [TDH] just assumes that everything is a priori in an order p group. How does this difference affect the security analysis? It seems that A 	performing a check that V is in the prime-order subgroup may be necessary in order to bring the protocol into line with what is assumed in [TDH]. Not doing this check has unknown (to me) 	consequences. 

I will need to look again at the new draft to see if it successfully ensures everything is in the order p subgroup, so that the original security analysis from [TDH] still applies. I welcome other inputs on this question, of course. But let me stress that, as many examples have shown, small changes to protocols can easily invalidate security proofs and allow attacks.

Cheers,

Kenny