contrib/bind9/lib/dns/rpz.c

   1 /*
   2  * Copyright (C) 2011  Internet Systems Consortium, Inc. ("ISC")
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
   9  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  10  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  11  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  12  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  13  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  14  * PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 /* $Id: rpz.c,v 1.7 2011-01-17 04:27:23 marka Exp $ */
  18
  19 /*! \file */
  20
  21 #include <config.h>
  22
  23 #include <isc/buffer.h>
  24 #include <isc/mem.h>
  25 #include <isc/net.h>
  26 #include <isc/netaddr.h>
  27 #include <isc/print.h>
  28 #include <isc/stdlib.h>
  29 #include <isc/string.h>
  30 #include <isc/util.h>
  31
  32 #include <dns/db.h>
  33 #include <dns/fixedname.h>
  34 #include <dns/log.h>
  35 #include <dns/rdata.h>
  36 #include <dns/rdataset.h>
  37 #include <dns/rdatastruct.h>
  38 #include <dns/result.h>
  39 #include <dns/rpz.h>
  40 #include <dns/view.h>
  41
  42
  43 /*
  44  * Parallel radix trees for databases of response policy IP addresses
  45  *
  46  * The radix or Patricia trees are somewhat specialized to handle response
  47  * policy addresses by representing the two test of IP IP addresses and name
  48  * server IP addresses in a single tree.
  49  *
  50  * Each leaf indicates that an IP address is listed in the IP address or the
  51  * name server IP address policy sub-zone (or both) of the corresponding
  52  * response response zone.  The policy data such as a CNAME or an A record
  53  * is kept in the policy zone.  After an IP address has been found in a radix
  54  * tree, the node in the policy zone's database is found by converting
  55  * the IP address to a domain name in a canonical form.
  56  *
  57  * The response policy zone canonical form of IPv6 addresses is one of:
  58  *      prefix.W.W.W.W.W.W.W.W
  59  *      prefix.WORDS.zz
  60  *      prefix.WORDS.zz.WORDS
  61  *      prefix.zz.WORDS
  62  *  where
  63  *      prefix  is the prefix length of the IPv6 address between 1 and 128
  64  *      W       is a number between 0 and 65535
  65  *      WORDS   is one or more numbers W separated with "."
  66  *      zz      corresponds to :: in the standard IPv6 text representation
  67  *
  68  * The canonical form of IPv4 addresses is:
  69  *      prefix.B.B.B.B
  70  *  where
  71  *      prefix  is the prefix length of the address between 1 and 32
  72  *      B       is a number between 0 and 255
  73  *
  74  * IPv4 addresses are distinguished from IPv6 addresses by having
  75  * 5 labels all of which are numbers, and a prefix between 1 and 32.
  76  */
  77
  78
  79 /*
  80  * Use a private definition of IPv6 addresses because s6_addr32 is not
  81  * always defined and our IPv6 addresses are in non-standard byte order
  82  */
  83 typedef isc_uint32_t            dns_rpz_cidr_word_t;
  84 #define DNS_RPZ_CIDR_WORD_BITS  ((int)sizeof(dns_rpz_cidr_word_t)*8)
  85 #define DNS_RPZ_CIDR_KEY_BITS   ((int)sizeof(dns_rpz_cidr_key_t)*8)
  86 #define DNS_RPZ_CIDR_WORDS      (128/DNS_RPZ_CIDR_WORD_BITS)
  87 typedef struct {
  88         dns_rpz_cidr_word_t     w[DNS_RPZ_CIDR_WORDS];
  89 } dns_rpz_cidr_key_t;
  90
  91 #define ADDR_V4MAPPED           0xffff
  92
  93 #define DNS_RPZ_WORD_MASK(b)                            \
  94         ((b) == 0 ? (dns_rpz_cidr_word_t)(-1)           \
  95                   : ((dns_rpz_cidr_word_t)(-1)          \
  96                     << (DNS_RPZ_CIDR_WORD_BITS - (b))))
  97
  98 #define DNS_RPZ_IP_BIT(ip, bitno) \
  99         (1 & ((ip)->w[(bitno)/DNS_RPZ_CIDR_WORD_BITS] >> \
 100             (DNS_RPZ_CIDR_WORD_BITS - 1 - ((bitno) % DNS_RPZ_CIDR_WORD_BITS))))
 101
 102 typedef struct dns_rpz_cidr_node        dns_rpz_cidr_node_t;
 103 typedef isc_uint8_t                     dns_rpz_cidr_flags_t;
 104 struct dns_rpz_cidr_node {
 105         dns_rpz_cidr_node_t             *parent;
 106         dns_rpz_cidr_node_t             *child[2];
 107         dns_rpz_cidr_key_t              ip;
 108         dns_rpz_cidr_bits_t             bits;
 109         dns_rpz_cidr_flags_t            flags;
 110 #define DNS_RPZ_CIDR_FG_IP       0x01   /* has IP data or is parent of IP */
 111 #define DNS_RPZ_CIDR_FG_IP_DATA  0x02   /* has IP data */
 112 #define DNS_RPZ_CIDR_FG_NSIPv4   0x04   /* has or is parent of NSIPv4 data */
 113 #define DNS_RPZ_CIDR_FG_NSIPv6   0x08   /* has or is parent of NSIPv6 data */
 114 #define DNS_RPZ_CIDR_FG_NSIP_DATA 0x10  /* has NSIP data */
 115 };
 116
 117 struct dns_rpz_cidr {
 118         isc_mem_t               *mctx;
 119         isc_boolean_t           had_nsdname;
 120         dns_rpz_cidr_node_t     *root;
 121         dns_name_t              ip_name;        /* RPZ_IP_ZONE.LOCALHOST. */
 122         dns_name_t              nsip_name;      /* RPZ_NSIP_ZONE.LOCALHOST. */
 123         dns_name_t              nsdname_name;   /* RPZ_NSDNAME_ZONE.LOCALHOST */
 124 };
 125
 126
 127 static isc_boolean_t            have_rpz_zones = ISC_FALSE;
 128
 129
 130 const char *
 131 dns_rpz_type2str(dns_rpz_type_t type)
 132 {
 133         switch (type) {
 134         case DNS_RPZ_TYPE_QNAME:
 135                 return ("QNAME");
 136         case DNS_RPZ_TYPE_IP:
 137                 return ("IP");
 138         case DNS_RPZ_TYPE_NSIP:
 139                 return ("NSIP");
 140         case DNS_RPZ_TYPE_NSDNAME:
 141                 return ("NSDNAME");
 142         case DNS_RPZ_TYPE_BAD:
 143                 break;
 144         }
 145         FATAL_ERROR(__FILE__, __LINE__,
 146                     "impossible response policy zone type %d", type);
 147         return ("impossible");
 148 }
 149
 150
 151
 152 dns_rpz_policy_t
 153 dns_rpz_str2policy(const char *str)
 154 {
 155         if (str == NULL)
 156                 return (DNS_RPZ_POLICY_ERROR);
 157         if (!strcasecmp(str, "given"))
 158                 return (DNS_RPZ_POLICY_GIVEN);
 159         if (!strcasecmp(str, "no-op"))
 160                 return (DNS_RPZ_POLICY_NO_OP);
 161         if (!strcasecmp(str, "nxdomain"))
 162                 return (DNS_RPZ_POLICY_NXDOMAIN);
 163         if (!strcasecmp(str, "nodata"))
 164                 return (DNS_RPZ_POLICY_NODATA);
 165         if (!strcasecmp(str, "cname"))
 166                 return (DNS_RPZ_POLICY_CNAME);
 167         return (DNS_RPZ_POLICY_ERROR);
 168 }
 169
 170
 171
 172 /*
 173  * Free the radix tree of a response policy database.
 174  */
 175 void
 176 dns_rpz_cidr_free(dns_rpz_cidr_t **cidrp) {
 177         dns_rpz_cidr_node_t *cur, *child, *parent;
 178         dns_rpz_cidr_t *cidr;
 179
 180         REQUIRE(cidrp != NULL);
 181
 182         cidr = *cidrp;
 183         if (cidr == NULL)
 184                 return;
 185
 186         cur = cidr->root;
 187         while (cur != NULL) {
 188                 /* Depth first. */
 189                 child = cur->child[0];
 190                 if (child != NULL) {
 191                         cur = child;
 192                         continue;
 193                 }
 194                 child = cur->child[1];
 195                 if (child != NULL) {
 196                         cur = child;
 197                         continue;
 198                 }
 199
 200                 /* Delete this leaf and go up. */
 201                 parent = cur->parent;
 202                 if (parent == NULL)
 203                         cidr->root = NULL;
 204                 else
 205                         parent->child[parent->child[1] == cur] = NULL;
 206                 isc_mem_put(cidr->mctx, cur, sizeof(*cur));
 207                 cur = parent;
 208         }
 209
 210         dns_name_free(&cidr->ip_name, cidr->mctx);
 211         dns_name_free(&cidr->nsip_name, cidr->mctx);
 212         dns_name_free(&cidr->nsdname_name, cidr->mctx);
 213         isc_mem_put(cidr->mctx, cidr, sizeof(*cidr));
 214         *cidrp = NULL;
 215 }
 216
 217
 218
 219 /*
 220  * Forget a view's list of policy zones.
 221  */
 222 void
 223 dns_rpz_view_destroy(dns_view_t *view) {
 224         dns_rpz_zone_t *zone;
 225
 226         REQUIRE(view != NULL);
 227
 228         while (!ISC_LIST_EMPTY(view->rpz_zones)) {
 229                 zone = ISC_LIST_HEAD(view->rpz_zones);
 230                 ISC_LIST_UNLINK(view->rpz_zones, zone, link);
 231                 if (dns_name_dynamic(&zone->origin))
 232                         dns_name_free(&zone->origin, view->mctx);
 233                 if (dns_name_dynamic(&zone->nsdname))
 234                         dns_name_free(&zone->nsdname, view->mctx);
 235                 if (dns_name_dynamic(&zone->cname))
 236                         dns_name_free(&zone->cname, view->mctx);
 237                 isc_mem_put(view->mctx, zone, sizeof(*zone));
 238         }
 239 }
 240
 241 /*
 242  * Note that we have at least one response policy zone.
 243  * It would be better for something to tell the rbtdb code that the
 244  * zone is in at least one view's list of policy zones.
 245  */
 246 void
 247 dns_rpz_set_need(isc_boolean_t need)
 248 {
 249         have_rpz_zones = need;
 250 }
 251
 252
 253 isc_boolean_t
 254 dns_rpz_needed(void)
 255 {
 256         return (have_rpz_zones);
 257 }
 258
 259
 260
 261 /*
 262  * Start a new radix tree for a response policy zone.
 263  */
 264 isc_result_t
 265 dns_rpz_new_cidr(isc_mem_t *mctx, dns_name_t *origin,
 266                  dns_rpz_cidr_t **rbtdb_cidr)
 267 {
 268         isc_result_t result;
 269         dns_rpz_cidr_t *cidr;
 270
 271         REQUIRE(rbtdb_cidr != NULL && *rbtdb_cidr == NULL);
 272
 273         /*
 274          * Only if there is at least one response policy zone.
 275          */
 276         if (!have_rpz_zones)
 277                 return (ISC_R_SUCCESS);
 278
 279         cidr = isc_mem_get(mctx, sizeof(*cidr));
 280         if (cidr == NULL)
 281                 return (ISC_R_NOMEMORY);
 282         memset(cidr, 0, sizeof(*cidr));
 283         cidr->mctx = mctx;
 284
 285         dns_name_init(&cidr->ip_name, NULL);
 286         result = dns_name_fromstring2(&cidr->ip_name, DNS_RPZ_IP_ZONE, origin,
 287                                       DNS_NAME_DOWNCASE, mctx);
 288         if (result != ISC_R_SUCCESS) {
 289                 isc_mem_put(mctx, cidr, sizeof(*cidr));
 290                 return (result);
 291         }
 292
 293         dns_name_init(&cidr->nsip_name, NULL);
 294         result = dns_name_fromstring2(&cidr->nsip_name, DNS_RPZ_NSIP_ZONE,
 295                                       origin, DNS_NAME_DOWNCASE, mctx);
 296         if (result != ISC_R_SUCCESS) {
 297                 dns_name_free(&cidr->ip_name, mctx);
 298                 isc_mem_put(mctx, cidr, sizeof(*cidr));
 299                 return (result);
 300         }
 301
 302         dns_name_init(&cidr->nsdname_name, NULL);
 303         result = dns_name_fromstring2(&cidr->nsdname_name, DNS_RPZ_NSDNAME_ZONE,
 304                                       origin, DNS_NAME_DOWNCASE, mctx);
 305         if (result != ISC_R_SUCCESS) {
 306                 dns_name_free(&cidr->nsip_name, mctx);
 307                 dns_name_free(&cidr->ip_name, mctx);
 308                 isc_mem_put(mctx, cidr, sizeof(*cidr));
 309                 return (result);
 310         }
 311
 312         *rbtdb_cidr = cidr;
 313         return (ISC_R_SUCCESS);
 314 }
 315
 316
 317 /*
 318  * See if a policy zone has IP, NSIP, or NSDNAME rules or records.
 319  */
 320 void
 321 dns_rpz_enabled(dns_rpz_cidr_t *cidr, dns_rpz_st_t *st) {
 322         if (cidr->root != NULL &&
 323             (cidr->root->flags & DNS_RPZ_CIDR_FG_IP) != 0)
 324                 st->state |= DNS_RPZ_HAVE_IP;
 325         if (cidr->root != NULL &&
 326             (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv4) != 0)
 327                 st->state |= DNS_RPZ_HAVE_NSIPv4;
 328         if (cidr->root != NULL &&
 329             (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv6) != 0)
 330                 st->state |= DNS_RPZ_HAVE_NSIPv6;
 331         if (cidr->had_nsdname)
 332                 st->state |= DNS_RPZ_HAD_NSDNAME;
 333 }
 334
 335 static inline dns_rpz_cidr_flags_t
 336 get_flags(const dns_rpz_cidr_key_t *ip, dns_rpz_cidr_bits_t prefix,
 337         dns_rpz_type_t rpz_type)
 338 {
 339         if (rpz_type == DNS_RPZ_TYPE_NSIP) {
 340                 if (prefix >= 96 &&
 341                     ip->w[0] == 0 && ip->w[1] == 0 &&
 342                     ip->w[2] == ADDR_V4MAPPED)
 343                         return (DNS_RPZ_CIDR_FG_NSIP_DATA |
 344                                 DNS_RPZ_CIDR_FG_NSIPv4);
 345                 else
 346                         return (DNS_RPZ_CIDR_FG_NSIP_DATA |
 347                                 DNS_RPZ_CIDR_FG_NSIPv6);
 348         } else {
 349                 return (DNS_RPZ_CIDR_FG_IP | DNS_RPZ_CIDR_FG_IP_DATA);
 350         }
 351 }
 352
 353
 354
 355 /*
 356  * Mark a node as having IP or NSIP data and all of its parents
 357  * as members of the IP or NSIP tree.
 358  */
 359 static void
 360 set_node_flags(dns_rpz_cidr_node_t *node, dns_rpz_type_t rpz_type) {
 361         dns_rpz_cidr_flags_t flags;
 362
 363         flags = get_flags(&node->ip, node->bits, rpz_type);
 364         node->flags |= flags;
 365         flags &= ~(DNS_RPZ_CIDR_FG_NSIP_DATA | DNS_RPZ_CIDR_FG_IP_DATA);
 366         for (;;) {
 367                 node = node->parent;
 368                 if (node == NULL)
 369                         return;
 370                 node->flags |= flags;
 371         }
 372 }
 373
 374
 375
 376 /*
 377  * Make a radix tree node.
 378  */
 379 static dns_rpz_cidr_node_t *
 380 new_node(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *ip,
 381          dns_rpz_cidr_bits_t bits, dns_rpz_cidr_flags_t flags)
 382 {
 383         dns_rpz_cidr_node_t *node;
 384         int i, words, wlen;
 385
 386         node = isc_mem_get(cidr->mctx, sizeof(*node));
 387         if (node == NULL)
 388                 return (NULL);
 389         memset(node, 0, sizeof(*node));
 390
 391         node->flags = flags & ~(DNS_RPZ_CIDR_FG_IP_DATA |
 392                                 DNS_RPZ_CIDR_FG_NSIP_DATA);
 393
 394         node->bits = bits;
 395         words = bits / DNS_RPZ_CIDR_WORD_BITS;
 396         wlen = bits % DNS_RPZ_CIDR_WORD_BITS;
 397         i = 0;
 398         while (i < words) {
 399                 node->ip.w[i] = ip->w[i];
 400                 ++i;
 401         }
 402         if (wlen != 0) {
 403                 node->ip.w[i] = ip->w[i] & DNS_RPZ_WORD_MASK(wlen);
 404                 ++i;
 405         }
 406         while (i < DNS_RPZ_CIDR_WORDS)
 407                 node->ip.w[i++] = 0;
 408
 409         return (node);
 410 }
 411
 412
 413
 414 static void
 415 badname(int level, dns_name_t *name, const char *comment)
 416 {
 417         char printname[DNS_NAME_FORMATSIZE];
 418
 419         if (isc_log_wouldlog(dns_lctx, level)) {
 420                 dns_name_format(name, printname, sizeof(printname));
 421                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 422                               DNS_LOGMODULE_RBTDB, level,
 423                               "invalid response policy name \"%s\"%s",
 424                               printname, comment);
 425         }
 426 }
 427
 428
 429
 430 /*
 431  * Convert an IP address from radix tree binary (host byte order) to
 432  * to its canonical response policy domain name and its name in the
 433  * policy zone.
 434  */
 435 static isc_result_t
 436 ip2name(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip,
 437         dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type,
 438         dns_name_t *canon_name, dns_name_t *search_name)
 439 {
 440 #ifndef INET6_ADDRSTRLEN
 441 #define INET6_ADDRSTRLEN 46
 442 #endif
 443         int w[DNS_RPZ_CIDR_WORDS*2];
 444         char str[1+8+1+INET6_ADDRSTRLEN+1];
 445         isc_buffer_t buffer;
 446         dns_name_t *name;
 447         isc_result_t result;
 448         isc_boolean_t zeros;
 449         int i, n, len;
 450
 451         if (tgt_prefix > 96 &&
 452             tgt_ip->w[0] == 0 &&
 453             tgt_ip->w[1] == 0 &&
 454             tgt_ip->w[2] == ADDR_V4MAPPED) {
 455                 len = snprintf(str, sizeof(str), "%d.%d.%d.%d.%d",
 456                                tgt_prefix - 96,
 457                                tgt_ip->w[3] & 0xff,
 458                                (tgt_ip->w[3]>>8) & 0xff,
 459                                (tgt_ip->w[3]>>16) & 0xff,
 460                                (tgt_ip->w[3]>>24) & 0xff);
 461                 if (len == -1 || len > (int)sizeof(str))
 462                         return (ISC_R_FAILURE);
 463         } else {
 464                 for (i = 0; i < DNS_RPZ_CIDR_WORDS; i++) {
 465                         w[i*2+1] = ((tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] >> 16)
 466                                     & 0xffff);
 467                         w[i*2] = tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] & 0xffff;
 468                 }
 469                 zeros = ISC_FALSE;
 470                 len = snprintf(str, sizeof(str), "%d", tgt_prefix);
 471                 if (len == -1)
 472                         return (ISC_R_FAILURE);
 473                 i = 0;
 474                 while (i < DNS_RPZ_CIDR_WORDS * 2) {
 475                         if (w[i] != 0 || zeros
 476                             || i >= DNS_RPZ_CIDR_WORDS * 2 - 1
 477                             || w[i+1] != 0) {
 478                                 INSIST((size_t)len <= sizeof(str));
 479                                 n = snprintf(&str[len], sizeof(str) - len,
 480                                              ".%x", w[i++]);
 481                                 if (n < 0)
 482                                         return (ISC_R_FAILURE);
 483                                 len += n;
 484                         } else {
 485                                 zeros = ISC_TRUE;
 486                                 INSIST((size_t)len <= sizeof(str));
 487                                 n = snprintf(&str[len], sizeof(str) - len,
 488                                              ".zz");
 489                                 if (n < 0)
 490                                         return (ISC_R_FAILURE);
 491                                 len += n;
 492                                 i += 2;
 493                                 while (i < DNS_RPZ_CIDR_WORDS * 2 && w[i] == 0)
 494                                         ++i;
 495                         }
 496                         if (len > (int)sizeof(str))
 497                                 return (ISC_R_FAILURE);
 498                 }
 499         }
 500
 501         if (canon_name != NULL) {
 502                 isc__buffer_init(&buffer, str, sizeof(str));
 503                 isc__buffer_add(&buffer, len);
 504                 result = dns_name_fromtext(canon_name, &buffer,
 505                                            dns_rootname, 0, NULL);
 506                 if (result != ISC_R_SUCCESS)
 507                         return (result);
 508         }
 509         if (search_name != NULL) {
 510                 isc__buffer_init(&buffer, str, sizeof(str));
 511                 isc__buffer_add(&buffer, len);
 512                 if (type == DNS_RPZ_TYPE_NSIP)
 513                         name = &cidr->nsip_name;
 514                 else
 515                         name = &cidr->ip_name;
 516                 result = dns_name_fromtext(search_name, &buffer, name, 0, NULL);
 517                 if (result != ISC_R_SUCCESS)
 518                         return (result);
 519         }
 520         return (ISC_R_SUCCESS);
 521 }
 522
 523
 524
 525 /*
 526  * Decide which kind of IP address response policy zone a name is in.
 527  */
 528 static dns_rpz_type_t
 529 set_type(dns_rpz_cidr_t *cidr, dns_name_t *name) {
 530
 531         if (dns_name_issubdomain(name, &cidr->ip_name))
 532                 return (DNS_RPZ_TYPE_IP);
 533
 534         /*
 535          * Require `./configure --enable-rpz-nsip` and nsdname
 536          * until consistency problems are resolved.
 537          */
 538 #ifdef ENABLE_RPZ_NSIP
 539         if (dns_name_issubdomain(name, &cidr->nsip_name))
 540                 return (DNS_RPZ_TYPE_NSIP);
 541 #endif
 542
 543 #ifdef ENABLE_RPZ_NSDNAME
 544         if (dns_name_issubdomain(name, &cidr->nsdname_name))
 545                 return (DNS_RPZ_TYPE_NSDNAME);
 546 #endif
 547
 548         return (DNS_RPZ_TYPE_QNAME);
 549 }
 550
 551
 552
 553 /*
 554  * Convert an IP address from canonical response policy domain name form
 555  * to radix tree binary (host byte order).
 556  */
 557 static isc_result_t
 558 name2ipkey(dns_rpz_cidr_t *cidr, int level, dns_name_t *src_name,
 559            dns_rpz_type_t type, dns_rpz_cidr_key_t *tgt_ip,
 560            dns_rpz_cidr_bits_t *tgt_prefix)
 561 {
 562         isc_buffer_t buffer;
 563         unsigned char data[DNS_NAME_MAXWIRE+1];
 564         dns_fixedname_t fname;
 565         dns_name_t *name;
 566         const char *cp, *end;
 567         char *cp2;
 568         int ip_labels;
 569         dns_rpz_cidr_bits_t bits;
 570         unsigned long prefix, l;
 571         int i;
 572
 573         /*
 574          * Need at least enough labels for the shortest name,
 575          * :: or 128.*.RPZ_x_ZONE.rpz.LOCALHOST.
 576          */
 577         ip_labels = dns_name_countlabels(src_name);
 578         ip_labels -= dns_name_countlabels(&cidr->ip_name);
 579         ip_labels--;
 580         if (ip_labels < 1) {
 581                 badname(level, src_name, ", too short");
 582                 return (ISC_R_FAILURE);
 583         }
 584
 585         /*
 586          * Get text for the IP address without RPZ_x_ZONE.rpz.LOCALHOST.
 587          */
 588         dns_fixedname_init(&fname);
 589         name = dns_fixedname_name(&fname);
 590         dns_name_split(src_name, dns_name_countlabels(&cidr->ip_name),
 591                        name, NULL);
 592         isc_buffer_init(&buffer, data, sizeof(data));
 593         dns_name_totext(name, ISC_TRUE, &buffer);
 594         isc_buffer_putuint8(&buffer, '\0');
 595         cp = isc_buffer_base(&buffer);
 596
 597         prefix = strtoul(cp, &cp2, 10);
 598         if (prefix < 1U || prefix > 128U || *cp2 != '.') {
 599                 badname(level, src_name, ", bad prefix length");
 600                 return (ISC_R_FAILURE);
 601         }
 602         cp = cp2+1;
 603
 604         end = isc_buffer_used(&buffer);
 605         if (ip_labels == 4 && !strchr(cp, 'z')) {
 606                 /*
 607                  * Convert an IPv4 address
 608                  * from the form "prefix.w.z.y.x"
 609                  */
 610                 if (prefix > 32U) {
 611                         badname(level, src_name, "; bad IPv4 prefix length");
 612                         return (ISC_R_FAILURE);
 613                 }
 614                 prefix += 96;
 615                 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix;
 616                 tgt_ip->w[0] = 0;
 617                 tgt_ip->w[1] = 0;
 618                 tgt_ip->w[2] = ADDR_V4MAPPED;
 619                 tgt_ip->w[3] = 0;
 620                 for (i = 0; i < 32; i += 8) {
 621                         l = strtoul(cp, &cp2, 10);
 622                         if (l > 255U || (*cp2 != '.' && *cp2 != '\0')) {
 623                                 badname(level, src_name, "; bad IPv4 address");
 624                                 return (ISC_R_FAILURE);
 625                         }
 626                         tgt_ip->w[3] |= l << i;
 627                         cp = cp2 + 1;
 628                 }
 629         } else {
 630                 /*
 631                  * Convert a text IPv6 address.
 632                  */
 633                 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix;
 634                 for (i = 0;
 635                      ip_labels > 0 && i < DNS_RPZ_CIDR_WORDS * 2;
 636                      ip_labels--) {
 637                         if (cp[0] == 'z' && cp[1] == 'z' &&
 638                             (cp[2] == '.' || cp[2] == '\0') &&
 639                             i <= 6) {
 640                                 do {
 641                                         if ((i & 1) == 0)
 642                                             tgt_ip->w[3-i/2] = 0;
 643                                         ++i;
 644                                 } while (ip_labels + i <= 8);
 645                                 cp += 3;
 646                         } else {
 647                                 l = strtoul(cp, &cp2, 16);
 648                                 if (l > 0xffffu ||
 649                                     (*cp2 != '.' && *cp2 != '\0')) {
 650                                         badname(level, src_name, "");
 651                                         return (ISC_R_FAILURE);
 652                                 }
 653                                 if ((i & 1) == 0)
 654                                         tgt_ip->w[3-i/2] = l;
 655                                 else
 656                                         tgt_ip->w[3-i/2] |= l << 16;
 657                                 i++;
 658                                 cp = cp2 + 1;
 659                         }
 660                 }
 661         }
 662         if (cp != end) {
 663                 badname(level, src_name, "");
 664                 return (ISC_R_FAILURE);
 665         }
 666
 667         /*
 668          * Check for 1s after the prefix length.
 669          */
 670         bits = (dns_rpz_cidr_bits_t)prefix;
 671         while (bits < DNS_RPZ_CIDR_KEY_BITS) {
 672                 dns_rpz_cidr_word_t aword;
 673
 674                 i = bits % DNS_RPZ_CIDR_WORD_BITS;
 675                 aword = tgt_ip->w[bits / DNS_RPZ_CIDR_WORD_BITS];
 676                 if ((aword & ~DNS_RPZ_WORD_MASK(i)) != 0) {
 677                         badname(level, src_name, "; wrong prefix length");
 678                         return (ISC_R_FAILURE);
 679                 }
 680                 bits -= i;
 681                 bits += DNS_RPZ_CIDR_WORD_BITS;
 682         }
 683
 684         /*
 685          * Convert the IPv6 address back to a canonical policy domain name
 686          * to ensure that it is in canonical form.
 687          */
 688         if (ISC_R_SUCCESS != ip2name(cidr, tgt_ip, (dns_rpz_cidr_bits_t)prefix,
 689                                      type, NULL, name) ||
 690             !dns_name_equal(src_name, name)) {
 691                 badname(level, src_name, "; not canonical");
 692                 return (ISC_R_FAILURE);
 693         }
 694
 695         return (ISC_R_SUCCESS);
 696 }
 697
 698
 699
 700 /*
 701  * find first differing bit
 702  */
 703 static int
 704 ffbit(dns_rpz_cidr_word_t w) {
 705         int bit;
 706
 707         if (w == 0)
 708                 return (DNS_RPZ_CIDR_WORD_BITS);
 709         for (bit = 0; (w & (1U << (DNS_RPZ_CIDR_WORD_BITS-1))) == 0; bit++)
 710                 w <<= 1;
 711         return (bit);
 712 }
 713
 714
 715
 716 /*
 717  * find the first differing bit in two keys
 718  */
 719 static int
 720 diff_keys(const dns_rpz_cidr_key_t *key1, dns_rpz_cidr_bits_t bits1,
 721           const dns_rpz_cidr_key_t *key2, dns_rpz_cidr_bits_t bits2)
 722 {
 723         dns_rpz_cidr_word_t delta;
 724         dns_rpz_cidr_bits_t maxbit, bit;
 725         int i;
 726
 727         maxbit = ISC_MIN(bits1, bits2);
 728
 729         /*
 730          * find the first differing words
 731          */
 732         for (i = 0, bit = 0;
 733              bit <= maxbit;
 734              i++, bit += DNS_RPZ_CIDR_WORD_BITS) {
 735                 delta = key1->w[i] ^ key2->w[i];
 736                 if (delta != 0) {
 737                         bit += ffbit(delta);
 738                         break;
 739                 }
 740         }
 741         return (ISC_MIN(bit, maxbit));
 742 }
 743
 744
 745
 746 /*
 747  * Search a radix tree for an IP address for ordinary lookup
 748  *      or for a CIDR block adding or deleting an entry
 749  * The tree read (for simple search) or write lock must be held by the caller.
 750  *
 751  * return ISC_R_SUCCESS, ISC_R_NOTFOUND, DNS_R_PARTIALMATCH, ISC_R_EXISTS,
 752  *      ISC_R_NOMEMORY
 753  */
 754 static isc_result_t
 755 search(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip,
 756        dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type,
 757        isc_boolean_t create,
 758        dns_rpz_cidr_node_t **found)             /* NULL or longest match node */
 759 {
 760         dns_rpz_cidr_node_t *cur, *parent, *child, *new_parent, *sibling;
 761         int cur_num, child_num;
 762         dns_rpz_cidr_bits_t dbit;
 763         dns_rpz_cidr_flags_t flags, data_flag;
 764         isc_result_t find_result;
 765
 766         flags = get_flags(tgt_ip, tgt_prefix, type);
 767         data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA |
 768                              DNS_RPZ_CIDR_FG_NSIP_DATA);
 769
 770         find_result = ISC_R_NOTFOUND;
 771         if (found != NULL)
 772                 *found = NULL;
 773         cur = cidr->root;
 774         parent = NULL;
 775         cur_num = 0;
 776         for (;;) {
 777                 if (cur == NULL) {
 778                         /*
 779                          * No child so we cannot go down.  Fail or
 780                          * add the target as a child of the current parent.
 781                          */
 782                         if (!create)
 783                                 return (find_result);
 784                         child = new_node(cidr, tgt_ip, tgt_prefix, 0);
 785                         if (child == NULL)
 786                                 return (ISC_R_NOMEMORY);
 787                         if (parent == NULL)
 788                                 cidr->root = child;
 789                         else
 790                                 parent->child[cur_num] = child;
 791                         child->parent = parent;
 792                         set_node_flags(child, type);
 793                         if (found != NULL)
 794                                 *found = cur;
 795                         return (ISC_R_SUCCESS);
 796                 }
 797
 798                 /*
 799                  * Pretend a node not in the correct tree does not exist
 800                  * if we are not adding to the tree,
 801                  * If we are adding, then continue down to eventually
 802                  * add a node and mark/put this node in the correct tree.
 803                  */
 804                 if ((cur->flags & flags) == 0 && !create)
 805                         return (find_result);
 806
 807                 dbit = diff_keys(tgt_ip, tgt_prefix, &cur->ip, cur->bits);
 808                 /*
 809                  * dbit <= tgt_prefix and dbit <= cur->bits always.
 810                  * We are finished searching if we matched all of the target.
 811                  */
 812                 if (dbit == tgt_prefix) {
 813                         if (tgt_prefix == cur->bits) {
 814                                 /*
 815                                  * The current node matches the target exactly.
 816                                  * It is the answer if it has data.
 817                                  */
 818                                 if ((cur->flags & data_flag) != 0) {
 819                                         if (create)
 820                                                 return (ISC_R_EXISTS);
 821                                         if (found != NULL)
 822                                                 *found = cur;
 823                                         return (ISC_R_SUCCESS);
 824                                 } else if (create) {
 825                                         /*
 826                                          * The node had no data but does now.
 827                                          */
 828                                         set_node_flags(cur, type);
 829                                         if (found != NULL)
 830                                                 *found = cur;
 831                                         return (ISC_R_SUCCESS);
 832                                 }
 833                                 return (find_result);
 834                         }
 835
 836                         /*
 837                          * We know tgt_prefix < cur_bits which means that
 838                          * the target is shorter than the current node.
 839                          * Add the target as the current node's parent.
 840                          */
 841                         if (!create)
 842                                 return (find_result);
 843
 844                         new_parent = new_node(cidr, tgt_ip, tgt_prefix,
 845                                               cur->flags);
 846                         if (new_parent == NULL)
 847                                 return (ISC_R_NOMEMORY);
 848                         new_parent->parent = parent;
 849                         if (parent == NULL)
 850                                 cidr->root = new_parent;
 851                         else
 852                                 parent->child[cur_num] = new_parent;
 853                         child_num = DNS_RPZ_IP_BIT(&cur->ip, tgt_prefix+1);
 854                         new_parent->child[child_num] = cur;
 855                         cur->parent = new_parent;
 856                         set_node_flags(new_parent, type);
 857                         if (found != NULL)
 858                                 *found = new_parent;
 859                         return (ISC_R_SUCCESS);
 860                 }
 861
 862                 if (dbit == cur->bits) {
 863                         /*
 864                          * We have a partial match by matching of all of the
 865                          * current node but only part of the target.
 866                          * Try to go down.
 867                          */
 868                         if ((cur->flags & data_flag) != 0) {
 869                                 find_result = DNS_R_PARTIALMATCH;
 870                                 if (found != NULL)
 871                                         *found = cur;
 872                         }
 873
 874                         parent = cur;
 875                         cur_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
 876                         cur = cur->child[cur_num];
 877                         continue;
 878                 }
 879
 880
 881                 /*
 882                  * dbit < tgt_prefix and dbit < cur->bits,
 883                  * so we failed to match both the target and the current node.
 884                  * Insert a fork of a parent above the current node and
 885                  * add the target as a sibling of the current node
 886                  */
 887                 if (!create)
 888                         return (find_result);
 889
 890                 sibling = new_node(cidr, tgt_ip, tgt_prefix, 0);
 891                 if (sibling == NULL)
 892                         return (ISC_R_NOMEMORY);
 893                 new_parent = new_node(cidr, tgt_ip, dbit, cur->flags);
 894                 if (new_parent == NULL) {
 895                         isc_mem_put(cidr->mctx, sibling, sizeof(*sibling));
 896                         return (ISC_R_NOMEMORY);
 897                 }
 898                 new_parent->parent = parent;
 899                 if (parent == NULL)
 900                         cidr->root = new_parent;
 901                 else
 902                         parent->child[cur_num] = new_parent;
 903                 child_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
 904                 new_parent->child[child_num] = sibling;
 905                 new_parent->child[1-child_num] = cur;
 906                 cur->parent = new_parent;
 907                 sibling->parent = new_parent;
 908                 set_node_flags(sibling, type);
 909                 if (found != NULL)
 910                         *found = sibling;
 911                 return (ISC_R_SUCCESS);
 912         }
 913 }
 914
 915
 916
 917 /*
 918  * Add an IP address to the radix tree of a response policy database.
 919  *      The tree write lock must be held by the caller.
 920  */
 921 void
 922 dns_rpz_cidr_addip(dns_rpz_cidr_t *cidr, dns_name_t *name)
 923 {
 924         dns_rpz_cidr_key_t tgt_ip;
 925         dns_rpz_cidr_bits_t tgt_prefix;
 926         dns_rpz_type_t type;
 927
 928         if (cidr == NULL)
 929                 return;
 930
 931         /*
 932          * no worries if the new name is not an IP address
 933          */
 934         type = set_type(cidr, name);
 935         switch (type) {
 936         case DNS_RPZ_TYPE_IP:
 937         case DNS_RPZ_TYPE_NSIP:
 938                 break;
 939         case DNS_RPZ_TYPE_NSDNAME:
 940                 cidr->had_nsdname = ISC_TRUE;
 941                 return;
 942         case DNS_RPZ_TYPE_QNAME:
 943         case DNS_RPZ_TYPE_BAD:
 944                 return;
 945         }
 946         if (ISC_R_SUCCESS != name2ipkey(cidr, DNS_RPZ_ERROR_LEVEL, name,
 947                                         type, &tgt_ip, &tgt_prefix))
 948                 return;
 949
 950         if (ISC_R_EXISTS == search(cidr, &tgt_ip, tgt_prefix, type,
 951                                    ISC_TRUE, NULL) &&
 952             isc_log_wouldlog(dns_lctx, DNS_RPZ_ERROR_LEVEL)) {
 953                 char printname[DNS_NAME_FORMATSIZE];
 954
 955                 dns_name_format(name, printname, sizeof(printname));
 956                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 957                               DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
 958                               "duplicate response policy name \"%s\"",
 959                               printname);
 960         }
 961 }
 962
 963
 964
 965 /*
 966  * Delete an IP address from the radix tree of a response policy database.
 967  *      The tree write lock must be held by the caller.
 968  */
 969 void
 970 dns_rpz_cidr_deleteip(dns_rpz_cidr_t *cidr, dns_name_t *name) {
 971         dns_rpz_cidr_key_t tgt_ip;
 972         dns_rpz_cidr_bits_t tgt_prefix;
 973         dns_rpz_type_t type;
 974         dns_rpz_cidr_node_t *tgt = NULL, *parent, *child;
 975         dns_rpz_cidr_flags_t flags, data_flag;
 976
 977         if (cidr == NULL)
 978                 return;
 979
 980         /*
 981          * Decide which kind of policy zone IP address it is, if either
 982          * and then find its node.
 983          */
 984         type = set_type(cidr, name);
 985         switch (type) {
 986         case DNS_RPZ_TYPE_IP:
 987         case DNS_RPZ_TYPE_NSIP:
 988                 break;
 989         case DNS_RPZ_TYPE_NSDNAME:
 990                 /*
 991                  * We cannot easily count nsdnames because
 992                  * internal rbt nodes get deleted.
 993                  */
 994                 return;
 995         case DNS_RPZ_TYPE_QNAME:
 996         case DNS_RPZ_TYPE_BAD:
 997                 return;
 998         }
 999
1000         /*
1001          * Do not get excited about the deletion of interior rbt nodes.
1002          */
1003         if (ISC_R_SUCCESS != name2ipkey(cidr, DNS_RPZ_DEBUG_LEVEL2, name,
1004                                         type, &tgt_ip, &tgt_prefix))
1005                 return;
1006         if (ISC_R_SUCCESS != search(cidr, &tgt_ip, tgt_prefix, type,
1007                                     ISC_FALSE, &tgt)) {
1008                 if (isc_log_wouldlog(dns_lctx, DNS_RPZ_ERROR_LEVEL)) {
1009                         char printname[DNS_NAME_FORMATSIZE];
1010
1011                         dns_name_format(name, printname, sizeof(printname));
1012                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
1013                                       DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
1014                                       "missing response policy node \"%s\"",
1015                                       printname);
1016                 }
1017                 return;
1018         }
1019
1020         /*
1021          * Mark the node and its parents to reflect the deleted IP address.
1022          */
1023         flags = get_flags(&tgt_ip, tgt_prefix, type);
1024         data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA |
1025                               DNS_RPZ_CIDR_FG_NSIP_DATA);
1026         tgt->flags &= ~data_flag;
1027         for (parent = tgt; parent != NULL; parent = parent->parent) {
1028                 if ((parent->flags & data_flag) != 0 ||
1029                     (parent->child[0] != NULL &&
1030                      (parent->child[0]->flags & flags) != 0) ||
1031                     (parent->child[1] != NULL &&
1032                      (parent->child[1]->flags & flags) != 0))
1033                         break;
1034                 parent->flags &= ~flags;
1035         }
1036
1037         /*
1038          * We might need to delete 2 nodes.
1039          */
1040         do {
1041                 /*
1042                  * The node is now useless if it has no data of its own
1043                  * and 0 or 1 children.  We are finished if it is not useless.
1044                  */
1045                 if ((child = tgt->child[0]) != NULL) {
1046                         if (tgt->child[1] != NULL)
1047                                 return;
1048                 } else {
1049                         child = tgt->child[1];
1050                 }
1051                 if ((tgt->flags & (DNS_RPZ_CIDR_FG_IP_DATA |
1052                                  DNS_RPZ_CIDR_FG_NSIP_DATA)) != 0)
1053                         return;
1054
1055                 /*
1056                  * Replace the pointer to this node in the parent with
1057                  * the remaining child or NULL.
1058                  */
1059                 parent = tgt->parent;
1060                 if (parent == NULL) {
1061                         cidr->root = child;
1062                 } else {
1063                         parent->child[parent->child[1] == tgt] = child;
1064                 }
1065                 /*
1066                  * If the child exists fix up its parent pointer.
1067                  */
1068                 if (child != NULL)
1069                         child->parent = parent;
1070                 isc_mem_put(cidr->mctx, tgt, sizeof(*tgt));
1071
1072                 tgt = parent;
1073         } while (tgt != NULL);
1074 }
1075
1076
1077
1078 /*
1079  * Caller must hold tree lock.
1080  * Return  ISC_R_NOTFOUND
1081  *      or ISC_R_SUCCESS and the found entry's canonical and search names
1082  *          and its prefix length
1083  */
1084 isc_result_t
1085 dns_rpz_cidr_find(dns_rpz_cidr_t *cidr, const isc_netaddr_t *netaddr,
1086                   dns_rpz_type_t type, dns_name_t *canon_name,
1087                   dns_name_t *search_name, dns_rpz_cidr_bits_t *prefix)
1088 {
1089         dns_rpz_cidr_key_t tgt_ip;
1090         isc_result_t result;
1091         dns_rpz_cidr_node_t *found;
1092         int i;
1093
1094         /*
1095          * Convert IP address to CIDR tree key.
1096          */
1097         if (netaddr->family == AF_INET) {
1098                 tgt_ip.w[0] = 0;
1099                 tgt_ip.w[1] = 0;
1100                 tgt_ip.w[2] = ADDR_V4MAPPED;
1101                 tgt_ip.w[3] = ntohl(netaddr->type.in.s_addr);
1102         } else if (netaddr->family == AF_INET6) {
1103                 dns_rpz_cidr_key_t src_ip6;
1104
1105                 /*
1106                  * Given the int aligned struct in_addr member of netaddr->type
1107                  * one could cast netaddr->type.in6 to dns_rpz_cidr_key_t *,
1108                  * but there are objections.
1109                  */
1110                 memcpy(src_ip6.w, &netaddr->type.in6, sizeof(src_ip6.w));
1111                 for (i = 0; i < 4; i++) {
1112                         tgt_ip.w[i] = ntohl(src_ip6.w[i]);
1113                 }
1114         } else {
1115                 return (ISC_R_NOTFOUND);
1116         }
1117
1118         result = search(cidr, &tgt_ip, 128, type, ISC_FALSE, &found);
1119         if (result != ISC_R_SUCCESS && result != DNS_R_PARTIALMATCH)
1120                 return (result);
1121
1122         *prefix = found->bits;
1123         return (ip2name(cidr, &found->ip, found->bits, type,
1124                         canon_name, search_name));
1125 }
1126
1127
1128
1129 /*
1130  * Translate CNAME rdata to a QNAME response policy action.
1131  */
1132 dns_rpz_policy_t
1133 dns_rpz_decode_cname(dns_rdataset_t *rdataset, dns_name_t *selfname) {
1134         dns_rdata_t rdata = DNS_RDATA_INIT;
1135         dns_rdata_cname_t cname;
1136         isc_result_t result;
1137
1138         result = dns_rdataset_first(rdataset);
1139         RUNTIME_CHECK(result == ISC_R_SUCCESS);
1140         dns_rdataset_current(rdataset, &rdata);
1141         result = dns_rdata_tostruct(&rdata, &cname, NULL);
1142         RUNTIME_CHECK(result == ISC_R_SUCCESS);
1143         dns_rdata_reset(&rdata);
1144
1145         /*
1146          * CNAME . means NXDOMAIN
1147          */
1148         if (dns_name_equal(&cname.cname, dns_rootname))
1149                 return (DNS_RPZ_POLICY_NXDOMAIN);
1150
1151         /*
1152          * CNAME *. means NODATA
1153          */
1154         if (dns_name_countlabels(&cname.cname) == 2
1155             && dns_name_iswildcard(&cname.cname))
1156                 return (DNS_RPZ_POLICY_NODATA);
1157
1158         /*
1159          * 128.1.0.127.rpz-ip CNAME  128.1.0.0.127. means "do not rewrite"
1160          */
1161         if (selfname != NULL && dns_name_equal(&cname.cname, selfname))
1162                 return (DNS_RPZ_POLICY_NO_OP);
1163
1164         /*
1165          * evil.com CNAME garden.net rewrites www.evil.com to www.garden.net.
1166          */
1167         return (DNS_RPZ_POLICY_RECORD);
1168 }