* gc_frm_kdc.c: Rewrite to modularize significantly. (~400-line

	functions do not deserve to live.)  The outer loop no longer
	explicitly attempts the direct path to the target; that attempt
	has been folded into the inner loop.  Remove some redundant
	credential lookups present in the old code.  Treat unexpected
	realm referrals as soft errors, in case some intermediate KDC
	disagrees with client regarding a transit path.

git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@17579 dc483132-0cff-0310-8789-dd5450dbe970

2 files changed, 752 insertions, 381 deletions

diff --git a/src/lib/krb5/krb/ChangeLog b/src/lib/krb5/krb/ChangeLog
index 8c91b1a60c..93047c5bd5 100644
--- a/src/lib/krb5/krb/ChangeLog
+++ b/src/lib/krb5/krb/ChangeLog
@@ -1,3 +1,13 @@
+2005-12-30  Tom Yu  <tlyu@mit.edu>
+
+	* gc_frm_kdc.c: Rewrite to modularize significantly.  (~400-line
+	functions do not deserve to live.)  The outer loop no longer
+	explicitly attempts the direct path to the target; that attempt
+	has been folded into the inner loop.  Remove some redundant
+	credential lookups present in the old code.  Treat unexpected
+	realm referrals as soft errors, in case some intermediate KDC
+	disagrees with client regarding a transit path.
+
 2005-12-28  Tom Yu  <tlyu@mit.edu>
 
 	* gc_frm_kdc.c (krb5_get_cred_from_kdc_opt): Cause free_tgt and
diff --git a/src/lib/krb5/krb/gc_frm_kdc.c b/src/lib/krb5/krb/gc_frm_kdc.c
index a4a0118f6a..807b81a86d 100644
--- a/src/lib/krb5/krb/gc_frm_kdc.c
+++ b/src/lib/krb5/krb/gc_frm_kdc.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1994,2003 by the Massachusetts Institute of Technology.
+ * Copyright (c) 1994,2003,2005 by the Massachusetts Institute of Technology.
  * Copyright (c) 1994 CyberSAFE Corporation
  * Copyright (c) 1993 Open Computing Security Group
  * Copyright (c) 1990,1991 by the Massachusetts Institute of Technology.
@@ -25,8 +25,9 @@
  * this software for any purpose.  It is provided "as is" without express
  * or implied warranty.
  * 
- * krb5_get_cred_from_kdc()
- * Get credentials from some KDC somewhere, possibly accumulating tgts
+ * krb5_get_cred_from_kdc() and related functions:
+ *
+ * Get credentials from some KDC somewhere, possibly accumulating TGTs
  * along the way.
  */
 
@@ -34,431 +35,791 @@
 #include <stdio.h>
 #include "int-proto.h"
 
+struct tr_state;
+
 /*
- * Retrieve credentials for principal in_cred->client,
- * server in_cred->server, ticket flags creds->ticket_flags, possibly
- * second_ticket if needed by ticket_flags.
- * 
- * Credentials are requested from the KDC for the server's realm.  Any
- * TGT credentials obtained in the process of contacting the KDC are
- * returned in an array of credentials; tgts is filled in to point to an
- * array of pointers to credential structures (if no TGT's were used, the
- * pointer is zeroed).  TGT's may be returned even if no useful end ticket
- * was obtained.
- * 
- * The returned credentials are NOT cached.
+ * Ring buffer abstraction for TGTs returned from a ccache; avoids
+ * lots of excess copying.
+ */
+
+#define NCC_TGTS 2
+struct cc_tgts {
+    krb5_creds cred[NCC_TGTS];
+    int dirty[NCC_TGTS];
+    unsigned int cur, nxt;
+};
+
+/* NOTE: This only checks if NXT_TGT is CUR_CC_TGT. */
+#define NXT_TGT_IS_CACHED(ts)			\
+	((ts)->nxt_tgt == (ts)->cur_cc_tgt)
+
+#define MARK_CUR_CC_TGT_CLEAN(ts)			\
+do {							\
+	(ts)->cc_tgts.dirty[(ts)->cc_tgts.cur] = 0;	\
+} while (0)
+
+static void init_cc_tgts(struct tr_state *);
+static void shift_cc_tgts(struct tr_state *);
+static void clean_cc_tgts(struct tr_state *);
+
+/*
+ * State struct for do_traversal() and helpers.
  *
- * This routine should not be called if the credentials are already in
- * the cache.
- * 
- * If credentials are obtained, creds is filled in with the results;
- * creds->ticket and creds->keyblock->key are set to allocated storage,
- * which should be freed by the caller when finished.
- * 
- * returns errors, system errors.
+ * CUR_TGT and NXT_TGT can each point either into CC_TGTS or into
+ * KDC_TGTS.
+ *
+ * CUR_TGT is the "working" TGT, which will be used to obtain new
+ * TGTs.  NXT_TGT will be CUR_TGT for the next iteration of the loop.
+ *
+ * Part of the baroqueness of this setup is to deal with annoying
+ * differences between krb5_cc_retrieve_cred() and
+ * krb5_get_cred_via_tkt(); krb5_cc_retrieve_cred() fills in a
+ * caller-allocated krb5_creds, while krb5_get_cred_via_tkt()
+ * allocates a krb5_creds for return.
  */
+struct tr_state {
+    krb5_context ctx;
+    krb5_ccache ccache;
+    krb5_principal *kdc_list;
+    unsigned int nkdcs;
+    krb5_principal *cur_kdc;
+    krb5_principal *nxt_kdc;
+    krb5_principal *lst_kdc;
+    krb5_creds *cur_tgt;
+    krb5_creds *nxt_tgt;
+    krb5_creds **kdc_tgts;
+    struct cc_tgts cc_tgts;
+    krb5_creds *cur_cc_tgt;
+    krb5_creds *nxt_cc_tgt;
+    unsigned int ntgts;
+};
 
-/* helper macro: convert flags to necessary KDC options */
+/*
+ * Debug support
+ */
+#ifdef DEBUG_GC_FRM_KDC
+
+#define TR_DBG(ts, prog) tr_dbg(ts, prog)
+#define TR_DBG_RET(ts, prog, ret) tr_dbg_ret(ts, prog, ret)
+#define TR_DBG_RTREE(ts, prog, princ) tr_dbg_rtree(ts, prog, princ)
+
+static void tr_dbg(struct tr_state *, const char *);
+static void tr_dbg_ret(struct tr_state *, const char *, krb5_error_code);
+static void tr_dbg_rtree(struct tr_state *, const char *, krb5_principal);
+
+#else
 
+#define TR_DBG(ts, prog)
+#define TR_DBG_RET(ts, prog, ret)
+#define TR_DBG_RTREE(ts, prog, princ)
+
+#endif /* !DEBUG_GC_FRM_KDC */
+
+/* Convert ticket flags to necessary KDC options */
 #define FLAGS2OPTS(flags) (flags & KDC_TKT_COMMON_MASK)
 
-static krb5_error_code
-krb5_get_cred_from_kdc_opt(krb5_context context, krb5_ccache ccache,
-			   krb5_creds *in_cred, krb5_creds **out_cred,
-			   krb5_creds ***tgts, int kdcopt)
+/*
+ * Certain krb5_cc_retrieve_cred() errors are soft errors when looking
+ * for a cross-realm TGT.
+ */
+#define HARD_CC_ERR(r) ((r) && (r) != KRB5_CC_NOTFOUND &&	\
+	(r) != KRB5_CC_NOT_KTYPE)
+
+/*
+ * Flags for ccache lookups of cross-realm TGTs.
+ *
+ * A cross-realm TGT may be issued by some other intermediate realm's
+ * KDC, so we use KRB5_TC_MATCH_SRV_NAMEONLY.
+ */
+#define RETR_FLAGS (KRB5_TC_MATCH_SRV_NAMEONLY | KRB5_TC_SUPPORTED_KTYPES)
+
+/*
+ * Prototypes of helper functions
+ */
+static krb5_error_code tgt_mcred(krb5_context, krb5_principal,
+    krb5_principal, krb5_principal, krb5_creds *);
+static krb5_error_code retr_local_tgt(struct tr_state *, krb5_principal);
+static krb5_error_code try_ccache(struct tr_state *, krb5_creds *);
+static krb5_error_code find_nxt_kdc(struct tr_state *);
+static krb5_error_code try_kdc(struct tr_state *, krb5_creds *);
+static krb5_error_code kdc_mcred(struct tr_state *, krb5_principal,
+    krb5_creds *mcreds);
+static krb5_error_code next_closest_tgt(struct tr_state *, krb5_principal);
+static krb5_error_code init_rtree(struct tr_state *,
+    krb5_principal, krb5_principal);
+static krb5_error_code do_traversal(krb5_context ctx, krb5_ccache,
+    krb5_principal client, krb5_principal server,
+    krb5_creds *out_cc_tgt, krb5_creds **out_tgt,
+    krb5_creds ***out_kdc_tgts);
+static krb5_error_code krb5_get_cred_from_kdc_opt(krb5_context, krb5_ccache,
+    krb5_creds *, krb5_creds **, krb5_creds ***, int);
+
+/*
+ * init_cc_tgts()
+ *
+ * Initialize indices for cached-TGT ring buffer.  Caller must zero
+ * CC_TGTS, CC_TGT_DIRTY arrays prior to calling.
+ */
+static void
+init_cc_tgts(struct tr_state *ts)
 {
-    krb5_creds      **ret_tgts = NULL;
-    int             ntgts = 0;
 
-    krb5_creds      tgt, tgtq, *tgtr = NULL, otgt;
+    ts->cc_tgts.cur = 0;
+    ts->cc_tgts.nxt = 1;
+    ts->cur_cc_tgt = &ts->cc_tgts.cred[0];
+    ts->nxt_cc_tgt = &ts->cc_tgts.cred[1];
+}
+
+/*
+ * shift_cc_tgts()
+ *
+ * Given a fresh assignment to NXT_CC_TGT, mark NXT_CC_TGT as dirty,
+ * and shift indices so old NXT_CC_TGT becomes new CUR_CC_TGT.  Clean
+ * the new NXT_CC_TGT.
+ */
+static void
+shift_cc_tgts(struct tr_state *ts)
+{
+    unsigned int i;
+    struct cc_tgts *rb;
+
+    rb = &ts->cc_tgts;
+    i = rb->cur = rb->nxt;
+    rb->dirty[i] = 1;
+    ts->cur_cc_tgt = ts->nxt_cc_tgt;
+
+    i = (i + 1) % NCC_TGTS;
+
+    rb->nxt = i;
+    ts->nxt_cc_tgt = &rb->cred[i];
+    if (rb->dirty[i]) {
+	krb5_free_cred_contents(ts->ctx, &rb->cred[i]);
+	rb->dirty[i] = 0;
+    }
+}
+
+/*
+ * clean_cc_tgts()
+ *
+ * Free CC_TGTS which were dirty, then mark them clean.
+ */
+static void
+clean_cc_tgts(struct tr_state *ts)
+{
+    unsigned int i;
+    struct cc_tgts *rb;
+
+    rb = &ts->cc_tgts;
+    for (i = 0; i < NCC_TGTS; i++) {
+	if (rb->dirty[i]) {
+	    krb5_free_cred_contents(ts->ctx, &rb->cred[i]);
+	    rb->dirty[i] = 0;
+	}
+    }
+}
+
+/*
+ * Debug support
+ */
+#ifdef DEBUG_GC_FRM_KDC
+static void
+tr_dbg(struct tr_state *ts, const char *prog)
+{
     krb5_error_code retval;
-    krb5_principal  int_server = NULL;    /* Intermediate server for request */
+    char *cur_tgt_str, *cur_kdc_str, *nxt_kdc_str;
+
+    cur_tgt_str = cur_kdc_str = nxt_kdc_str = NULL;
+    retval = krb5_unparse_name(ts->ctx, ts->cur_tgt->server, &cur_tgt_str);
+    if (retval) goto cleanup;
+    retval = krb5_unparse_name(ts->ctx, *ts->cur_kdc, &cur_kdc_str);
+    if (retval) goto cleanup;
+    retval = krb5_unparse_name(ts->ctx, *ts->nxt_kdc, &nxt_kdc_str);
+    if (retval) goto cleanup;
+    fprintf(stderr, "%s: cur_tgt %s\n", prog, cur_tgt_str);
+    fprintf(stderr, "%s: cur_kdc %s\n", prog, cur_kdc_str);
+    fprintf(stderr, "%s: nxt_kdc %s\n", prog, nxt_kdc_str);
+cleanup:
+    if (cur_tgt_str)
+	krb5_free_unparsed_name(ts->ctx, cur_tgt_str);
+    if (cur_kdc_str)
+	krb5_free_unparsed_name(ts->ctx, cur_kdc_str);
+    if (nxt_kdc_str)
+	krb5_free_unparsed_name(ts->ctx, nxt_kdc_str);
+}
+
+static void
+tr_dbg_ret(struct tr_state *ts, const char *prog, krb5_error_code ret)
+{
+    fprintf(stderr, "%s: return %d (%s)\n", prog, (int)ret,
+	    error_message(ret));
+}
 
-    krb5_principal  *tgs_list = NULL;
-    krb5_principal  *top_server = NULL;
-    krb5_principal  *next_server = NULL;
-    unsigned int    nservers = 0;
-    krb5_boolean	  old_use_conf_ktypes = context->use_conf_ktypes;
-    int		    retr_flags = KRB5_TC_MATCH_SRV_NAMEONLY | KRB5_TC_SUPPORTED_KTYPES;
-    int		    free_tgt = 0, free_otgt = 0;
+static void
+tr_dbg_rtree(struct tr_state *ts, const char *prog, krb5_principal princ)
+{
+    char *str;
 
-    /* in case we never get a TGT, zero the return */
+    if (krb5_unparse_name(ts->ctx, princ, &str))
+	return;
+    fprintf(stderr, "%s: %s\n", prog, str);
+    krb5_free_unparsed_name(ts->ctx, str);
+}
+#endif /* DEBUG_GC_FRM_KDC */
 
-    *tgts = NULL;
-     
-    memset((char *)&tgtq, 0, sizeof(tgtq));
-    memset((char *)&tgt, 0, sizeof(tgt));
-    memset((char *)&otgt, 0, sizeof(otgt));
+/*
+ * tgt_mcred()
+ *
+ * Return MCREDS for use as a match criterion.
+ *
+ * Resulting credential has CLIENT as the client principal, and
+ * krbtgt/realm_of(DST)@realm_of(SRC) as the server principal.  Zeroes
+ * MCREDS first, does not allocate MCREDS, and cleans MCREDS on
+ * failure.  The peculiar ordering of DST and SRC args is for
+ * consistency with krb5_tgtname().
+ */
+static krb5_error_code
+tgt_mcred(krb5_context ctx, krb5_principal client,
+	  krb5_principal dst, krb5_principal src,
+	  krb5_creds *mcreds)
+{
+    krb5_error_code retval;
 
-    /*
-     * we know that the desired credentials aren't in the cache yet.
-     *
-     * To get them, we first need a tgt for the realm of the server.
-     * first, we see if we have such a TGT in cache.  if not, then
-     * we ask the kdc to give us one.  if that doesn't work, then
-     * we try to get a tgt for a realm that is closest to the target.
-     * once we have that, then we ask that realm if it can give us
-     * tgt for the target.  if not, we do the process over with this
-     * new tgt.
-     */
-  
-    /*
-     * (the ticket may be issued by some other intermediate
-     *  realm's KDC; so we use KRB5_TC_MATCH_SRV_NAMEONLY)
-     */
-    if ((retval = krb5_copy_principal(context, in_cred->client, &tgtq.client)))
+    retval = 0;
+    memset(mcreds, 0, sizeof(*mcreds));
+
+    retval = krb5_copy_principal(ctx, client, &mcreds->client);
+    if (retval)
 	goto cleanup;
 
-    /* get target tgt from cache */
-    if ((retval = krb5_tgtname(context,
-			       krb5_princ_realm(context, in_cred->server),
-			       krb5_princ_realm(context, in_cred->client),
-			       &int_server))) {
+    retval = krb5_tgtname(ctx, krb5_princ_realm(ctx, dst),
+			  krb5_princ_realm(ctx, src), &mcreds->server);
+    if (retval)
 	goto cleanup;
+
+cleanup:
+    if (retval)
+	krb5_free_cred_contents(ctx, mcreds);
+
+    return retval;
+}
+
+/*
+ * init_rtree()
+ *
+ * Populate KDC_LIST with the output of krb5_walk_realm_tree().
+ */
+static krb5_error_code
+init_rtree(struct tr_state *ts,
+	   krb5_principal client, krb5_principal server)
+{
+    krb5_error_code retval;
+
+    ts->kdc_list = NULL;
+    retval = krb5_walk_realm_tree(ts->ctx, krb5_princ_realm(ts->ctx, client),
+				  krb5_princ_realm(ts->ctx, server),
+				  &ts->kdc_list, KRB5_REALM_BRANCH_CHAR);
+    if (retval)
+	return retval;
+
+    for (ts->nkdcs = 0; ts->kdc_list[ts->nkdcs]; ts->nkdcs++) {
+	assert(krb5_princ_size(ts->ctx, ts->kdc_list[ts->nkdcs]) == 2);
+	TR_DBG_RTREE(ts, "init_rtree", ts->kdc_list[ts->nkdcs]);
     }
+    assert(ts->nkdcs > 1);
+    ts->lst_kdc = ts->kdc_list + ts->nkdcs - 1;
 
-    if ((retval = krb5_copy_principal(context, int_server, &tgtq.server))) {
-	goto cleanup;
+    ts->kdc_tgts = calloc(ts->nkdcs + 1, sizeof(krb5_creds));
+    if (ts->kdc_tgts == NULL)
+	return ENOMEM;
+
+    return 0;
+}
+
+/*
+ * retr_local_tgt()
+ *
+ * Prime CUR_TGT with the cached TGT of the client's local realm.
+ */
+static krb5_error_code
+retr_local_tgt(struct tr_state *ts, krb5_principal client)
+{
+    krb5_error_code retval;
+    krb5_creds tgtq;
+
+    memset(&tgtq, 0, sizeof(tgtq));
+    retval = tgt_mcred(ts->ctx, client, client, client, &tgtq);
+    if (retval)
+	return retval;
+
+    /* Match realm, unlike other ccache retrievals here. */
+    retval = krb5_cc_retrieve_cred(ts->ctx, ts->ccache,
+				   KRB5_TC_SUPPORTED_KTYPES,
+				   &tgtq, ts->nxt_cc_tgt);
+    krb5_free_cred_contents(ts->ctx, &tgtq);
+    if (!retval) {
+	shift_cc_tgts(ts);
+	ts->nxt_tgt = ts->cur_tgt = ts->cur_cc_tgt;
     }
+    return retval;
+}
 
-    context->use_conf_ktypes = 1;
-    retval = krb5_cc_retrieve_cred(context, ccache, retr_flags, &tgtq, &tgt);
-    if (retval == 0) {
-        free_tgt = 1;
-	/* Falls through to the got/finally have tgt */
-    } else {
-	if (retval != KRB5_CC_NOTFOUND && retval != KRB5_CC_NOT_KTYPE) {
-	    goto cleanup;
-	}
+/*
+ * try_ccache()
+ *
+ * Attempt to retrieve desired NXT_TGT from ccache.  Point NXT_TGT to
+ * it if successful.
+ */
+static krb5_error_code
+try_ccache(struct tr_state *ts, krb5_creds *tgtq)
+{
+    krb5_error_code retval;
 
+    TR_DBG(ts, "try_ccache");
+    retval = krb5_cc_retrieve_cred(ts->ctx, ts->ccache, RETR_FLAGS,
+				   tgtq, ts->nxt_cc_tgt);
+    if (!retval) {
+	shift_cc_tgts(ts);
+	ts->nxt_tgt = ts->cur_cc_tgt;
+    }
+    TR_DBG_RET(ts, "try_ccache", retval);
+    return retval;
+}
+
+/*
+ * find_nxt_kdc()
+ *
+ * A NXT_TGT gotten from an intermediate KDC might actually be a
+ * referral.  Search KDC_LIST forward starting from CUR_KDC, looking
+ * for the KDC with the same remote realm as NXT_TGT.  If we don't
+ * find it, the intermediate KDC is leading us off the transit path.
+ *
+ * Match on CUR_KDC's remote realm, not local realm, because, among
+ * other reasons, we can get a referral to the final realm; e.g.,
+ * given
+ *
+ *     KDC_LIST == { krbtgt/R1@R1, krbtgt/R2@R1, krbtgt/R3@R2,
+ *                   krbtgt/R4@R3, NULL }
+ *     CUR_TGT->SERVER == krbtgt/R2@R1
+ *     NXT_TGT->SERVER == krbtgt/R4@R2
+ *
+ * i.e., we got a ticket issued by R2 with remote realm R4, we want to
+ * find krbtgt/R4@R3, not krbtgt/R3@R2, even though we have no TGT
+ * with R3 as its local realm.
+ *
+ * Set up for next iteration of do_traversal() loop by pointing
+ * NXT_KDC to one entry forward of the match.
+ */
+static krb5_error_code
+find_nxt_kdc(struct tr_state *ts)
+{
+    krb5_data *r1, *r2;
+    krb5_principal *kdcptr;
+
+    TR_DBG(ts, "find_nxt_kdc");
+    assert(ts->nxt_tgt == ts->kdc_tgts[ts->ntgts-1]);
+    if (krb5_princ_size(ts->ctx, ts->nxt_tgt->server) != 2)
+	return KRB5_KDCREP_MODIFIED;
+
+    r1 = krb5_princ_component(ts->ctx, ts->nxt_tgt->server, 1);
+
+    for (kdcptr = ts->cur_kdc + 1; *kdcptr != NULL; kdcptr++) {
+
+	r2 = krb5_princ_component(ts->ctx, *kdcptr, 1);
+
+	if (r1 != NULL && r2 != NULL &&
+	    r1->length == r2->length &&
+	    !memcmp(r1->data, r2->data, r1->length)) {
+	    break;
+	}
+    }
+    if (*kdcptr == NULL) {
 	/*
-	 * Note that we want to request a TGT from our local KDC, even
-	 * if we already have a TGT for some intermediate realm.  The 
-	 * reason is that our local KDC may have a shortcut to the
-	 * destination realm, and if it does we want to use the
-	 * shortcut because it will provide greater security. - bcn
-	 */
-  
-	/*
-	 * didn't find it in the cache so it is time to get a local
-	 * tgt and walk the realms tree.
+	 * Not found; we probably got an unexpected realm referral.
+	 * Don't touch NXT_KDC, thus allowing next_closest_tgt() to
+	 * continue looping backwards.
 	 */
-	krb5_free_principal(context, int_server);
-	int_server = NULL;
-	if ((retval = krb5_tgtname(context, 
-				   krb5_princ_realm(context, in_cred->client),
-				   krb5_princ_realm(context, in_cred->client),
-				   &int_server))) {
-	    goto cleanup;
+	if (ts->ntgts > 0) {
+	    /* Punt NXT_TGT from KDC_TGTS if bogus. */
+	    krb5_free_creds(ts->ctx, ts->kdc_tgts[--ts->ntgts]);
 	}
-  
-	krb5_free_cred_contents(context, &tgtq);
-	memset((char *)&tgtq, 0, sizeof(tgtq));
-	if ((retval = krb5_copy_principal(context, in_cred->client,
-					  &tgtq.client)))
-	    goto cleanup;
-	if ((retval = krb5_copy_principal(context, int_server, &tgtq.server)))
-	    goto cleanup;
+	TR_DBG_RET(ts, "find_nxt_kdc", KRB5_KDCREP_MODIFIED);
+	return KRB5_KDCREP_MODIFIED;
+    }
+    ts->nxt_kdc = kdcptr;
+    TR_DBG_RET(ts, "find_nxt_kdc", 0);
+    return 0;
+}
 
-	if ((retval = krb5_cc_retrieve_cred(context, ccache,
-					    retr_flags,
-					    &tgtq, &tgt))) {
-	    goto cleanup;
-	}
-	free_tgt = 1;
-  
-	/* get a list of realms to consult */
-  
-	if ((retval = krb5_walk_realm_tree(context, 
-					   krb5_princ_realm(context,
-							    in_cred->client),
-					   krb5_princ_realm(context,
-							    in_cred->server),
-					   &tgs_list, 
-					   KRB5_REALM_BRANCH_CHAR))) {
+/*
+ * try_kdc()
+ *
+ * Using CUR_TGT, attempt to get desired NXT_TGT.  Update NXT_KDC if
+ * successful.
+ */
+static krb5_error_code
+try_kdc(struct tr_state *ts, krb5_creds *tgtq)
+{
+    krb5_error_code retval;
+    krb5_creds ltgtq;
+
+    TR_DBG(ts, "try_kdc");
+    /* This check should probably be in gc_via_tkt. */
+    if (!krb5_c_valid_enctype(ts->cur_tgt->keyblock.enctype))
+	return KRB5_PROG_ETYPE_NOSUPP;
+
+    ltgtq = *tgtq;
+    ltgtq.is_skey = FALSE;
+    ltgtq.ticket_flags = ts->cur_tgt->ticket_flags;
+    retval = krb5_get_cred_via_tkt(ts->ctx, ts->cur_tgt,
+				   FLAGS2OPTS(ltgtq.ticket_flags),
+				   ts->cur_tgt->addresses,
+				   &ltgtq, &ts->kdc_tgts[ts->ntgts++]);
+    if (retval) {
+	ts->ntgts--;
+	ts->nxt_tgt = ts->cur_tgt;
+	TR_DBG_RET(ts, "try_kdc", retval);
+	return retval;
+    }
+    ts->nxt_tgt = ts->kdc_tgts[ts->ntgts-1];
+    retval = find_nxt_kdc(ts);
+    TR_DBG_RET(ts, "try_kdc", retval);
+    return retval;
+}
+
+/*
+ * kdc_mcred()
+ *
+ * Return MCREDS for use as a match criterion.
+ *
+ * Resulting credential has CLIENT as the client principal, and
+ * krbtgt/remote_realm(NXT_KDC)@local_realm(CUR_KDC) as the server
+ * principal.  Zeroes MCREDS first, does not allocate MCREDS, and
+ * cleans MCREDS on failure.
+ */
+static krb5_error_code
+kdc_mcred(struct tr_state *ts, krb5_principal client, krb5_creds *mcreds)
+{
+    krb5_error_code retval;
+    krb5_data *rdst, *rsrc;
+
+    retval = 0;
+    memset(mcreds, 0, sizeof(*mcreds));
+
+    rdst = krb5_princ_component(ts->ctx, *ts->nxt_kdc, 1);
+    rsrc = krb5_princ_component(ts->ctx, *ts->cur_kdc, 1);
+    retval = krb5_copy_principal(ts->ctx, client, &mcreds->client);
+    if (retval)
+	goto cleanup;
+
+    retval = krb5_tgtname(ts->ctx, rdst, rsrc, &mcreds->server);
+    if (retval)
+	goto cleanup;
+
+cleanup:
+    if (retval)
+	krb5_free_cred_contents(ts->ctx, mcreds);
+
+    return retval;
+}
+
+/*
+ * next_closest_tgt()
+ *
+ * Using CUR_TGT, attempt to get the cross-realm TGT having its remote
+ * realm closest to the target principal's.  Update NXT_TGT, NXT_KDC
+ * accordingly.
+ */
+static krb5_error_code
+next_closest_tgt(struct tr_state *ts, krb5_principal client)
+{
+    krb5_error_code retval;
+    krb5_creds tgtq;
+
+    retval = 0;
+    memset(&tgtq, 0, sizeof(tgtq));
+
+    for (ts->nxt_kdc = ts->lst_kdc;
+	 ts->nxt_kdc > ts->cur_kdc;
+	 ts->nxt_kdc--) {
+
+	krb5_free_cred_contents(ts->ctx, &tgtq);
+	retval = kdc_mcred(ts, client, &tgtq);
+	if (retval)
 	    goto cleanup;
+	/* Don't waste time retrying ccache for direct path. */
+	if (ts->cur_kdc != ts->kdc_list || ts->nxt_kdc != ts->lst_kdc) {
+	    retval = try_ccache(ts, &tgtq);
+	    if (!retval)
+		break;
+	    if (HARD_CC_ERR(retval))
+		goto cleanup;
 	}
-  
-	for (nservers = 0; tgs_list[nservers]; nservers++)
-	    ;
-  
-	/* allocate storage for TGT pointers. */
-    
-	if (!(ret_tgts = (krb5_creds **) calloc(nservers+1,
-						sizeof(krb5_creds)))) {
-	    retval = ENOMEM;
-	    goto cleanup;
+	/* Not in the ccache, so talk to a KDC. */
+	retval = try_kdc(ts, &tgtq);
+	if (!retval) {
+	    break;
 	}
-	*tgts = ret_tgts;
-    
 	/*
-	 * step one is to take the current tgt and see if there is a tgt for
-	 * krbtgt/realmof(target)@realmof(tgt).  if not, try to get one with
-	 * the tgt.
-	 *
-	 * if we don't get a tgt for the target, then try to find a tgt as
-	 * close to the target realm as possible. at each step if there isn't
-	 * a tgt in the cache we have to try and get one with our latest tgt.
-	 * once we have a tgt for a closer realm, we go back to step one.
-	 *
-	 * once we have a tgt for the target, we go try and get credentials.
+	 * Because try_kdc() validates referral TGTs, it can return an
+	 * error indicating a bogus referral.  The loop continues when
+	 * it gets a bogus referral, which is arguably the right
+	 * thing.  (Previous implementation unconditionally failed.)
 	 */
-  
-	for (top_server = tgs_list;
-	     top_server < tgs_list + nservers;
-	     top_server = next_server) {
-    
-	    /* look in cache for a tgt for the destination */
-    
-	    krb5_free_cred_contents(context, &tgtq);
-	    memset(&tgtq, 0, sizeof(tgtq));
-	    if ((retval = krb5_copy_principal(context, tgt.client,
-					      &tgtq.client)))
-		goto cleanup;
+    }
+    /*
+     * If we have a non-zero retval, we either have a hard error or we
+     * failed to find a closer TGT.
+     */
+cleanup:
+    krb5_free_cred_contents(ts->ctx, &tgtq);
+    return retval;
+}
 
-	    krb5_free_principal(context, int_server);
-	    int_server = NULL;
-	    if ((retval = krb5_tgtname(context, 
-				       krb5_princ_realm(context,
-							in_cred->server),
-				       krb5_princ_realm(context, *top_server),
-				       &int_server))) {
-		goto cleanup;
-	    }
-    
-	    if ((retval = krb5_copy_principal(context, int_server,
-					      &tgtq.server)))
-		goto cleanup;
+/*
+ * do_traversal()
+ *
+ * Find final TGT needed to get CLIENT a ticket for SERVER.  Point
+ * OUT_TGT at the desired TGT, which may be an existing cached TGT
+ * (copied into OUT_CC_TGT) or one of the newly obtained TGTs
+ * (collected in OUT_KDC_TGTS).
+ *
+ * Get comfortable; this is somewhat complicated.
+ *
+ * Nomenclature: Cross-realm TGS principal names have the form:
+ *
+ *     krbtgt/REMOTE@LOCAL
+ *
+ * krb5_walk_realm_tree() returns a list like:
+ *
+ *     krbtgt/R1@R1, krbtgt/R2@R1, krbtgt/R3@R2, ...
+ *
+ * These are prinicpal names, not realm names.  We only really use the
+ * remote parts of the TGT principal names.
+ *
+ * The do_traversal loop calls next_closest_tgt() to find the next
+ * closest TGT to the destination realm.  next_closest_tgt() updates
+ * NXT_KDC for the following iteration of the do_traversal() loop.
+ *
+ * At the beginning of any given iteration of the do_traversal() loop,
+ * CUR_KDC's remote realm is the remote realm of CUR_TGT->SERVER.  The
+ * local realms of CUR_KDC and CUR_TGT->SERVER may not match due to
+ * short-circuit paths provided by intermediate KDCs, e.g., CUR_KDC
+ * might be krbtgt/D@C, while CUR_TGT->SERVER is krbtgt/D@B.
+ *
+ * For example, given KDC_LIST of
+ *
+ * krbtgt/R1@R1, krbtgt/R2@R1, krbtgt/R3@R2, krbtgt/R4@R3,
+ * krbtgt/R5@R4
+ *
+ * The next_closest_tgt() loop moves NXT_KDC to the left starting from
+ * R5, stopping before it reaches CUR_KDC.  When next_closest_tgt()
+ * returns, the do_traversal() loop updates CUR_KDC to be NXT_KDC, and
+ * calls next_closest_tgt() again.
+ *
+ * next_closest_tgt() at start of its loop:
+ *
+ *      CUR                 NXT
+ *       |                   |
+ *       V                   V
+ *     +----+----+----+----+----+
+ *     | R1 | R2 | R3 | R4 | R5 |
+ *     +----+----+----+----+----+
+ *
+ * next_closest_tgt() returns after finding a ticket for krbtgt/R3@R1:
+ *
+ *      CUR       NXT
+ *       |         |
+ *       V         V
+ *     +----+----+----+----+----+
+ *     | R1 | R2 | R3 | R4 | R5 |
+ *     +----+----+----+----+----+
+ *
+ * do_traversal() updates CUR_KDC:
+ *
+ *                NXT
+ *                CUR
+ *                 |
+ *                 V
+ *     +----+----+----+----+----+
+ *     | R1 | R2 | R3 | R4 | R5 |
+ *     +----+----+----+----+----+
+ *
+ * next_closest_tgt() at start of its loop:
+ *
+ *                CUR       NXT
+ *                 |         |
+ *                 V         V
+ *     +----+----+----+----+----+
+ *     | R1 | R2 | R3 | R4 | R5 |
+ *     +----+----+----+----+----+
+ *
+ * etc.
+ *
+ * The algorithm executes in n*(n-1)/2 (the sum of integers from 1 to
+ * n-1) attempts in the worst case, i.e., each KDC only has a
+ * cross-realm ticket for the immediately following KDC in the transit
+ * path.  Typically, short-circuit paths will cause execution occur
+ * faster than this worst-case scenario.
+ *
+ * When next_closest_tgt() updates NXT_KDC, it may not perform a
+ * simple increment from CUR_KDC, in part because some KDC may
+ * short-circuit pieces of the transit path.
+ */
+static krb5_error_code
+do_traversal(krb5_context ctx,
+	     krb5_ccache ccache,
+	     krb5_principal client,
+	     krb5_principal server,
+	     krb5_creds *out_cc_tgt,
+	     krb5_creds **out_tgt,
+	     krb5_creds ***out_kdc_tgts)
+{
+    krb5_error_code retval;
+    struct tr_state state, *ts;
+
+    *out_tgt = NULL;
+    *out_kdc_tgts = NULL;
+    ts = &state;
+    memset(ts, 0, sizeof(*ts));
+    ts->ctx = ctx;
+    ts->ccache = ccache;
+    init_cc_tgts(ts);
+
+    retval = init_rtree(ts, client, server);
+    if (retval)
+	goto cleanup;
 
-	    if (free_otgt)
-		krb5_free_cred_contents(context, &otgt);
-	    otgt = tgt;
-	    free_otgt = free_tgt;
-	    free_tgt = 0;
-
-	    retval = krb5_cc_retrieve_cred(context, ccache, retr_flags,
-					   &tgtq, &tgt);
-	    if (retval == 0) {
-	        free_tgt = 1;
-		/* We are now done - proceed to got/finally have tgt */
-	    } else {
-		if (retval != KRB5_CC_NOTFOUND && retval != KRB5_CC_NOT_KTYPE) {
-		    goto cleanup;
-		}
-  
-		/* didn't find it in the cache so try and get one */
-		/* with current tgt.                              */
-		/* Copy back in case invalided */
-		tgt = otgt;
-		free_tgt = free_otgt;
-		free_otgt = 0;
-		if (!krb5_c_valid_enctype(tgt.keyblock.enctype)) {
-		    retval = KRB5_PROG_ETYPE_NOSUPP;
-		    goto cleanup;
-		}
-    
-		krb5_free_cred_contents(context, &tgtq);
-		memset(&tgtq, 0, sizeof(tgtq));
-		tgtq.times        = tgt.times;
-		if ((retval = krb5_copy_principal(context, tgt.client,
-						  &tgtq.client)))
-		    goto cleanup;
-		if ((retval = krb5_copy_principal(context, int_server,
-						  &tgtq.server)))
-		    goto cleanup;
-		tgtq.is_skey      = FALSE;
-		tgtq.ticket_flags = tgt.ticket_flags;
-		retval = krb5_get_cred_via_tkt(context, &tgt,
-					       FLAGS2OPTS(tgtq.ticket_flags),
-					       tgt.addresses, &tgtq, &tgtr);
-		if (retval == 0) {
-		    /* Falls through to 'Got a tgt. If it is for the target' */
-		    ;
-		} else {
-		    /*
-		     * Couldn't get one so now loop backwards through
-		     * the realms list and try and get a tgt for a
-		     * realm as close to the target as possible.  The
-		     * kdc should give us a tgt for the closest one it
-		     * knows about, but not all kdc's do this yet.
-		     */
-		    for (next_server = tgs_list + nservers - 1;
-			 next_server > top_server;
-			 next_server--) {
-			krb5_free_cred_contents(context, &tgtq);
-			memset(&tgtq, 0, sizeof(tgtq));
-			if ((retval = krb5_copy_principal(context, tgt.client,
-							  &tgtq.client)))
-			    goto cleanup;
-
-			krb5_free_principal(context, int_server);
-			int_server = NULL;
-			if ((retval = krb5_tgtname(context, 
-						   krb5_princ_realm(context, *next_server),
-						   krb5_princ_realm(context, *top_server),
-						   &int_server))) {
-			    goto cleanup;
-			}
-    
-			if ((retval = krb5_copy_principal(context, int_server,
-							  &tgtq.server)))
-			    goto cleanup;
-
-			if (free_otgt)
-			    krb5_free_cred_contents(context, &otgt);
-			otgt = tgt;
-			free_otgt = free_tgt;
-			free_tgt = 0;
-			retval = krb5_cc_retrieve_cred(context, ccache,
-							    retr_flags,
-							    &tgtq, &tgt);
-			if (retval == 0) {
-			    free_tgt = 1;
-			    /* Continues with 'got one as close as possible' */
-			} else {
-			    if (retval != KRB5_CC_NOTFOUND) {
-				goto cleanup;
-			    }
-  
-			    /* not in the cache so try and get one with our current tgt. */
-  
-			    tgt = otgt;
-			    free_tgt = free_otgt;
-			    free_otgt = 0;
-			    if (!krb5_c_valid_enctype(tgt.keyblock.enctype)) {
-				retval = KRB5_PROG_ETYPE_NOSUPP;
-				goto cleanup;
-			    }
-            
-			    krb5_free_cred_contents(context, &tgtq);
-			    memset(&tgtq, 0, sizeof(tgtq));
-			    tgtq.times        = tgt.times;
-			    if ((retval = krb5_copy_principal(context,
-							      tgt.client,
-							      &tgtq.client)))
-				goto cleanup;
-			    if ((retval = krb5_copy_principal(context,
-							      int_server,
-							      &tgtq.server)))
-				goto cleanup;
-			    tgtq.is_skey      = FALSE;
-			    tgtq.ticket_flags = tgt.ticket_flags;
-			    retval = krb5_get_cred_via_tkt(context, &tgt,
-							   FLAGS2OPTS(tgtq.ticket_flags),
-							   tgt.addresses,
-							   &tgtq, &tgtr);
-			    if (retval)
-				continue;
-	      
-			    /* save tgt in return array */
-			    if ((retval = krb5_copy_creds(context, tgtr,
-							  &ret_tgts[ntgts]))) {
-				goto cleanup;
-			    }
-			    krb5_free_creds(context, tgtr);
-			    tgtr = NULL;
-
-			    if (free_tgt) {
-				krb5_free_cred_contents(context, &tgt);
-				free_tgt = 0;
-			    }
-	      
-			    tgt = *ret_tgts[ntgts++];
-			} 
-          
-			/* got one as close as possible, now start all over */
-  
-			break;
-		    }
-  
-		    if (next_server == top_server) {
-			goto cleanup;
-		    }
-		    continue;
-		}
- 
-		/*
-		 * Got a tgt.  If it is for the target realm we can go
-		 * try for the credentials.  If it is not for the
-		 * target realm, then make sure it is in the realms
-		 * hierarchy and if so, save it and start the loop
-		 * over from there.  Note that we only need to compare
-		 * the instance names since that is the target realm
-		 * of the tgt.
-		 */
-    
-		for (next_server = top_server; *next_server; next_server++) {
-		    krb5_data *realm_1 = krb5_princ_component(context,
-							      next_server[0],
-							      1);
-		    krb5_data *realm_2 = krb5_princ_component(context,
-							      tgtr->server, 1);
-		    if (realm_1 != NULL &&
-			realm_2 != NULL &&
-			realm_1->length == realm_2->length &&
-			!memcmp(realm_1->data, realm_2->data, realm_1->length)) {
-			break;
-		    }
-		}
-
-		if (!next_server) {
-		    retval = KRB5_KDCREP_MODIFIED;
-		    goto cleanup;
-		}
-
-		if ((retval = krb5_copy_creds(context, tgtr, &ret_tgts[ntgts]))) {
-		    goto cleanup;
-		}
-		krb5_free_creds(context, tgtr);
-		tgtr = NULL;
-
-		if (free_tgt) {
-		    krb5_free_cred_contents(context, &tgt);
-		    free_tgt = 0;
-		}
-
-		tgt = *ret_tgts[ntgts++];
-
-		/* we're done if it is the target */
-
-		if (!*next_server++) break;
-	    }
-	}
+    retval = retr_local_tgt(ts, client);
+    if (retval)
+	goto cleanup;
+
+    for (ts->cur_kdc = ts->kdc_list, ts->nxt_kdc = NULL;
+	 ts->cur_kdc != NULL && ts->cur_kdc < ts->lst_kdc;
+	 ts->cur_kdc = ts->nxt_kdc, ts->cur_tgt = ts->nxt_tgt) {
+
+	retval = next_closest_tgt(ts, client);
+	if (retval)
+	    goto cleanup;
+	assert(ts->cur_kdc != ts->nxt_kdc);
+    }
+
+    if (NXT_TGT_IS_CACHED(ts)) {
+	*out_cc_tgt = *ts->cur_cc_tgt;
+	*out_tgt = out_cc_tgt;
+	MARK_CUR_CC_TGT_CLEAN(ts);
+    } else {
+	/* CUR_TGT is somewhere in KDC_TGTS; no need to copy. */
+	*out_tgt = ts->nxt_tgt;
     }
 
-    /* got/finally have tgt!  try for the creds */
+cleanup:
+    clean_cc_tgts(ts);
+    if (ts->kdc_list != NULL)
+	krb5_free_realm_tree(ctx, ts->kdc_list);
+    if (ts->ntgts == 0) {
+	*out_kdc_tgts = NULL;
+	if (ts->kdc_tgts != NULL)
+	    free(ts->kdc_tgts);
+    } else
+	*out_kdc_tgts = ts->kdc_tgts;
+    return retval;
+}
 
-    if (!krb5_c_valid_enctype(tgt.keyblock.enctype)) {
+/*
+ * krb5_get_cred_from_kdc_opt()
+ * krb5_get_cred_from_kdc()
+ * krb5_get_cred_from_kdc_validate()
+ * krb5_get_cred_from_kdc_renew()
+ *
+ * Retrieve credentials for client IN_CRED->CLIENT, server
+ * IN_CRED->SERVER, ticket flags IN_CRED->TICKET_FLAGS, possibly
+ * second_ticket if needed.
+ *
+ * Request credentials from the KDC for the server's realm.  Point
+ * TGTS to an allocated array of pointers to krb5_creds, containing
+ * any intermediate credentials obtained in the process of contacting
+ * the server's KDC; if no intermediate credentials were obtained,
+ * TGTS is a null pointer.  Return intermediate credentials if
+ * intermediate KDCs provided credentials, even if no useful end
+ * ticket results.
+ *
+ * Caller must free TGTS, regardless of whether this function returns
+ * success.
+ *
+ * This function does NOT cache the intermediate TGTs.
+ *
+ * Do not call this routine if desired credentials are already cached.
+ *
+ * On success, OUT_CRED contains the desired credentials; the caller
+ * must free them.
+ *
+ * Returns errors, system errors.
+ */
+
+static krb5_error_code
+krb5_get_cred_from_kdc_opt(krb5_context context, krb5_ccache ccache,
+			   krb5_creds *in_cred, krb5_creds **out_cred,
+			   krb5_creds ***tgts, int kdcopt)
+{
+    krb5_error_code retval;
+    krb5_principal client, server;
+    krb5_creds tgtq, cc_tgt, *tgtptr;
+    krb5_boolean old_use_conf_ktypes;
+
+    client = in_cred->client;
+    server = in_cred->server;
+    memset(&cc_tgt, 0, sizeof(cc_tgt));
+    memset(&tgtq, 0, sizeof(tgtq));
+    tgtptr = NULL;
+    *tgts = NULL;
+    old_use_conf_ktypes = context->use_conf_ktypes;
+
+    /*
+     * Get a TGT for the target realm.
+     */
+
+    retval = tgt_mcred(context, client, server, client, &tgtq);
+    if (retval)
+	goto cleanup;
+
+    /* Fast path: Is it in the ccache? */
+    context->use_conf_ktypes = 1;
+    retval = krb5_cc_retrieve_cred(context, ccache, RETR_FLAGS,
+				   &tgtq, &cc_tgt);
+    if (!retval) {
+	tgtptr = &cc_tgt;
+    } else if (!HARD_CC_ERR(retval)) {
+	/* Not in ccache, so traverse the transit path. */
+	retval = do_traversal(context, ccache, client, server,
+			      &cc_tgt, &tgtptr, tgts);
+    }
+    if (retval)
+	goto cleanup;
+
+    /*
+     * Finally have TGT for target realm!  Try using it to get creds.
+     */
+
+    if (!krb5_c_valid_enctype(tgtptr->keyblock.enctype)) {
 	retval = KRB5_PROG_ETYPE_NOSUPP;
 	goto cleanup;
     }
 
     context->use_conf_ktypes = old_use_conf_ktypes;
-    retval = krb5_get_cred_via_tkt(context, &tgt,
-				   FLAGS2OPTS(tgt.ticket_flags) |
+    retval = krb5_get_cred_via_tkt(context, tgtptr,
+				   FLAGS2OPTS(tgtptr->ticket_flags) |
 				   kdcopt |
 				   (in_cred->second_ticket.length ?
 				    KDC_OPT_ENC_TKT_IN_SKEY : 0),
-				   tgt.addresses, in_cred, out_cred);
-
-    /* cleanup and return */
+				   tgtptr->addresses, in_cred, out_cred);
 
 cleanup:
-
-    if (tgtr) krb5_free_creds(context, tgtr);
-    if(tgs_list)  krb5_free_realm_tree(context, tgs_list);
-    krb5_free_cred_contents(context, &tgtq); 
-    if (int_server) krb5_free_principal(context, int_server); 
-    if (ntgts == 0) {
-	*tgts = NULL;
-	if (ret_tgts)  free(ret_tgts);
-    } 
-    if (free_otgt)
-	krb5_free_cred_contents(context, &otgt);
-    if (free_tgt)
-	krb5_free_cred_contents(context, &tgt);
+    krb5_free_cred_contents(context, &tgtq);
+    if (tgtptr == &cc_tgt)
+	krb5_free_cred_contents(context, tgtptr);
     context->use_conf_ktypes = old_use_conf_ktypes;
-    return(retval);
+
+    return retval;
 }
 
 krb5_error_code