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