Re: [kitten] SPAKE and non-deterministic RFC 3961 checksums

[Benjamin Kaduk <[e-mail]>]

On Sun, Sep 17, 2017 at 01:24:51AM -0400, Greg Hudson wrote:
> RFC 3961 says about the checksum profile get_mic operation: "This
> function is not required to return the same deterministic result for
> each use; it need only generate a token that the verify_mic routine can
> check."  In practice, only the oldest checksum types (used with
> single-DES keys) are non-deterministic.
> 
> The SPAKE preauth transcript checksum is computed independently by the
> client and KDC using the RFC 3961 checksum operation (iterated several
> times).  In hindsight, this design obviously requires a deterministic
> checksum operation, so the pieces don't currently fit.  I unfortunately
> only realized this mismatch today when I started doing integration tests
> using DES keys in a prototype implementation.
> 
> The potential remedies I can think of fall into these bins:
> 
> 1. Don't change the SPAKE design.  Instead, update RFC 3961 to specify
> that new checksum types must be deterministic, and specify that SPAKE
> preauth can't be used with single-DES keys.  Aside from the
> standards-space cost of pushing our problem down into a lower layer, the
> prohibition against using SPAKE with single-DES keys could make it
> harder for clients to be configured to refuse encrypted timestamp
> preauth on a pre-realm basis.  That is perhaps not a large cost as
> Kerberos implementations are moving away from single-DES support anyway.
> 
> 2. A relatively quick fix: use PRF instead of checksum.  (Or PRF+, in
> which case we have to decide how much length of output we want.)  I
> think PRF has the requisite properties, but I would want to think on it
> more.

This is probably the most appealing option, provided we can accurately
state which properties we need (and they are provided by PRF(+)).

> 3. We could use a hash (it doesn't need to be keyed) independent of RFC
> 3961.  The hash algorithm could be specified in the group profile,
> perhaps, but I believe the rejected-optimistic-challenge case poses a
> difficulty for that design.

The hash algorithm could also be negotiated independently (so that in
practice, e.g., sha256 is always used, at least in the initial deployments).
For the rejected-optimistic case there is still an issue, but if the KDC
only supports O(2) hash algorithms during a hash transition, then the
amount of state needed in the cookie is bounded by a number that might
be smaller than the number of supported groups (but then again, might
not).

> 4. The most open-ended option is to back up and reconsider the purpose
> of the transcript checksum, which is to bind at least the public keys
> into key derivation.  The current transcript also binds in group
> negotiation and the initial factor challenge.  I can't immediately think
> of an alternative design which doesn't require the KDC to store a lot of
> information in the cookie.

I agree that we are likely to end up with something resembling a
"transcript hash", even if it does not directly use a hash primitve.

-Ben