contrib/bind9/lib/dns/nsec.c

   1 /*
   2  * Copyright (C) 2004, 2005, 2007-2009, 2011-2014  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 void
  46 dns_nsec_setbit(unsigned char *array, unsigned int type, unsigned int bit) {
  47         unsigned int shift, mask;
  48
  49         shift = 7 - (type % 8);
  50         mask = 1 << shift;
  51
  52         if (bit != 0)
  53                 array[type / 8] |= mask;
  54         else
  55                 array[type / 8] &= (~mask & 0xFF);
  56 }
  57
  58 isc_boolean_t
  59 dns_nsec_isset(const unsigned char *array, unsigned int type) {
  60         unsigned int byte, shift, mask;
  61
  62         byte = array[type / 8];
  63         shift = 7 - (type % 8);
  64         mask = 1 << shift;
  65
  66         return (ISC_TF(byte & mask));
  67 }
  68
  69 unsigned int
  70 dns_nsec_compressbitmap(unsigned char *map, const unsigned char *raw,
  71                         unsigned int max_type)
  72 {
  73         unsigned char *start = map;
  74         unsigned int window;
  75         int octet;
  76
  77         if (raw == NULL)
  78                 return (0);
  79
  80         for (window = 0; window < 256; window++) {
  81                 if (window * 256 > max_type)
  82                         break;
  83                 for (octet = 31; octet >= 0; octet--)
  84                         if (*(raw + octet) != 0)
  85                                 break;
  86                 if (octet < 0) {
  87                         raw += 32;
  88                         continue;
  89                 }
  90                 *map++ = window;
  91                 *map++ = octet + 1;
  92                 /*
  93                  * Note: potential overlapping move.
  94                  */
  95                 memmove(map, raw, octet + 1);
  96                 map += octet + 1;
  97                 raw += 32;
  98         }
  99         return (unsigned int)(map - start);
 100 }
 101
 102 isc_result_t
 103 dns_nsec_buildrdata(dns_db_t *db, dns_dbversion_t *version,
 104                     dns_dbnode_t *node, dns_name_t *target,
 105                     unsigned char *buffer, dns_rdata_t *rdata)
 106 {
 107         isc_result_t result;
 108         dns_rdataset_t rdataset;
 109         isc_region_t r;
 110         unsigned int i;
 111
 112         unsigned char *nsec_bits, *bm;
 113         unsigned int max_type;
 114         dns_rdatasetiter_t *rdsiter;
 115
 116         memset(buffer, 0, DNS_NSEC_BUFFERSIZE);
 117         dns_name_toregion(target, &r);
 118         memmove(buffer, r.base, r.length);
 119         r.base = buffer;
 120         /*
 121          * Use the end of the space for a raw bitmap leaving enough
 122          * space for the window identifiers and length octets.
 123          */
 124         bm = r.base + r.length + 512;
 125         nsec_bits = r.base + r.length;
 126         dns_nsec_setbit(bm, dns_rdatatype_rrsig, 1);
 127         dns_nsec_setbit(bm, dns_rdatatype_nsec, 1);
 128         max_type = dns_rdatatype_nsec;
 129         dns_rdataset_init(&rdataset);
 130         rdsiter = NULL;
 131         result = dns_db_allrdatasets(db, node, version, 0, &rdsiter);
 132         if (result != ISC_R_SUCCESS)
 133                 return (result);
 134         for (result = dns_rdatasetiter_first(rdsiter);
 135              result == ISC_R_SUCCESS;
 136              result = dns_rdatasetiter_next(rdsiter))
 137         {
 138                 dns_rdatasetiter_current(rdsiter, &rdataset);
 139                 if (rdataset.type != dns_rdatatype_nsec &&
 140                     rdataset.type != dns_rdatatype_nsec3 &&
 141                     rdataset.type != dns_rdatatype_rrsig) {
 142                         if (rdataset.type > max_type)
 143                                 max_type = rdataset.type;
 144                         dns_nsec_setbit(bm, rdataset.type, 1);
 145                 }
 146                 dns_rdataset_disassociate(&rdataset);
 147         }
 148
 149         /*
 150          * At zone cuts, deny the existence of glue in the parent zone.
 151          */
 152         if (dns_nsec_isset(bm, dns_rdatatype_ns) &&
 153             ! dns_nsec_isset(bm, dns_rdatatype_soa)) {
 154                 for (i = 0; i <= max_type; i++) {
 155                         if (dns_nsec_isset(bm, i) &&
 156                             ! dns_rdatatype_iszonecutauth((dns_rdatatype_t)i))
 157                                 dns_nsec_setbit(bm, i, 0);
 158                 }
 159         }
 160
 161         dns_rdatasetiter_destroy(&rdsiter);
 162         if (result != ISC_R_NOMORE)
 163                 return (result);
 164
 165         nsec_bits += dns_nsec_compressbitmap(nsec_bits, bm, max_type);
 166
 167         r.length = (unsigned int)(nsec_bits - r.base);
 168         INSIST(r.length <= DNS_NSEC_BUFFERSIZE);
 169         dns_rdata_fromregion(rdata,
 170                              dns_db_class(db),
 171                              dns_rdatatype_nsec,
 172                              &r);
 173
 174         return (ISC_R_SUCCESS);
 175 }
 176
 177 isc_result_t
 178 dns_nsec_build(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node,
 179                dns_name_t *target, dns_ttl_t ttl)
 180 {
 181         isc_result_t result;
 182         dns_rdata_t rdata = DNS_RDATA_INIT;
 183         unsigned char data[DNS_NSEC_BUFFERSIZE];
 184         dns_rdatalist_t rdatalist;
 185         dns_rdataset_t rdataset;
 186
 187         dns_rdataset_init(&rdataset);
 188         dns_rdata_init(&rdata);
 189
 190         RETERR(dns_nsec_buildrdata(db, version, node, target, data, &rdata));
 191
 192         rdatalist.rdclass = dns_db_class(db);
 193         rdatalist.type = dns_rdatatype_nsec;
 194         rdatalist.covers = 0;
 195         rdatalist.ttl = ttl;
 196         ISC_LIST_INIT(rdatalist.rdata);
 197         ISC_LIST_APPEND(rdatalist.rdata, &rdata, link);
 198         RETERR(dns_rdatalist_tordataset(&rdatalist, &rdataset));
 199         result = dns_db_addrdataset(db, node, version, 0, &rdataset,
 200                                     0, NULL);
 201         if (result == DNS_R_UNCHANGED)
 202                 result = ISC_R_SUCCESS;
 203
 204  failure:
 205         if (dns_rdataset_isassociated(&rdataset))
 206                 dns_rdataset_disassociate(&rdataset);
 207         return (result);
 208 }
 209
 210 isc_boolean_t
 211 dns_nsec_typepresent(dns_rdata_t *nsec, dns_rdatatype_t type) {
 212         dns_rdata_nsec_t nsecstruct;
 213         isc_result_t result;
 214         isc_boolean_t present;
 215         unsigned int i, len, window;
 216
 217         REQUIRE(nsec != NULL);
 218         REQUIRE(nsec->type == dns_rdatatype_nsec);
 219
 220         /* This should never fail */
 221         result = dns_rdata_tostruct(nsec, &nsecstruct, NULL);
 222         INSIST(result == ISC_R_SUCCESS);
 223
 224         present = ISC_FALSE;
 225         for (i = 0; i < nsecstruct.len; i += len) {
 226                 INSIST(i + 2 <= nsecstruct.len);
 227                 window = nsecstruct.typebits[i];
 228                 len = nsecstruct.typebits[i + 1];
 229                 INSIST(len > 0 && len <= 32);
 230                 i += 2;
 231                 INSIST(i + len <= nsecstruct.len);
 232                 if (window * 256 > type)
 233                         break;
 234                 if ((window + 1) * 256 <= type)
 235                         continue;
 236                 if (type < (window * 256) + len * 8)
 237                         present = ISC_TF(dns_nsec_isset(&nsecstruct.typebits[i],
 238                                                         type % 256));
 239                 break;
 240         }
 241         dns_rdata_freestruct(&nsecstruct);
 242         return (present);
 243 }
 244
 245 isc_result_t
 246 dns_nsec_nseconly(dns_db_t *db, dns_dbversion_t *version,
 247                   isc_boolean_t *answer)
 248 {
 249         dns_dbnode_t *node = NULL;
 250         dns_rdataset_t rdataset;
 251         dns_rdata_dnskey_t dnskey;
 252         isc_result_t result;
 253
 254         REQUIRE(answer != NULL);
 255
 256         dns_rdataset_init(&rdataset);
 257
 258         result = dns_db_getoriginnode(db, &node);
 259         if (result != ISC_R_SUCCESS)
 260                 return (result);
 261
 262         result = dns_db_findrdataset(db, node, version, dns_rdatatype_dnskey,
 263                                      0, 0, &rdataset, NULL);
 264         dns_db_detachnode(db, &node);
 265
 266         if (result == ISC_R_NOTFOUND)
 267                 *answer = ISC_FALSE;
 268         if (result != ISC_R_SUCCESS)
 269                 return (result);
 270         for (result = dns_rdataset_first(&rdataset);
 271              result == ISC_R_SUCCESS;
 272              result = dns_rdataset_next(&rdataset)) {
 273                 dns_rdata_t rdata = DNS_RDATA_INIT;
 274
 275                 dns_rdataset_current(&rdataset, &rdata);
 276                 result = dns_rdata_tostruct(&rdata, &dnskey, NULL);
 277                 RUNTIME_CHECK(result == ISC_R_SUCCESS);
 278
 279                 if (dnskey.algorithm == DST_ALG_RSAMD5 ||
 280                     dnskey.algorithm == DST_ALG_RSASHA1 ||
 281                     dnskey.algorithm == DST_ALG_DSA ||
 282                     dnskey.algorithm == DST_ALG_ECC)
 283                         break;
 284         }
 285         dns_rdataset_disassociate(&rdataset);
 286         if (result == ISC_R_SUCCESS)
 287                 *answer = ISC_TRUE;
 288         if (result == ISC_R_NOMORE) {
 289                 *answer = ISC_FALSE;
 290                 result = ISC_R_SUCCESS;
 291         }
 292         return (result);
 293 }
 294
 295 /*%
 296  * Return ISC_R_SUCCESS if we can determine that the name doesn't exist
 297  * or we can determine whether there is data or not at the name.
 298  * If the name does not exist return the wildcard name.
 299  *
 300  * Return ISC_R_IGNORE when the NSEC is not the appropriate one.
 301  */
 302 isc_result_t
 303 dns_nsec_noexistnodata(dns_rdatatype_t type, dns_name_t *name,
 304                        dns_name_t *nsecname, dns_rdataset_t *nsecset,
 305                        isc_boolean_t *exists, isc_boolean_t *data,
 306                        dns_name_t *wild, dns_nseclog_t logit, void *arg)
 307 {
 308         int order;
 309         dns_rdata_t rdata = DNS_RDATA_INIT;
 310         isc_result_t result;
 311         dns_namereln_t relation;
 312         unsigned int olabels, nlabels, labels;
 313         dns_rdata_nsec_t nsec;
 314         isc_boolean_t atparent;
 315         isc_boolean_t ns;
 316         isc_boolean_t soa;
 317
 318         REQUIRE(exists != NULL);
 319         REQUIRE(data != NULL);
 320         REQUIRE(nsecset != NULL &&
 321                 nsecset->type == dns_rdatatype_nsec);
 322
 323         result = dns_rdataset_first(nsecset);
 324         if (result != ISC_R_SUCCESS) {
 325                 (*logit)(arg, ISC_LOG_DEBUG(3), "failure processing NSEC set");
 326                 return (result);
 327         }
 328         dns_rdataset_current(nsecset, &rdata);
 329
 330         (*logit)(arg, ISC_LOG_DEBUG(3), "looking for relevant NSEC");
 331         relation = dns_name_fullcompare(name, nsecname, &order, &olabels);
 332
 333         if (order < 0) {
 334                 /*
 335                  * The name is not within the NSEC range.
 336                  */
 337                 (*logit)(arg, ISC_LOG_DEBUG(3),
 338                               "NSEC does not cover name, before NSEC");
 339                 return (ISC_R_IGNORE);
 340         }
 341
 342         if (order == 0) {
 343                 /*
 344                  * The names are the same.   If we are validating "."
 345                  * then atparent should not be set as there is no parent.
 346                  */
 347                 atparent = (olabels != 1) && dns_rdatatype_atparent(type);
 348                 ns = dns_nsec_typepresent(&rdata, dns_rdatatype_ns);
 349                 soa = dns_nsec_typepresent(&rdata, dns_rdatatype_soa);
 350                 if (ns && !soa) {
 351                         if (!atparent) {
 352                                 /*
 353                                  * This NSEC record is from somewhere higher in
 354                                  * the DNS, and at the parent of a delegation.
 355                                  * It can not be legitimately used here.
 356                                  */
 357                                 (*logit)(arg, ISC_LOG_DEBUG(3),
 358                                               "ignoring parent nsec");
 359                                 return (ISC_R_IGNORE);
 360                         }
 361                 } else if (atparent && ns && soa) {
 362                         /*
 363                          * This NSEC record is from the child.
 364                          * It can not be legitimately used here.
 365                          */
 366                         (*logit)(arg, ISC_LOG_DEBUG(3),
 367                                       "ignoring child nsec");
 368                         return (ISC_R_IGNORE);
 369                 }
 370                 if (type == dns_rdatatype_cname || type == dns_rdatatype_nxt ||
 371                     type == dns_rdatatype_nsec || type == dns_rdatatype_key ||
 372                     !dns_nsec_typepresent(&rdata, dns_rdatatype_cname)) {
 373                         *exists = ISC_TRUE;
 374                         *data = dns_nsec_typepresent(&rdata, type);
 375                         (*logit)(arg, ISC_LOG_DEBUG(3),
 376                                       "nsec proves name exists (owner) data=%d",
 377                                       *data);
 378                         return (ISC_R_SUCCESS);
 379                 }
 380                 (*logit)(arg, ISC_LOG_DEBUG(3), "NSEC proves CNAME exists");
 381                 return (ISC_R_IGNORE);
 382         }
 383
 384         if (relation == dns_namereln_subdomain &&
 385             dns_nsec_typepresent(&rdata, dns_rdatatype_ns) &&
 386             !dns_nsec_typepresent(&rdata, dns_rdatatype_soa))
 387         {
 388                 /*
 389                  * This NSEC record is from somewhere higher in
 390                  * the DNS, and at the parent of a delegation.
 391                  * It can not be legitimately used here.
 392                  */
 393                 (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring parent nsec");
 394                 return (ISC_R_IGNORE);
 395         }
 396
 397         result = dns_rdata_tostruct(&rdata, &nsec, NULL);
 398         if (result != ISC_R_SUCCESS)
 399                 return (result);
 400         relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels);
 401         if (order == 0) {
 402                 dns_rdata_freestruct(&nsec);
 403                 (*logit)(arg, ISC_LOG_DEBUG(3),
 404                               "ignoring nsec matches next name");
 405                 return (ISC_R_IGNORE);
 406         }
 407
 408         if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) {
 409                 /*
 410                  * The name is not within the NSEC range.
 411                  */
 412                 dns_rdata_freestruct(&nsec);
 413                 (*logit)(arg, ISC_LOG_DEBUG(3),
 414                             "ignoring nsec because name is past end of range");
 415                 return (ISC_R_IGNORE);
 416         }
 417
 418         if (order > 0 && relation == dns_namereln_subdomain) {
 419                 (*logit)(arg, ISC_LOG_DEBUG(3),
 420                               "nsec proves name exist (empty)");
 421                 dns_rdata_freestruct(&nsec);
 422                 *exists = ISC_TRUE;
 423                 *data = ISC_FALSE;
 424                 return (ISC_R_SUCCESS);
 425         }
 426         if (wild != NULL) {
 427                 dns_name_t common;
 428                 dns_name_init(&common, NULL);
 429                 if (olabels > nlabels) {
 430                         labels = dns_name_countlabels(nsecname);
 431                         dns_name_getlabelsequence(nsecname, labels - olabels,
 432                                                   olabels, &common);
 433                 } else {
 434                         labels = dns_name_countlabels(&nsec.next);
 435                         dns_name_getlabelsequence(&nsec.next, labels - nlabels,
 436                                                   nlabels, &common);
 437                 }
 438                 result = dns_name_concatenate(dns_wildcardname, &common,
 439                                                wild, NULL);
 440                 if (result != ISC_R_SUCCESS) {
 441                         dns_rdata_freestruct(&nsec);
 442                         (*logit)(arg, ISC_LOG_DEBUG(3),
 443                                     "failure generating wildcard name");
 444                         return (result);
 445                 }
 446         }
 447         dns_rdata_freestruct(&nsec);
 448         (*logit)(arg, ISC_LOG_DEBUG(3), "nsec range ok");
 449         *exists = ISC_FALSE;
 450         return (ISC_R_SUCCESS);
 451 }