Subject: [kitten] GSS extension to minimize need for replay caching: indication of use/non-use of PROT_READY

From: Nico Williams <[email-masked]>
Date: Tue, 26 Apr 2011 14:51:43 -0500

I've been looking for ways to minimize the need to have replay caching
of AP-REQs/Authenticators in the Kerberos V5 mechanism.  I've come up
with a few methods that generalize (there are other mechanism designs
which might require replay caching).

Here's one based on the fact that most GSS-API applications do not
make use of PROT_READY _and_ have the initiator send the first
per-message token:

 - Add a req_flag named GSS_C_PROT_READY_NOT_USED, to be used by
initiator applications that know they will not make use of PROT_READY.
- [OPTIONAL] Add a supplementary major status code
GSS_S_PROT_READY_USED to be returned by GSS_Unwrap() and
GSS_VerifyMIC().

How it works:

 - Raw Kerberos implementations should reject AP-REQs whose
Authenticators' checksum fields have a "checksum" of type 0x8003 which
appears to have the GSS_C_PROT_READY_NOT_USED flag set.  This prevents
cut-n-paste attacks that steal AP-REQs from initial context tokens for
the krb5 mech and play them to raw krb5 apps.
 - krb5 mech acceptors will delay use of a replay cache such that if
the initiator's first per-message token uses the acceptor-asserted
sub-session key, then the replay cache will not be used at all, else
it will be.  (The acceptor has to be sure that the first per-message
token received has the expected initial sequence number.  Also, it may
be possible to allow PROT_READY MIC tokens and still avoid the need
for a replay cache, but this needs careful analysis.)
 - [OPTIONAL] Applications that expect the peer to not use PROT_READY
should check for and react accordingly (e.g., terminate the
connection) to the presence of the GSS_S_PROT_READY_USED supplementary
status code in major status values returned by GSS_Unwrap() and
GSS_VerifyMIC().

The Kerberos V5 mechanism can make this work reliably only when using
RFC4121 (i.e., newer enctypes), since use of the acceptor's sub-key is
critical to preventing replays.

Existing GSS applications that *do* make use of PROT_READY will be
affected IFF we include the supplementary code mentioned above and
they are coded to not accept per-message tokens which yielded
GSS_S_COMPLETE and a supplementary status code.  I suspect that there
are not very many such applications, and, indeed, I believe there
ought to be none since applications should check for supplementary
status codes.  I think it's reasonable to believe that supplementary
status codes were intended to be non-critical and to allow for future
additions, though this is debatable, and I look forward to hearing
your opinions on this, and am open to being convinced of the opposite
(particularly since a new supplementary status code is not strictly
necessary).

Deployment on systems that have multiple Kerberos implementations may
be difficult, since it is critical to first deploy the change that
prevents cut-n-paste attacks on systems that use GSS and raw krb5 for
the same acceptor/service principals.  However, I believe it may still
be worthwhile.

Also, note that this extension generalizes to other mechanisms.
Consider Solaris' mech_dh, for example.  mech_dh uses DH public keys
published in a directory to obtain a shared secret key before any
tokens have even been exchanged -- a design that lends itself quite
well to the same 1/2 and 1 round-trip options that Kerberos V5 offers,
and which too would require replay caching when those 1/2 and 1
round-trip options are used.

The mech_dh design also can avoid replay caching by using "DCE style"
3/2 round-trip security token exchanges, like the Kerberos V5
mechanism.  Extensions to negotiate the use of 3/2 round-trips are
another avenue for replay cache avoidance, and I have a proposal to
make along those lines, but it has the problematic feature of
requiring that the KDC know whether a service is able to use such an
extension.

I do believe that it is possible to build very high-performance,
secure replay caches by making certain trade-offs regarding maximum
allowable client clock skew into the future, and by reducing the
maximum allowable client clock skew into the past after reboots.
Indeed, I have implemented such a thing.  And yet I believe it would
be simpler and better if we just avoid replay caches altogether.  I
would very much like to explore replay cache avoidance.

Comments?

Nico
--

---

From: Luke Howard <[email-masked]>
Date: Tue, 26 Apr 2011 22:41:04 +0200

> requiring that the KDC know whether a service is able to use such an

I didn't read through this all in detail so please excuse the possibly dumb question. Why does the KDC need to know if DCE_STYLE is available?

The initiator could try (and fallback to non-DCE style) or another OID could be used and it negotiated via SPNEGO.

-- Luke

---

From: Nico Williams <[email-masked]>
Date: Tue, 26 Apr 2011 16:13:36 -0500

> I didn't read through this all in detail so please excuse the possibly dumb question. Why does the KDC need to know if DCE_STYLE is available?

Great question.  Maybe I misunderstand DCE style (I hope so!), but
IIUC: there's no way for the acceptor to indicate that it understood
the initiator's request to engage in DCE style, so there's no way for
the initiator to know if the acceptor will be expecting one more
context token or not.

> The initiator could try (and fallback to non-DCE style) or another OID could be used and it negotiated via SPNEGO.

Another OID has the same problem, only worse.  As for SPNEGO, if the
app protocol in question wasn't already using it, then you have the
same problem as with a new OID.

Now, DCE style would always remove the need for a replay cache.  My
solution doesn't always eliminate the rcache, just often (i.e., when
using AES) and for most apps, hopefully often enough -- and without
negotiation.  There is an acceptor-side local configuration issue in
my proposal: the acceptor must not skip the rcache unless configured
to because other raw krb5 apps also implement the check I mentioned.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Tue, 26 Apr 2011 16:41:08 -0500

My proposal does have a flaw for apps that use neither channel binding
nor per-message tokens.  But then, such apps should not exist, as they
are not secure.  I'm willing to live with that as an acceptor-side
configuration parameter.

---

From: Martin Rex <[email-masked]>
Date: Wed, 27 Apr 2011 01:25:15 +0200 (MEST)

> are not secure.  I'm willing to live with that as an acceptor-side

Those apps do exist.  They're implementations of rfc-4559
"HTTP Negotiate", prior to the use of channel bindings.

I don't know whether TLS channel bindings for rfc-4559 were retrofitted
into Kerberos&SChannel&MSIE for  Windows XP.  If not, then it about 50%
of the installed base doing this (all versions of MSIE on XP).

Your scheme also does not work for apps that (for whatever reason)
do not request MUTUAL_AUTH at the GSS-API level--which results
in a 1-token security context establishment equivalent to PROT_READY,
and with the same app-side rationale as for using PROT_READY.

An initiator is not limited to sending only a single protected message
with PROT_READY.  It could transfer millions of protected messages
before processing the context token response from the server.

-Martin

---

From: Nico Williams <[email-masked]>
Date: Tue, 26 Apr 2011 20:46:34 -0500

> "HTTP Negotiate", prior to the use of channel bindings.

Not really.  Prior to CB HTTP/Negotiate did not do mutual auth, so
replay caches are unavoidable.  And if using CB then we have to use a
replay cache too (because we don't know if the CB type is tls-unique
or something else that isn't unique).

(Also, because HTTP/Negotiate uses the "HTTP" service name one could
always hardcode or configure the acceptor to always use a replay cache
for HTTP.)

To avoid replay caching in protocols that use CB really does require a
3-legged security context token exchange (or longer).

> and with the same app-side rationale as for using PROT_READY.

I know I didn't mention non-mutual auth apps, but I figured it'd be
clear that the replay cache is not avoidable in those.  I'm trying to
avoid replay caches in a common sub-set of cases, not all.  (Though
I'd rather never have to use a replay cache either -- don't get me
wrong.  It's just that it's not possible to avoid a replay cache and
have a 1/2 round-trip sec context token exchange.

> before processing the context token response from the server.

Of course.  But if the initiator's first per-message token (by
sequence number!) is not a PROT_READY token then it can act as the
confirmation of the acceptor's sub-session key -- that's the trick.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Thu, 28 Apr 2011 11:03:00 -0400

How well does this work for mechanisms like GS2 that never send a
per-message token?

---

From: Sam Hartman <[email-masked]>
Date: Thu, 28 Apr 2011 11:22:45 -0400

Note that in practice no one actually uses replay caches for HTTP.
Make what you will of the security.
(Well IIS may, although I doubt it, but no one else does.)

---

From: Nico Williams <[email-masked]>
Date: Thu, 28 Apr 2011 10:31:08 -0500

> How well does this work for mechanisms like GS2 that never send a

As I initially proposed, it doesn't.  If we add some API by which the
acceptor app can tell GSS that this protocol doesn't need a replay
cache, that might be a lot better.  I was trying to avoid having to
add new functions, but it seems unavoidable.

---

From: "Henry B. Hotz" <[email-masked]>
Date: Thu, 28 Apr 2011 12:57:24 -0700

> (Well IIS may, although I doubt it, but no one else does.)

Always intended to try it.  The original reasons for that are supposed to have been fixed.  My fear is that bugs in the replay cache code will break complex web sites.  In other words, it won't work.

------------------------------------------------------
The opinions expressed in this message are mine,
not those of Caltech, JPL, NASA, or the US Government.
[email-masked], or [email-masked]

---

From: Paul Leach <[email-masked]>
Date: Fri, 29 Apr 2011 18:53:24 +0000

I don't see in principal how, in a  protocol whose authenticator is a signed timestamp supplied in the initial protocol message, one can ever avoid needing to detect replay of the signed timestamp. Hence, the description in the post in terms of Kerb protocol details fails to convince -- just leaves me feeling I can't find a flaw that must exist. 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Nico Williams
Sent: Tuesday, April 26, 2011 12:52 PM
To: [email-masked]
Subject: [kitten] GSS extension to minimize need for replay caching: indication of use/non-use of PROT_READY

---

From: Paul Leach <[email-masked]>
Date: Fri, 29 Apr 2011 19:09:54 +0000

Never mind. I realize I asked myself a trick question: the answer is that you don't need replay detection for the authenticator when the authenticator isn't used in any essential way in the authentication. E.g., if the only thing that matters is proving knowledge of the (sub)session key in the ticket on each (app protocol) message after authentication completes.