1135446Strhodes/* 2262706Serwin * Copyright (C) 2004, 2005, 2007-2009, 2011-2014 Internet Systems Consortium, Inc. ("ISC") 3135446Strhodes * Copyright (C) 1999-2001, 2003 Internet Software Consortium. 4135446Strhodes * 5193149Sdougb * Permission to use, copy, modify, and/or distribute this software for any 6135446Strhodes * purpose with or without fee is hereby granted, provided that the above 7135446Strhodes * copyright notice and this permission notice appear in all copies. 8135446Strhodes * 9135446Strhodes * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10135446Strhodes * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11135446Strhodes * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12135446Strhodes * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13135446Strhodes * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14135446Strhodes * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15135446Strhodes * PERFORMANCE OF THIS SOFTWARE. 16135446Strhodes */ 17135446Strhodes 18234010Sdougb/* $Id$ */ 19135446Strhodes 20170222Sdougb/*! \file */ 21170222Sdougb 22135446Strhodes#include <config.h> 23135446Strhodes 24254402Serwin#include <isc/log.h> 25135446Strhodes#include <isc/string.h> 26135446Strhodes#include <isc/util.h> 27135446Strhodes 28135446Strhodes#include <dns/db.h> 29135446Strhodes#include <dns/nsec.h> 30135446Strhodes#include <dns/rdata.h> 31135446Strhodes#include <dns/rdatalist.h> 32135446Strhodes#include <dns/rdataset.h> 33135446Strhodes#include <dns/rdatasetiter.h> 34135446Strhodes#include <dns/rdatastruct.h> 35135446Strhodes#include <dns/result.h> 36135446Strhodes 37193149Sdougb#include <dst/dst.h> 38193149Sdougb 39135446Strhodes#define RETERR(x) do { \ 40135446Strhodes result = (x); \ 41135446Strhodes if (result != ISC_R_SUCCESS) \ 42135446Strhodes goto failure; \ 43135446Strhodes } while (0) 44135446Strhodes 45254897Serwinvoid 46254897Serwindns_nsec_setbit(unsigned char *array, unsigned int type, unsigned int bit) { 47135446Strhodes unsigned int shift, mask; 48135446Strhodes 49254897Serwin shift = 7 - (type % 8); 50135446Strhodes mask = 1 << shift; 51135446Strhodes 52135446Strhodes if (bit != 0) 53254897Serwin array[type / 8] |= mask; 54135446Strhodes else 55254897Serwin array[type / 8] &= (~mask & 0xFF); 56135446Strhodes} 57135446Strhodes 58254897Serwinisc_boolean_t 59254897Serwindns_nsec_isset(const unsigned char *array, unsigned int type) { 60135446Strhodes unsigned int byte, shift, mask; 61135446Strhodes 62254897Serwin byte = array[type / 8]; 63254897Serwin shift = 7 - (type % 8); 64135446Strhodes mask = 1 << shift; 65135446Strhodes 66254897Serwin return (ISC_TF(byte & mask)); 67135446Strhodes} 68135446Strhodes 69254897Serwinunsigned int 70254897Serwindns_nsec_compressbitmap(unsigned char *map, const unsigned char *raw, 71254897Serwin unsigned int max_type) 72254897Serwin{ 73254897Serwin unsigned char *start = map; 74254897Serwin unsigned int window; 75254897Serwin int octet; 76254897Serwin 77254897Serwin if (raw == NULL) 78254897Serwin return (0); 79254897Serwin 80254897Serwin for (window = 0; window < 256; window++) { 81254897Serwin if (window * 256 > max_type) 82254897Serwin break; 83254897Serwin for (octet = 31; octet >= 0; octet--) 84254897Serwin if (*(raw + octet) != 0) 85254897Serwin break; 86254897Serwin if (octet < 0) { 87254897Serwin raw += 32; 88254897Serwin continue; 89254897Serwin } 90254897Serwin *map++ = window; 91254897Serwin *map++ = octet + 1; 92254897Serwin /* 93254897Serwin * Note: potential overlapping move. 94254897Serwin */ 95254897Serwin memmove(map, raw, octet + 1); 96254897Serwin map += octet + 1; 97254897Serwin raw += 32; 98254897Serwin } 99262706Serwin return (unsigned int)(map - start); 100254897Serwin} 101254897Serwin 102135446Strhodesisc_result_t 103135446Strhodesdns_nsec_buildrdata(dns_db_t *db, dns_dbversion_t *version, 104135446Strhodes dns_dbnode_t *node, dns_name_t *target, 105135446Strhodes unsigned char *buffer, dns_rdata_t *rdata) 106135446Strhodes{ 107135446Strhodes isc_result_t result; 108135446Strhodes dns_rdataset_t rdataset; 109135446Strhodes isc_region_t r; 110254897Serwin unsigned int i; 111135446Strhodes 112135446Strhodes unsigned char *nsec_bits, *bm; 113135446Strhodes unsigned int max_type; 114135446Strhodes dns_rdatasetiter_t *rdsiter; 115135446Strhodes 116135446Strhodes memset(buffer, 0, DNS_NSEC_BUFFERSIZE); 117135446Strhodes dns_name_toregion(target, &r); 118262706Serwin memmove(buffer, r.base, r.length); 119135446Strhodes r.base = buffer; 120135446Strhodes /* 121135446Strhodes * Use the end of the space for a raw bitmap leaving enough 122135446Strhodes * space for the window identifiers and length octets. 123135446Strhodes */ 124135446Strhodes bm = r.base + r.length + 512; 125135446Strhodes nsec_bits = r.base + r.length; 126254897Serwin dns_nsec_setbit(bm, dns_rdatatype_rrsig, 1); 127254897Serwin dns_nsec_setbit(bm, dns_rdatatype_nsec, 1); 128135446Strhodes max_type = dns_rdatatype_nsec; 129135446Strhodes dns_rdataset_init(&rdataset); 130135446Strhodes rdsiter = NULL; 131135446Strhodes result = dns_db_allrdatasets(db, node, version, 0, &rdsiter); 132135446Strhodes if (result != ISC_R_SUCCESS) 133135446Strhodes return (result); 134135446Strhodes for (result = dns_rdatasetiter_first(rdsiter); 135135446Strhodes result == ISC_R_SUCCESS; 136135446Strhodes result = dns_rdatasetiter_next(rdsiter)) 137135446Strhodes { 138135446Strhodes dns_rdatasetiter_current(rdsiter, &rdataset); 139193149Sdougb if (rdataset.type != dns_rdatatype_nsec && 140193149Sdougb rdataset.type != dns_rdatatype_nsec3 && 141193149Sdougb rdataset.type != dns_rdatatype_rrsig) { 142135446Strhodes if (rdataset.type > max_type) 143135446Strhodes max_type = rdataset.type; 144254897Serwin dns_nsec_setbit(bm, rdataset.type, 1); 145135446Strhodes } 146135446Strhodes dns_rdataset_disassociate(&rdataset); 147135446Strhodes } 148135446Strhodes 149135446Strhodes /* 150135446Strhodes * At zone cuts, deny the existence of glue in the parent zone. 151135446Strhodes */ 152254897Serwin if (dns_nsec_isset(bm, dns_rdatatype_ns) && 153254897Serwin ! dns_nsec_isset(bm, dns_rdatatype_soa)) { 154135446Strhodes for (i = 0; i <= max_type; i++) { 155254897Serwin if (dns_nsec_isset(bm, i) && 156135446Strhodes ! dns_rdatatype_iszonecutauth((dns_rdatatype_t)i)) 157254897Serwin dns_nsec_setbit(bm, i, 0); 158135446Strhodes } 159135446Strhodes } 160135446Strhodes 161135446Strhodes dns_rdatasetiter_destroy(&rdsiter); 162135446Strhodes if (result != ISC_R_NOMORE) 163135446Strhodes return (result); 164135446Strhodes 165254897Serwin nsec_bits += dns_nsec_compressbitmap(nsec_bits, bm, max_type); 166254897Serwin 167262706Serwin r.length = (unsigned int)(nsec_bits - r.base); 168135446Strhodes INSIST(r.length <= DNS_NSEC_BUFFERSIZE); 169135446Strhodes dns_rdata_fromregion(rdata, 170135446Strhodes dns_db_class(db), 171135446Strhodes dns_rdatatype_nsec, 172135446Strhodes &r); 173135446Strhodes 174135446Strhodes return (ISC_R_SUCCESS); 175135446Strhodes} 176135446Strhodes 177135446Strhodesisc_result_t 178135446Strhodesdns_nsec_build(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node, 179135446Strhodes dns_name_t *target, dns_ttl_t ttl) 180135446Strhodes{ 181135446Strhodes isc_result_t result; 182135446Strhodes dns_rdata_t rdata = DNS_RDATA_INIT; 183135446Strhodes unsigned char data[DNS_NSEC_BUFFERSIZE]; 184135446Strhodes dns_rdatalist_t rdatalist; 185135446Strhodes dns_rdataset_t rdataset; 186135446Strhodes 187135446Strhodes dns_rdataset_init(&rdataset); 188135446Strhodes dns_rdata_init(&rdata); 189135446Strhodes 190135446Strhodes RETERR(dns_nsec_buildrdata(db, version, node, target, data, &rdata)); 191135446Strhodes 192135446Strhodes rdatalist.rdclass = dns_db_class(db); 193135446Strhodes rdatalist.type = dns_rdatatype_nsec; 194135446Strhodes rdatalist.covers = 0; 195135446Strhodes rdatalist.ttl = ttl; 196135446Strhodes ISC_LIST_INIT(rdatalist.rdata); 197135446Strhodes ISC_LIST_APPEND(rdatalist.rdata, &rdata, link); 198135446Strhodes RETERR(dns_rdatalist_tordataset(&rdatalist, &rdataset)); 199135446Strhodes result = dns_db_addrdataset(db, node, version, 0, &rdataset, 200135446Strhodes 0, NULL); 201135446Strhodes if (result == DNS_R_UNCHANGED) 202135446Strhodes result = ISC_R_SUCCESS; 203225361Sdougb 204135446Strhodes failure: 205135446Strhodes if (dns_rdataset_isassociated(&rdataset)) 206135446Strhodes dns_rdataset_disassociate(&rdataset); 207135446Strhodes return (result); 208135446Strhodes} 209135446Strhodes 210135446Strhodesisc_boolean_t 211135446Strhodesdns_nsec_typepresent(dns_rdata_t *nsec, dns_rdatatype_t type) { 212135446Strhodes dns_rdata_nsec_t nsecstruct; 213135446Strhodes isc_result_t result; 214135446Strhodes isc_boolean_t present; 215135446Strhodes unsigned int i, len, window; 216135446Strhodes 217135446Strhodes REQUIRE(nsec != NULL); 218135446Strhodes REQUIRE(nsec->type == dns_rdatatype_nsec); 219135446Strhodes 220135446Strhodes /* This should never fail */ 221135446Strhodes result = dns_rdata_tostruct(nsec, &nsecstruct, NULL); 222135446Strhodes INSIST(result == ISC_R_SUCCESS); 223193149Sdougb 224135446Strhodes present = ISC_FALSE; 225135446Strhodes for (i = 0; i < nsecstruct.len; i += len) { 226135446Strhodes INSIST(i + 2 <= nsecstruct.len); 227135446Strhodes window = nsecstruct.typebits[i]; 228135446Strhodes len = nsecstruct.typebits[i + 1]; 229135446Strhodes INSIST(len > 0 && len <= 32); 230135446Strhodes i += 2; 231135446Strhodes INSIST(i + len <= nsecstruct.len); 232135446Strhodes if (window * 256 > type) 233135446Strhodes break; 234135446Strhodes if ((window + 1) * 256 <= type) 235135446Strhodes continue; 236135446Strhodes if (type < (window * 256) + len * 8) 237254897Serwin present = ISC_TF(dns_nsec_isset(&nsecstruct.typebits[i], 238254897Serwin type % 256)); 239135446Strhodes break; 240135446Strhodes } 241193149Sdougb dns_rdata_freestruct(&nsecstruct); 242135446Strhodes return (present); 243135446Strhodes} 244193149Sdougb 245193149Sdougbisc_result_t 246193149Sdougbdns_nsec_nseconly(dns_db_t *db, dns_dbversion_t *version, 247193149Sdougb isc_boolean_t *answer) 248193149Sdougb{ 249193149Sdougb dns_dbnode_t *node = NULL; 250193149Sdougb dns_rdataset_t rdataset; 251193149Sdougb dns_rdata_dnskey_t dnskey; 252193149Sdougb isc_result_t result; 253193149Sdougb 254193149Sdougb REQUIRE(answer != NULL); 255193149Sdougb 256193149Sdougb dns_rdataset_init(&rdataset); 257193149Sdougb 258193149Sdougb result = dns_db_getoriginnode(db, &node); 259193149Sdougb if (result != ISC_R_SUCCESS) 260193149Sdougb return (result); 261193149Sdougb 262193149Sdougb result = dns_db_findrdataset(db, node, version, dns_rdatatype_dnskey, 263193149Sdougb 0, 0, &rdataset, NULL); 264193149Sdougb dns_db_detachnode(db, &node); 265193149Sdougb 266254897Serwin if (result == ISC_R_NOTFOUND) 267193149Sdougb *answer = ISC_FALSE; 268193149Sdougb if (result != ISC_R_SUCCESS) 269193149Sdougb return (result); 270193149Sdougb for (result = dns_rdataset_first(&rdataset); 271193149Sdougb result == ISC_R_SUCCESS; 272193149Sdougb result = dns_rdataset_next(&rdataset)) { 273193149Sdougb dns_rdata_t rdata = DNS_RDATA_INIT; 274193149Sdougb 275193149Sdougb dns_rdataset_current(&rdataset, &rdata); 276193149Sdougb result = dns_rdata_tostruct(&rdata, &dnskey, NULL); 277193149Sdougb RUNTIME_CHECK(result == ISC_R_SUCCESS); 278193149Sdougb 279193149Sdougb if (dnskey.algorithm == DST_ALG_RSAMD5 || 280193149Sdougb dnskey.algorithm == DST_ALG_RSASHA1 || 281193149Sdougb dnskey.algorithm == DST_ALG_DSA || 282193149Sdougb dnskey.algorithm == DST_ALG_ECC) 283193149Sdougb break; 284193149Sdougb } 285193149Sdougb dns_rdataset_disassociate(&rdataset); 286193149Sdougb if (result == ISC_R_SUCCESS) 287193149Sdougb *answer = ISC_TRUE; 288193149Sdougb if (result == ISC_R_NOMORE) { 289193149Sdougb *answer = ISC_FALSE; 290193149Sdougb result = ISC_R_SUCCESS; 291193149Sdougb } 292193149Sdougb return (result); 293193149Sdougb} 294254402Serwin 295254402Serwin/*% 296254402Serwin * Return ISC_R_SUCCESS if we can determine that the name doesn't exist 297254402Serwin * or we can determine whether there is data or not at the name. 298254402Serwin * If the name does not exist return the wildcard name. 299254402Serwin * 300254402Serwin * Return ISC_R_IGNORE when the NSEC is not the appropriate one. 301254402Serwin */ 302254402Serwinisc_result_t 303254402Serwindns_nsec_noexistnodata(dns_rdatatype_t type, dns_name_t *name, 304254402Serwin dns_name_t *nsecname, dns_rdataset_t *nsecset, 305254402Serwin isc_boolean_t *exists, isc_boolean_t *data, 306254402Serwin dns_name_t *wild, dns_nseclog_t logit, void *arg) 307254402Serwin{ 308254402Serwin int order; 309254402Serwin dns_rdata_t rdata = DNS_RDATA_INIT; 310254402Serwin isc_result_t result; 311254402Serwin dns_namereln_t relation; 312254402Serwin unsigned int olabels, nlabels, labels; 313254402Serwin dns_rdata_nsec_t nsec; 314254402Serwin isc_boolean_t atparent; 315254402Serwin isc_boolean_t ns; 316254402Serwin isc_boolean_t soa; 317254402Serwin 318254402Serwin REQUIRE(exists != NULL); 319254402Serwin REQUIRE(data != NULL); 320254402Serwin REQUIRE(nsecset != NULL && 321254402Serwin nsecset->type == dns_rdatatype_nsec); 322254402Serwin 323254402Serwin result = dns_rdataset_first(nsecset); 324254402Serwin if (result != ISC_R_SUCCESS) { 325254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), "failure processing NSEC set"); 326254402Serwin return (result); 327254402Serwin } 328254402Serwin dns_rdataset_current(nsecset, &rdata); 329254402Serwin 330254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), "looking for relevant NSEC"); 331254402Serwin relation = dns_name_fullcompare(name, nsecname, &order, &olabels); 332254402Serwin 333254402Serwin if (order < 0) { 334254402Serwin /* 335254402Serwin * The name is not within the NSEC range. 336254402Serwin */ 337254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 338254402Serwin "NSEC does not cover name, before NSEC"); 339254402Serwin return (ISC_R_IGNORE); 340254402Serwin } 341254402Serwin 342254402Serwin if (order == 0) { 343254402Serwin /* 344254402Serwin * The names are the same. If we are validating "." 345254402Serwin * then atparent should not be set as there is no parent. 346254402Serwin */ 347254402Serwin atparent = (olabels != 1) && dns_rdatatype_atparent(type); 348254402Serwin ns = dns_nsec_typepresent(&rdata, dns_rdatatype_ns); 349254402Serwin soa = dns_nsec_typepresent(&rdata, dns_rdatatype_soa); 350254402Serwin if (ns && !soa) { 351254402Serwin if (!atparent) { 352254402Serwin /* 353254402Serwin * This NSEC record is from somewhere higher in 354254402Serwin * the DNS, and at the parent of a delegation. 355254402Serwin * It can not be legitimately used here. 356254402Serwin */ 357254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 358254402Serwin "ignoring parent nsec"); 359254402Serwin return (ISC_R_IGNORE); 360254402Serwin } 361254402Serwin } else if (atparent && ns && soa) { 362254402Serwin /* 363254402Serwin * This NSEC record is from the child. 364254402Serwin * It can not be legitimately used here. 365254402Serwin */ 366254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 367254402Serwin "ignoring child nsec"); 368254402Serwin return (ISC_R_IGNORE); 369254402Serwin } 370254402Serwin if (type == dns_rdatatype_cname || type == dns_rdatatype_nxt || 371254402Serwin type == dns_rdatatype_nsec || type == dns_rdatatype_key || 372254402Serwin !dns_nsec_typepresent(&rdata, dns_rdatatype_cname)) { 373254402Serwin *exists = ISC_TRUE; 374254402Serwin *data = dns_nsec_typepresent(&rdata, type); 375254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 376254402Serwin "nsec proves name exists (owner) data=%d", 377254402Serwin *data); 378254402Serwin return (ISC_R_SUCCESS); 379254402Serwin } 380254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), "NSEC proves CNAME exists"); 381254402Serwin return (ISC_R_IGNORE); 382254402Serwin } 383254402Serwin 384254402Serwin if (relation == dns_namereln_subdomain && 385254402Serwin dns_nsec_typepresent(&rdata, dns_rdatatype_ns) && 386254402Serwin !dns_nsec_typepresent(&rdata, dns_rdatatype_soa)) 387254402Serwin { 388254402Serwin /* 389254402Serwin * This NSEC record is from somewhere higher in 390254402Serwin * the DNS, and at the parent of a delegation. 391254402Serwin * It can not be legitimately used here. 392254402Serwin */ 393254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring parent nsec"); 394254402Serwin return (ISC_R_IGNORE); 395254402Serwin } 396254402Serwin 397254402Serwin result = dns_rdata_tostruct(&rdata, &nsec, NULL); 398254402Serwin if (result != ISC_R_SUCCESS) 399254402Serwin return (result); 400254402Serwin relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels); 401254402Serwin if (order == 0) { 402254402Serwin dns_rdata_freestruct(&nsec); 403254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 404254402Serwin "ignoring nsec matches next name"); 405254402Serwin return (ISC_R_IGNORE); 406254402Serwin } 407254402Serwin 408254402Serwin if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) { 409254402Serwin /* 410254402Serwin * The name is not within the NSEC range. 411254402Serwin */ 412254402Serwin dns_rdata_freestruct(&nsec); 413254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 414254402Serwin "ignoring nsec because name is past end of range"); 415254402Serwin return (ISC_R_IGNORE); 416254402Serwin } 417254402Serwin 418254402Serwin if (order > 0 && relation == dns_namereln_subdomain) { 419254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 420254402Serwin "nsec proves name exist (empty)"); 421254402Serwin dns_rdata_freestruct(&nsec); 422254402Serwin *exists = ISC_TRUE; 423254402Serwin *data = ISC_FALSE; 424254402Serwin return (ISC_R_SUCCESS); 425254402Serwin } 426254402Serwin if (wild != NULL) { 427254402Serwin dns_name_t common; 428254402Serwin dns_name_init(&common, NULL); 429254402Serwin if (olabels > nlabels) { 430254402Serwin labels = dns_name_countlabels(nsecname); 431254402Serwin dns_name_getlabelsequence(nsecname, labels - olabels, 432254402Serwin olabels, &common); 433254402Serwin } else { 434254402Serwin labels = dns_name_countlabels(&nsec.next); 435254402Serwin dns_name_getlabelsequence(&nsec.next, labels - nlabels, 436254402Serwin nlabels, &common); 437254402Serwin } 438254402Serwin result = dns_name_concatenate(dns_wildcardname, &common, 439254402Serwin wild, NULL); 440254402Serwin if (result != ISC_R_SUCCESS) { 441254402Serwin dns_rdata_freestruct(&nsec); 442254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), 443254402Serwin "failure generating wildcard name"); 444254402Serwin return (result); 445254402Serwin } 446254402Serwin } 447254402Serwin dns_rdata_freestruct(&nsec); 448254402Serwin (*logit)(arg, ISC_LOG_DEBUG(3), "nsec range ok"); 449254402Serwin *exists = ISC_FALSE; 450254402Serwin return (ISC_R_SUCCESS); 451254402Serwin} 452