external/bsd/bind/dist/lib/dns/nsec.c

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