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

From: [email-masked]
Date: Mon, 11 Mar 2019 10:03:15 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : SPAKE2, a PAKE
        Authors         : Watson Ladd
                          Benjamin Kaduk
	Filename        : draft-irtf-cfrg-spake2-08.txt
	Pages           : 13
	Date            : 2019-03-11

Abstract:
   This document describes SPAKE2 and its augmented variant SPAKE2+,
   which are protocols for two parties that share a password to derive a
   strong shared key with no risk of disclosing the password.  This
   method is compatible with any prime order group, is computationally
   efficient, and SPAKE2 (but not SPAKE2+) has a security proof.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-spake2/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-irtf-cfrg-spake2-08
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-spake2-08

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-spake2-08

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: Greg Hudson <[email-masked]>
Date: Tue, 12 Mar 2019 00:18:32 -0400

* The old version of the draft uses secret coefficients which are
multiples of the cofactor h, similar to X25519, in order to ensure that
the computed point K is in the prime-order subgroup generated by P.  The
new version of the draft instead asks each party to check the other
party's public point order by checking if h*S=I or h*T=I.  This seems
less efficient, and I also don't think it is correct.  It would catch
points of small order (h or factors of h), but not points of order 2p,
4p, ..., hp.  Why the change?

* "[K] MUST NOT be used as a shared secret" is a weird statement, as we
go on to describe how to use it as a shared secret in key derivation.
Perhaps, "MUST NOT be directly used as a cryptographic key".

* This revision includes allowances for omitting one or the other
identity from key derivation.  I think this departs from the SPAKE2
security proof, and I don't recall discussion here about relaxing that
requirement.

* scrypt seems like an outdated choice of memory-hard hash function.

* I know what a MAC address is, but had to google what a Media Access
Control address is.  (Only in hindsight are they obviously the same thing.)

* "w0s and w1s MUST NOT equal I" seems not well-formed, as they seem to
be numbers, not group elements.  If they are instead to be checked
against 0 and/or 1, I think this needs a justification; it is
vanishingly unlikely to happen by chance (and an attacker is not in
control of the password); an attacker who just passively waits to spot
this case would be equally likely to succeed by passively waiting for
some other specific value.

* Typo: "protocl".

As the draft now more specifically constrains key derivation and key
confirmation (presumably in response to Kenny Paterson's feedback), I
think it can no longer be used as a normative reference for
draft-ietf-kitten-spake-preauth.  That is probably not an overriding
concern.

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 12 Mar 2019 22:43:53 -0500

Hi Greg, CFRG

Thanks for the comments.  I'll get to them in a bit, but let me try to give
a summary of the intended changes first, since I ran out of time to do that
yesterday (with my rush to beat the submission deadline).

Most of these changes are prompted by Kenny's review, and Chris Wood did a
lot of the work preparing the updates as a pull request.  Thank you to
both; the document is better because of it.

There were some notational changes, to be consistent about multiplicative
notation, avoid using the same symbol for different purposes, etc..

We also fleshed things out to make a more complete protocol, introducing a
transcript to protect the negotiation from MITM and the derivation of key
confirmation keys (and key confirmation algorithms, allowing for
application-provided AAD).  Kenny also suggested that the extension of the
PAKE to new curves is not an easy undertaking, so we may be advised to
limit it to a vetted set of parameters, which led to the introduction of
the table of "ciphersuites", combining group, hash, KDF, key-confirmation
MAC, and memory-hard hash function needed for a full system.

These are some pretty dramatic changes (without specific RG input), so I
have to consider them to still be "in flux".  I'm inclined to agree with
Kenny on the value of having a complete protocol, but that also puts me in
the uncomfortable position of making a lot of changes without specific
justification.  I'm happy to receive further guidance here, including
reverting most or all of this stuff.  The I-D submission deadline does
serve as a forcing function to get changes in and trigger discussion, even
if it's not always the prettiest way to do so...

We clarified the construction of w0 and w1, as well as several
editorial-type changes.

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),
to sending unscaled values and having the recipient make the multiplication
by the cofactor (and thus directly check for small-subgroup membership).
Unfortunately, I'm not sure that I did this properly, for at least:

(1) I attempted to add some clarifying text about the cofactor
multiplication being just for subgroup membership verification and the
intermediate inputs being unchanged, but I didn't go through the math to
check that it is doing the right thing

(2) The Z and V constructions actually have different contributions from M
and N, now, since in the old scheme x and y are "in [0, p*h) divisible by
h" but now they're "in [0,p)", but the M and N contributions do not get
similarly rescaled.  (Recall that the procedure used to generate M and N
requires that the value be on the curve *and in the prime order subgroup*.)

I also moved the algorithm and python code to generate M and N into an
Appendix, since it's not directly relevant to the primary output of the
document.

On to Greg's comments...

> 4p, ..., hp.  Why the change?

This should probably be (3) in my list above.  I think when I was merging
Chris's PR, I had convinced myself that only order-p and order-h subgroups
were possible (or factors of h), so that (e.g.) 2p would not be possible.
But I can't back that up right now -- Chris, can you say more?

> Perhaps, "MUST NOT be directly used as a cryptographic key".

I can do that.

> security proof, and I don't recall discussion here about relaxing that

I also don't recall discussion, though the text is attempting to indicate
that this can only happen in cases where the identity in question is
implicit in the containing protocol.

> * scrypt seems like an outdated choice of memory-hard hash function.

That's fair.  I assume you're thinking of draft-irtf-cfrg-argon2?

> Control address is.  (Only in hindsight are they obviously the same thing.)

I'm (only slightly) surprised to see this is not marked as "well-known" in
https://www.rfc-editor.org/materials/abbrev.expansion.txt, and will make
the expansion.

> * "w0s and w1s MUST NOT equal I" seems not well-formed, as they seem to

(It's just w0 and w1, right, not the 's' variants?)

> some other specific value.

I think this was intended to also be a subgroup-membership check, but
clearly is not as currently phrased.

> * Typo: "protocl".

will fix

> draft-ietf-kitten-spake-preauth.  That is probably not an overriding

I did not get to think about this question particularly hard, but the main
barrier here seemed to be the change in cofactor multiplication; a lot of
the other changes could be wrapped into a specific "ciphersuite" for the
kerberos usage, if needed.  (Since that protocol does do the transcripting,
key derivation, and key confirmation steps that are needed, just with a
somewhat tighter integration with the containing kerberos context.)

Thanks again,

Ben

---

From: Greg Hudson <[email-masked]>
Date: Wed, 13 Mar 2019 00:39:13 -0400

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

> But I can't back that up right now -- Chris, can you say more?

https://safecurves.cr.yp.to/twist.html lists the possible orders of
group points.  It includes p times divisors of h.  There is also some
discussion of small-subgroup attacks and why scaled coefficients are
useful against them.

> implicit in the containing protocol.

That doesn't seem like a helpful property.  One concern is that a
message (or a derivative of a message) might be taken from one session
and used in another.  If different sessions have different implicit
identities, omitting an identity from key derivation definitely seems to
potentially compromise the security proof.

> That's fair.  I assume you're thinking of draft-irtf-cfrg-argon2?

Yes.

> somewhat tighter integration with the containing kerberos context.)

Rather than put a lot of Kerberos-specific stuff in the CFRG document, I
think it will make more sense to fully describe the SPAKE math in the
Kerberos document.

---

From: "Paterson Kenneth" <[email-masked]>
Date: Wed, 13 Mar 2019 10:59:31 +0000

Hi Greg,

In-line...

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of Greg Hudson <[email-masked]>
Date: Wednesday, 13 March 2019 at 04:40
To: Benjamin Kaduk <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt

    

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

---

From: Greg Hudson <[email-masked]>
Date: Wed, 13 Mar 2019 10:47:12 -0400

On 3/13/19 6:59 AM, Paterson  Kenneth wrote:
> 	-- 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?

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

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

---

From: "Paterson Kenneth" <[email-masked]>
Date: Wed, 13 Mar 2019 15:01:33 +0000

In-line...

-----Original Message-----
From: Greg Hudson <[email-masked]>
Date: Wednesday, 13 March 2019 at 14:47
To: Paterson  Kenneth <[email-masked]>, Benjamin Kaduk <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt

   
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.

Right.

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

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 13 Mar 2019 10:12:06 -0500

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

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

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

---

From: Greg Hudson <[email-masked]>
Date: Wed, 13 Mar 2019 11:45:00 -0400

On 3/13/19 11:01 AM, Paterson  Kenneth wrote:
> G is not of order p (at least that's how I read the spec.) - rather it has order hp.

If g is the generator, then in the new terminology L=w1*P.  P is a point
of order p, so L should have order p as well.

> See Section 3.1:

That refers to the group.  (Having G refer to both the group and the
generator is of course confusing, and was rightly rectified in -08.)

The new draft defines "a generator P of the (large) prime-order subgroup
of G".  In the old draft, it was not clear in the text that G (the
generator point) was a point of order p, but for edwards25519 and
edwards448 it used the standard generators for those groups, which are
of order p.

---

From: "Paterson Kenneth" <[email-masked]>
Date: Wed, 13 Mar 2019 16:20:05 +0000

Thanks for those clarifications - I should have read the new draft all the way through. I'll get to it in due course, and I hope others will too.

---

From: Chris Wood <[email-masked]>
Date: Wed, 13 Mar 2019 09:50:59 -0700

(Chiming in late — thanks for the comments, Greg!)

> On Mar 12, 2019, at 9:39 PM, Greg Hudson <[email-masked]> 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:

   … A and B multiply protocol
   messages from each peer by h so as to avoid small subgroup attacks,
   but the result of the multiplication is not used for operations other
   than the comparison against I and the non-multiplied value is used in
   subsequent calculations.

I’m hopeful the actual cryptographers on this will correct me if I’m wrong. :-)

>> That's fair.  I assume you're thinking of draft-irtf-cfrg-argon2?

As part of the ciphersuite, we could define both.

---

From: Greg Hudson <[email-masked]>
Date: Wed, 13 Mar 2019 13:42:09 -0400

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

---

From: Eike Kiltz <[email-masked]>
Date: Thu, 14 Mar 2019 11:58:33 +0100

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 <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Eike Kiltz <[email-masked]>
Date: Tue, 26 Mar 2019 15:21:06 +0100

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