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

["Paterson Kenneth" <[e-mail]>]

Hi Greg,

In-line...

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