diff options
Diffstat (limited to 'validator/val_nsec.c')
| -rw-r--r-- | validator/val_nsec.c | 603 |
1 files changed, 603 insertions, 0 deletions
diff --git a/validator/val_nsec.c b/validator/val_nsec.c new file mode 100644 index 000000000000..8bda8dabc937 --- /dev/null +++ b/validator/val_nsec.c @@ -0,0 +1,603 @@ +/* + * validator/val_nsec.c - validator NSEC denial of existance functions. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file + * + * This file contains helper functions for the validator module. + * The functions help with NSEC checking, the different NSEC proofs + * for denial of existance, and proofs for presence of types. + */ +#include "config.h" +#include <ldns/packet.h> +#include "validator/val_nsec.h" +#include "validator/val_utils.h" +#include "util/data/msgreply.h" +#include "util/data/dname.h" +#include "util/net_help.h" +#include "util/module.h" +#include "services/cache/rrset.h" + +/** get ttl of rrset */ +static uint32_t +rrset_get_ttl(struct ub_packed_rrset_key* k) +{ + struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data; + return d->ttl; +} + +int +nsecbitmap_has_type_rdata(uint8_t* bitmap, size_t len, uint16_t type) +{ + /* Check type present in NSEC typemap with bitmap arg */ + /* bitmasks for determining type-lowerbits presence */ + uint8_t masks[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; + uint8_t type_window = type>>8; + uint8_t type_low = type&0xff; + uint8_t win, winlen; + /* read each of the type bitmap windows and see if the searched + * type is amongst it */ + while(len > 0) { + if(len < 3) /* bad window, at least window# winlen bitmap */ + return 0; + win = *bitmap++; + winlen = *bitmap++; + len -= 2; + if(len < winlen || winlen < 1 || winlen > 32) + return 0; /* bad window length */ + if(win == type_window) { + /* search window bitmap for the correct byte */ + /* mybyte is 0 if we need the first byte */ + size_t mybyte = type_low>>3; + if(winlen <= mybyte) + return 0; /* window too short */ + return (int)(bitmap[mybyte] & masks[type_low&0x7]); + } else { + /* not the window we are looking for */ + bitmap += winlen; + len -= winlen; + } + } + /* end of bitmap reached, no type found */ + return 0; +} + +int +nsec_has_type(struct ub_packed_rrset_key* nsec, uint16_t type) +{ + struct packed_rrset_data* d = (struct packed_rrset_data*)nsec-> + entry.data; + size_t len; + if(!d || d->count == 0 || d->rr_len[0] < 2+1) + return 0; + len = dname_valid(d->rr_data[0]+2, d->rr_len[0]-2); + if(!len) + return 0; + return nsecbitmap_has_type_rdata(d->rr_data[0]+2+len, + d->rr_len[0]-2-len, type); +} + +/** + * Get next owner name from nsec record + * @param nsec: the nsec RRset. + * If there are multiple RRs, then this will only return one of them. + * @param nm: the next name is returned. + * @param ln: length of nm is returned. + * @return false on a bad NSEC RR (too short, malformed dname). + */ +static int +nsec_get_next(struct ub_packed_rrset_key* nsec, uint8_t** nm, size_t* ln) +{ + struct packed_rrset_data* d = (struct packed_rrset_data*)nsec-> + entry.data; + if(!d || d->count == 0 || d->rr_len[0] < 2+1) { + *nm = 0; + *ln = 0; + return 0; + } + *nm = d->rr_data[0]+2; + *ln = dname_valid(*nm, d->rr_len[0]-2); + if(!*ln) { + *nm = 0; + *ln = 0; + return 0; + } + return 1; +} + +/** + * For an NSEC that matches the DS queried for, check absence of DS type. + * + * @param nsec: NSEC for proof, must be trusted. + * @param qinfo: what is queried for. + * @return if secure the nsec proves that no DS is present, or + * insecure if it proves it is not a delegation point. + * or bogus if something was wrong. + */ +static enum sec_status +val_nsec_proves_no_ds(struct ub_packed_rrset_key* nsec, + struct query_info* qinfo) +{ + log_assert(qinfo->qtype == LDNS_RR_TYPE_DS); + log_assert(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC); + + if(nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && qinfo->qname_len != 1) { + /* SOA present means that this is the NSEC from the child, + * not the parent (so it is the wrong one). */ + return sec_status_bogus; + } + if(nsec_has_type(nsec, LDNS_RR_TYPE_DS)) { + /* DS present means that there should have been a positive + * response to the DS query, so there is something wrong. */ + return sec_status_bogus; + } + + if(!nsec_has_type(nsec, LDNS_RR_TYPE_NS)) { + /* If there is no NS at this point at all, then this + * doesn't prove anything one way or the other. */ + return sec_status_insecure; + } + /* Otherwise, this proves no DS. */ + return sec_status_secure; +} + +/** check security status from cache or verify rrset, returns true if secure */ +static int +nsec_verify_rrset(struct module_env* env, struct val_env* ve, + struct ub_packed_rrset_key* nsec, struct key_entry_key* kkey, + char** reason) +{ + struct packed_rrset_data* d = (struct packed_rrset_data*) + nsec->entry.data; + if(d->security == sec_status_secure) + return 1; + rrset_check_sec_status(env->rrset_cache, nsec, *env->now); + if(d->security == sec_status_secure) + return 1; + d->security = val_verify_rrset_entry(env, ve, nsec, kkey, reason); + if(d->security == sec_status_secure) { + rrset_update_sec_status(env->rrset_cache, nsec, *env->now); + return 1; + } + return 0; +} + +enum sec_status +val_nsec_prove_nodata_dsreply(struct module_env* env, struct val_env* ve, + struct query_info* qinfo, struct reply_info* rep, + struct key_entry_key* kkey, uint32_t* proof_ttl, char** reason) +{ + struct ub_packed_rrset_key* nsec = reply_find_rrset_section_ns( + rep, qinfo->qname, qinfo->qname_len, LDNS_RR_TYPE_NSEC, + qinfo->qclass); + enum sec_status sec; + size_t i; + uint8_t* wc = NULL, *ce = NULL; + int valid_nsec = 0; + struct ub_packed_rrset_key* wc_nsec = NULL; + + /* If we have a NSEC at the same name, it must prove one + * of two things + * -- + * 1) this is a delegation point and there is no DS + * 2) this is not a delegation point */ + if(nsec) { + if(!nsec_verify_rrset(env, ve, nsec, kkey, reason)) { + verbose(VERB_ALGO, "NSEC RRset for the " + "referral did not verify."); + return sec_status_bogus; + } + sec = val_nsec_proves_no_ds(nsec, qinfo); + if(sec == sec_status_bogus) { + /* something was wrong. */ + *reason = "NSEC does not prove absence of DS"; + return sec; + } else if(sec == sec_status_insecure) { + /* this wasn't a delegation point. */ + return sec; + } else if(sec == sec_status_secure) { + /* this proved no DS. */ + *proof_ttl = ub_packed_rrset_ttl(nsec); + return sec; + } + /* if unchecked, fall through to next proof */ + } + + /* Otherwise, there is no NSEC at qname. This could be an ENT. + * (ENT=empty non terminal). If not, this is broken. */ + + /* verify NSEC rrsets in auth section */ + for(i=rep->an_numrrsets; i < rep->an_numrrsets+rep->ns_numrrsets; + i++) { + if(rep->rrsets[i]->rk.type != htons(LDNS_RR_TYPE_NSEC)) + continue; + if(!nsec_verify_rrset(env, ve, rep->rrsets[i], kkey, reason)) { + verbose(VERB_ALGO, "NSEC for empty non-terminal " + "did not verify."); + return sec_status_bogus; + } + if(nsec_proves_nodata(rep->rrsets[i], qinfo, &wc)) { + verbose(VERB_ALGO, "NSEC for empty non-terminal " + "proved no DS."); + *proof_ttl = rrset_get_ttl(rep->rrsets[i]); + if(wc && dname_is_wild(rep->rrsets[i]->rk.dname)) + wc_nsec = rep->rrsets[i]; + valid_nsec = 1; + } + if(val_nsec_proves_name_error(rep->rrsets[i], qinfo->qname)) { + ce = nsec_closest_encloser(qinfo->qname, + rep->rrsets[i]); + } + } + if(wc && !ce) + valid_nsec = 0; + else if(wc && ce) { + /* ce and wc must match */ + if(query_dname_compare(wc, ce) != 0) + valid_nsec = 0; + else if(!wc_nsec) + valid_nsec = 0; + } + if(valid_nsec) { + if(wc) { + /* check if this is a delegation */ + *reason = "NSEC for wildcard does not prove absence of DS"; + return val_nsec_proves_no_ds(wc_nsec, qinfo); + } + /* valid nsec proves empty nonterminal */ + return sec_status_insecure; + } + + /* NSEC proof did not conlusively point to DS or no DS */ + return sec_status_unchecked; +} + +int nsec_proves_nodata(struct ub_packed_rrset_key* nsec, + struct query_info* qinfo, uint8_t** wc) +{ + log_assert(wc); + if(query_dname_compare(nsec->rk.dname, qinfo->qname) != 0) { + uint8_t* nm; + size_t ln; + + /* empty-non-terminal checking. + * Done before wildcard, because this is an exact match, + * and would prevent a wildcard from matching. */ + + /* If the nsec is proving that qname is an ENT, the nsec owner + * will be less than qname, and the next name will be a child + * domain of the qname. */ + if(!nsec_get_next(nsec, &nm, &ln)) + return 0; /* bad nsec */ + if(dname_strict_subdomain_c(nm, qinfo->qname) && + dname_canonical_compare(nsec->rk.dname, + qinfo->qname) < 0) { + return 1; /* proves ENT */ + } + + /* wildcard checking. */ + + /* If this is a wildcard NSEC, make sure that a) it was + * possible to have generated qname from the wildcard and + * b) the type map does not contain qtype. Note that this + * does NOT prove that this wildcard was the applicable + * wildcard. */ + if(dname_is_wild(nsec->rk.dname)) { + /* the purported closest encloser. */ + uint8_t* ce = nsec->rk.dname; + size_t ce_len = nsec->rk.dname_len; + dname_remove_label(&ce, &ce_len); + + /* The qname must be a strict subdomain of the + * closest encloser, for the wildcard to apply + */ + if(dname_strict_subdomain_c(qinfo->qname, ce)) { + /* here we have a matching NSEC for the qname, + * perform matching NSEC checks */ + if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) { + /* should have gotten the wildcard CNAME */ + return 0; + } + if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) && + !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) { + /* wrong parentside (wildcard) NSEC used */ + return 0; + } + if(nsec_has_type(nsec, qinfo->qtype)) { + return 0; + } + *wc = ce; + return 1; + } + } + + /* Otherwise, this NSEC does not prove ENT and is not a + * wildcard, so it does not prove NODATA. */ + return 0; + } + + /* If the qtype exists, then we should have gotten it. */ + if(nsec_has_type(nsec, qinfo->qtype)) { + return 0; + } + + /* if the name is a CNAME node, then we should have gotten the CNAME*/ + if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) { + return 0; + } + + /* If an NS set exists at this name, and NOT a SOA (so this is a + * zone cut, not a zone apex), then we should have gotten a + * referral (or we just got the wrong NSEC). + * The reverse of this check is used when qtype is DS, since that + * must use the NSEC from above the zone cut. */ + if(qinfo->qtype != LDNS_RR_TYPE_DS && + nsec_has_type(nsec, LDNS_RR_TYPE_NS) && + !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) { + return 0; + } else if(qinfo->qtype == LDNS_RR_TYPE_DS && + nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && + !dname_is_root(qinfo->qname)) { + return 0; + } + + return 1; +} + +int +val_nsec_proves_name_error(struct ub_packed_rrset_key* nsec, uint8_t* qname) +{ + uint8_t* owner = nsec->rk.dname; + uint8_t* next; + size_t nlen; + if(!nsec_get_next(nsec, &next, &nlen)) + return 0; + + /* If NSEC owner == qname, then this NSEC proves that qname exists. */ + if(query_dname_compare(qname, owner) == 0) { + return 0; + } + + /* If NSEC is a parent of qname, we need to check the type map + * If the parent name has a DNAME or is a delegation point, then + * this NSEC is being misused. */ + if(dname_subdomain_c(qname, owner) && + (nsec_has_type(nsec, LDNS_RR_TYPE_DNAME) || + (nsec_has_type(nsec, LDNS_RR_TYPE_NS) + && !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) + )) { + return 0; + } + + if(query_dname_compare(owner, next) == 0) { + /* this nsec is the only nsec */ + /* zone.name NSEC zone.name, disproves everything else */ + /* but only for subdomains of that zone */ + if(dname_strict_subdomain_c(qname, next)) + return 1; + } + else if(dname_canonical_compare(owner, next) > 0) { + /* this is the last nsec, ....(bigger) NSEC zonename(smaller) */ + /* the names after the last (owner) name do not exist + * there are no names before the zone name in the zone + * but the qname must be a subdomain of the zone name(next). */ + if(dname_canonical_compare(owner, qname) < 0 && + dname_strict_subdomain_c(qname, next)) + return 1; + } else { + /* regular NSEC, (smaller) NSEC (larger) */ + if(dname_canonical_compare(owner, qname) < 0 && + dname_canonical_compare(qname, next) < 0) { + return 1; + } + } + return 0; +} + +int val_nsec_proves_insecuredelegation(struct ub_packed_rrset_key* nsec, + struct query_info* qinfo) +{ + if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) && + !nsec_has_type(nsec, LDNS_RR_TYPE_DS) && + !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) { + /* see if nsec signals an insecure delegation */ + if(qinfo->qtype == LDNS_RR_TYPE_DS) { + /* if type is DS and qname is equal to nsec, then it + * is an exact match nsec, result not insecure */ + if(dname_strict_subdomain_c(qinfo->qname, + nsec->rk.dname)) + return 1; + } else { + if(dname_subdomain_c(qinfo->qname, nsec->rk.dname)) + return 1; + } + } + return 0; +} + +uint8_t* +nsec_closest_encloser(uint8_t* qname, struct ub_packed_rrset_key* nsec) +{ + uint8_t* next; + size_t nlen; + uint8_t* common1, *common2; + if(!nsec_get_next(nsec, &next, &nlen)) + return NULL; + /* longest common with owner or next name */ + common1 = dname_get_shared_topdomain(nsec->rk.dname, qname); + common2 = dname_get_shared_topdomain(next, qname); + if(dname_count_labels(common1) > dname_count_labels(common2)) + return common1; + return common2; +} + +int val_nsec_proves_positive_wildcard(struct ub_packed_rrset_key* nsec, + struct query_info* qinf, uint8_t* wc) +{ + uint8_t* ce; + /* 1) prove that qname doesn't exist and + * 2) that the correct wildcard was used + * nsec has been verified already. */ + if(!val_nsec_proves_name_error(nsec, qinf->qname)) + return 0; + /* check wildcard name */ + ce = nsec_closest_encloser(qinf->qname, nsec); + if(!ce) + return 0; + if(query_dname_compare(wc, ce) != 0) { + return 0; + } + return 1; +} + +int +val_nsec_proves_no_wc(struct ub_packed_rrset_key* nsec, uint8_t* qname, + size_t qnamelen) +{ + /* Determine if a NSEC record proves the non-existence of a + * wildcard that could have produced qname. */ + int labs; + int i; + uint8_t* ce = nsec_closest_encloser(qname, nsec); + uint8_t* strip; + size_t striplen; + uint8_t buf[LDNS_MAX_DOMAINLEN+3]; + if(!ce) + return 0; + /* we can subtract the closest encloser count - since that is the + * largest shared topdomain with owner and next NSEC name, + * because the NSEC is no proof for names shorter than the owner + * and next names. */ + labs = dname_count_labels(qname) - dname_count_labels(ce); + + for(i=labs; i>0; i--) { + /* i is number of labels to strip off qname, prepend * wild */ + strip = qname; + striplen = qnamelen; + dname_remove_labels(&strip, &striplen, i); + if(striplen > LDNS_MAX_DOMAINLEN-2) + continue; /* too long to prepend wildcard */ + buf[0] = 1; + buf[1] = (uint8_t)'*'; + memmove(buf+2, strip, striplen); + if(val_nsec_proves_name_error(nsec, buf)) { + return 1; + } + } + return 0; +} + +/** + * Find shared topdomain that exists + */ +static void +dlv_topdomain(struct ub_packed_rrset_key* nsec, uint8_t* qname, + uint8_t** nm, size_t* nm_len) +{ + /* make sure reply is part of nm */ + /* take shared topdomain with left of NSEC. */ + + /* because, if empty nonterminal, then right is subdomain of qname. + * and any shared topdomain would be empty nonterminals. + * + * If nxdomain, then the right is bigger, and could have an + * interesting shared topdomain, but if it does have one, it is + * an empty nonterminal. An empty nonterminal shared with the left + * one. */ + int n; + uint8_t* common = dname_get_shared_topdomain(qname, nsec->rk.dname); + n = dname_count_labels(*nm) - dname_count_labels(common); + dname_remove_labels(nm, nm_len, n); +} + +int val_nsec_check_dlv(struct query_info* qinfo, + struct reply_info* rep, uint8_t** nm, size_t* nm_len) +{ + uint8_t* next; + size_t i, nlen; + int c; + /* we should now have a NOERROR/NODATA or NXDOMAIN message */ + if(rep->an_numrrsets != 0) { + return 0; + } + /* is this NOERROR ? */ + if(FLAGS_GET_RCODE(rep->flags) == LDNS_RCODE_NOERROR) { + /* it can be a plain NSEC match - go up one more level. */ + /* or its an empty nonterminal - go up to nonempty level */ + for(i=0; i<rep->ns_numrrsets; i++) { + if(htons(rep->rrsets[i]->rk.type)!=LDNS_RR_TYPE_NSEC || + !nsec_get_next(rep->rrsets[i], &next, &nlen)) + continue; + c = dname_canonical_compare( + rep->rrsets[i]->rk.dname, qinfo->qname); + if(c == 0) { + /* plain match */ + if(nsec_has_type(rep->rrsets[i], + LDNS_RR_TYPE_DLV)) + return 0; + dname_remove_label(nm, nm_len); + return 1; + } else if(c < 0 && + dname_strict_subdomain_c(next, qinfo->qname)) { + /* ENT */ + dlv_topdomain(rep->rrsets[i], qinfo->qname, + nm, nm_len); + return 1; + } + } + return 0; + } + + /* is this NXDOMAIN ? */ + if(FLAGS_GET_RCODE(rep->flags) == LDNS_RCODE_NXDOMAIN) { + /* find the qname denial NSEC record. It can tell us + * a closest encloser name; or that we not need bother */ + for(i=0; i<rep->ns_numrrsets; i++) { + if(htons(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC) + continue; + if(val_nsec_proves_name_error(rep->rrsets[i], + qinfo->qname)) { + log_nametypeclass(VERB_ALGO, "topdomain on", + rep->rrsets[i]->rk.dname, + ntohs(rep->rrsets[i]->rk.type), 0); + dlv_topdomain(rep->rrsets[i], qinfo->qname, + nm, nm_len); + return 1; + } + } + return 0; + } + return 0; +} |