src/lib/krb5/krb/walk_rtree.c

   1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 /* lib/krb5/krb/walk_rtree.c */
   3 /*
   4  * Copyright 1990,1991,2008,2009 by the Massachusetts Institute of Technology.
   5  * All Rights Reserved.
   6  *
   7  * Export of this software from the United States of America may
   8  *   require a specific license from the United States Government.
   9  *   It is the responsibility of any person or organization contemplating
  10  *   export to obtain such a license before exporting.
  11  *
  12  * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
  13  * distribute this software and its documentation for any purpose and
  14  * without fee is hereby granted, provided that the above copyright
  15  * notice appear in all copies and that both that copyright notice and
  16  * this permission notice appear in supporting documentation, and that
  17  * the name of M.I.T. not be used in advertising or publicity pertaining
  18  * to distribution of the software without specific, written prior
  19  * permission.  Furthermore if you modify this software you must label
  20  * your software as modified software and not distribute it in such a
  21  * fashion that it might be confused with the original M.I.T. software.
  22  * M.I.T. makes no representations about the suitability of
  23  * this software for any purpose.  It is provided "as is" without express
  24  * or implied warranty.
  25  */
  26
  27 /*
  28  * krb5_walk_realm_tree()
  29  * krb5_free_realm_tree()
  30  *
  31  * internal function, used by krb5_get_cred_from_kdc()
  32  */
  33
  34 #include "k5-int.h"
  35 #include "int-proto.h"
  36
  37 /*
  38  * Structure to help with finding the common suffix between client and
  39  * server realm during hierarchical traversal.
  40  */
  41 struct hstate {
  42     char *str;
  43     size_t len;
  44     char *tail;
  45     char *dot;
  46 };
  47
  48 static krb5_error_code
  49 rtree_capath_tree(krb5_context context,
  50                   const krb5_data *client,
  51                   const krb5_data *server,
  52                   char **vals,
  53                   krb5_principal **tree);
  54
  55 static krb5_error_code
  56 rtree_capath_vals(krb5_context context,
  57                   const krb5_data *client,
  58                   const krb5_data *server,
  59                   char ***vals);
  60
  61 static krb5_error_code
  62 rtree_hier_tree(krb5_context context,
  63                 const krb5_data *client,
  64                 const krb5_data *server,
  65                 krb5_principal **rettree,
  66                 int sep);
  67
  68 static krb5_error_code
  69 rtree_hier_realms(krb5_context context,
  70                   const krb5_data *client,
  71                   const krb5_data *server,
  72                   krb5_data **realms,
  73                   size_t *nrealms,
  74                   int sep);
  75
  76 static void
  77 free_realmlist(krb5_context context,
  78                krb5_data *realms,
  79                size_t nrealms);
  80
  81 static krb5_error_code
  82 rtree_hier_tweens(krb5_context context,
  83                   struct hstate *realm,
  84                   krb5_data **tweens,
  85                   size_t *ntweens,
  86                   int dotail,
  87                   int sep);
  88
  89 static void
  90 adjtail(struct hstate *c, struct hstate *s, int sep);
  91
  92 static void
  93 comtail(struct hstate *c, struct hstate *s, int sep);
  94
  95 krb5_error_code
  96 krb5_walk_realm_tree( krb5_context context,
  97                       const krb5_data *client,
  98                       const krb5_data *server,
  99                       krb5_principal **tree,
 100                       int realm_sep)
 101 {
 102     krb5_error_code retval = 0;
 103     char **capvals;
 104
 105     if (client->data == NULL || server->data == NULL)
 106         return KRB5_NO_TKT_IN_RLM;
 107
 108     if (data_eq(*client, *server))
 109         return KRB5_NO_TKT_IN_RLM;
 110     retval = rtree_capath_vals(context, client, server, &capvals);
 111     if (retval)
 112         return retval;
 113
 114     if (capvals != NULL) {
 115         retval = rtree_capath_tree(context, client, server, capvals, tree);
 116         return retval;
 117     }
 118
 119     retval = rtree_hier_tree(context, client, server, tree, realm_sep);
 120     return retval;
 121 }
 122
 123 krb5_error_code
 124 k5_client_realm_path(krb5_context context, const krb5_data *client,
 125                      const krb5_data *server, krb5_data **rpath_out)
 126 {
 127     krb5_error_code retval;
 128     char **capvals = NULL;
 129     size_t i;
 130     krb5_data *rpath = NULL, d;
 131
 132     retval = rtree_capath_vals(context, client, server, &capvals);
 133     if (retval)
 134         return retval;
 135
 136     /* A capaths value of "." means no intermediates. */
 137     if (capvals != NULL && capvals[0] != NULL && *capvals[0] == '.') {
 138         profile_free_list(capvals);
 139         capvals = NULL;
 140     }
 141
 142     /* Count capaths (if any) and allocate space.  Leave room for the client
 143      * realm, server realm, and terminator. */
 144     for (i = 0; capvals != NULL && capvals[i] != NULL; i++);
 145     rpath = calloc(i + 3, sizeof(*rpath));
 146     if (rpath == NULL)
 147         return ENOMEM;
 148
 149     /* Populate rpath with the client realm, capaths, and server realm. */
 150     retval = krb5int_copy_data_contents(context, client, &rpath[0]);
 151     if (retval)
 152         goto cleanup;
 153     for (i = 0; capvals != NULL && capvals[i] != NULL; i++) {
 154         d = make_data(capvals[i], strcspn(capvals[i], "\t "));
 155         retval = krb5int_copy_data_contents(context, &d, &rpath[i + 1]);
 156         if (retval)
 157             goto cleanup;
 158     }
 159     retval = krb5int_copy_data_contents(context, server, &rpath[i + 1]);
 160     if (retval)
 161         goto cleanup;
 162
 163     /* Terminate rpath and return it. */
 164     rpath[i + 2] = empty_data();
 165     *rpath_out = rpath;
 166     rpath = NULL;
 167
 168 cleanup:
 169     profile_free_list(capvals);
 170     krb5int_free_data_list(context, rpath);
 171     return retval;
 172 }
 173
 174 /* ANL - Modified to allow Configurable Authentication Paths.
 175  * This modification removes the restriction on the choice of realm
 176  * names, i.e. they nolonger have to be hierarchical. This
 177  * is allowed by RFC 1510: "If a hierarchical organization is not used
 178  * it may be necessary to consult some database in order to construct
 179  * an authentication path between realms."  The database is contained
 180  * in the [capaths] section of the krb5.conf file.
 181  * Client to server paths are defined. There are n**2 possible
 182  * entries, but only those entries which are needed by the client
 183  * or server need be present in its krb5.conf file. (n entries or 2*n
 184  * entries if the same krb5.conf is used for clients and servers)
 185  *
 186  * for example: ESnet will be running a KDC which will share
 187  * inter-realm keys with its many organizations which include among
 188  * other ANL, NERSC and PNL. Each of these organizations wants to
 189  * use its DNS name in the realm, ANL.GOV. In addition ANL wants
 190  * to authenticatite to HAL.COM via a K5.MOON and K5.JUPITER
 191  * A [capaths] section of the krb5.conf file for the ANL.GOV clients
 192  * and servers would look like:
 193  *
 194  * [capaths]
 195  * ANL.GOV = {
 196  *              NERSC.GOV = ES.NET
 197  *              PNL.GOV = ES.NET
 198  *              ES.NET = .
 199  *              HAL.COM = K5.MOON
 200  *              HAL.COM = K5.JUPITER
 201  * }
 202  * NERSC.GOV = {
 203  *              ANL.GOV = ES.NET
 204  * }
 205  * PNL.GOV = {
 206  *              ANL.GOV = ES.NET
 207  * }
 208  * ES.NET = {
 209  *              ANL.GOV = .
 210  * }
 211  * HAL.COM = {
 212  *              ANL.GOV = K5.JUPITER
 213  *              ANL.GOV = K5.MOON
 214  * }
 215  *
 216  * In the above a "." is used to mean directly connected since the
 217  * the profile routines cannot handle a null entry.
 218  *
 219  * If no client-to-server path is found, the default hierarchical path
 220  * is still generated.
 221  *
 222  * This version of the Configurable Authentication Path modification
 223  * differs from the previous versions prior to K5 beta 5 in that
 224  * the profile routines are used, and the explicit path from client's
 225  * realm to server's realm must be given. The modifications will work
 226  * together.
 227  * DEE - 5/23/95
 228  */
 229
 230 /*
 231  * Build a tree given a set of profile values retrieved by
 232  * walk_rtree_capath_vals().
 233  */
 234 static krb5_error_code
 235 rtree_capath_tree(krb5_context context,
 236                   const krb5_data *client,
 237                   const krb5_data *server,
 238                   char **vals,
 239                   krb5_principal **rettree)
 240 {
 241     krb5_error_code retval = 0;
 242     unsigned int nvals, nlinks, nprincs, i;
 243     krb5_data srcrealm, dstrealm;
 244     krb5_principal *tree, *pprinc;
 245
 246     *rettree = NULL;
 247     tree = pprinc = NULL;
 248     for (nvals = 0; vals[nvals] != NULL; nvals++)
 249         ;
 250     if (vals[0] != NULL && *vals[0] == '.') {
 251         nlinks = 0;
 252     } else {
 253         nlinks = nvals;
 254     }
 255     nprincs = nlinks + 2;
 256     tree = calloc(nprincs + 1, sizeof(krb5_principal));
 257     if (tree == NULL) {
 258         retval = ENOMEM;
 259         goto error;
 260     }
 261     for (i = 0; i < nprincs + 1; i++)
 262         tree[i] = NULL;
 263     /* Invariant: PPRINC points one past end of list. */
 264     pprinc = &tree[0];
 265     /* Local TGS name */
 266     retval = krb5int_tgtname(context, client, client, pprinc++);
 267     if (retval) goto error;
 268     srcrealm = *client;
 269     for (i = 0; i < nlinks; i++) {
 270         dstrealm.data = vals[i];
 271         dstrealm.length = strcspn(vals[i], "\t ");
 272         retval = krb5int_tgtname(context, &dstrealm, &srcrealm, pprinc++);
 273         if (retval) goto error;
 274         srcrealm = dstrealm;
 275     }
 276     retval = krb5int_tgtname(context, server, &srcrealm, pprinc++);
 277     if (retval) goto error;
 278     *rettree = tree;
 279
 280 error:
 281     profile_free_list(vals);
 282     if (retval) {
 283         while (pprinc != NULL && pprinc > &tree[0]) {
 284             /* krb5_free_principal() correctly handles null input */
 285             krb5_free_principal(context, *--pprinc);
 286             *pprinc = NULL;
 287         }
 288         free(tree);
 289     }
 290     return retval;
 291 }
 292
 293 /*
 294  * Get realm list from "capaths" section of the profile.  Deliberately
 295  * returns success but leaves VALS null if profile_get_values() fails
 296  * by not finding anything.
 297  */
 298 static krb5_error_code
 299 rtree_capath_vals(krb5_context context,
 300                   const krb5_data *client,
 301                   const krb5_data *server,
 302                   char ***vals)
 303 {
 304     krb5_error_code retval = 0;
 305     /* null-terminated realm names */
 306     char *clientz = NULL, *serverz = NULL;
 307     const char *key[4];
 308
 309     *vals = NULL;
 310
 311     clientz = k5memdup0(client->data, client->length, &retval);
 312     if (clientz == NULL)
 313         goto error;
 314
 315     serverz = k5memdup0(server->data, server->length, &retval);
 316     if (serverz == NULL)
 317         goto error;
 318
 319     key[0] = "capaths";
 320     key[1] = clientz;
 321     key[2] = serverz;
 322     key[3] = NULL;
 323     retval = profile_get_values(context->profile, key, vals);
 324     switch (retval) {
 325     case PROF_NO_SECTION:
 326     case PROF_NO_RELATION:
 327         /*
 328          * Not found; don't return an error.
 329          */
 330         retval = 0;
 331         break;
 332     default:
 333         break;
 334     }
 335 error:
 336     free(clientz);
 337     free(serverz);
 338     return retval;
 339 }
 340
 341 /*
 342  * Build tree by hierarchical traversal.
 343  */
 344 static krb5_error_code
 345 rtree_hier_tree(krb5_context context,
 346                 const krb5_data *client,
 347                 const krb5_data *server,
 348                 krb5_principal **rettree,
 349                 int sep)
 350 {
 351     krb5_error_code retval;
 352     krb5_data *realms;
 353     const krb5_data *dstrealm, *srcrealm;
 354     krb5_principal *tree, *pprinc;
 355     size_t nrealms, nprincs, i;
 356
 357     *rettree = NULL;
 358     retval = rtree_hier_realms(context, client, server,
 359                                &realms, &nrealms, sep);
 360     if (retval)
 361         return retval;
 362     nprincs = nrealms;
 363     pprinc = tree = calloc(nprincs + 1, sizeof(krb5_principal));
 364     if (tree == NULL) {
 365         retval = ENOMEM;
 366         goto error;
 367     }
 368     for (i = 0; i < nrealms; i++)
 369         tree[i] = NULL;
 370     srcrealm = client;
 371     for (i = 0; i < nrealms; i++) {
 372         dstrealm = &realms[i];
 373         retval = krb5int_tgtname(context, dstrealm, srcrealm, pprinc++);
 374         if (retval) goto error;
 375         srcrealm = dstrealm;
 376     }
 377     *rettree = tree;
 378     free_realmlist(context, realms, nrealms);
 379     return 0;
 380 error:
 381     while (pprinc != NULL && pprinc > tree) {
 382         krb5_free_principal(context, *--pprinc);
 383         *pprinc = NULL;
 384     }
 385     free_realmlist(context, realms, nrealms);
 386     free(tree);
 387     return retval;
 388 }
 389
 390 /*
 391  * Construct list of realms between client and server.
 392  */
 393 static krb5_error_code
 394 rtree_hier_realms(krb5_context context,
 395                   const krb5_data *client,
 396                   const krb5_data *server,
 397                   krb5_data **realms,
 398                   size_t *nrealms,
 399                   int sep)
 400 {
 401     krb5_error_code retval;
 402     struct hstate c, s;
 403     krb5_data *ctweens = NULL, *stweens = NULL, *twp, *r, *rp;
 404     size_t nctween, nstween;
 405
 406     *realms = NULL;
 407     *nrealms = 0;
 408
 409     r = rp = NULL;
 410     c.str = client->data;
 411     c.len = client->length;
 412     c.dot = c.tail = NULL;
 413     s.str = server->data;
 414     s.len = server->length;
 415     s.dot = s.tail = NULL;
 416
 417     comtail(&c, &s, sep);
 418     adjtail(&c, &s, sep);
 419
 420     retval = rtree_hier_tweens(context, &c, &ctweens, &nctween, 1, sep);
 421     if (retval) goto error;
 422     retval = rtree_hier_tweens(context, &s, &stweens, &nstween, 0, sep);
 423     if (retval) goto error;
 424
 425     rp = r = calloc(nctween + nstween, sizeof(krb5_data));
 426     if (r == NULL) {
 427         retval = ENOMEM;
 428         goto error;
 429     }
 430     /* Copy client realm "tweens" forward. */
 431     for (twp = ctweens; twp < &ctweens[nctween]; twp++) {
 432         retval = krb5int_copy_data_contents(context, twp, rp);
 433         if (retval) goto error;
 434         rp++;
 435     }
 436     /* Copy server realm "tweens" backward. */
 437     for (twp = &stweens[nstween]; twp-- > stweens;) {
 438         retval = krb5int_copy_data_contents(context, twp, rp);
 439         if (retval) goto error;
 440         rp++;
 441     }
 442 error:
 443     free(ctweens);
 444     free(stweens);
 445     if (retval) {
 446         free_realmlist(context, r, rp - r);
 447         return retval;
 448     }
 449     *realms = r;
 450     *nrealms = rp - r;
 451     return 0;
 452 }
 453
 454 static void
 455 free_realmlist(krb5_context context,
 456                krb5_data *realms,
 457                size_t nrealms)
 458 {
 459     size_t i;
 460
 461     for (i = 0; i < nrealms; i++)
 462         krb5_free_data_contents(context, &realms[i]);
 463     free(realms);
 464 }
 465
 466 /*
 467  * Build a list of realms between a given realm and the common
 468  * suffix.  The original realm is included, but the "tail" is only
 469  * included if DOTAIL is true.
 470  *
 471  * Warning: This function intentionally aliases memory.  Caller must
 472  * make copies as needed and not call krb5_free_data_contents, etc.
 473  */
 474 static krb5_error_code
 475 rtree_hier_tweens(krb5_context context,
 476                   struct hstate *realm,
 477                   krb5_data **tweens,
 478                   size_t *ntweens,
 479                   int dotail,
 480                   int sep)
 481 {
 482     char *p, *r, *rtail, *lp;
 483     size_t rlen, n;
 484     krb5_data *tws, *ntws;
 485
 486     r = realm->str;
 487     rlen = realm->len;
 488     rtail = realm->tail;
 489     *tweens = ntws = tws = NULL;
 490     *ntweens = n = 0;
 491
 492     for (lp = p = r; p < &r[rlen]; p++) {
 493         if (*p != sep && &p[1] != &r[rlen])
 494             continue;
 495         if (lp == rtail && !dotail)
 496             break;
 497         ntws = realloc(tws, (n + 1) * sizeof(krb5_data));
 498         if (ntws == NULL) {
 499             free(tws);
 500             return ENOMEM;
 501         }
 502         tws = ntws;
 503         tws[n].data = lp;
 504         tws[n].length = &r[rlen] - lp;
 505         n++;
 506         if (lp == rtail)
 507             break;
 508         lp = &p[1];
 509     }
 510     *tweens = tws;
 511     *ntweens = n;
 512     return 0;
 513 }
 514
 515 /*
 516  * Adjust suffixes that each starts at the beginning of a component,
 517  * to avoid the problem where "BC.EXAMPLE.COM" is erroneously reported
 518  * as a parent of "ABC.EXAMPLE.COM".
 519  */
 520 static void
 521 adjtail(struct hstate *c, struct hstate *s, int sep)
 522 {
 523     int cfull, sfull;
 524     char *cp, *sp;
 525
 526     cp = c->tail;
 527     sp = s->tail;
 528     if (cp == NULL || sp == NULL)
 529         return;
 530     /*
 531      * Is it a full component?  Yes, if it's the beginning of the
 532      * string or there's a separator to the left.
 533      *
 534      * The index of -1 is valid because it only gets evaluated if the
 535      * pointer is not at the beginning of the string.
 536      */
 537     cfull = (cp == c->str || cp[-1] == sep);
 538     sfull = (sp == s->str || sp[-1] == sep);
 539     /*
 540      * If they're both full components, we're done.
 541      */
 542     if (cfull && sfull) {
 543         return;
 544     } else if (c->dot != NULL && s->dot != NULL) {
 545         cp = c->dot + 1;
 546         sp = s->dot + 1;
 547         /*
 548          * Out of bounds? Can only happen if there are trailing dots.
 549          */
 550         if (cp >= &c->str[c->len] || sp >= &s->str[s->len]) {
 551             cp = sp = NULL;
 552         }
 553     } else {
 554         cp = sp = NULL;
 555     }
 556     c->tail = cp;
 557     s->tail = sp;
 558 }
 559
 560 /*
 561  * Find common suffix of C and S.
 562  *
 563  * C->TAIL and S->TAIL will point to the respective suffixes.  C->DOT
 564  * and S->DOT will point to the nearest instances of SEP to the right
 565  * of the start of each suffix.  Caller must initialize TAIL and DOT
 566  * pointers to null.
 567  */
 568 static void
 569 comtail(struct hstate *c, struct hstate *s, int sep)
 570 {
 571     char *cp, *sp, *cdot, *sdot;
 572
 573     if (c->len == 0 || s->len == 0)
 574         return;
 575
 576     cdot = sdot = NULL;
 577     /*
 578      * ANSI/ISO C allows a pointer one past the end but not one
 579      * before the beginning of an array.
 580      */
 581     cp = &c->str[c->len];
 582     sp = &s->str[s->len];
 583     /*
 584      * Set CP and SP to point to the common suffix of each string.
 585      * When we run into separators (dots, unless someone has a X.500
 586      * style realm), keep pointers to the latest pair.
 587      */
 588     while (cp > c->str && sp > s->str) {
 589         if (*--cp != *--sp) {
 590             /*
 591              * Didn't match, so most recent match is one byte to the
 592              * right (or not at all).
 593              */
 594             cp++;
 595             sp++;
 596             break;
 597         }
 598         /*
 599          * Keep track of matching dots.
 600          */
 601         if (*cp == sep) {
 602             cdot = cp;
 603             sdot = sp;
 604         }
 605     }
 606     /* No match found at all. */
 607     if (cp == &c->str[c->len])
 608         return;
 609     c->tail = cp;
 610     s->tail = sp;
 611     c->dot = cdot;
 612     s->dot = sdot;
 613 }
 614
 615 void
 616 krb5_free_realm_tree(krb5_context context, krb5_principal *realms)
 617 {
 618     krb5_principal *nrealms = realms;
 619     if (realms == NULL)
 620         return;
 621     while (*nrealms) {
 622         krb5_free_principal(context, *nrealms);
 623         nrealms++;
 624     }
 625     free(realms);
 626 }