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

[Eike Kiltz <[e-mail]>]

I had a closer look and using scaled coefficients for x, y and w1
solves the "subgroup issued" in SPAKE2+, see my technical
explanation below.

 -Eike

----------------------------------------
Setup: G is a group of order p*h. P, N, M are generators of the
prime-order subgroup Gp of order p, h is the (small) co-factor.
Let (w0 || w1) be the output of H(pw), where w0 and w1 are
interpreted as numbers in Zp.

Define w1' := h*w1

The idea of the "scaled SPAKE2+" protocol is to substitute x by x':=x*h,
y by y':=y*h and w1 by w1':=w1*h.

The modified protocol between A(w0, w1':=w1*h) and B(w0, L'=w1'*P)
works as follows
1. A picks random x from Zp, defines x':=h*x, computes X:=x'*P+w0*M
and sends X to B
2. B picks random y from Zp, defines y':=h*y, computes Y:=y'*P+w0*N
and sends Y to A
3. A computes Z:=x'*(Y-w0*N), which equals x'y'*P in an honest execution.
    A computes V:=w1'*(Y-w0*N), which equals w1'y'* in an honest execution.
4. B computes Z:=y'*(Y-w0*M), which equals x'y'*P in an honest execution.
    B computes V:=y'*L, which equals w1'y'* in an honest execution.

The problem is that the security argument of [TDH] assumes
X and Y to be in the prime-order subgroup but in general they
can be (adversarially chosen) arbitrary group elements.

Let's look at the case of Y which is the slightly more difficult
case since one has to consider Z and V. A computes from
Y the elements Z and V as
      Z:=x'*(Y-w0*N) = x*h*(Y-w0*N) = x*h*Y - x*h*w0*N
Multiplication by the co-factor h annihilates all parts of Y which
are not contained in the prime-order subgroup Gp. Hence we
can assume wlog that Y is contained in the subgroup Gp since
all other parts are ignored by the protocol.

Exactly the same argument also holds for
     V:=w1'*(Y-w0*N) = w1*h*Y - w1*h*w0*N
----------------------------------------

On Thu, Mar 14, 2019 at 11:58 AM Eike Kiltz <[e-mail]> wrote:
>
> I'm one of the authors of [TDH] and I'm happy to see that our ideas
> are considered for inclusion into the PAKE standard.
>
> If I understand correctly, then the group proposes to use "scaled
> coefficients" x and y in the SPAKE2 protocol to
> avoid subgroup attacks. That is, replace any appearance of x and y in
> the protocol with x*h and y*h, respectively.
> This way the "algebraic key" K is forced to be in the prime-order sub-group.
>
> My understanding is that the same argument can be applied to the
> SPAKE2+ protocol by using scaled coefficients
> x, y, and w1. (w0 does not have to be scaled.)
>
> I will have a closer look.
>
>  -Eike
>
> On Wed, Mar 13, 2019 at 6:42 PM Greg Hudson <[e-mail]> wrote:
> >
> > On 3/13/19 12:50 PM, Chris Wood wrote:
> > > Indeed, I forgot to consider these other subgroups when preparing the
> > > PR. While the new cofactor check ensure that the small subgroups are
> > > avoided, it does not help against those groups that are multiples of p
> > > and (small) divisors of h. So perhaps in addition to the small subgroup
> > > check, could we also use the result of the cofactor multiplication in
> > > each computation? That is, for SPAKE, use S*h and T*h instead of S and H
> > > when computing the shared secret? Currently, -08 says this is not done:
> >
> > That would work, but using scaled x and y coefficients solves the same
> > problem, and is more consistent with X25519.  So I don't really know
> > problem what the coefficient change in -08 was trying to solve.
> >
> > (I now agree with Kenny that there was a problem specifically with
> > SPAKE2+.  But no changes to the SPAKE2 writeup should be required to
> > solve that.)
> >
> > _______________________________________________
> > Cfrg mailing list
> > [e-mail]
> > https://www.irtf.org/mailman/listinfo/cfrg