[kitten] Kerberos preauth negotiation techniques

Greg Hudson <ghudson@mit.edu> Wed, 11 February 2015 18:36 UTC

Return-Path: <ghudson@mit.edu>
X-Original-To: kitten@ietfa.amsl.com
Delivered-To: kitten@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 982B61A1A5B for <kitten@ietfa.amsl.com>; Wed, 11 Feb 2015 10:36:04 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.312
X-Spam-Status: No, score=-2.312 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id Gzoi58HbePR9 for <kitten@ietfa.amsl.com>; Wed, 11 Feb 2015 10:36:02 -0800 (PST)
Received: from dmz-mailsec-scanner-1.mit.edu (dmz-mailsec-scanner-1.mit.edu []) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C06AB1A1A83 for <kitten@ietf.org>; Wed, 11 Feb 2015 10:36:01 -0800 (PST)
X-AuditID: 1209190c-f79696d000005933-a4-54dba1102e95
Received: from mailhub-auth-4.mit.edu ( []) (using TLS with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by dmz-mailsec-scanner-1.mit.edu (Symantec Messaging Gateway) with SMTP id 1C.33.22835.011ABD45; Wed, 11 Feb 2015 13:36:00 -0500 (EST)
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu []) by mailhub-auth-4.mit.edu (8.13.8/8.9.2) with ESMTP id t1BIZxj7006858 for <kitten@ietf.org>; Wed, 11 Feb 2015 13:36:00 -0500
Received: from localhost (equal-rites.mit.edu []) (authenticated bits=0) (User authenticated as ghudson@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.8/8.12.4) with ESMTP id t1BIZwEL022277 for <kitten@ietf.org>; Wed, 11 Feb 2015 13:35:59 -0500
From: Greg Hudson <ghudson@mit.edu>
To: kitten@ietf.org
Date: Wed, 11 Feb 2015 13:35:58 -0500
Message-ID: <x7da90k47ox.fsf@equal-rites.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrOIsWRmVeSWpSXmKPExsUixG6nriuw8HaIwbnNChZHN69icWD0WLLk J1MAYxSXTUpqTmZZapG+XQJXxpyvT9gLVmpW/Lz4j62BcY9iFyMnh4SAicSs9TNZIGwxiQv3 1rN1MXJxCAksZpI4NGMzI4RznFHi9qd/7BBOB5PE3zPXWEFa2ASUJdbv3wrWLiIgLLF76ztm EFtYwEBib8d7MJtFQFXizKJ/YPW8AoYSPR07GSFsQYmTM5+A9TILSEgcfPGCeQIjzywkqVlI UgsYmVYxyqbkVunmJmbmFKcm6xYnJ+blpRbpGurlZpbopaaUbmIEhQenJM8OxjcHlQ4xCnAw KvHwemy9FSLEmlhWXJl7iFGSg0lJlHf9tNshQnxJ+SmVGYnFGfFFpTmpxYcYJTiYlUR4K2YB 5XhTEiurUovyYVLSHCxK4rybfvCFCAmkJ5akZqemFqQWwWRlODiUJHh3zAdqFCxKTU+tSMvM KUFIM3FwggznARpuuwBkeHFBYm5xZjpE/hSjopQ47wmQZgGQREZpHlwvLH5fMYoDvSLMewCk igcY+3Ddr4AGMwENnjgDbHBJIkJKqoHRQN6/9gK71In9c7TnrAqXuSulO+d2bnvj6tz8maud 5bIZVsaqBk85suywTqxYKntw/8Zc781sD7jsc6pZrvtenHAu+CRb2f2XVdz/dJzmJn7aJTZF ++3H90L5O+2Zjjx4WWZSfjLimpFv364FO/7xH49JObPwwP0FYsEmaXasD1el3RJcvslXiaU4 I9FQi7moOBEApu5JKLoCAAA=
Archived-At: <http://mailarchive.ietf.org/arch/msg/kitten/lDlCSlq5PasuS0WduGP7CLoKfXM>
Subject: [kitten] Kerberos preauth negotiation techniques
X-BeenThere: kitten@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Common Authentication Technologies - Next Generation <kitten.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/kitten>, <mailto:kitten-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/kitten/>
List-Post: <mailto:kitten@ietf.org>
List-Help: <mailto:kitten-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/kitten>, <mailto:kitten-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 11 Feb 2015 18:36:04 -0000

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

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

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?