Re: [kitten] Kerberos preauth negotiation techniques

Nathaniel McCallum <> Tue, 17 February 2015 16:14 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id B865F1A8904 for <>; Tue, 17 Feb 2015 08:14:57 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.212
X-Spam-Status: No, score=-3.212 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HK_RANDOM_ENVFROM=0.001, HK_RANDOM_FROM=0.999, RCVD_IN_DNSWL_HI=-5, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id IJBtLr1FnKfp for <>; Tue, 17 Feb 2015 08:14:52 -0800 (PST)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 3E4801A8AB3 for <>; Tue, 17 Feb 2015 08:14:46 -0800 (PST)
Received: from ( []) by (8.14.4/8.14.4) with ESMTP id t1HGEiGd006026 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Tue, 17 Feb 2015 11:14:45 -0500
Received: from ( []) by (8.14.4/8.14.4) with ESMTP id t1HGEcw5012734 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NO); Tue, 17 Feb 2015 11:14:42 -0500
Message-ID: <>
From: Nathaniel McCallum <>
To: Greg Hudson <>
Date: Tue, 17 Feb 2015 11:14:35 -0500
In-Reply-To: <>
References: <>
Content-Type: text/plain; charset="UTF-8"
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
X-Scanned-By: MIMEDefang 2.68 on
Archived-At: <>
Subject: Re: [kitten] Kerberos preauth negotiation techniques
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Common Authentication Technologies - Next Generation <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 17 Feb 2015 16:14:57 -0000

On Wed, 2015-02-11 at 13:35 -0500, Greg Hudson wrote:
> Nathaniel McCallum has been working on a Kerberos PAKE preauth 
> mechanism ( 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 

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