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

"Paterson Kenneth" <> Wed, 13 March 2019 11:01 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id A9398130EED for <>; Wed, 13 Mar 2019 04:01:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.199
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 8pwnuxG61d6l for <>; Wed, 13 Mar 2019 04:01:18 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id CB2C1130EBF for <>; Wed, 13 Mar 2019 04:01:16 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (TLS) id 14.3.439.0; Wed, 13 Mar 2019 11:59:32 +0100
Received: from ([fe80::c1d4:d225:fabf:1974]) by ([fe80::7861:4ecb:7c42:cad4%10]) with mapi id 14.03.0439.000; Wed, 13 Mar 2019 11:59:32 +0100
From: "Paterson Kenneth" <>
To: Greg Hudson <>, Benjamin Kaduk <>
CC: "" <>, "" <>
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: <>
References: <> <> <> <>
In-Reply-To: <>
Accept-Language: de-CH, en-US
Content-Language: en-US
x-originating-ip: []
Content-Type: text/plain; charset="utf-8"
Content-ID: <>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: <>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 13 Mar 2019 11:01:21 -0000

Hi Greg,


-----Original Message-----
From: Cfrg <> on behalf of Greg Hudson <>
Date: Wednesday, 13 March 2019 at 04:40
To: Benjamin Kaduk <>
Cc: "" <>rg>, "" <>
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.