Re: [kitten] Kerberos preauth negotiation techniques

Nico Williams <> Tue, 17 February 2015 17:27 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id D98D81A1B5C for <>; Tue, 17 Feb 2015 09:27:54 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.666
X-Spam-Status: No, score=-1.666 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, IP_NOT_FRIENDLY=0.334, RCVD_IN_DNSWL_NONE=-0.0001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id xxjiVdDMUjz1 for <>; Tue, 17 Feb 2015 09:27:53 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 89A771A1B51 for <>; Tue, 17 Feb 2015 09:27:53 -0800 (PST)
Received: from (localhost []) by (Postfix) with ESMTP id 37351360075; Tue, 17 Feb 2015 09:27:53 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed;; h=date :from:to:cc:subject:message-id:references:mime-version :content-type:in-reply-to;; bh=7QmPKojYhaSzOH VonUjAWNp9ChQ=; b=mTQnQ1kyESUG7pw5VBQiWscQo7CVgH8iPWUGjrIvtzglJC I+s1vNCAPU/qiT8UcwpevqEf7VggE88t1OLq7WPBH15FjWh1Q7tioYE7ITOkIFM/ +tzQq8W2BN/uCt4Alz8FuNYQTGjhmU/oX1FazhSZ16WHFNxUOlkinT18kdsik=
Received: from localhost ( []) (Authenticated sender: by (Postfix) with ESMTPA id E31B2360059; Tue, 17 Feb 2015 09:27:52 -0800 (PST)
Date: Tue, 17 Feb 2015 11:27:52 -0600
From: Nico Williams <>
To: Greg Hudson <>
Message-ID: <20150217172751.GG5246@localhost>
References: <>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <>
User-Agent: Mutt/1.5.21 (2010-09-15)
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 17:27:55 -0000

On Wed, Feb 11, 2015 at 01:35:58PM -0500, Greg Hudson wrote:
> 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.


(For some two-round-trip PAKEs the amount of work to do on the first go
could be negligible, but nonetheless, the remaining points apply.)

> I think there are basically three options:
> 1. Add a third round trip.  The exchange could look like this:

This has the advantage of having a return routability check built-in so
that the AS doesn't spend too many resources computing public values for
a client that isn't there to complete the exchange.

At a minimum, an over-worked AS should have an option to force the
additional 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.

Not just that, but this approach has been used to extend other
protocols (e.g., TLS).

> 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.

I don't mind this too much.

A problem with (2) is that if we ever need more than "which PAKEs does
the client support" hints, then (2) will be insufficient.  Or perhaps
we'll have a bit of a cartesian explosion (PAKEs x curves).  Or perhaps
we'll end up with many pseudo-enctypes for hinting (one set for PAKEs,
another for curves, ...).

> 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.

I don't mind this either.  It is decidedly more elegant.  The
1-round-trip penalty when talking to older KDCs will vanish when those
are upgraded.

> The client hint value will inevitably be larger than a few
> pseudo-enctypes would be, especially if the sub-negotiation parameters

I don't think this need be inevitable.  See comment above about
cartesian explosions in (2).

> could include multiple OID values.  If several preauth mechanisms come

If we use OIDs for PAKEs and curves, then yeah, the hints in (3) could
get large!  :)  (This is a bad joke about space inefficiency of OIDs.)

We've talked about using relative OIDs, but the problem with those (or
integers, bits in a bit string, ...) is that they really force use to
have a registry.

> 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.

If the only things the client has to send a priori were a set of PAKEs
and a set of curves, then the hints can be fairly space efficient.  If
we need a cartesian explosion (e.g., if some PAKEs are not orthogonal to
the choice of curve) then hints have to get large in the long run

> ---
> 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?

Why not (3)?  It too will cost 3 round trips _at first_, but will
eventually improve to 2 round trips as KDCs are upgraded.  Seems like a
win to me.

I don't mind (2) much either, but on the whole I prefer (3), mostly
because it will allow us to make registration optional (if we use OIDs)
and because it will allow the hint data structure to evolve in ways that
pseudo-enctypes simply can't.