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