Re: [kitten] Kerberos preauth negotiation techniques

[Simo Sorce <[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 strongly prefer 3.
Clients can easily limit the amount of data they will send so I am not
concerned that the AS_REQ will grow too much.

Simo.

-- 
Simo Sorce * Red Hat, Inc * New York