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