[kitten] Kerberos preauth negotiation techniques

[Greg Hudson <[e-mail]>]

Nathaniel McCallum has been working on a Kerberos PAKE preauth mechanism
(https://github.com/npmccallum/krb5-pake) which also supports a second
factor value.  Although there are many variables to how this mechanism
could wind up working, we know that the exchange will end with the
client sending a key confirmation and encrypted second factor (perhaps
in addition to a client public value), and the KDC either issuing a
ticket or an error.  If the KDC implementation is careful enough about
operating in constant time, the client doesn't find out whether it was
wrong about the key or the second factor value.

If the PAKE mechanism only requires two hops (as in SPAKE2), then we
could theoretically fit the whole exchange into the same number of round
trips as traditional encrypted timestamp:

    C: unauthenticated AS-REQ
    K: PREAUTH_REQUIRED (KDC public value in hint)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

Naively putting a KDC public value into a hint list isn't a great
strategy for a preauth mech.  Even with a modern group like Curve25519
the public value will take non-negligible time to compute and
non-negligible space to transport.  If there were many preauth mechs
making this choice, the hint list would become large and expensive to
produce.  Also, if there is any kind of sub-negotiation within the
preauth mech (curve choice, PAKE algorithm choice, etc.), this approach
doesn't work.

I think there are basically three options:

1. Add a third round trip.  The exchange could look like this:

    C: unauthenticated AS-REQ
    K: PREAUTH_REQUIRED (empty hint)
    C: AS-REQ (client sub-negotiation parameters)
    K: MORE_PREAUTH_DATA_REQUIRED (KDC parameter choice, KDC public value)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

Other variations are possible--the KDC hint list could contain
sub-negotiation parameters to be interpreted by the client, and the
second client AS-REQ could contain a client public value for three-hop
PAKE mechanisms.  The point is that the KDC doesn't put much work or
data into its hint list, and receives sub-negotiation parameters before
it generates a public value.

This approach fits solidly within the confines of RFC 6113 and (at least
with an empty KDC hint) postpones almost all of the cost of the mech
until after it is agreed upon by the client and KDC.  The only real
disadvantage is the extra latency of a third round trip.

2. Use pseudo-enctypes:

    C: unauthenticated AS-REQ (pseudo-enctypes in etype field)
    K: PREAUTH_REQUIRED (KDC public value in hint)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

Each pseudo-enctype indicates client support for the preauth mech and
particular sub-negotiation parameters.  Because the KDC knows the client
supports the mech, it can suppress other preauth mechs in the hint list
and generate a public value known to be compatible with the client's
capabilities.

There is some half-hearted precedent for this idea.  RFC 4556 specifies
some PKINIT pseudo-enctypes to indicate CMS algorithm support, but then
immediately deprecates the practice and recommends the use of OIDs
instead.

Pseudo-enctypes are compact, and there is already support for them in
the MIT krb5 client preauth framework because of PKINIT.  However, this
approach requires that every sub-negotiation parameter value be
registered within the IANA Kerberos enctype registry; one can't use OIDs
to name curves, for instance.  And some people find it inelegant to use
the enctype number space for purposes other than actual RFC 3961
encryption types.

3. Use client preauth hints:

    C: unauthenticate AS-REQ (padata containing sub-negotiation params)
    K: PREAUTH_REQUIRED (KDC public value in hint)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

In this strategy, the client includes an unsolicited padata value in its
initial request which indicates support for the mechanism and contains
sub-negotiation parameters.  RFC 6113 does not currently envision this
kind of client hint as part of preauth negotiation, so we would have to
extend it.  Clients would have to retry without hints if an older KDC
rejects the unauthenticated AS-REQ with PREAUTH_FAILED; this is already
required for clients implementing RFC 6806 FAST negotiation.

The client hint value will inevitably be larger than a few
pseudo-enctypes would be, especially if the sub-negotiation parameters
could include multiple OID values.  If several preauth mechanisms come
into the world using non-trivial client hints, initial AS-REQs could
grow larger than we might like.  Otherwise, this approach has similar
properties as option 2, but without requiring any abuse of the enctype
number space.

---

As I write this, I am leaning towards option 1.  My only reservation is
that I would like this mechanism to eventually displace encrypted
timestamp in the Kerberos ecosystem, and it might be a shame to make
essentially all password-based initial Kerberos authentications take
three round trips.  What are other people's thoughts?