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

[Benjamin Kaduk <[e-mail]>]

On Wed, Mar 13, 2019 at 03:01:33PM +0000, Paterson  Kenneth wrote:
> 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:

[Just to clarify: the -08 attempts to use G for the group or order p*h,
with distinguished generator P.  I think Greg may be using the old
terminology.]

> 	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.

Given that we don't have a proof of any sort for SPAKE2+ (as opposed to
regular SPAKE2), even limited to a prime-order group, wouldn't that suggest
removing the augmented version from the document entirely?

-Ben