contrib/bind9/lib/dns/nsec.c

   1 /*
   2  * Copyright (C) 2004, 2005, 2007-2009, 2011-2013  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2001, 2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and/or distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id$ */
  19
  20 /*! \file */
  21
  22 #include <config.h>
  23
  24 #include <isc/log.h>
  25 #include <isc/string.h>
  26 #include <isc/util.h>
  27
  28 #include <dns/db.h>
  29 #include <dns/nsec.h>
  30 #include <dns/rdata.h>
  31 #include <dns/rdatalist.h>
  32 #include <dns/rdataset.h>
  33 #include <dns/rdatasetiter.h>
  34 #include <dns/rdatastruct.h>
  35 #include <dns/result.h>
  36
  37 #include <dst/dst.h>
  38
  39 #define RETERR(x) do { \
  40         result = (x); \
  41         if (result != ISC_R_SUCCESS) \
  42                 goto failure; \
  43         } while (0)
  44
  45 static void
  46 set_bit(unsigned char *array, unsigned int index, unsigned int bit) {
  47         unsigned int shift, mask;
  48
  49         shift = 7 - (index % 8);
  50         mask = 1 << shift;
  51
  52         if (bit != 0)
  53                 array[index / 8] |= mask;
  54         else
  55                 array[index / 8] &= (~mask & 0xFF);
  56 }
  57
  58 static unsigned int
  59 bit_isset(unsigned char *array, unsigned int index) {
  60         unsigned int byte, shift, mask;
  61
  62         byte = array[index / 8];
  63         shift = 7 - (index % 8);
  64         mask = 1 << shift;
  65
  66         return ((byte & mask) != 0);
  67 }
  68
  69 isc_result_t
  70 dns_nsec_buildrdata(dns_db_t *db, dns_dbversion_t *version,
  71                     dns_dbnode_t *node, dns_name_t *target,
  72                     unsigned char *buffer, dns_rdata_t *rdata)
  73 {
  74         isc_result_t result;
  75         dns_rdataset_t rdataset;
  76         isc_region_t r;
  77         unsigned int i, window;
  78         int octet;
  79
  80         unsigned char *nsec_bits, *bm;
  81         unsigned int max_type;
  82         dns_rdatasetiter_t *rdsiter;
  83
  84         memset(buffer, 0, DNS_NSEC_BUFFERSIZE);
  85         dns_name_toregion(target, &r);
  86         memcpy(buffer, r.base, r.length);
  87         r.base = buffer;
  88         /*
  89          * Use the end of the space for a raw bitmap leaving enough
  90          * space for the window identifiers and length octets.
  91          */
  92         bm = r.base + r.length + 512;
  93         nsec_bits = r.base + r.length;
  94         set_bit(bm, dns_rdatatype_rrsig, 1);
  95         set_bit(bm, dns_rdatatype_nsec, 1);
  96         max_type = dns_rdatatype_nsec;
  97         dns_rdataset_init(&rdataset);
  98         rdsiter = NULL;
  99         result = dns_db_allrdatasets(db, node, version, 0, &rdsiter);
 100         if (result != ISC_R_SUCCESS)
 101                 return (result);
 102         for (result = dns_rdatasetiter_first(rdsiter);
 103              result == ISC_R_SUCCESS;
 104              result = dns_rdatasetiter_next(rdsiter))
 105         {
 106                 dns_rdatasetiter_current(rdsiter, &rdataset);
 107                 if (rdataset.type != dns_rdatatype_nsec &&
 108                     rdataset.type != dns_rdatatype_nsec3 &&
 109                     rdataset.type != dns_rdatatype_rrsig) {
 110                         if (rdataset.type > max_type)
 111                                 max_type = rdataset.type;
 112                         set_bit(bm, rdataset.type, 1);
 113                 }
 114                 dns_rdataset_disassociate(&rdataset);
 115         }
 116
 117         /*
 118          * At zone cuts, deny the existence of glue in the parent zone.
 119          */
 120         if (bit_isset(bm, dns_rdatatype_ns) &&
 121             ! bit_isset(bm, dns_rdatatype_soa)) {
 122                 for (i = 0; i <= max_type; i++) {
 123                         if (bit_isset(bm, i) &&
 124                             ! dns_rdatatype_iszonecutauth((dns_rdatatype_t)i))
 125                                 set_bit(bm, i, 0);
 126                 }
 127         }
 128
 129         dns_rdatasetiter_destroy(&rdsiter);
 130         if (result != ISC_R_NOMORE)
 131                 return (result);
 132
 133         for (window = 0; window < 256; window++) {
 134                 if (window * 256 > max_type)
 135                         break;
 136                 for (octet = 31; octet >= 0; octet--)
 137                         if (bm[window * 32 + octet] != 0)
 138                                 break;
 139                 if (octet < 0)
 140                         continue;
 141                 nsec_bits[0] = window;
 142                 nsec_bits[1] = octet + 1;
 143                 /*
 144                  * Note: potential overlapping move.
 145                  */
 146                 memmove(&nsec_bits[2], &bm[window * 32], octet + 1);
 147                 nsec_bits += 3 + octet;
 148         }
 149         r.length = nsec_bits - r.base;
 150         INSIST(r.length <= DNS_NSEC_BUFFERSIZE);
 151         dns_rdata_fromregion(rdata,
 152                              dns_db_class(db),
 153                              dns_rdatatype_nsec,
 154                              &r);
 155
 156         return (ISC_R_SUCCESS);
 157 }
 158
 159
 160 isc_result_t
 161 dns_nsec_build(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node,
 162                dns_name_t *target, dns_ttl_t ttl)
 163 {
 164         isc_result_t result;
 165         dns_rdata_t rdata = DNS_RDATA_INIT;
 166         unsigned char data[DNS_NSEC_BUFFERSIZE];
 167         dns_rdatalist_t rdatalist;
 168         dns_rdataset_t rdataset;
 169
 170         dns_rdataset_init(&rdataset);
 171         dns_rdata_init(&rdata);
 172
 173         RETERR(dns_nsec_buildrdata(db, version, node, target, data, &rdata));
 174
 175         rdatalist.rdclass = dns_db_class(db);
 176         rdatalist.type = dns_rdatatype_nsec;
 177         rdatalist.covers = 0;
 178         rdatalist.ttl = ttl;
 179         ISC_LIST_INIT(rdatalist.rdata);
 180         ISC_LIST_APPEND(rdatalist.rdata, &rdata, link);
 181         RETERR(dns_rdatalist_tordataset(&rdatalist, &rdataset));
 182         result = dns_db_addrdataset(db, node, version, 0, &rdataset,
 183                                     0, NULL);
 184         if (result == DNS_R_UNCHANGED)
 185                 result = ISC_R_SUCCESS;
 186
 187  failure:
 188         if (dns_rdataset_isassociated(&rdataset))
 189                 dns_rdataset_disassociate(&rdataset);
 190         return (result);
 191 }
 192
 193 isc_boolean_t
 194 dns_nsec_typepresent(dns_rdata_t *nsec, dns_rdatatype_t type) {
 195         dns_rdata_nsec_t nsecstruct;
 196         isc_result_t result;
 197         isc_boolean_t present;
 198         unsigned int i, len, window;
 199
 200         REQUIRE(nsec != NULL);
 201         REQUIRE(nsec->type == dns_rdatatype_nsec);
 202
 203         /* This should never fail */
 204         result = dns_rdata_tostruct(nsec, &nsecstruct, NULL);
 205         INSIST(result == ISC_R_SUCCESS);
 206
 207         present = ISC_FALSE;
 208         for (i = 0; i < nsecstruct.len; i += len) {
 209                 INSIST(i + 2 <= nsecstruct.len);
 210                 window = nsecstruct.typebits[i];
 211                 len = nsecstruct.typebits[i + 1];
 212                 INSIST(len > 0 && len <= 32);
 213                 i += 2;
 214                 INSIST(i + len <= nsecstruct.len);
 215                 if (window * 256 > type)
 216                         break;
 217                 if ((window + 1) * 256 <= type)
 218                         continue;
 219                 if (type < (window * 256) + len * 8)
 220                         present = ISC_TF(bit_isset(&nsecstruct.typebits[i],
 221                                                    type % 256));
 222                 break;
 223         }
 224         dns_rdata_freestruct(&nsecstruct);
 225         return (present);
 226 }
 227
 228 isc_result_t
 229 dns_nsec_nseconly(dns_db_t *db, dns_dbversion_t *version,
 230                   isc_boolean_t *answer)
 231 {
 232         dns_dbnode_t *node = NULL;
 233         dns_rdataset_t rdataset;
 234         dns_rdata_dnskey_t dnskey;
 235         isc_result_t result;
 236
 237         REQUIRE(answer != NULL);
 238
 239         dns_rdataset_init(&rdataset);
 240
 241         result = dns_db_getoriginnode(db, &node);
 242         if (result != ISC_R_SUCCESS)
 243                 return (result);
 244
 245         result = dns_db_findrdataset(db, node, version, dns_rdatatype_dnskey,
 246                                      0, 0, &rdataset, NULL);
 247         dns_db_detachnode(db, &node);
 248
 249         if (result == ISC_R_NOTFOUND) {
 250                 *answer = ISC_FALSE;
 251                 return (ISC_R_SUCCESS);
 252         }
 253         if (result != ISC_R_SUCCESS)
 254                 return (result);
 255         for (result = dns_rdataset_first(&rdataset);
 256              result == ISC_R_SUCCESS;
 257              result = dns_rdataset_next(&rdataset)) {
 258                 dns_rdata_t rdata = DNS_RDATA_INIT;
 259
 260                 dns_rdataset_current(&rdataset, &rdata);
 261                 result = dns_rdata_tostruct(&rdata, &dnskey, NULL);
 262                 RUNTIME_CHECK(result == ISC_R_SUCCESS);
 263
 264                 if (dnskey.algorithm == DST_ALG_RSAMD5 ||
 265                     dnskey.algorithm == DST_ALG_RSASHA1 ||
 266                     dnskey.algorithm == DST_ALG_DSA ||
 267                     dnskey.algorithm == DST_ALG_ECC)
 268                         break;
 269         }
 270         dns_rdataset_disassociate(&rdataset);
 271         if (result == ISC_R_SUCCESS)
 272                 *answer = ISC_TRUE;
 273         if (result == ISC_R_NOMORE) {
 274                 *answer = ISC_FALSE;
 275                 result = ISC_R_SUCCESS;
 276         }
 277         return (result);
 278 }
 279
 280 /*%
 281  * Return ISC_R_SUCCESS if we can determine that the name doesn't exist
 282  * or we can determine whether there is data or not at the name.
 283  * If the name does not exist return the wildcard name.
 284  *
 285  * Return ISC_R_IGNORE when the NSEC is not the appropriate one.
 286  */
 287 isc_result_t
 288 dns_nsec_noexistnodata(dns_rdatatype_t type, dns_name_t *name,
 289                        dns_name_t *nsecname, dns_rdataset_t *nsecset,
 290                        isc_boolean_t *exists, isc_boolean_t *data,
 291                        dns_name_t *wild, dns_nseclog_t logit, void *arg)
 292 {
 293         int order;
 294         dns_rdata_t rdata = DNS_RDATA_INIT;
 295         isc_result_t result;
 296         dns_namereln_t relation;
 297         unsigned int olabels, nlabels, labels;
 298         dns_rdata_nsec_t nsec;
 299         isc_boolean_t atparent;
 300         isc_boolean_t ns;
 301         isc_boolean_t soa;
 302
 303         REQUIRE(exists != NULL);
 304         REQUIRE(data != NULL);
 305         REQUIRE(nsecset != NULL &&
 306                 nsecset->type == dns_rdatatype_nsec);
 307
 308         result = dns_rdataset_first(nsecset);
 309         if (result != ISC_R_SUCCESS) {
 310                 (*logit)(arg, ISC_LOG_DEBUG(3), "failure processing NSEC set");
 311                 return (result);
 312         }
 313         dns_rdataset_current(nsecset, &rdata);
 314
 315         (*logit)(arg, ISC_LOG_DEBUG(3), "looking for relevant NSEC");
 316         relation = dns_name_fullcompare(name, nsecname, &order, &olabels);
 317
 318         if (order < 0) {
 319                 /*
 320                  * The name is not within the NSEC range.
 321                  */
 322                 (*logit)(arg, ISC_LOG_DEBUG(3),
 323                               "NSEC does not cover name, before NSEC");
 324                 return (ISC_R_IGNORE);
 325         }
 326
 327         if (order == 0) {
 328                 /*
 329                  * The names are the same.   If we are validating "."
 330                  * then atparent should not be set as there is no parent.
 331                  */
 332                 atparent = (olabels != 1) && dns_rdatatype_atparent(type);
 333                 ns = dns_nsec_typepresent(&rdata, dns_rdatatype_ns);
 334                 soa = dns_nsec_typepresent(&rdata, dns_rdatatype_soa);
 335                 if (ns && !soa) {
 336                         if (!atparent) {
 337                                 /*
 338                                  * This NSEC record is from somewhere higher in
 339                                  * the DNS, and at the parent of a delegation.
 340                                  * It can not be legitimately used here.
 341                                  */
 342                                 (*logit)(arg, ISC_LOG_DEBUG(3),
 343                                               "ignoring parent nsec");
 344                                 return (ISC_R_IGNORE);
 345                         }
 346                 } else if (atparent && ns && soa) {
 347                         /*
 348                          * This NSEC record is from the child.
 349                          * It can not be legitimately used here.
 350                          */
 351                         (*logit)(arg, ISC_LOG_DEBUG(3),
 352                                       "ignoring child nsec");
 353                         return (ISC_R_IGNORE);
 354                 }
 355                 if (type == dns_rdatatype_cname || type == dns_rdatatype_nxt ||
 356                     type == dns_rdatatype_nsec || type == dns_rdatatype_key ||
 357                     !dns_nsec_typepresent(&rdata, dns_rdatatype_cname)) {
 358                         *exists = ISC_TRUE;
 359                         *data = dns_nsec_typepresent(&rdata, type);
 360                         (*logit)(arg, ISC_LOG_DEBUG(3),
 361                                       "nsec proves name exists (owner) data=%d",
 362                                       *data);
 363                         return (ISC_R_SUCCESS);
 364                 }
 365                 (*logit)(arg, ISC_LOG_DEBUG(3), "NSEC proves CNAME exists");
 366                 return (ISC_R_IGNORE);
 367         }
 368
 369         if (relation == dns_namereln_subdomain &&
 370             dns_nsec_typepresent(&rdata, dns_rdatatype_ns) &&
 371             !dns_nsec_typepresent(&rdata, dns_rdatatype_soa))
 372         {
 373                 /*
 374                  * This NSEC record is from somewhere higher in
 375                  * the DNS, and at the parent of a delegation.
 376                  * It can not be legitimately used here.
 377                  */
 378                 (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring parent nsec");
 379                 return (ISC_R_IGNORE);
 380         }
 381
 382         result = dns_rdata_tostruct(&rdata, &nsec, NULL);
 383         if (result != ISC_R_SUCCESS)
 384                 return (result);
 385         relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels);
 386         if (order == 0) {
 387                 dns_rdata_freestruct(&nsec);
 388                 (*logit)(arg, ISC_LOG_DEBUG(3),
 389                               "ignoring nsec matches next name");
 390                 return (ISC_R_IGNORE);
 391         }
 392
 393         if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) {
 394                 /*
 395                  * The name is not within the NSEC range.
 396                  */
 397                 dns_rdata_freestruct(&nsec);
 398                 (*logit)(arg, ISC_LOG_DEBUG(3),
 399                             "ignoring nsec because name is past end of range");
 400                 return (ISC_R_IGNORE);
 401         }
 402
 403         if (order > 0 && relation == dns_namereln_subdomain) {
 404                 (*logit)(arg, ISC_LOG_DEBUG(3),
 405                               "nsec proves name exist (empty)");
 406                 dns_rdata_freestruct(&nsec);
 407                 *exists = ISC_TRUE;
 408                 *data = ISC_FALSE;
 409                 return (ISC_R_SUCCESS);
 410         }
 411         if (wild != NULL) {
 412                 dns_name_t common;
 413                 dns_name_init(&common, NULL);
 414                 if (olabels > nlabels) {
 415                         labels = dns_name_countlabels(nsecname);
 416                         dns_name_getlabelsequence(nsecname, labels - olabels,
 417                                                   olabels, &common);
 418                 } else {
 419                         labels = dns_name_countlabels(&nsec.next);
 420                         dns_name_getlabelsequence(&nsec.next, labels - nlabels,
 421                                                   nlabels, &common);
 422                 }
 423                 result = dns_name_concatenate(dns_wildcardname, &common,
 424                                                wild, NULL);
 425                 if (result != ISC_R_SUCCESS) {
 426                         dns_rdata_freestruct(&nsec);
 427                         (*logit)(arg, ISC_LOG_DEBUG(3),
 428                                     "failure generating wildcard name");
 429                         return (result);
 430                 }
 431         }
 432         dns_rdata_freestruct(&nsec);
 433         (*logit)(arg, ISC_LOG_DEBUG(3), "nsec range ok");
 434         *exists = ISC_FALSE;
 435         return (ISC_R_SUCCESS);
 436 }