Set the canonicalize flag in TGS requests and accept cross-realm referral tickets.
[krb5.git] / src / lib / krb5 / krb / gc_frm_kdc.c
index 26f195b264b8d44687c7be3d5789a12f717730e7..44e1b6c3946bab49ff613f6b9e5a49c0b191f661 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1994 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.
  */
 
 #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;
+};
+
+/*
+ * 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)
 
-/* helper macro: convert flags to necessary KDC options */
+#endif /* !DEBUG_GC_FRM_KDC */
 
+/* Convert ticket flags to necessary KDC options */
 #define FLAGS2OPTS(flags) (flags & KDC_TKT_COMMON_MASK)
 
+/*
+ * 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)
+{
+
+    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;
+    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));
+}
+
+static void
+tr_dbg_rtree(struct tr_state *ts, const char *prog, krb5_principal princ)
+{
+    char *str;
+
+    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 */
+
+/*
+ * 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
-krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts, kdcopt)
-    krb5_context context;
-    krb5_ccache ccache;
-    krb5_creds  *in_cred;
-    krb5_creds  **out_cred;
-    krb5_creds  ***tgts;
-    int                kdcopt;
+tgt_mcred(krb5_context ctx, krb5_principal client,
+         krb5_principal dst, krb5_principal src,
+         krb5_creds *mcreds)
 {
-  krb5_creds      **ret_tgts = NULL;
-  int             ntgts = 0;
-
-  krb5_creds      tgt, tgtq, *tgtr = NULL;
-  krb5_error_code retval;
-  krb5_principal  int_server = NULL;    /* Intermediate server for request */
-
-  krb5_principal  *tgs_list = NULL;
-  krb5_principal  *top_server = NULL;
-  krb5_principal  *next_server = NULL;
-  unsigned int    nservers = 0;
-
-  /* in case we never get a TGT, zero the return */
-
-  *tgts = NULL;
-     
-  memset((char *)&tgtq, 0, sizeof(tgtq));
-  memset((char *)&tgt, 0, sizeof(tgt));
-
-  /*
-   * 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)))
-      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))) {
-      goto cleanup;
-  }
-
-  if ((retval = krb5_copy_principal(context, int_server, &tgtq.server))) {
-      goto cleanup;
-  }
-
-  if ((retval = krb5_cc_retrieve_cred(context, ccache,
-                                     KRB5_TC_MATCH_SRV_NAMEONLY | KRB5_TC_SUPPORTED_KTYPES,
-                                     &tgtq, &tgt))) {
-
-    if (retval != KRB5_CC_NOTFOUND && retval != KRB5_CC_NOT_KTYPE) {
+    krb5_error_code retval;
+
+    retval = 0;
+    memset(mcreds, 0, sizeof(*mcreds));
+
+    retval = krb5_copy_principal(ctx, client, &mcreds->client);
+    if (retval)
        goto cleanup;
-    }
 
-    /*
-     * 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.
-     */
-    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))) {
+    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]);
     }
-  
-    krb5_free_cred_contents(context, &tgtq);
-    memset((char *)&tgtq, 0, sizeof(tgtq));
-    if ((retval = krb5_copy_principal(context, in_cred->client, &tgtq.client)))
+    assert(ts->nkdcs > 1);
+    ts->lst_kdc = ts->kdc_list + ts->nkdcs - 1;
+
+    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;
+}
+
+/*
+ * 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) {
+       /*
+        * Not found; we probably got an unexpected realm referral.
+        * Don't touch NXT_KDC, thus allowing next_closest_tgt() to
+        * continue looping backwards.
+        */
+       if (ts->ntgts > 0) {
+           /* Punt NXT_TGT from KDC_TGTS if bogus. */
+           krb5_free_creds(ts->ctx, ts->kdc_tgts[--ts->ntgts]);
+       }
+       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;
+}
+
+/*
+ * 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;
-    if ((retval = krb5_copy_principal(context, int_server, &tgtq.server)))
+
+    retval = krb5_tgtname(ts->ctx, rdst, rsrc, &mcreds->server);
+    if (retval)
        goto cleanup;
 
-    if ((retval = krb5_cc_retrieve_cred(context, ccache,
-                                       KRB5_TC_MATCH_SRV_NAMEONLY | KRB5_TC_SUPPORTED_KTYPES,
-                                       &tgtq, &tgt))) {
+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;
+       }
+       /* Not in the ccache, so talk to a KDC. */
+       retval = try_kdc(ts, &tgtq);
+       if (!retval) {
+           break;
+       }
+       /*
+        * 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.)
+        */
+    }
+    /*
+     * 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;
+}
+
+/*
+ * 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;
+
+    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);
     }
-  
-    /* 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))) {
+
+    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;
+    }
+
+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;
+}
+
+/*
+ * 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.
+ *
+ * Beware memory management issues if you have modifications in mind.
+ * With the addition of referral support, it is now the case that *tgts,
+ * referral_tgts, tgtptr, referral_tgts, and *out_creds all may point to
+ * the same credential at different times.
+ *
+ * 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, subretval;
+    krb5_principal client, server, supplied_server, out_supplied_server;
+    krb5_creds tgtq, cc_tgt, *tgtptr, *referral_tgts[KRB5_REFERRAL_MAXHOPS];
+    krb5_boolean old_use_conf_ktypes;
+    char **hrealms;
+    int referral_count, i;
+
+    /* 
+     * Set up client and server pointers.  Make a fresh and modifyable
+     * copy of the in_cred server and save the supplied version.
+     */
+    client = in_cred->client;
+    if ((retval=krb5_copy_principal(context, in_cred->server, &server)))
+        return retval;
+    /* We need a second copy for the output creds. */
+    if ((retval = krb5_copy_principal(context, server, &out_supplied_server)) != 0 ) {
+       krb5_free_principal(context, server);
+       return retval;
+    }
+    supplied_server = in_cred->server;
+    in_cred->server=server;
+
+
+#ifdef DEBUG_REFERRALS
+    krb5int_dbgref_dump_principal("gc_from_kdc initial client", client);
+    krb5int_dbgref_dump_principal("gc_from_kdc initial server", server);
+#endif
+    memset(&cc_tgt, 0, sizeof(cc_tgt));
+    memset(&tgtq, 0, sizeof(tgtq));
+    memset(&referral_tgts, 0, sizeof(referral_tgts));
+
+    tgtptr = NULL;
+    *tgts = NULL;
+    *out_cred=NULL;
+    old_use_conf_ktypes = context->use_conf_ktypes;
+
+    /* Copy client realm to server if no hint. */
+    if (krb5_is_referral_realm(&server->realm)) {
+        /* Use the client realm. */
+#ifdef DEBUG_REFERRALS
+        printf("gc_from_kdc: no server realm supplied, using client realm.\n");
+#endif
+       krb5_free_data_contents(context, &server->realm);
+       if (!( server->realm.data = (char *)malloc(client->realm.length+1)))
+           return ENOMEM;
+       memcpy(server->realm.data, client->realm.data, client->realm.length);
+       server->realm.length = client->realm.length;
+       server->realm.data[server->realm.length] = 0;
+    }
+    /*
+     * Retreive initial TGT to match the specified server, either for the
+     * local realm in the default (referral) case or for the remote
+     * realm if we're starting someplace non-local.
+     */
+    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)) {
+#ifdef DEBUG_REFERRALS
+        printf("gc_from_kdc: starting do_traversal to find initial TGT for referral\n");
+#endif
+       retval = do_traversal(context, ccache, client, server,
+                             &cc_tgt, &tgtptr, tgts);
     }
-  
-    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;
+    if (retval) {
+#ifdef DEBUG_REFERRALS
+        printf("gc_from_kdc: failed to find initial TGT for referral\n");
+#endif
+        goto cleanup;
     }
-    *tgts = ret_tgts;
-    
+
+#ifdef DEBUG_REFERRALS
+    krb5int_dbgref_dump_principal("gc_from_kdc: server as requested", supplied_server);
+#endif
+
     /*
-     * 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.
+     * Try requesting a service ticket from our local KDC with referrals
+     * turned on.  If the first referral succeeds, follow a referral-only
+     * path, otherwise fall back to old-style assumptions.
      */
-  
-    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;
-
-      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;
 
-      if ((retval = krb5_cc_retrieve_cred(context, ccache,
-                                         KRB5_TC_MATCH_SRV_NAMEONLY | KRB5_TC_SUPPORTED_KTYPES,
-                                         &tgtq, &tgt))) {
-    
-       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.                              */
-    
-       if (!krb5_c_valid_enctype(tgt.keyblock.enctype)) {
-           retval = KRB5_PROG_ETYPE_NOSUPP;
+    for (referral_count=0;referral_count<KRB5_REFERRAL_MAXHOPS;referral_count++) {
+#ifdef DEBUG_REFERRALS
+#if 0
+        krb5int_dbgref_dump_principal("gc_from_kdc: referral loop: tgt in use", tgtptr->server);
+        krb5int_dbgref_dump_principal("gc_from_kdc: referral loop: request is for", server);
+#endif
+#endif
+        retval = krb5_get_cred_via_tkt(context, tgtptr,
+                                      KDC_OPT_CANONICALIZE | 
+                                      FLAGS2OPTS(tgtptr->ticket_flags) |  
+                                      kdcopt |
+                                      (in_cred->second_ticket.length ?
+                                       KDC_OPT_ENC_TKT_IN_SKEY : 0),
+                                      tgtptr->addresses, in_cred, out_cred);
+       if (retval) {
+#ifdef DEBUG_REFERRALS
+           printf("gc_from_kdc: referral TGS-REQ request failed: <%s>\n",error_message(retval));
+#endif
+           /* If we haven't gone anywhere yet, fail through to the
+              non-referral case. */
+           if (referral_count==0) {
+#ifdef DEBUG_REFERRALS
+               printf("gc_from_kdc: initial referral failed; punting to fallback.\n");
+#endif
+               break;
+           }
+           /* Otherwise, try the same query without canonicalization
+              set, and fail hard if that doesn't work. */
+#ifdef DEBUG_REFERRALS
+           printf("gc_from_kdc: referral #%d failed; retrying without option.\n",
+                  referral_count+1);
+#endif
+           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),
+                                          tgtptr->addresses,
+                                          in_cred, out_cred);
+           /* Whether or not that succeeded, we're done. */
            goto cleanup;
        }
-    
-       krb5_free_cred_contents(context, &tgtq);
-       memset(&tgtq, 0, sizeof(tgtq));
-#ifdef HAVE_C_STRUCTURE_ASSIGNMENT
-       tgtq.times        = tgt.times;
-#else
-       memcpy(&tgtq.times, &tgt.times, sizeof(krb5_ticket_times));
+       else {
+           /* Referral request succeeded; let's see what it is. */
+           if (krb5_principal_compare(context, in_cred->server, (*out_cred)->server)) {
+#ifdef DEBUG_REFERRALS
+               printf("gc_from_kdc: request generated ticket for requested server principal\n");
+               krb5int_dbgref_dump_principal("gc_from_kdc final referred reply",in_cred->server);
 #endif
-
-       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;
-       if ((retval = krb5_get_cred_via_tkt(context, &tgt,
-                                           FLAGS2OPTS(tgtq.ticket_flags),
-                                           tgt.addresses, &tgtq, &tgtr))) {
-             
-       /*
-       * 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 ((retval = krb5_cc_retrieve_cred(context, ccache,
-                                               KRB5_TC_MATCH_SRV_NAMEONLY | KRB5_TC_SUPPORTED_KTYPES,
-                                               &tgtq, &tgt))) {
-             if (retval != KRB5_CC_NOTFOUND) {
-                 goto cleanup;
-             }
-  
-             /* not in the cache so try and get one with our current tgt. */
-  
-             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;
-             if ((retval = krb5_get_cred_via_tkt(context, &tgt,
-                                                 FLAGS2OPTS(tgtq.ticket_flags),
-                                                 tgt.addresses,
-                                                 &tgtq, &tgtr))) {
-                 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;
-             
-             tgt = *ret_tgts[ntgts++];
+           else {
+#ifdef DEBUG_REFERRALS
+               printf("gc_from_kdc: request generated referral tgt\n");
+               krb5int_dbgref_dump_principal("gc_from_kdc credential received", (*out_cred)->server);
+#endif
+               /* Check for referral routing loop. */
+               for (i=0;i<referral_count;i++) {
+#ifdef DEBUG_REFERRALS
+#if 0
+                   krb5int_dbgref_dump_principal("gc_from_kdc: loop compare #1", (*out_cred)->server);
+                   krb5int_dbgref_dump_principal("gc_from_kdc: loop compare #2", referral_tgts[i]->server);
+#endif
+#endif
+                   if (krb5_principal_compare(context, (*out_cred)->server, referral_tgts[i]->server)) {
+                       fprintf(stderr, "krb5_get_cred_from_kdc_opt: referral routing loop afer %d hops\n",i);
+                       retval=KRB5_KDC_UNREACH;
+                       goto cleanup;
+                   }
+               }
+               /* Point current tgt pointer at newly-received TGT. */
+               if (tgtptr == &cc_tgt)
+                   krb5_free_cred_contents(context, tgtptr);
+               tgtptr=*out_cred;
+               /* Save pointer to tgt in referral_tgts. */
+               referral_tgts[referral_count]=*out_cred;
+               /* Copy krbtgt realm to server principal. */
+               krb5_free_data_contents(context, &server->realm);
+               if ((retval=krb5int_copy_data_contents(context, &tgtptr->server->data[1], &server->realm)))
+                   return retval;
+               /* Future work: rewrite server principal per any supplied padata. */
            }
-          
-           /* 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->length == realm_2->length &&
-                !memcmp(realm_1->data, realm_2->data, realm_1->length)) {
-               break;
-            }
        }
+    }
 
-       if (!next_server) {
-           retval = KRB5_KDCREP_MODIFIED;
-           goto cleanup;
-       }
+#ifdef DEBUG_REFERRALS
+    krb5int_dbgref_dump_principal("gc_from_kdc client at fallback", client);
+    krb5int_dbgref_dump_principal("gc_from_kdc server at fallback", server);
+#endif
 
-       if ((retval = krb5_copy_creds(context, tgtr, &ret_tgts[ntgts]))) {
-           goto cleanup;
+    /*
+     * At this point referrals have been tried and have failed.  Go back
+     * to the server principal as originally issued and try the conventional path.
+     */
+  
+    /* Referrals have failed.  Look up fallback realm if not originally provided. */
+    if (krb5_is_referral_realm(&supplied_server->realm)) {
+        if (server->length >= 2) {
+           retval=krb5_get_fallback_host_realm(context, &server->data[1],
+                                               &hrealms);
+           if (retval) goto cleanup;
+#ifdef DEBUG_REFERRALS
+#if 0
+           printf("gc_from_kdc: using fallback realm of %s\n",hrealms[0]);
+#endif
+#endif
+           krb5_free_data_contents(context,&in_cred->server->realm);
+           server->realm.data=hrealms[0];
+           server->realm.length=strlen(hrealms[0]);
+           free(hrealms);
        }
-       krb5_free_creds(context, tgtr);
-       tgtr = NULL;
-    
-        tgt = *ret_tgts[ntgts++];
+       else {
+           /*
+            * Problem case: Realm tagged for referral but apparently not
+            * in a <type>/<host> format that
+            * krb5_get_fallback_host_realm can deal with.
+            */
+#ifdef DEBUG_REFERRALS
+           printf("gc_from_kdc: referral specified but no fallback realm avaiable!\n");
+#endif
+           return KRB5_ERR_HOST_REALM_UNKNOWN;
+       }
+    }
 
-        /* we're done if it is the target */
+#ifdef DEBUG_REFERRALS
+    krb5int_dbgref_dump_principal("gc_from_kdc server at fallback after fallback rewrite", server);
+#endif
 
-        if (!*next_server++) break;
-      }
-    }
-  }
+    /*
+     * Get a TGT for the target realm.
+     */
+    
+    krb5_free_cred_contents(context, &tgtq);
+    retval = tgt_mcred(context, client, server, client, &tgtq);
+    if (retval)
+       goto cleanup;
 
-  /* got/finally have tgt!  try for the creds */
+    /* Fast path: Is it in the ccache? */
+    /* Free tgtptr data if reused from above. */
+    if (tgtptr == &cc_tgt)
+       krb5_free_cred_contents(context, tgtptr);
+    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)) {
+       retval = do_traversal(context, ccache, client, server,
+                             &cc_tgt, &tgtptr, tgts);
+    }
+    if (retval)
+       goto cleanup;
 
-  if (!krb5_c_valid_enctype(tgt.keyblock.enctype)) {
-    retval = KRB5_PROG_ETYPE_NOSUPP;
-    goto cleanup;
-  }
+    /*
+     * Finally have TGT for target realm!  Try using it to get creds.
+     */
 
-  retval = krb5_get_cred_via_tkt(context, &tgt, FLAGS2OPTS(tgt.ticket_flags) |
-                                kdcopt | 
-                                       (in_cred->second_ticket.length ? 
-                                        KDC_OPT_ENC_TKT_IN_SKEY : 0),
-                                tgt.addresses, in_cred, out_cred);
+    if (!krb5_c_valid_enctype(tgtptr->keyblock.enctype)) {
+       retval = KRB5_PROG_ETYPE_NOSUPP;
+       goto cleanup;
+    }
 
-  /* cleanup and return */
+    context->use_conf_ktypes = old_use_conf_ktypes;
+    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),
+                                  tgtptr->addresses, in_cred, out_cred);
 
 cleanup:
+    krb5_free_cred_contents(context, &tgtq);
+    if (tgtptr == &cc_tgt)
+       krb5_free_cred_contents(context, tgtptr);
+    context->use_conf_ktypes = old_use_conf_ktypes;
+    /* Drop the original principal back into in_cred so that it's cached
+       in the expected format. */
+#ifdef DEBUG_REFERRALS
+    krb5int_dbgref_dump_principal("gc_from_kdc: final hacked server principal at cleanup",server);
+#endif
+    krb5_free_principal(context, server);
+    in_cred->server = supplied_server;
+    if (*out_cred && !retval) {
+        /* Success: free server, swap supplied server back in. */
+        krb5_free_principal (context, (*out_cred)->server);
+       (*out_cred)->server= out_supplied_server;
+    }
+    else {
+        /* 
+        * Failure: free out_supplied_server.  Don't free out_cred here
+        * since it's either null or a referral TGT that we free below,
+        * and we may need it to return.
+        */
+        krb5_free_principal (context, out_supplied_server);
+    }
+#ifdef DEBUG_REFERRALS
+    krb5int_dbgref_dump_principal("gc_from_kdc: final server after reversion",in_cred->server);
+#endif
+    /*
+     * Deal with ccache TGT management: If tgts has been set from
+     * initial non-referral TGT discovery, leave it alone.  Otherwise, if
+     * referral_tgts[0] exists return it as the only entry in tgts.
+     * (Further referrals are never cached, only the referral from the
+     * local KDC.)  This is part of cleanup because useful received TGTs
+     * should be cached even if the main request resulted in failure.
+     */
+
+    if (*tgts == NULL) {
+        if (referral_tgts[0]) {
+#if 0
+           /*
+            * This should possibly be a check on the candidate return
+            * credential against the cache, in the circumstance where we
+            * don't want to clutter the cache with near-duplicate
+            * credentials on subsequent iterations.  For now, it is
+            * disabled.
+            */
+           subretval=...?;
+           if (subretval) {
+#endif
+               /* Allocate returnable TGT list. */
+               if (!(*tgts=calloc(sizeof (krb5_creds *), 2)))
+                   return ENOMEM;
+               subretval=krb5_copy_creds(context, referral_tgts[0], &((*tgts)[0]));
+               if(subretval)
+                   return subretval;
+               (*tgts)[1]=NULL;
+#ifdef DEBUG_REFERRALS
+               krb5int_dbgref_dump_principal("gc_from_kdc: returning referral TGT for ccache",(*tgts)[0]->server);
+#endif
+#if 0
+           }
+#endif
+       }
+    }
 
-  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);
-      krb5_free_cred_contents(context, &tgt);
-  }
-  return(retval);
+    /* Free referral TGTs list. */
+    for (i=0;i<KRB5_REFERRAL_MAXHOPS;i++) {
+        if(referral_tgts[i]) {
+           krb5_free_creds(context, referral_tgts[i]);
+       }
+    }
+#ifdef DEBUG_REFERRALS
+    printf("gc_from_kdc finishing with %s\n", retval?error_message(retval):"no error");
+#endif
+    return retval;
 }
 
 krb5_error_code
-krb5_get_cred_from_kdc(context, ccache, in_cred, out_cred, tgts)
-    krb5_context context;
-    krb5_ccache ccache;
-    krb5_creds  *in_cred;
-    krb5_creds  **out_cred;
-    krb5_creds  ***tgts;
+krb5_get_cred_from_kdc(krb5_context context, krb5_ccache ccache,
+                      krb5_creds *in_cred, krb5_creds **out_cred,
+                      krb5_creds ***tgts)
 {
-
-  return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
-                                   0);
+    return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
+                                     0);
 }
 
 krb5_error_code
-krb5_get_cred_from_kdc_validate(context, ccache, in_cred, out_cred, tgts)
-    krb5_context context;
-    krb5_ccache ccache;
-    krb5_creds  *in_cred;
-    krb5_creds  **out_cred;
-    krb5_creds  ***tgts;
+krb5_get_cred_from_kdc_validate(krb5_context context, krb5_ccache ccache,
+                               krb5_creds *in_cred, krb5_creds **out_cred,
+                               krb5_creds ***tgts)
 {
-
-  return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
-                                   KDC_OPT_VALIDATE);
+    return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
+                                     KDC_OPT_VALIDATE);
 }
 
 krb5_error_code
-krb5_get_cred_from_kdc_renew(context, ccache, in_cred, out_cred, tgts)
-    krb5_context context;
-    krb5_ccache ccache;
-    krb5_creds  *in_cred;
-    krb5_creds  **out_cred;
-    krb5_creds  ***tgts;
+krb5_get_cred_from_kdc_renew(krb5_context context, krb5_ccache ccache,
+                            krb5_creds *in_cred, krb5_creds **out_cred,
+                            krb5_creds ***tgts)
 {
-
-  return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
-                                   KDC_OPT_RENEW);
+    return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
+                                     KDC_OPT_RENEW);
 }