src/lib/krb5/krb/gc_frm_kdc.c

   1 /*
   2  * Copyright (c) 1994,2003,2005 by the Massachusetts Institute of Technology.
   3  * Copyright (c) 1994 CyberSAFE Corporation
   4  * Copyright (c) 1993 Open Computing Security Group
   5  * Copyright (c) 1990,1991 by the Massachusetts Institute of Technology.
   6  * All Rights Reserved.
   7  *
   8  * Export of this software from the United States of America may
   9  *   require a specific license from the United States Government.
  10  *   It is the responsibility of any person or organization contemplating
  11  *   export to obtain such a license before exporting.
  12  *
  13  * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
  14  * distribute this software and its documentation for any purpose and
  15  * without fee is hereby granted, provided that the above copyright
  16  * notice appear in all copies and that both that copyright notice and
  17  * this permission notice appear in supporting documentation, and that
  18  * the name of M.I.T. not be used in advertising or publicity pertaining
  19  * to distribution of the software without specific, written prior
  20  * permission.  Furthermore if you modify this software you must label
  21  * your software as modified software and not distribute it in such a
  22  * fashion that it might be confused with the original M.I.T. software.
  23  * Neither M.I.T., the Open Computing Security Group, nor
  24  * CyberSAFE Corporation make any representations about the suitability of
  25  * this software for any purpose.  It is provided "as is" without express
  26  * or implied warranty.
  27  *
  28  * krb5_get_cred_from_kdc() and related functions:
  29  *
  30  * Get credentials from some KDC somewhere, possibly accumulating TGTs
  31  * along the way.
  32  */
  33
  34 #include "k5-int.h"
  35 #include <stdio.h>
  36 #include "int-proto.h"
  37
  38 struct tr_state;
  39
  40 /*
  41  * Ring buffer abstraction for TGTs returned from a ccache; avoids
  42  * lots of excess copying.
  43  */
  44
  45 #define NCC_TGTS 2
  46 struct cc_tgts {
  47     krb5_creds cred[NCC_TGTS];
  48     int dirty[NCC_TGTS];
  49     unsigned int cur, nxt;
  50 };
  51
  52 /* NOTE: This only checks if NXT_TGT is CUR_CC_TGT. */
  53 #define NXT_TGT_IS_CACHED(ts)                   \
  54         ((ts)->nxt_tgt == (ts)->cur_cc_tgt)
  55
  56 #define MARK_CUR_CC_TGT_CLEAN(ts)                       \
  57 do {                                                    \
  58         (ts)->cc_tgts.dirty[(ts)->cc_tgts.cur] = 0;     \
  59 } while (0)
  60
  61 static void init_cc_tgts(struct tr_state *);
  62 static void shift_cc_tgts(struct tr_state *);
  63 static void clean_cc_tgts(struct tr_state *);
  64
  65 /*
  66  * State struct for do_traversal() and helpers.
  67  *
  68  * CUR_TGT and NXT_TGT can each point either into CC_TGTS or into
  69  * KDC_TGTS.
  70  *
  71  * CUR_TGT is the "working" TGT, which will be used to obtain new
  72  * TGTs.  NXT_TGT will be CUR_TGT for the next iteration of the loop.
  73  *
  74  * Part of the baroqueness of this setup is to deal with annoying
  75  * differences between krb5_cc_retrieve_cred() and
  76  * krb5_get_cred_via_tkt(); krb5_cc_retrieve_cred() fills in a
  77  * caller-allocated krb5_creds, while krb5_get_cred_via_tkt()
  78  * allocates a krb5_creds for return.
  79  */
  80 struct tr_state {
  81     krb5_context ctx;
  82     krb5_ccache ccache;
  83     krb5_principal *kdc_list;
  84     unsigned int nkdcs;
  85     krb5_principal *cur_kdc;
  86     krb5_principal *nxt_kdc;
  87     krb5_principal *lst_kdc;
  88     krb5_creds *cur_tgt;
  89     krb5_creds *nxt_tgt;
  90     krb5_creds **kdc_tgts;
  91     struct cc_tgts cc_tgts;
  92     krb5_creds *cur_cc_tgt;
  93     krb5_creds *nxt_cc_tgt;
  94     unsigned int ntgts;
  95 };
  96
  97 /*
  98  * Debug support
  99  */
 100 #ifdef DEBUG_GC_FRM_KDC
 101
 102 #define TR_DBG(ts, prog) tr_dbg(ts, prog)
 103 #define TR_DBG_RET(ts, prog, ret) tr_dbg_ret(ts, prog, ret)
 104 #define TR_DBG_RTREE(ts, prog, princ) tr_dbg_rtree(ts, prog, princ)
 105
 106 static void tr_dbg(struct tr_state *, const char *);
 107 static void tr_dbg_ret(struct tr_state *, const char *, krb5_error_code);
 108 static void tr_dbg_rtree(struct tr_state *, const char *, krb5_principal);
 109
 110 #else
 111
 112 #define TR_DBG(ts, prog)
 113 #define TR_DBG_RET(ts, prog, ret)
 114 #define TR_DBG_RTREE(ts, prog, princ)
 115
 116 #endif /* !DEBUG_GC_FRM_KDC */
 117
 118 #ifdef DEBUG_REFERRALS
 119
 120 #define DPRINTF(x) printf x
 121 #define DFPRINTF(x) fprintf x
 122 #define DUMP_PRINC(x, y) krb5int_dbgref_dump_principal((x), (y))
 123
 124 #else
 125
 126 #define DPRINTF(x)
 127 #define DFPRINTF(x)
 128 #define DUMP_PRINC(x, y)
 129
 130 #endif
 131
 132 /* Convert ticket flags to necessary KDC options */
 133 #define FLAGS2OPTS(flags) (flags & KDC_TKT_COMMON_MASK)
 134
 135 /*
 136  * Certain krb5_cc_retrieve_cred() errors are soft errors when looking
 137  * for a cross-realm TGT.
 138  */
 139 #define HARD_CC_ERR(r) ((r) && (r) != KRB5_CC_NOTFOUND &&       \
 140         (r) != KRB5_CC_NOT_KTYPE)
 141
 142 #define IS_TGS_PRINC(c, p)                              \
 143     ((krb5_princ_size((c), (p)) == 2) &&                \
 144      (krb5_princ_component((c), (p), 0)->length ==      \
 145       KRB5_TGS_NAME_SIZE) &&                            \
 146      (!memcmp(krb5_princ_component((c), (p), 0)->data,  \
 147               KRB5_TGS_NAME, KRB5_TGS_NAME_SIZE)))
 148
 149 /*
 150  * Flags for ccache lookups of cross-realm TGTs.
 151  *
 152  * A cross-realm TGT may be issued by some other intermediate realm's
 153  * KDC, so we use KRB5_TC_MATCH_SRV_NAMEONLY.
 154  */
 155 #define RETR_FLAGS (KRB5_TC_MATCH_SRV_NAMEONLY | KRB5_TC_SUPPORTED_KTYPES)
 156
 157 /*
 158  * Prototypes of helper functions
 159  */
 160 static krb5_error_code tgt_mcred(krb5_context, krb5_principal,
 161     krb5_principal, krb5_principal, krb5_creds *);
 162 static krb5_error_code retr_local_tgt(struct tr_state *, krb5_principal);
 163 static krb5_error_code try_ccache(struct tr_state *, krb5_creds *);
 164 static krb5_error_code find_nxt_kdc(struct tr_state *);
 165 static krb5_error_code try_kdc(struct tr_state *, krb5_creds *);
 166 static krb5_error_code kdc_mcred(struct tr_state *, krb5_principal,
 167     krb5_creds *mcreds);
 168 static krb5_error_code next_closest_tgt(struct tr_state *, krb5_principal);
 169 static krb5_error_code init_rtree(struct tr_state *,
 170     krb5_principal, krb5_principal);
 171 static krb5_error_code do_traversal(krb5_context ctx, krb5_ccache,
 172     krb5_principal client, krb5_principal server,
 173     krb5_creds *out_cc_tgt, krb5_creds **out_tgt,
 174     krb5_creds ***out_kdc_tgts);
 175 static krb5_error_code krb5_get_cred_from_kdc_opt(krb5_context, krb5_ccache,
 176     krb5_creds *, krb5_creds **, krb5_creds ***, int);
 177
 178 /*
 179  * init_cc_tgts()
 180  *
 181  * Initialize indices for cached-TGT ring buffer.  Caller must zero
 182  * CC_TGTS, CC_TGT_DIRTY arrays prior to calling.
 183  */
 184 static void
 185 init_cc_tgts(struct tr_state *ts)
 186 {
 187
 188     ts->cc_tgts.cur = 0;
 189     ts->cc_tgts.nxt = 1;
 190     ts->cur_cc_tgt = &ts->cc_tgts.cred[0];
 191     ts->nxt_cc_tgt = &ts->cc_tgts.cred[1];
 192 }
 193
 194 /*
 195  * shift_cc_tgts()
 196  *
 197  * Given a fresh assignment to NXT_CC_TGT, mark NXT_CC_TGT as dirty,
 198  * and shift indices so old NXT_CC_TGT becomes new CUR_CC_TGT.  Clean
 199  * the new NXT_CC_TGT.
 200  */
 201 static void
 202 shift_cc_tgts(struct tr_state *ts)
 203 {
 204     unsigned int i;
 205     struct cc_tgts *rb;
 206
 207     rb = &ts->cc_tgts;
 208     i = rb->cur = rb->nxt;
 209     rb->dirty[i] = 1;
 210     ts->cur_cc_tgt = ts->nxt_cc_tgt;
 211
 212     i = (i + 1) % NCC_TGTS;
 213
 214     rb->nxt = i;
 215     ts->nxt_cc_tgt = &rb->cred[i];
 216     if (rb->dirty[i]) {
 217         krb5_free_cred_contents(ts->ctx, &rb->cred[i]);
 218         rb->dirty[i] = 0;
 219     }
 220 }
 221
 222 /*
 223  * clean_cc_tgts()
 224  *
 225  * Free CC_TGTS which were dirty, then mark them clean.
 226  */
 227 static void
 228 clean_cc_tgts(struct tr_state *ts)
 229 {
 230     unsigned int i;
 231     struct cc_tgts *rb;
 232
 233     rb = &ts->cc_tgts;
 234     for (i = 0; i < NCC_TGTS; i++) {
 235         if (rb->dirty[i]) {
 236             krb5_free_cred_contents(ts->ctx, &rb->cred[i]);
 237             rb->dirty[i] = 0;
 238         }
 239     }
 240 }
 241
 242 /*
 243  * Debug support
 244  */
 245 #ifdef DEBUG_GC_FRM_KDC
 246 static void
 247 tr_dbg(struct tr_state *ts, const char *prog)
 248 {
 249     krb5_error_code retval;
 250     char *cur_tgt_str, *cur_kdc_str, *nxt_kdc_str;
 251
 252     cur_tgt_str = cur_kdc_str = nxt_kdc_str = NULL;
 253     retval = krb5_unparse_name(ts->ctx, ts->cur_tgt->server, &cur_tgt_str);
 254     if (retval) goto cleanup;
 255     retval = krb5_unparse_name(ts->ctx, *ts->cur_kdc, &cur_kdc_str);
 256     if (retval) goto cleanup;
 257     retval = krb5_unparse_name(ts->ctx, *ts->nxt_kdc, &nxt_kdc_str);
 258     if (retval) goto cleanup;
 259     fprintf(stderr, "%s: cur_tgt %s\n", prog, cur_tgt_str);
 260     fprintf(stderr, "%s: cur_kdc %s\n", prog, cur_kdc_str);
 261     fprintf(stderr, "%s: nxt_kdc %s\n", prog, nxt_kdc_str);
 262 cleanup:
 263     if (cur_tgt_str)
 264         krb5_free_unparsed_name(ts->ctx, cur_tgt_str);
 265     if (cur_kdc_str)
 266         krb5_free_unparsed_name(ts->ctx, cur_kdc_str);
 267     if (nxt_kdc_str)
 268         krb5_free_unparsed_name(ts->ctx, nxt_kdc_str);
 269 }
 270
 271 static void
 272 tr_dbg_ret(struct tr_state *ts, const char *prog, krb5_error_code ret)
 273 {
 274     fprintf(stderr, "%s: return %d (%s)\n", prog, (int)ret,
 275             error_message(ret));
 276 }
 277
 278 static void
 279 tr_dbg_rtree(struct tr_state *ts, const char *prog, krb5_principal princ)
 280 {
 281     char *str;
 282
 283     if (krb5_unparse_name(ts->ctx, princ, &str))
 284         return;
 285     fprintf(stderr, "%s: %s\n", prog, str);
 286     krb5_free_unparsed_name(ts->ctx, str);
 287 }
 288 #endif /* DEBUG_GC_FRM_KDC */
 289
 290 /*
 291  * tgt_mcred()
 292  *
 293  * Return MCREDS for use as a match criterion.
 294  *
 295  * Resulting credential has CLIENT as the client principal, and
 296  * krbtgt/realm_of(DST)@realm_of(SRC) as the server principal.  Zeroes
 297  * MCREDS first, does not allocate MCREDS, and cleans MCREDS on
 298  * failure.  The peculiar ordering of DST and SRC args is for
 299  * consistency with krb5_tgtname().
 300  */
 301 static krb5_error_code
 302 tgt_mcred(krb5_context ctx, krb5_principal client,
 303           krb5_principal dst, krb5_principal src,
 304           krb5_creds *mcreds)
 305 {
 306     krb5_error_code retval;
 307
 308     retval = 0;
 309     memset(mcreds, 0, sizeof(*mcreds));
 310
 311     retval = krb5_copy_principal(ctx, client, &mcreds->client);
 312     if (retval)
 313         goto cleanup;
 314
 315     retval = krb5_tgtname(ctx, krb5_princ_realm(ctx, dst),
 316                           krb5_princ_realm(ctx, src), &mcreds->server);
 317     if (retval)
 318         goto cleanup;
 319
 320 cleanup:
 321     if (retval)
 322         krb5_free_cred_contents(ctx, mcreds);
 323
 324     return retval;
 325 }
 326
 327 /*
 328  * init_rtree()
 329  *
 330  * Populate KDC_LIST with the output of krb5_walk_realm_tree().
 331  */
 332 static krb5_error_code
 333 init_rtree(struct tr_state *ts,
 334            krb5_principal client, krb5_principal server)
 335 {
 336     krb5_error_code retval;
 337
 338     ts->kdc_list = NULL;
 339     retval = krb5_walk_realm_tree(ts->ctx, krb5_princ_realm(ts->ctx, client),
 340                                   krb5_princ_realm(ts->ctx, server),
 341                                   &ts->kdc_list, KRB5_REALM_BRANCH_CHAR);
 342     if (retval)
 343         return retval;
 344
 345     for (ts->nkdcs = 0; ts->kdc_list[ts->nkdcs]; ts->nkdcs++) {
 346         assert(krb5_princ_size(ts->ctx, ts->kdc_list[ts->nkdcs]) == 2);
 347         TR_DBG_RTREE(ts, "init_rtree", ts->kdc_list[ts->nkdcs]);
 348     }
 349     assert(ts->nkdcs > 1);
 350     ts->lst_kdc = ts->kdc_list + ts->nkdcs - 1;
 351
 352     ts->kdc_tgts = calloc(ts->nkdcs + 1, sizeof(krb5_creds));
 353     if (ts->kdc_tgts == NULL)
 354         return ENOMEM;
 355
 356     return 0;
 357 }
 358
 359 /*
 360  * retr_local_tgt()
 361  *
 362  * Prime CUR_TGT with the cached TGT of the client's local realm.
 363  */
 364 static krb5_error_code
 365 retr_local_tgt(struct tr_state *ts, krb5_principal client)
 366 {
 367     krb5_error_code retval;
 368     krb5_creds tgtq;
 369
 370     memset(&tgtq, 0, sizeof(tgtq));
 371     retval = tgt_mcred(ts->ctx, client, client, client, &tgtq);
 372     if (retval)
 373         return retval;
 374
 375     /* Match realm, unlike other ccache retrievals here. */
 376     retval = krb5_cc_retrieve_cred(ts->ctx, ts->ccache,
 377                                    KRB5_TC_SUPPORTED_KTYPES,
 378                                    &tgtq, ts->nxt_cc_tgt);
 379     krb5_free_cred_contents(ts->ctx, &tgtq);
 380     if (!retval) {
 381         shift_cc_tgts(ts);
 382         ts->nxt_tgt = ts->cur_tgt = ts->cur_cc_tgt;
 383     }
 384     return retval;
 385 }
 386
 387 /*
 388  * try_ccache()
 389  *
 390  * Attempt to retrieve desired NXT_TGT from ccache.  Point NXT_TGT to
 391  * it if successful.
 392  */
 393 static krb5_error_code
 394 try_ccache(struct tr_state *ts, krb5_creds *tgtq)
 395 {
 396     krb5_error_code retval;
 397
 398     TR_DBG(ts, "try_ccache");
 399     retval = krb5_cc_retrieve_cred(ts->ctx, ts->ccache, RETR_FLAGS,
 400                                    tgtq, ts->nxt_cc_tgt);
 401     if (!retval) {
 402         shift_cc_tgts(ts);
 403         ts->nxt_tgt = ts->cur_cc_tgt;
 404     }
 405     TR_DBG_RET(ts, "try_ccache", retval);
 406     return retval;
 407 }
 408
 409 /*
 410  * find_nxt_kdc()
 411  *
 412  * A NXT_TGT gotten from an intermediate KDC might actually be a
 413  * referral.  Search KDC_LIST forward starting from CUR_KDC, looking
 414  * for the KDC with the same remote realm as NXT_TGT.  If we don't
 415  * find it, the intermediate KDC is leading us off the transit path.
 416  *
 417  * Match on CUR_KDC's remote realm, not local realm, because, among
 418  * other reasons, we can get a referral to the final realm; e.g.,
 419  * given
 420  *
 421  *     KDC_LIST == { krbtgt/R1@R1, krbtgt/R2@R1, krbtgt/R3@R2,
 422  *                   krbtgt/R4@R3, NULL }
 423  *     CUR_TGT->SERVER == krbtgt/R2@R1
 424  *     NXT_TGT->SERVER == krbtgt/R4@R2
 425  *
 426  * i.e., we got a ticket issued by R2 with remote realm R4, we want to
 427  * find krbtgt/R4@R3, not krbtgt/R3@R2, even though we have no TGT
 428  * with R3 as its local realm.
 429  *
 430  * Set up for next iteration of do_traversal() loop by pointing
 431  * NXT_KDC to one entry forward of the match.
 432  */
 433 static krb5_error_code
 434 find_nxt_kdc(struct tr_state *ts)
 435 {
 436     krb5_data *r1, *r2;
 437     krb5_principal *kdcptr;
 438
 439     TR_DBG(ts, "find_nxt_kdc");
 440     assert(ts->nxt_tgt == ts->kdc_tgts[ts->ntgts-1]);
 441     if (krb5_princ_size(ts->ctx, ts->nxt_tgt->server) != 2)
 442         return KRB5_KDCREP_MODIFIED;
 443
 444     r1 = krb5_princ_component(ts->ctx, ts->nxt_tgt->server, 1);
 445
 446     for (kdcptr = ts->cur_kdc + 1; *kdcptr != NULL; kdcptr++) {
 447
 448         r2 = krb5_princ_component(ts->ctx, *kdcptr, 1);
 449
 450         if (r1 != NULL && r2 != NULL &&
 451             r1->length == r2->length &&
 452             !memcmp(r1->data, r2->data, r1->length)) {
 453             break;
 454         }
 455     }
 456     if (*kdcptr == NULL) {
 457         /*
 458          * Not found; we probably got an unexpected realm referral.
 459          * Don't touch NXT_KDC, thus allowing next_closest_tgt() to
 460          * continue looping backwards.
 461          */
 462         if (ts->ntgts > 0) {
 463             /* Punt NXT_TGT from KDC_TGTS if bogus. */
 464             krb5_free_creds(ts->ctx, ts->kdc_tgts[--ts->ntgts]);
 465             ts->kdc_tgts[ts->ntgts] = NULL;
 466         }
 467         TR_DBG_RET(ts, "find_nxt_kdc", KRB5_KDCREP_MODIFIED);
 468         return KRB5_KDCREP_MODIFIED;
 469     }
 470     ts->nxt_kdc = kdcptr;
 471     TR_DBG_RET(ts, "find_nxt_kdc", 0);
 472     return 0;
 473 }
 474
 475 /*
 476  * try_kdc()
 477  *
 478  * Using CUR_TGT, attempt to get desired NXT_TGT.  Update NXT_KDC if
 479  * successful.
 480  */
 481 static krb5_error_code
 482 try_kdc(struct tr_state *ts, krb5_creds *tgtq)
 483 {
 484     krb5_error_code retval;
 485     krb5_creds ltgtq;
 486
 487     TR_DBG(ts, "try_kdc");
 488     /* This check should probably be in gc_via_tkt. */
 489     if (!krb5_c_valid_enctype(ts->cur_tgt->keyblock.enctype))
 490         return KRB5_PROG_ETYPE_NOSUPP;
 491
 492     ltgtq = *tgtq;
 493     ltgtq.is_skey = FALSE;
 494     ltgtq.ticket_flags = ts->cur_tgt->ticket_flags;
 495     retval = krb5_get_cred_via_tkt(ts->ctx, ts->cur_tgt,
 496                                    FLAGS2OPTS(ltgtq.ticket_flags),
 497                                    ts->cur_tgt->addresses,
 498                                    &ltgtq, &ts->kdc_tgts[ts->ntgts++]);
 499     if (retval) {
 500         ts->ntgts--;
 501         ts->nxt_tgt = ts->cur_tgt;
 502         TR_DBG_RET(ts, "try_kdc", retval);
 503         return retval;
 504     }
 505     ts->nxt_tgt = ts->kdc_tgts[ts->ntgts-1];
 506     retval = find_nxt_kdc(ts);
 507     TR_DBG_RET(ts, "try_kdc", retval);
 508     return retval;
 509 }
 510
 511 /*
 512  * kdc_mcred()
 513  *
 514  * Return MCREDS for use as a match criterion.
 515  *
 516  * Resulting credential has CLIENT as the client principal, and
 517  * krbtgt/remote_realm(NXT_KDC)@local_realm(CUR_KDC) as the server
 518  * principal.  Zeroes MCREDS first, does not allocate MCREDS, and
 519  * cleans MCREDS on failure.
 520  */
 521 static krb5_error_code
 522 kdc_mcred(struct tr_state *ts, krb5_principal client, krb5_creds *mcreds)
 523 {
 524     krb5_error_code retval;
 525     krb5_data *rdst, *rsrc;
 526
 527     retval = 0;
 528     memset(mcreds, 0, sizeof(*mcreds));
 529
 530     rdst = krb5_princ_component(ts->ctx, *ts->nxt_kdc, 1);
 531     rsrc = krb5_princ_component(ts->ctx, *ts->cur_kdc, 1);
 532     retval = krb5_copy_principal(ts->ctx, client, &mcreds->client);
 533     if (retval)
 534         goto cleanup;
 535
 536     retval = krb5_tgtname(ts->ctx, rdst, rsrc, &mcreds->server);
 537     if (retval)
 538         goto cleanup;
 539
 540 cleanup:
 541     if (retval)
 542         krb5_free_cred_contents(ts->ctx, mcreds);
 543
 544     return retval;
 545 }
 546
 547 /*
 548  * next_closest_tgt()
 549  *
 550  * Using CUR_TGT, attempt to get the cross-realm TGT having its remote
 551  * realm closest to the target principal's.  Update NXT_TGT, NXT_KDC
 552  * accordingly.
 553  */
 554 static krb5_error_code
 555 next_closest_tgt(struct tr_state *ts, krb5_principal client)
 556 {
 557     krb5_error_code retval;
 558     krb5_creds tgtq;
 559
 560     retval = 0;
 561     memset(&tgtq, 0, sizeof(tgtq));
 562
 563     for (ts->nxt_kdc = ts->lst_kdc;
 564          ts->nxt_kdc > ts->cur_kdc;
 565          ts->nxt_kdc--) {
 566
 567         krb5_free_cred_contents(ts->ctx, &tgtq);
 568         retval = kdc_mcred(ts, client, &tgtq);
 569         if (retval)
 570             goto cleanup;
 571         /* Don't waste time retrying ccache for direct path. */
 572         if (ts->cur_kdc != ts->kdc_list || ts->nxt_kdc != ts->lst_kdc) {
 573             retval = try_ccache(ts, &tgtq);
 574             if (!retval)
 575                 break;
 576             if (HARD_CC_ERR(retval))
 577                 goto cleanup;
 578         }
 579         /* Not in the ccache, so talk to a KDC. */
 580         retval = try_kdc(ts, &tgtq);
 581         if (!retval) {
 582             break;
 583         }
 584         /*
 585          * Because try_kdc() validates referral TGTs, it can return an
 586          * error indicating a bogus referral.  The loop continues when
 587          * it gets a bogus referral, which is arguably the right
 588          * thing.  (Previous implementation unconditionally failed.)
 589          */
 590     }
 591     /*
 592      * If we have a non-zero retval, we either have a hard error or we
 593      * failed to find a closer TGT.
 594      */
 595 cleanup:
 596     krb5_free_cred_contents(ts->ctx, &tgtq);
 597     return retval;
 598 }
 599
 600 /*
 601  * do_traversal()
 602  *
 603  * Find final TGT needed to get CLIENT a ticket for SERVER.  Point
 604  * OUT_TGT at the desired TGT, which may be an existing cached TGT
 605  * (copied into OUT_CC_TGT) or one of the newly obtained TGTs
 606  * (collected in OUT_KDC_TGTS).
 607  *
 608  * Get comfortable; this is somewhat complicated.
 609  *
 610  * Nomenclature: Cross-realm TGS principal names have the form:
 611  *
 612  *     krbtgt/REMOTE@LOCAL
 613  *
 614  * krb5_walk_realm_tree() returns a list like:
 615  *
 616  *     krbtgt/R1@R1, krbtgt/R2@R1, krbtgt/R3@R2, ...
 617  *
 618  * These are prinicpal names, not realm names.  We only really use the
 619  * remote parts of the TGT principal names.
 620  *
 621  * The do_traversal loop calls next_closest_tgt() to find the next
 622  * closest TGT to the destination realm.  next_closest_tgt() updates
 623  * NXT_KDC for the following iteration of the do_traversal() loop.
 624  *
 625  * At the beginning of any given iteration of the do_traversal() loop,
 626  * CUR_KDC's remote realm is the remote realm of CUR_TGT->SERVER.  The
 627  * local realms of CUR_KDC and CUR_TGT->SERVER may not match due to
 628  * short-circuit paths provided by intermediate KDCs, e.g., CUR_KDC
 629  * might be krbtgt/D@C, while CUR_TGT->SERVER is krbtgt/D@B.
 630  *
 631  * For example, given KDC_LIST of
 632  *
 633  * krbtgt/R1@R1, krbtgt/R2@R1, krbtgt/R3@R2, krbtgt/R4@R3,
 634  * krbtgt/R5@R4
 635  *
 636  * The next_closest_tgt() loop moves NXT_KDC to the left starting from
 637  * R5, stopping before it reaches CUR_KDC.  When next_closest_tgt()
 638  * returns, the do_traversal() loop updates CUR_KDC to be NXT_KDC, and
 639  * calls next_closest_tgt() again.
 640  *
 641  * next_closest_tgt() at start of its loop:
 642  *
 643  *      CUR                 NXT
 644  *       |                   |
 645  *       V                   V
 646  *     +----+----+----+----+----+
 647  *     | R1 | R2 | R3 | R4 | R5 |
 648  *     +----+----+----+----+----+
 649  *
 650  * next_closest_tgt() returns after finding a ticket for krbtgt/R3@R1:
 651  *
 652  *      CUR       NXT
 653  *       |         |
 654  *       V         V
 655  *     +----+----+----+----+----+
 656  *     | R1 | R2 | R3 | R4 | R5 |
 657  *     +----+----+----+----+----+
 658  *
 659  * do_traversal() updates CUR_KDC:
 660  *
 661  *                NXT
 662  *                CUR
 663  *                 |
 664  *                 V
 665  *     +----+----+----+----+----+
 666  *     | R1 | R2 | R3 | R4 | R5 |
 667  *     +----+----+----+----+----+
 668  *
 669  * next_closest_tgt() at start of its loop:
 670  *
 671  *                CUR       NXT
 672  *                 |         |
 673  *                 V         V
 674  *     +----+----+----+----+----+
 675  *     | R1 | R2 | R3 | R4 | R5 |
 676  *     +----+----+----+----+----+
 677  *
 678  * etc.
 679  *
 680  * The algorithm executes in n*(n-1)/2 (the sum of integers from 1 to
 681  * n-1) attempts in the worst case, i.e., each KDC only has a
 682  * cross-realm ticket for the immediately following KDC in the transit
 683  * path.  Typically, short-circuit paths will cause execution occur
 684  * faster than this worst-case scenario.
 685  *
 686  * When next_closest_tgt() updates NXT_KDC, it may not perform a
 687  * simple increment from CUR_KDC, in part because some KDC may
 688  * short-circuit pieces of the transit path.
 689  */
 690 static krb5_error_code
 691 do_traversal(krb5_context ctx,
 692              krb5_ccache ccache,
 693              krb5_principal client,
 694              krb5_principal server,
 695              krb5_creds *out_cc_tgt,
 696              krb5_creds **out_tgt,
 697              krb5_creds ***out_kdc_tgts)
 698 {
 699     krb5_error_code retval;
 700     struct tr_state state, *ts;
 701
 702     *out_tgt = NULL;
 703     *out_kdc_tgts = NULL;
 704     ts = &state;
 705     memset(ts, 0, sizeof(*ts));
 706     ts->ctx = ctx;
 707     ts->ccache = ccache;
 708     init_cc_tgts(ts);
 709
 710     retval = init_rtree(ts, client, server);
 711     if (retval)
 712         goto cleanup;
 713
 714     retval = retr_local_tgt(ts, client);
 715     if (retval)
 716         goto cleanup;
 717
 718     for (ts->cur_kdc = ts->kdc_list, ts->nxt_kdc = NULL;
 719          ts->cur_kdc != NULL && ts->cur_kdc < ts->lst_kdc;
 720          ts->cur_kdc = ts->nxt_kdc, ts->cur_tgt = ts->nxt_tgt) {
 721
 722         retval = next_closest_tgt(ts, client);
 723         if (retval)
 724             goto cleanup;
 725         assert(ts->cur_kdc != ts->nxt_kdc);
 726     }
 727
 728     if (NXT_TGT_IS_CACHED(ts)) {
 729         *out_cc_tgt = *ts->cur_cc_tgt;
 730         *out_tgt = out_cc_tgt;
 731         MARK_CUR_CC_TGT_CLEAN(ts);
 732     } else {
 733         /* CUR_TGT is somewhere in KDC_TGTS; no need to copy. */
 734         *out_tgt = ts->nxt_tgt;
 735     }
 736
 737 cleanup:
 738     clean_cc_tgts(ts);
 739     if (ts->kdc_list != NULL)
 740         krb5_free_realm_tree(ctx, ts->kdc_list);
 741     if (ts->ntgts == 0) {
 742         *out_kdc_tgts = NULL;
 743         if (ts->kdc_tgts != NULL)
 744             free(ts->kdc_tgts);
 745     } else
 746         *out_kdc_tgts = ts->kdc_tgts;
 747     return retval;
 748 }
 749
 750 /*
 751  * krb5_get_cred_from_kdc_opt()
 752  * krb5_get_cred_from_kdc()
 753  * krb5_get_cred_from_kdc_validate()
 754  * krb5_get_cred_from_kdc_renew()
 755  *
 756  * Retrieve credentials for client IN_CRED->CLIENT, server
 757  * IN_CRED->SERVER, ticket flags IN_CRED->TICKET_FLAGS, possibly
 758  * second_ticket if needed.
 759  *
 760  * Request credentials from the KDC for the server's realm.  Point
 761  * TGTS to an allocated array of pointers to krb5_creds, containing
 762  * any intermediate credentials obtained in the process of contacting
 763  * the server's KDC; if no intermediate credentials were obtained,
 764  * TGTS is a null pointer.  Return intermediate credentials if
 765  * intermediate KDCs provided credentials, even if no useful end
 766  * ticket results.
 767  *
 768  * Caller must free TGTS, regardless of whether this function returns
 769  * success.
 770  *
 771  * This function does NOT cache the intermediate TGTs.
 772  *
 773  * Do not call this routine if desired credentials are already cached.
 774  *
 775  * On success, OUT_CRED contains the desired credentials; the caller
 776  * must free them.
 777  *
 778  * Beware memory management issues if you have modifications in mind.
 779  * With the addition of referral support, it is now the case that *tgts,
 780  * referral_tgts, tgtptr, referral_tgts, and *out_creds all may point to
 781  * the same credential at different times.
 782  *
 783  * Returns errors, system errors.
 784  */
 785
 786 static krb5_error_code
 787 krb5_get_cred_from_kdc_opt(krb5_context context, krb5_ccache ccache,
 788                            krb5_creds *in_cred, krb5_creds **out_cred,
 789                            krb5_creds ***tgts, int kdcopt)
 790 {
 791     krb5_error_code retval, subretval;
 792     krb5_principal client, server, supplied_server, out_supplied_server;
 793     krb5_creds tgtq, cc_tgt, *tgtptr, *referral_tgts[KRB5_REFERRAL_MAXHOPS];
 794     krb5_boolean old_use_conf_ktypes;
 795     char **hrealms;
 796     int referral_count, i;
 797
 798     /*
 799      * Set up client and server pointers.  Make a fresh and modifyable
 800      * copy of the in_cred server and save the supplied version.
 801      */
 802     client = in_cred->client;
 803     if ((retval=krb5_copy_principal(context, in_cred->server, &server)))
 804         return retval;
 805     /* We need a second copy for the output creds. */
 806     if ((retval = krb5_copy_principal(context, server,
 807                                       &out_supplied_server)) != 0 ) {
 808         krb5_free_principal(context, server);
 809         return retval;
 810     }
 811     supplied_server = in_cred->server;
 812     in_cred->server=server;
 813
 814     DUMP_PRINC("gc_from_kdc initial client", client);
 815     DUMP_PRINC("gc_from_kdc initial server", server);
 816     memset(&cc_tgt, 0, sizeof(cc_tgt));
 817     memset(&tgtq, 0, sizeof(tgtq));
 818     memset(&referral_tgts, 0, sizeof(referral_tgts));
 819
 820     tgtptr = NULL;
 821     *tgts = NULL;
 822     *out_cred=NULL;
 823     old_use_conf_ktypes = context->use_conf_ktypes;
 824
 825     /* Copy client realm to server if no hint. */
 826     if (krb5_is_referral_realm(&server->realm)) {
 827         /* Use the client realm. */
 828         DPRINTF(("gc_from_kdc: no server realm supplied, "
 829                  "using client realm.\n"));
 830         krb5_free_data_contents(context, &server->realm);
 831         if (!( server->realm.data = (char *)malloc(client->realm.length+1)))
 832             return ENOMEM;
 833         memcpy(server->realm.data, client->realm.data, client->realm.length);
 834         server->realm.length = client->realm.length;
 835         server->realm.data[server->realm.length] = 0;
 836     }
 837     /*
 838      * Retreive initial TGT to match the specified server, either for the
 839      * local realm in the default (referral) case or for the remote
 840      * realm if we're starting someplace non-local.
 841      */
 842     retval = tgt_mcred(context, client, server, client, &tgtq);
 843     if (retval)
 844         goto cleanup;
 845
 846     /* Fast path: Is it in the ccache? */
 847     context->use_conf_ktypes = 1;
 848     retval = krb5_cc_retrieve_cred(context, ccache, RETR_FLAGS,
 849                                    &tgtq, &cc_tgt);
 850     if (!retval) {
 851         tgtptr = &cc_tgt;
 852     } else if (!HARD_CC_ERR(retval)) {
 853         DPRINTF(("gc_from_kdc: starting do_traversal to find "
 854                  "initial TGT for referral\n"));
 855         retval = do_traversal(context, ccache, client, server,
 856                               &cc_tgt, &tgtptr, tgts);
 857     }
 858     if (retval) {
 859         DPRINTF(("gc_from_kdc: failed to find initial TGT for referral\n"));
 860         goto cleanup;
 861     }
 862
 863     DUMP_PRINC("gc_from_kdc: server as requested", supplied_server);
 864
 865     /*
 866      * Try requesting a service ticket from our local KDC with referrals
 867      * turned on.  If the first referral succeeds, follow a referral-only
 868      * path, otherwise fall back to old-style assumptions.
 869      */
 870
 871     for (referral_count = 0;
 872          referral_count < KRB5_REFERRAL_MAXHOPS;
 873          referral_count++) {
 874 #if 0
 875         DUMP_PRINC("gc_from_kdc: referral loop: tgt in use", tgtptr->server);
 876         DUMP_PRINC("gc_from_kdc: referral loop: request is for", server);
 877 #endif
 878         retval = krb5_get_cred_via_tkt(context, tgtptr,
 879                                        KDC_OPT_CANONICALIZE |
 880                                        FLAGS2OPTS(tgtptr->ticket_flags) |
 881                                        kdcopt |
 882                                        (in_cred->second_ticket.length ?
 883                                         KDC_OPT_ENC_TKT_IN_SKEY : 0),
 884                                        tgtptr->addresses, in_cred, out_cred);
 885         if (retval) {
 886             DPRINTF(("gc_from_kdc: referral TGS-REQ request failed: <%s>\n",
 887                      error_message(retval)));
 888             /* If we haven't gone anywhere yet, fail through to the
 889                non-referral case. */
 890             if (referral_count==0) {
 891                 DPRINTF(("gc_from_kdc: initial referral failed; "
 892                          "punting to fallback.\n"));
 893                 break;
 894             }
 895             /* Otherwise, try the same query without canonicalization
 896                set, and fail hard if that doesn't work. */
 897             DPRINTF(("gc_from_kdc: referral #%d failed; "
 898                      "retrying without option.\n", referral_count + 1));
 899             retval = krb5_get_cred_via_tkt(context, tgtptr,
 900                                            FLAGS2OPTS(tgtptr->ticket_flags) |
 901                                            kdcopt |
 902                                            (in_cred->second_ticket.length ?
 903                                             KDC_OPT_ENC_TKT_IN_SKEY : 0),
 904                                            tgtptr->addresses,
 905                                            in_cred, out_cred);
 906             /* Whether or not that succeeded, we're done. */
 907             goto cleanup;
 908         }
 909         else {
 910             /* Referral request succeeded; let's see what it is. */
 911             if (krb5_principal_compare(context, in_cred->server,
 912                                        (*out_cred)->server)) {
 913                 DPRINTF(("gc_from_kdc: request generated ticket "
 914                          "for requested server principal\n"));
 915                 DUMP_PRINC("gc_from_kdc final referred reply",
 916                            in_cred->server);
 917                 goto cleanup;
 918             }
 919             else if (IS_TGS_PRINC(context, (*out_cred)->server)) {
 920                 krb5_data *r1, *r2;
 921
 922                 DPRINTF(("gc_from_kdc: request generated referral tgt\n"));
 923                 DUMP_PRINC("gc_from_kdc credential received",
 924                            (*out_cred)->server);
 925
 926                 if (referral_count == 0)
 927                     r1 = &tgtptr->server->data[1];
 928                 else
 929                     r1 = &referral_tgts[referral_count-1]->server->data[1];
 930
 931                 r2 = &(*out_cred)->server->data[1];
 932                 if (r1->length == r2->length &&
 933                     !memcmp(r1->data, r2->data, r1->length)) {
 934                     DPRINTF(("gc_from_kdc: referred back to "
 935                              "previous realm; fall back\n"));
 936                     krb5_free_creds(context, *out_cred);
 937                     *out_cred = NULL;
 938                     break;
 939                 }
 940                 /* Check for referral routing loop. */
 941                 for (i=0;i<referral_count;i++) {
 942 #if 0
 943                     DUMP_PRINC("gc_from_kdc: loop compare #1",
 944                                (*out_cred)->server);
 945                     DUMP_PRINC("gc_from_kdc: loop compare #2",
 946                                referral_tgts[i]->server);
 947 #endif
 948                     if (krb5_principal_compare(context,
 949                                                (*out_cred)->server,
 950                                                referral_tgts[i]->server)) {
 951                         DFPRINTF((stderr,
 952                                   "krb5_get_cred_from_kdc_opt: "
 953                                   "referral routing loop - "
 954                                   "got referral back to hop #%d\n", i));
 955                         retval=KRB5_KDC_UNREACH;
 956                         goto cleanup;
 957                     }
 958                 }
 959                 /* Point current tgt pointer at newly-received TGT. */
 960                 if (tgtptr == &cc_tgt)
 961                     krb5_free_cred_contents(context, tgtptr);
 962                 tgtptr=*out_cred;
 963                 /* Save pointer to tgt in referral_tgts. */
 964                 referral_tgts[referral_count]=*out_cred;
 965                 /* Copy krbtgt realm to server principal. */
 966                 krb5_free_data_contents(context, &server->realm);
 967                 retval = krb5int_copy_data_contents(context,
 968                                                     &tgtptr->server->data[1],
 969                                                     &server->realm);
 970                 if (retval)
 971                     return retval;
 972                 /*
 973                  * Future work: rewrite server principal per any
 974                  * supplied padata.
 975                  */
 976             } else {
 977                 /* Not a TGT; punt to fallback. */
 978                 krb5_free_creds(context, *out_cred);
 979                 *out_cred = NULL;
 980                 break;
 981             }
 982         }
 983     }
 984
 985     DUMP_PRINC("gc_from_kdc client at fallback", client);
 986     DUMP_PRINC("gc_from_kdc server at fallback", server);
 987
 988     /*
 989      * At this point referrals have been tried and have failed.  Go
 990      * back to the server principal as originally issued and try the
 991      * conventional path.
 992      */
 993
 994     /*
 995      * Referrals have failed.  Look up fallback realm if not
 996      * originally provided.
 997      */
 998     if (krb5_is_referral_realm(&supplied_server->realm)) {
 999         if (server->length >= 2) {
1000             retval=krb5_get_fallback_host_realm(context, &server->data[1],
1001                                                 &hrealms);
1002             if (retval) goto cleanup;
1003 #if 0
1004             DPRINTF(("gc_from_kdc: using fallback realm of %s\n",
1005                      hrealms[0]));
1006 #endif
1007             krb5_free_data_contents(context,&in_cred->server->realm);
1008             server->realm.data=hrealms[0];
1009             server->realm.length=strlen(hrealms[0]);
1010             free(hrealms);
1011         }
1012         else {
1013             /*
1014              * Problem case: Realm tagged for referral but apparently not
1015              * in a <type>/<host> format that
1016              * krb5_get_fallback_host_realm can deal with.
1017              */
1018             DPRINTF(("gc_from_kdc: referral specified "
1019                      "but no fallback realm avaiable!\n"));
1020             return KRB5_ERR_HOST_REALM_UNKNOWN;
1021         }
1022     }
1023
1024     DUMP_PRINC("gc_from_kdc server at fallback after fallback rewrite",
1025                server);
1026
1027     /*
1028      * Get a TGT for the target realm.
1029      */
1030
1031     krb5_free_cred_contents(context, &tgtq);
1032     retval = tgt_mcred(context, client, server, client, &tgtq);
1033     if (retval)
1034         goto cleanup;
1035
1036     /* Fast path: Is it in the ccache? */
1037     /* Free tgtptr data if reused from above. */
1038     if (tgtptr == &cc_tgt)
1039         krb5_free_cred_contents(context, tgtptr);
1040     /* Free TGTS if previously filled by do_traversal() */
1041     if (*tgts != NULL) {
1042         for (i = 0; (*tgts)[i] != NULL; i++) {
1043             krb5_free_creds(context, (*tgts)[i]);
1044         }
1045         free(*tgts);
1046         *tgts = NULL;
1047     }
1048     context->use_conf_ktypes = 1;
1049     retval = krb5_cc_retrieve_cred(context, ccache, RETR_FLAGS,
1050                                    &tgtq, &cc_tgt);
1051     if (!retval) {
1052         tgtptr = &cc_tgt;
1053     } else if (!HARD_CC_ERR(retval)) {
1054         retval = do_traversal(context, ccache, client, server,
1055                               &cc_tgt, &tgtptr, tgts);
1056     }
1057     if (retval)
1058         goto cleanup;
1059
1060     /*
1061      * Finally have TGT for target realm!  Try using it to get creds.
1062      */
1063
1064     if (!krb5_c_valid_enctype(tgtptr->keyblock.enctype)) {
1065         retval = KRB5_PROG_ETYPE_NOSUPP;
1066         goto cleanup;
1067     }
1068
1069     context->use_conf_ktypes = old_use_conf_ktypes;
1070     retval = krb5_get_cred_via_tkt(context, tgtptr,
1071                                    FLAGS2OPTS(tgtptr->ticket_flags) |
1072                                    kdcopt |
1073                                    (in_cred->second_ticket.length ?
1074                                     KDC_OPT_ENC_TKT_IN_SKEY : 0),
1075                                    tgtptr->addresses, in_cred, out_cred);
1076
1077 cleanup:
1078     krb5_free_cred_contents(context, &tgtq);
1079     if (tgtptr == &cc_tgt)
1080         krb5_free_cred_contents(context, tgtptr);
1081     context->use_conf_ktypes = old_use_conf_ktypes;
1082     /* Drop the original principal back into in_cred so that it's cached
1083        in the expected format. */
1084     DUMP_PRINC("gc_from_kdc: final hacked server principal at cleanup",
1085                server);
1086     krb5_free_principal(context, server);
1087     in_cred->server = supplied_server;
1088     if (*out_cred && !retval) {
1089         /* Success: free server, swap supplied server back in. */
1090         krb5_free_principal (context, (*out_cred)->server);
1091         (*out_cred)->server= out_supplied_server;
1092     }
1093     else {
1094         /*
1095          * Failure: free out_supplied_server.  Don't free out_cred here
1096          * since it's either null or a referral TGT that we free below,
1097          * and we may need it to return.
1098          */
1099         krb5_free_principal (context, out_supplied_server);
1100     }
1101     DUMP_PRINC("gc_from_kdc: final server after reversion", in_cred->server);
1102     /*
1103      * Deal with ccache TGT management: If tgts has been set from
1104      * initial non-referral TGT discovery, leave it alone.  Otherwise, if
1105      * referral_tgts[0] exists return it as the only entry in tgts.
1106      * (Further referrals are never cached, only the referral from the
1107      * local KDC.)  This is part of cleanup because useful received TGTs
1108      * should be cached even if the main request resulted in failure.
1109      */
1110
1111     if (*tgts == NULL) {
1112         if (referral_tgts[0]) {
1113 #if 0
1114             /*
1115              * This should possibly be a check on the candidate return
1116              * credential against the cache, in the circumstance where we
1117              * don't want to clutter the cache with near-duplicate
1118              * credentials on subsequent iterations.  For now, it is
1119              * disabled.
1120              */
1121             subretval=...?;
1122             if (subretval) {
1123 #endif
1124                 /* Allocate returnable TGT list. */
1125                 if (!(*tgts=calloc(sizeof (krb5_creds *), 2)))
1126                     return ENOMEM;
1127                 subretval=krb5_copy_creds(context, referral_tgts[0], &((*tgts)[0]));
1128                 if(subretval)
1129                     return subretval;
1130                 (*tgts)[1]=NULL;
1131                 DUMP_PRINC("gc_from_kdc: returning referral TGT for ccache",
1132                            (*tgts)[0]->server);
1133 #if 0
1134             }
1135 #endif
1136         }
1137     }
1138
1139     /* Free referral TGTs list. */
1140     for (i=0;i<KRB5_REFERRAL_MAXHOPS;i++) {
1141         if(referral_tgts[i]) {
1142             krb5_free_creds(context, referral_tgts[i]);
1143         }
1144     }
1145     DPRINTF(("gc_from_kdc finishing with %s\n",
1146              retval ? error_message(retval) : "no error"));
1147     return retval;
1148 }
1149
1150 krb5_error_code
1151 krb5_get_cred_from_kdc(krb5_context context, krb5_ccache ccache,
1152                        krb5_creds *in_cred, krb5_creds **out_cred,
1153                        krb5_creds ***tgts)
1154 {
1155     return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
1156                                       0);
1157 }
1158
1159 krb5_error_code
1160 krb5_get_cred_from_kdc_validate(krb5_context context, krb5_ccache ccache,
1161                                 krb5_creds *in_cred, krb5_creds **out_cred,
1162                                 krb5_creds ***tgts)
1163 {
1164     return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
1165                                       KDC_OPT_VALIDATE);
1166 }
1167
1168 krb5_error_code
1169 krb5_get_cred_from_kdc_renew(krb5_context context, krb5_ccache ccache,
1170                              krb5_creds *in_cred, krb5_creds **out_cred,
1171                              krb5_creds ***tgts)
1172 {
1173     return krb5_get_cred_from_kdc_opt(context, ccache, in_cred, out_cred, tgts,
1174                                       KDC_OPT_RENEW);
1175 }