/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
/*
* lib/krb5/krb/walk_rtree.c
*
* Copyright 1990,1991,2008,2009 by the Massachusetts Institute of Technology.
* All Rights Reserved.
*
* Export of this software from the United States of America may
* require a specific license from the United States Government.
* It is the responsibility of any person or organization contemplating
* export to obtain such a license before exporting.
*
* WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
* distribute this software and its documentation for any purpose and
* without fee is hereby granted, provided that the above copyright
* notice appear in all copies and that both that copyright notice and
* this permission notice appear in supporting documentation, and that
* the name of M.I.T. not be used in advertising or publicity pertaining
* to distribution of the software without specific, written prior
* permission. Furthermore if you modify this software you must label
* your software as modified software and not distribute it in such a
* fashion that it might be confused with the original M.I.T. software.
* M.I.T. makes no representations about the suitability of
* this software for any purpose. It is provided "as is" without express
* or implied warranty.
*/
/*
* Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved.
*/
/* krb5_walk_realm_tree()
* krb5_free_realm_tree()
*
* internal function, used by krb5_get_cred_from_kdc()
*/
#include "k5-int.h"
#include "int-proto.h"
/* Solaris Kerberos */
#include <locale.h>
/*
* Structure to help with finding the common suffix between client and
* server realm during hierarchical traversal.
*/
struct hstate {
char *str;
size_t len;
char *tail;
char *dot;
};
static krb5_error_code
rtree_capath_tree(krb5_context context,
const krb5_data *client,
const krb5_data *server,
char **vals,
krb5_principal **tree);
static krb5_error_code
rtree_capath_vals(krb5_context context,
const krb5_data *client,
const krb5_data *server,
char ***vals);
static krb5_error_code
rtree_hier_tree(krb5_context context,
const krb5_data *client,
const krb5_data *server,
krb5_principal **rettree,
int sep);
static krb5_error_code
rtree_hier_realms(krb5_context context,
const krb5_data *client,
const krb5_data *server,
krb5_data **realms,
size_t *nrealms,
int sep);
static void
free_realmlist(krb5_context context,
krb5_data *realms,
size_t nrealms);
static krb5_error_code
rtree_hier_tweens(krb5_context context,
struct hstate *realm,
krb5_data **tweens,
size_t *ntweens,
int dotail,
int sep);
static void
adjtail(struct hstate *c, struct hstate *s, int sep);
static void
comtail(struct hstate *c, struct hstate *s, int sep);
krb5_error_code
krb5_walk_realm_tree( krb5_context context,
const krb5_data *client,
const krb5_data *server,
krb5_principal **tree,
int realm_sep)
{
krb5_error_code retval = 0;
char **capvals;
if (client->data == NULL || server->data == NULL) {
/* Solaris Kerberos - enhance error message */
if (client->data == NULL && server->data == NULL) {
krb5_set_error_message(context, KRB5_NO_TKT_IN_RLM,
dgettext(TEXT_DOMAIN,
"Cannot find ticket for "
"requested realm: unknown "
"client and server"));
} else {
if (client->data == NULL) {
krb5_set_error_message(context, KRB5_NO_TKT_IN_RLM,
dgettext(TEXT_DOMAIN,
"Cannot find ticket for "
"requested realm: unknown "
"client"));
} else {
krb5_set_error_message(context, KRB5_NO_TKT_IN_RLM,
dgettext(TEXT_DOMAIN,
"Cannot find ticket for "
"requested realm: unknown "
"server"));
}
}
return KRB5_NO_TKT_IN_RLM;
}
if (client->length == server->length &&
memcmp(client->data, server->data, server->length) == 0) {
return KRB5_NO_TKT_IN_RLM;
}
retval = rtree_capath_vals(context, client, server, &capvals);
if (retval)
return retval;
if (capvals != NULL) {
retval = rtree_capath_tree(context, client, server, capvals, tree);
return retval;
}
retval = rtree_hier_tree(context, client, server, tree, realm_sep);
return retval;
}
/* ANL - Modified to allow Configurable Authentication Paths.
* This modification removes the restriction on the choice of realm
* names, i.e. they nolonger have to be hierarchical. This
* is allowed by RFC 1510: "If a hierarchical orginization is not used
* it may be necessary to consult some database in order to construct
* an authentication path between realms." The database is contained
* in the [capaths] section of the krb5.conf file.
* Client to server paths are defined. There are n**2 possible
* entries, but only those entries which are needed by the client
* or server need be present in its krb5.conf file. (n entries or 2*n
* entries if the same krb5.conf is used for clients and servers)
*
* for example: ESnet will be running a KDC which will share
* inter-realm keys with its many orginizations which include among
* other ANL, NERSC and PNL. Each of these orginizations wants to
* use its DNS name in the realm, ANL.GOV. In addition ANL wants
* to authenticatite to HAL.COM via a K5.MOON and K5.JUPITER
* A [capaths] section of the krb5.conf file for the ANL.GOV clients
* and servers would look like:
*
* [capaths]
* ANL.GOV = {
* NERSC.GOV = ES.NET
* PNL.GOV = ES.NET
* ES.NET = .
* HAL.COM = K5.MOON
* HAL.COM = K5.JUPITER
* }
* NERSC.GOV = {
* ANL.GOV = ES.NET
* }
* PNL.GOV = {
* ANL.GOV = ES.NET
* }
* ES.NET = {
* ANL.GOV = .
* }
* HAL.COM = {
* ANL.GOV = K5.JUPITER
* ANL.GOV = K5.MOON
* }
*
* In the above a "." is used to mean directly connected since the
* the profile routines cannot handle a null entry.
*
* If no client-to-server path is found, the default hierarchical path
* is still generated.
*
* This version of the Configurable Authentication Path modification
* differs from the previous versions prior to K5 beta 5 in that
* the profile routines are used, and the explicite path from
* client's realm to server's realm must be given. The modifications
* will work together.
* DEE - 5/23/95
*/
/*
* Build a tree given a set of profile values retrieved by
* walk_rtree_capath_vals().
*/
static krb5_error_code
rtree_capath_tree(krb5_context context,
const krb5_data *client,
const krb5_data *server,
char **vals,
krb5_principal **rettree)
{
krb5_error_code retval = 0;
unsigned int nvals, nlinks, nprincs, i;
krb5_data srcrealm, dstrealm;
krb5_principal *tree, *pprinc;
*rettree = NULL;
tree = pprinc = NULL;
for (nvals = 0; vals[nvals] != NULL; nvals++)
;
if (vals[0] != NULL && *vals[0] == '.') {
nlinks = 0;
} else {
nlinks = nvals;
}
nprincs = nlinks + 2;
tree = calloc(nprincs + 1, sizeof(krb5_principal));
if (tree == NULL) {
retval = ENOMEM;
goto error;
}
for (i = 0; i < nprincs + 1; i++)
tree[i] = NULL;
/* Invariant: PPRINC points one past end of list. */
pprinc = &tree[0];
/* Local TGS name */
retval = krb5_tgtname(context, client, client, pprinc++);
if (retval) goto error;
srcrealm = *client;
for (i = 0; i < nlinks; i++) {
dstrealm.data = vals[i];
dstrealm.length = strcspn(vals[i], "\t ");
retval = krb5_tgtname(context, &dstrealm, &srcrealm, pprinc++);
if (retval) goto error;
srcrealm = dstrealm;
}
retval = krb5_tgtname(context, server, &srcrealm, pprinc++);
if (retval) goto error;
*rettree = tree;
error:
profile_free_list(vals);
if (retval) {
while (pprinc != NULL && pprinc > &tree[0]) {
/* krb5_free_principal() correctly handles null input */
krb5_free_principal(context, *--pprinc);
*pprinc = NULL;
}
free(tree);
}
return retval;
}
/*
* Get realm list from "capaths" section of the profile. Deliberately
* returns success but leaves VALS null if profile_get_values() fails
* by not finding anything.
*/
static krb5_error_code
rtree_capath_vals(krb5_context context,
const krb5_data *client,
const krb5_data *server,
char ***vals)
{
krb5_error_code retval = 0;
/* null-terminated realm names */
char *clientz = NULL, *serverz = NULL;
const char *key[4];
*vals = NULL;
clientz = calloc(client->length + 1, 1);
if (clientz == NULL) {
retval = ENOMEM;
goto error;
}
memcpy(clientz, client->data, client->length);
serverz = calloc(server->length + 1, 1);
if (serverz == NULL) {
retval = ENOMEM;
goto error;
}
memcpy(serverz, server->data, server->length);
key[0] = "capaths";
key[1] = clientz;
key[2] = serverz;
key[3] = NULL;
retval = profile_get_values(context->profile, key, vals);
switch (retval) {
case PROF_NO_SECTION:
case PROF_NO_RELATION:
/*
* Not found; don't return an error.
*/
retval = 0;
break;
default:
break;
}
error:
free(clientz);
free(serverz);
return retval;
}
/*
* Build tree by hierarchical traversal.
*/
static krb5_error_code
rtree_hier_tree(krb5_context context,
const krb5_data *client,
const krb5_data *server,
krb5_principal **rettree,
int sep)
{
krb5_error_code retval;
krb5_data *realms;
const krb5_data *dstrealm, *srcrealm;
krb5_principal *tree, *pprinc;
size_t nrealms, nprincs, i;
*rettree = NULL;
retval = rtree_hier_realms(context, client, server,
&realms, &nrealms, sep);
if (retval)
return retval;
nprincs = nrealms;
pprinc = tree = calloc(nprincs + 1, sizeof(krb5_principal));
if (tree == NULL) {
retval = ENOMEM;
goto error;
}
for (i = 0; i < nrealms; i++)
tree[i] = NULL;
srcrealm = client;
for (i = 0; i < nrealms; i++) {
dstrealm = &realms[i];
retval = krb5_tgtname(context, dstrealm, srcrealm, pprinc++);
if (retval) goto error;
srcrealm = dstrealm;
}
*rettree = tree;
free_realmlist(context, realms, nrealms);
return 0;
error:
while (pprinc != NULL && pprinc > tree) {
krb5_free_principal(context, *--pprinc);
*pprinc = NULL;
}
free_realmlist(context, realms, nrealms);
free(tree);
return retval;
}
/*
* Construct list of realms between client and server.
*/
static krb5_error_code
rtree_hier_realms(krb5_context context,
const krb5_data *client,
const krb5_data *server,
krb5_data **realms,
size_t *nrealms,
int sep)
{
krb5_error_code retval;
struct hstate c, s;
krb5_data *ctweens = NULL, *stweens = NULL, *twp, *r, *rp;
size_t nctween, nstween;
*realms = NULL;
*nrealms = 0;
r = rp = NULL;
c.str = client->data;
c.len = client->length;
c.dot = c.tail = NULL;
s.str = server->data;
s.len = server->length;
s.dot = s.tail = NULL;
comtail(&c, &s, sep);
adjtail(&c, &s, sep);
retval = rtree_hier_tweens(context, &c, &ctweens, &nctween, 1, sep);
if (retval) goto error;
retval = rtree_hier_tweens(context, &s, &stweens, &nstween, 0, sep);
if (retval) goto error;
rp = r = calloc(nctween + nstween, sizeof(krb5_data));
if (r == NULL) {
retval = ENOMEM;
goto error;
}
/* Copy client realm "tweens" forward. */
for (twp = ctweens; twp < &ctweens[nctween]; twp++) {
retval = krb5int_copy_data_contents(context, twp, rp);
if (retval) goto error;
rp++;
}
/* Copy server realm "tweens" backward. */
for (twp = &stweens[nstween]; twp-- > stweens;) {
retval = krb5int_copy_data_contents(context, twp, rp);
if (retval) goto error;
rp++;
}
error:
free(ctweens);
free(stweens);
if (retval) {
free_realmlist(context, r, rp - r);
return retval;
}
*realms = r;
*nrealms = rp - r;
return 0;
}
static void
free_realmlist(krb5_context context,
krb5_data *realms,
size_t nrealms)
{
size_t i;
for (i = 0; i < nrealms; i++)
krb5_free_data_contents(context, &realms[i]);
free(realms);
}
/*
* Build a list of realms between a given realm and the common
* suffix. The original realm is included, but the "tail" is only
* included if DOTAIL is true.
*
* Warning: This function intentionally aliases memory. Caller must
* make copies as needed and not call krb5_free_data_contents, etc.
*/
static krb5_error_code
rtree_hier_tweens(krb5_context context,
struct hstate *realm,
krb5_data **tweens,
size_t *ntweens,
int dotail,
int sep)
{
char *p, *r, *rtail, *lp;
size_t rlen, n;
krb5_data *tws, *ntws;
r = realm->str;
rlen = realm->len;
rtail = realm->tail;
*tweens = ntws = tws = NULL;
*ntweens = n = 0;
for (lp = p = r; p < &r[rlen]; p++) {
if (*p != sep && &p[1] != &r[rlen])
continue;
if (lp == rtail && !dotail)
break;
ntws = realloc(tws, (n + 1) * sizeof(krb5_data));
if (ntws == NULL) {
free(tws);
return ENOMEM;
}
tws = ntws;
tws[n].data = lp;
tws[n].length = &r[rlen] - lp;
n++;
if (lp == rtail)
break;
lp = &p[1];
}
*tweens = tws;
*ntweens = n;
return 0;
}
/*
* Adjust suffixes that each starts at the beginning of a component,
* to avoid the problem where "BC.EXAMPLE.COM" is erroneously reported
* as a parent of "ABC.EXAMPLE.COM".
*/
static void
adjtail(struct hstate *c, struct hstate *s, int sep)
{
int cfull, sfull;
char *cp, *sp;
cp = c->tail;
sp = s->tail;
if (cp == NULL || sp == NULL)
return;
/*
* Is it a full component? Yes, if it's the beginning of the
* string or there's a separator to the left.
*
* The index of -1 is valid because it only gets evaluated if the
* pointer is not at the beginning of the string.
*/
cfull = (cp == c->str || cp[-1] == sep);
sfull = (sp == s->str || sp[-1] == sep);
/*
* If they're both full components, we're done.
*/
if (cfull && sfull) {
return;
} else if (c->dot != NULL && s->dot != NULL) {
cp = c->dot + 1;
sp = s->dot + 1;
/*
* Out of bounds? Can only happen if there are trailing dots.
*/
if (cp >= &c->str[c->len] || sp >= &s->str[s->len]) {
cp = sp = NULL;
}
} else {
cp = sp = NULL;
}
c->tail = cp;
s->tail = sp;
}
/*
* Find common suffix of C and S.
*
* C->TAIL and S->TAIL will point to the respective suffixes. C->DOT
* and S->DOT will point to the nearest instances of SEP to the right
* of the start of each suffix. Caller must initialize TAIL and DOT
* pointers to null.
*/
static void
comtail(struct hstate *c, struct hstate *s, int sep)
{
char *cp, *sp, *cdot, *sdot;
if (c->len == 0 || s->len == 0)
return;
cdot = sdot = NULL;
/*
* ANSI/ISO C allows a pointer one past the end but not one
* before the beginning of an array.
*/
cp = &c->str[c->len];
sp = &s->str[s->len];
/*
* Set CP and SP to point to the common suffix of each string.
* When we run into separators (dots, unless someone has a X.500
* style realm), keep pointers to the latest pair.
*/
while (cp > c->str && sp > s->str) {
if (*--cp != *--sp) {
/*
* Didn't match, so most recent match is one byte to the
* right (or not at all).
*/
cp++;
sp++;
break;
}
/*
* Keep track of matching dots.
*/
if (*cp == sep) {
cdot = cp;
sdot = sp;
}
}
/* No match found at all. */
if (cp == &c->str[c->len])
return;
c->tail = cp;
s->tail = sp;
c->dot = cdot;
s->dot = sdot;
}
void
krb5_free_realm_tree(krb5_context context, krb5_principal *realms)
{
register krb5_principal *nrealms = realms;
if (realms == NULL)
return;
while (*nrealms) {
krb5_free_principal(context, *nrealms);
nrealms++;
}
free(realms);
}