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

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

In-line...

-----Original Message-----
From: Greg Hudson <[e-mail]>
Date: Wednesday, 13 March 2019 at 14:47
To: Paterson  Kenneth <[e-mail]>, 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/13/19 6:59 AM, Paterson  Kenneth wrote:
    > 		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.
    
    Since L is a multiple of G, it will be of order p (since G is of order
    p).  Unless I'm badly mistaken?
   
G is not of order p (at least that's how I read the spec.) - rather it has order hp. See Section 3.1:

	Suppose G has order p*h where p is a large prime; h will be called the cofactor.

    > 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.
    
    I hadn't looked too closely at SPAKE2+.  This step does seem problematic
    because w1 is not a scaled coefficient, and I agree that it does not sit
    well with the security considerations text (which I think was written
    when the draft didn't cover SPAKE2+).  Following the same logic as your
    analysis (except in regard to L), it probably doesn't lead to a
    small-subgroup attack since the attacker cannot see V and cannot easily
    make Y-w0*N be of small order.  But it may invalidate the security proof
    because it's easy for an attacker to make V be of order 2p, 4p, ..., hp.

Right.
    
    I'm not sure I'm qualified to suggest a fix, but I would probably start
    with making w1 a scaled coefficient (however it's generated mod p,
    multiply it by h so that it's in the range [0,ph) mod h, similar to x
    and y).  Although this is asymmetric with w0, note that w0 is used just
    like w in SPAKE (multiplied by M or N to produce a mask), while w1 is
    used similarly to x or y (multiplied by the generator or the other
    party's point).

My intuition here is that we need to be very careful, and (without my chair's hat) I would not want CFRG to finalise an RFC on scheme until we are sure we have a proof that applies to the protocol as specified.

Cheers

Kenny