Re: [kitten] Kerberos preauth negotiation techniques

[Nathaniel McCallum <[e-mail]>]

On Wed, 2015-02-11 at 13:35 -0500, Greg Hudson wrote:
> 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?

I see 1 and 3 as the only good options. Having to register group 
parameters instead of using OIDs is a deal-breaker in my book.

1 and 3 are also compatible workflows. In 3, the first AS-REQ is 
exactly the same padata as the second AS-REQ in 1. That is to say, 3 
is an optimization of 1 where the first round-trip of 1, which 
includes no meaningful data, is simply not used. Put another way, 3 is 
just 1 with optimistic preauth.

So a KDC can actually implement both 1 and 3 simultaneously. If the 
KDC does not receive the padata in the first step (option 3), it 
generates the empty hint (option 1). Otherwise, 1 and 3 are identical. 
Only one thing differs: PREAUTH_REQUIRED or 
MORE_PREAUTH_DATA_REQUIRED. Can we just always use the latter error?

The problem, as Greg rightly notes, is that a client cannot know if 
the KDC supports the PAKE preauth mech and will have to handle 
PREAUTH_FAILED properly.

After thinking about this (and implementing it), I think the best way 
forward is 1 with 3 as an optional optimization. The KDC should always 
support both 1 and 3; adding support for (optional) 3 should be 
trivial. Clients should choose whether or not to support 3 based on 
complexity of implementation; 3 can always be added later as an 
optimization.

Nathaniel