Re: [Cfrg] Using draft-irtf-cfrg-spake2-00 in Kerberos Preauth

[Watson Ladd <[e-mail]>]

On Wed, Jan 28, 2015 at 7:53 AM, Nathaniel McCallum
<[e-mail]> wrote:
> I've only just now joined the mailing list, so I'm a bit late to the
> party (though I see my name has been brought up in the previous
> discussions).
>
> I am currently implementing a PAKE preauthentication mechanism for
> Kerberos. https://github.com/npmccallum/krb5-pake
>
> One of the PAKEs we have chosen to use is SPAKE2. The aforementioned
> program that I am using to generate M and N constants is here:
> https://github.com/npmccallum/krb5-pake/blob/master/src/pake/spake_constants.c
>
> This program uses two seed strings:
>  "OID point generation seed (M)"
>  "OID point generation seed (N)"
>
> OID is replaced by the OID of the curve. Since some curves have multiple
> aliases, the use of OIDs removes any ambiguity to the seed.
>
> The method use to generate the constants is fairly similar to that used
> by Chromium, but differs in several ways:
> http://src.chromium.org/viewvc/chrome/trunk/src/crypto/p224_spake.cc
>
> First, we calculate the length of the encoded value of a single point on
> the curve. I'll call this $CURVE_SIZE.
>
> Second, we determine which is the smallest hash function (of SHA-1,
> SHA-2-*) which outputs at least $CURVE_SIZE bytes. So, for instance,
> given P256, SHA-2-256 will be used. If no hash function is larger than
> $CURVE_SIZE, we use the largest hash. For example, P521 uses SHA-2-512.
>
> Third, we generate the seeds by filling in the OID value.
>
> Fourth, we begin a recursive process whereby we hash the seed (or the
> previous hash of the seed) until the output of the hash yields an X
> coordinate on the curve. The Y coordinate (+/-) is chosen using the
> right-most bit of the hash.

I don't think this is what your C code is doing, or if it is, I can't
figure it out because of the way it uses OpenSSL internals.
I may try coding that up in SAGE and seeing if it agrees in the
output. (In particular I think the first byte of the digest might get
mangled to have the decode function work).

>
> This methodology differs from the Chromium methodology in three ways:
> 1. The hash function is variable.
> 2. OIDs are used instead of a friendly name (like P256).
> 3. We generate M/N for all curves supported by OpenSSL at build time.
>
> In short, this is just a poorly devised method for hashing a constant
> string onto the curve. I am definitely open to alternatives.

Do they matter? This only needs to happen once.

>
> One other important difference of our implementation from
> draft-irtf-cfrg-spake2-00 is that we do not use the SPAKE2 derivation
> hash, but rather use a variant of it. The purpose of this is to have a
> generic derivation which:
> 1. Works for all PAKE types (notably, JPAKE).
> 2. Includes all public negotiation data to provide protection from
> downgrade attacks.
>
> Specifically, our derivation step includes:
> * Client identity
> * Server identity
> * Recursive hash of all negotiation data (including SPAKE's public keys)
> * The secret (w)
> * The derived session key (K)
>
> So, all that to say this...
>
> As I see it, two improvements are needed to the draft.
>
> First, the method to calculate M/N needs to be clearly laid out. If an
> existing method is chosen (Chromium's/krb5-pake's), I feel that using
> curve names is not sufficiently unambiguous. Alternatively, a new method
> of producing M/N constants could be devised. The latter may be necessary
> since I'm not sure either of the existing methods will work for
> Curve25519.

Why won't the same method work for the Edwards curve? I pick x by
incrementing until there is a valid y value, then pick one of the two
solutions of the quadratic.

Why do we need to be completely unambiguous? The only thing we need is
that I don't know the discrete logarithms, which the method being used
now already achieves.

>
> Second, the "real" SPAKE algorithm is the generation of K. The
> derivation step is a common step that should be done for all PAKEs and
> is not SPAKE specific. This derivation step is usually application
> specific. While it may include other data, it must include at least the
> following in some form:
> * Client identity
> * Server identity
> * All publicly exchanged group members (in SPAKE: T and S)
> * The secret (w)
> * The derived session key (K)

I disagree with this change for the following reason: hashing the
transcript needs to be done anyway. But some protocols don't do it
correctly. In those protocols we derive additional protection from
defining K to already include the data from SPAKE2.

Sincerely,
Watson Ladd

>
> Nathaniel
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin