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

[Benjamin Kaduk <[e-mail]>]

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

On Tue, Mar 12, 2019 at 12:18:32AM -0400, Greg Hudson wrote:
> * 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?

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?

> * "[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".

I can do that.

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

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?

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

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

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

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

> * Typo: "protocl".

will fix

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

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