1 /*
2 * validator/val_nsec.c - validator NSEC denial of existence functions.
3 *
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
18 *
19 * Neither the name of the NLNET LABS nor the names of its contributors may
20 * be used to endorse or promote products derived from this software without
21 * specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 /**
37 * \file
38 *
39 * This file contains helper functions for the validator module.
40 * The functions help with NSEC checking, the different NSEC proofs
41 * for denial of existence, and proofs for presence of types.
42 */
43 #include "config.h"
44 #include "validator/val_nsec.h"
45 #include "validator/val_utils.h"
46 #include "util/data/msgreply.h"
47 #include "util/data/dname.h"
48 #include "util/net_help.h"
49 #include "util/module.h"
50 #include "services/cache/rrset.h"
51
52 /** get ttl of rrset */
53 static uint32_t
rrset_get_ttl(struct ub_packed_rrset_key * k)54 rrset_get_ttl(struct ub_packed_rrset_key* k)
55 {
56 struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
57 return d->ttl;
58 }
59
60 int
nsecbitmap_has_type_rdata(uint8_t * bitmap,size_t len,uint16_t type)61 nsecbitmap_has_type_rdata(uint8_t* bitmap, size_t len, uint16_t type)
62 {
63 /* Check type present in NSEC typemap with bitmap arg */
64 /* bitmasks for determining type-lowerbits presence */
65 uint8_t masks[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
66 uint8_t type_window = type>>8;
67 uint8_t type_low = type&0xff;
68 uint8_t win, winlen;
69 /* read each of the type bitmap windows and see if the searched
70 * type is amongst it */
71 while(len > 0) {
72 if(len < 3) /* bad window, at least window# winlen bitmap */
73 return 0;
74 win = *bitmap++;
75 winlen = *bitmap++;
76 len -= 2;
77 if(len < winlen || winlen < 1 || winlen > 32)
78 return 0; /* bad window length */
79 if(win == type_window) {
80 /* search window bitmap for the correct byte */
81 /* mybyte is 0 if we need the first byte */
82 size_t mybyte = type_low>>3;
83 if(winlen <= mybyte)
84 return 0; /* window too short */
85 return (int)(bitmap[mybyte] & masks[type_low&0x7]);
86 } else {
87 /* not the window we are looking for */
88 bitmap += winlen;
89 len -= winlen;
90 }
91 }
92 /* end of bitmap reached, no type found */
93 return 0;
94 }
95
96 int
nsec_has_type(struct ub_packed_rrset_key * nsec,uint16_t type)97 nsec_has_type(struct ub_packed_rrset_key* nsec, uint16_t type)
98 {
99 struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
100 entry.data;
101 size_t len;
102 if(!d || d->count == 0 || d->rr_len[0] < 2+1)
103 return 0;
104 len = dname_valid(d->rr_data[0]+2, d->rr_len[0]-2);
105 if(!len)
106 return 0;
107 return nsecbitmap_has_type_rdata(d->rr_data[0]+2+len,
108 d->rr_len[0]-2-len, type);
109 }
110
111 /**
112 * Get next owner name from nsec record
113 * @param nsec: the nsec RRset.
114 * If there are multiple RRs, then this will only return one of them.
115 * @param nm: the next name is returned.
116 * @param ln: length of nm is returned.
117 * @return false on a bad NSEC RR (too short, malformed dname).
118 */
119 static int
nsec_get_next(struct ub_packed_rrset_key * nsec,uint8_t ** nm,size_t * ln)120 nsec_get_next(struct ub_packed_rrset_key* nsec, uint8_t** nm, size_t* ln)
121 {
122 struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
123 entry.data;
124 if(!d || d->count == 0 || d->rr_len[0] < 2+1) {
125 *nm = 0;
126 *ln = 0;
127 return 0;
128 }
129 *nm = d->rr_data[0]+2;
130 *ln = dname_valid(*nm, d->rr_len[0]-2);
131 if(!*ln) {
132 *nm = 0;
133 *ln = 0;
134 return 0;
135 }
136 return 1;
137 }
138
139 /**
140 * For an NSEC that matches the DS queried for, check absence of DS type.
141 *
142 * @param nsec: NSEC for proof, must be trusted.
143 * @param qinfo: what is queried for.
144 * @return if secure the nsec proves that no DS is present, or
145 * insecure if it proves it is not a delegation point.
146 * or bogus if something was wrong.
147 */
148 static enum sec_status
val_nsec_proves_no_ds(struct ub_packed_rrset_key * nsec,struct query_info * qinfo)149 val_nsec_proves_no_ds(struct ub_packed_rrset_key* nsec,
150 struct query_info* qinfo)
151 {
152 log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);
153 log_assert(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC);
154
155 if(nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && qinfo->qname_len != 1) {
156 /* SOA present means that this is the NSEC from the child,
157 * not the parent (so it is the wrong one). */
158 return sec_status_bogus;
159 }
160 if(nsec_has_type(nsec, LDNS_RR_TYPE_DS)) {
161 /* DS present means that there should have been a positive
162 * response to the DS query, so there is something wrong. */
163 return sec_status_bogus;
164 }
165
166 if(!nsec_has_type(nsec, LDNS_RR_TYPE_NS)) {
167 /* If there is no NS at this point at all, then this
168 * doesn't prove anything one way or the other. */
169 return sec_status_insecure;
170 }
171 /* Otherwise, this proves no DS. */
172 return sec_status_secure;
173 }
174
175 /** check security status from cache or verify rrset, returns true if secure */
176 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,sldns_ede_code * reason_bogus,struct module_qstate * qstate)177 nsec_verify_rrset(struct module_env* env, struct val_env* ve,
178 struct ub_packed_rrset_key* nsec, struct key_entry_key* kkey,
179 char** reason, sldns_ede_code* reason_bogus,
180 struct module_qstate* qstate)
181 {
182 struct packed_rrset_data* d = (struct packed_rrset_data*)
183 nsec->entry.data;
184 int verified = 0;
185 if(!d) return 0;
186 if(d->security == sec_status_secure)
187 return 1;
188 rrset_check_sec_status(env->rrset_cache, nsec, *env->now);
189 if(d->security == sec_status_secure)
190 return 1;
191 d->security = val_verify_rrset_entry(env, ve, nsec, kkey, reason,
192 reason_bogus, LDNS_SECTION_AUTHORITY, qstate, &verified);
193 if(d->security == sec_status_secure) {
194 rrset_update_sec_status(env->rrset_cache, nsec, *env->now);
195 return 1;
196 }
197 return 0;
198 }
199
200 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,time_t * proof_ttl,char ** reason,sldns_ede_code * reason_bogus,struct module_qstate * qstate)201 val_nsec_prove_nodata_dsreply(struct module_env* env, struct val_env* ve,
202 struct query_info* qinfo, struct reply_info* rep,
203 struct key_entry_key* kkey, time_t* proof_ttl, char** reason,
204 sldns_ede_code* reason_bogus, struct module_qstate* qstate)
205 {
206 struct ub_packed_rrset_key* nsec = reply_find_rrset_section_ns(
207 rep, qinfo->qname, qinfo->qname_len, LDNS_RR_TYPE_NSEC,
208 qinfo->qclass);
209 enum sec_status sec;
210 size_t i;
211 uint8_t* wc = NULL, *ce = NULL;
212 int valid_nsec = 0;
213 struct ub_packed_rrset_key* wc_nsec = NULL;
214
215 /* If we have a NSEC at the same name, it must prove one
216 * of two things
217 * --
218 * 1) this is a delegation point and there is no DS
219 * 2) this is not a delegation point */
220 if(nsec) {
221 if(!nsec_verify_rrset(env, ve, nsec, kkey, reason,
222 reason_bogus, qstate)) {
223 verbose(VERB_ALGO, "NSEC RRset for the "
224 "referral did not verify.");
225 return sec_status_bogus;
226 }
227 sec = val_nsec_proves_no_ds(nsec, qinfo);
228 if(sec == sec_status_bogus) {
229 /* something was wrong. */
230 *reason = "NSEC does not prove absence of DS";
231 *reason_bogus = LDNS_EDE_DNSSEC_BOGUS;
232 return sec;
233 } else if(sec == sec_status_insecure) {
234 /* this wasn't a delegation point. */
235 return sec;
236 } else if(sec == sec_status_secure) {
237 /* this proved no DS. */
238 *proof_ttl = ub_packed_rrset_ttl(nsec);
239 return sec;
240 }
241 /* if unchecked, fall through to next proof */
242 }
243
244 /* Otherwise, there is no NSEC at qname. This could be an ENT.
245 * (ENT=empty non terminal). If not, this is broken. */
246
247 /* verify NSEC rrsets in auth section */
248 for(i=rep->an_numrrsets; i < rep->an_numrrsets+rep->ns_numrrsets;
249 i++) {
250 if(rep->rrsets[i]->rk.type != htons(LDNS_RR_TYPE_NSEC))
251 continue;
252 if(!nsec_verify_rrset(env, ve, rep->rrsets[i], kkey, reason,
253 reason_bogus, qstate)) {
254 verbose(VERB_ALGO, "NSEC for empty non-terminal "
255 "did not verify.");
256 *reason = "NSEC for empty non-terminal "
257 "did not verify.";
258 return sec_status_bogus;
259 }
260 if(nsec_proves_nodata(rep->rrsets[i], qinfo, &wc)) {
261 verbose(VERB_ALGO, "NSEC for empty non-terminal "
262 "proved no DS.");
263 *proof_ttl = rrset_get_ttl(rep->rrsets[i]);
264 if(wc && dname_is_wild(rep->rrsets[i]->rk.dname))
265 wc_nsec = rep->rrsets[i];
266 valid_nsec = 1;
267 }
268 if(val_nsec_proves_name_error(rep->rrsets[i], qinfo->qname)) {
269 ce = nsec_closest_encloser(qinfo->qname,
270 rep->rrsets[i]);
271 }
272 }
273 if(wc && !ce)
274 valid_nsec = 0;
275 else if(wc && ce) {
276 /* ce and wc must match */
277 if(query_dname_compare(wc, ce) != 0)
278 valid_nsec = 0;
279 else if(!wc_nsec)
280 valid_nsec = 0;
281 }
282 if(valid_nsec) {
283 if(wc) {
284 /* check if this is a delegation */
285 *reason = "NSEC for wildcard does not prove absence of DS";
286 return val_nsec_proves_no_ds(wc_nsec, qinfo);
287 }
288 /* valid nsec proves empty nonterminal */
289 return sec_status_insecure;
290 }
291
292 /* NSEC proof did not conclusively point to DS or no DS */
293 return sec_status_unchecked;
294 }
295
nsec_proves_nodata(struct ub_packed_rrset_key * nsec,struct query_info * qinfo,uint8_t ** wc)296 int nsec_proves_nodata(struct ub_packed_rrset_key* nsec,
297 struct query_info* qinfo, uint8_t** wc)
298 {
299 log_assert(wc);
300 if(query_dname_compare(nsec->rk.dname, qinfo->qname) != 0) {
301 uint8_t* nm;
302 size_t ln;
303
304 /* empty-non-terminal checking.
305 * Done before wildcard, because this is an exact match,
306 * and would prevent a wildcard from matching. */
307
308 /* If the nsec is proving that qname is an ENT, the nsec owner
309 * will be less than qname, and the next name will be a child
310 * domain of the qname. */
311 if(!nsec_get_next(nsec, &nm, &ln))
312 return 0; /* bad nsec */
313 if(dname_strict_subdomain_c(nm, qinfo->qname) &&
314 dname_canonical_compare(nsec->rk.dname,
315 qinfo->qname) < 0) {
316 return 1; /* proves ENT */
317 }
318
319 /* wildcard checking. */
320
321 /* If this is a wildcard NSEC, make sure that a) it was
322 * possible to have generated qname from the wildcard and
323 * b) the type map does not contain qtype. Note that this
324 * does NOT prove that this wildcard was the applicable
325 * wildcard. */
326 if(dname_is_wild(nsec->rk.dname)) {
327 /* the purported closest encloser. */
328 uint8_t* ce = nsec->rk.dname;
329 size_t ce_len = nsec->rk.dname_len;
330 dname_remove_label(&ce, &ce_len);
331
332 /* The qname must be a strict subdomain of the
333 * closest encloser, for the wildcard to apply
334 */
335 if(dname_strict_subdomain_c(qinfo->qname, ce)) {
336 /* here we have a matching NSEC for the qname,
337 * perform matching NSEC checks */
338 if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {
339 /* should have gotten the wildcard CNAME */
340 return 0;
341 }
342 if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&
343 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
344 /* wrong parentside (wildcard) NSEC used */
345 return 0;
346 }
347 if(nsec_has_type(nsec, qinfo->qtype)) {
348 return 0;
349 }
350 *wc = ce;
351 return 1;
352 }
353 } else {
354 /* See if the next owner name covers a wildcard
355 * empty non-terminal. */
356 while (dname_canonical_compare(nsec->rk.dname, nm) < 0) {
357 /* wildcard does not apply if qname below
358 * the name that exists under the '*' */
359 if (dname_subdomain_c(qinfo->qname, nm))
360 break;
361 /* but if it is a wildcard and qname is below
362 * it, then the wildcard applies. The wildcard
363 * is an empty nonterminal. nodata proven. */
364 if (dname_is_wild(nm)) {
365 size_t ce_len = ln;
366 uint8_t* ce = nm;
367 dname_remove_label(&ce, &ce_len);
368 if(dname_strict_subdomain_c(qinfo->qname, ce)) {
369 *wc = ce;
370 return 1;
371 }
372 }
373 dname_remove_label(&nm, &ln);
374 }
375 }
376
377 /* Otherwise, this NSEC does not prove ENT and is not a
378 * wildcard, so it does not prove NODATA. */
379 return 0;
380 }
381
382 /* If the qtype exists, then we should have gotten it. */
383 if(nsec_has_type(nsec, qinfo->qtype)) {
384 return 0;
385 }
386
387 /* if the name is a CNAME node, then we should have gotten the CNAME*/
388 if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {
389 return 0;
390 }
391
392 /* If an NS set exists at this name, and NOT a SOA (so this is a
393 * zone cut, not a zone apex), then we should have gotten a
394 * referral (or we just got the wrong NSEC).
395 * The reverse of this check is used when qtype is DS, since that
396 * must use the NSEC from above the zone cut. */
397 if(qinfo->qtype != LDNS_RR_TYPE_DS &&
398 nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&
399 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
400 return 0;
401 } else if(qinfo->qtype == LDNS_RR_TYPE_DS &&
402 nsec_has_type(nsec, LDNS_RR_TYPE_SOA) &&
403 !dname_is_root(qinfo->qname)) {
404 return 0;
405 }
406
407 return 1;
408 }
409
410 int
val_nsec_proves_name_error(struct ub_packed_rrset_key * nsec,uint8_t * qname)411 val_nsec_proves_name_error(struct ub_packed_rrset_key* nsec, uint8_t* qname)
412 {
413 uint8_t* owner = nsec->rk.dname;
414 uint8_t* next;
415 size_t nlen;
416 if(!nsec_get_next(nsec, &next, &nlen))
417 return 0;
418
419 /* If NSEC owner == qname, then this NSEC proves that qname exists. */
420 if(query_dname_compare(qname, owner) == 0) {
421 return 0;
422 }
423
424 /* If NSEC is a parent of qname, we need to check the type map
425 * If the parent name has a DNAME or is a delegation point, then
426 * this NSEC is being misused. */
427 if(dname_subdomain_c(qname, owner) &&
428 (nsec_has_type(nsec, LDNS_RR_TYPE_DNAME) ||
429 (nsec_has_type(nsec, LDNS_RR_TYPE_NS)
430 && !nsec_has_type(nsec, LDNS_RR_TYPE_SOA))
431 )) {
432 return 0;
433 }
434
435 if(query_dname_compare(owner, next) == 0) {
436 /* this nsec is the only nsec */
437 /* zone.name NSEC zone.name, disproves everything else */
438 /* but only for subdomains of that zone */
439 if(dname_strict_subdomain_c(qname, next))
440 return 1;
441 }
442 else if(dname_canonical_compare(owner, next) > 0) {
443 /* this is the last nsec, ....(bigger) NSEC zonename(smaller) */
444 /* the names after the last (owner) name do not exist
445 * there are no names before the zone name in the zone
446 * but the qname must be a subdomain of the zone name(next). */
447 if(dname_canonical_compare(owner, qname) < 0 &&
448 dname_strict_subdomain_c(qname, next))
449 return 1;
450 } else {
451 /* regular NSEC, (smaller) NSEC (larger) */
452 if(dname_canonical_compare(owner, qname) < 0 &&
453 dname_canonical_compare(qname, next) < 0) {
454 return 1;
455 }
456 }
457 return 0;
458 }
459
val_nsec_proves_insecuredelegation(struct ub_packed_rrset_key * nsec,struct query_info * qinfo)460 int val_nsec_proves_insecuredelegation(struct ub_packed_rrset_key* nsec,
461 struct query_info* qinfo)
462 {
463 if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&
464 !nsec_has_type(nsec, LDNS_RR_TYPE_DS) &&
465 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
466 /* see if nsec signals an insecure delegation */
467 if(qinfo->qtype == LDNS_RR_TYPE_DS) {
468 /* if type is DS and qname is equal to nsec, then it
469 * is an exact match nsec, result not insecure */
470 if(dname_strict_subdomain_c(qinfo->qname,
471 nsec->rk.dname))
472 return 1;
473 } else {
474 if(dname_subdomain_c(qinfo->qname, nsec->rk.dname))
475 return 1;
476 }
477 }
478 return 0;
479 }
480
481 uint8_t*
nsec_closest_encloser(uint8_t * qname,struct ub_packed_rrset_key * nsec)482 nsec_closest_encloser(uint8_t* qname, struct ub_packed_rrset_key* nsec)
483 {
484 uint8_t* next;
485 size_t nlen;
486 uint8_t* common1, *common2;
487 if(!nsec_get_next(nsec, &next, &nlen))
488 return NULL;
489 /* longest common with owner or next name */
490 common1 = dname_get_shared_topdomain(nsec->rk.dname, qname);
491 common2 = dname_get_shared_topdomain(next, qname);
492 if(dname_count_labels(common1) > dname_count_labels(common2))
493 return common1;
494 return common2;
495 }
496
val_nsec_proves_positive_wildcard(struct ub_packed_rrset_key * nsec,struct query_info * qinf,uint8_t * wc)497 int val_nsec_proves_positive_wildcard(struct ub_packed_rrset_key* nsec,
498 struct query_info* qinf, uint8_t* wc)
499 {
500 uint8_t* ce;
501 /* 1) prove that qname doesn't exist and
502 * 2) that the correct wildcard was used
503 * nsec has been verified already. */
504 if(!val_nsec_proves_name_error(nsec, qinf->qname))
505 return 0;
506 /* check wildcard name */
507 ce = nsec_closest_encloser(qinf->qname, nsec);
508 if(!ce)
509 return 0;
510 if(query_dname_compare(wc, ce) != 0) {
511 return 0;
512 }
513 return 1;
514 }
515
516 int
val_nsec_proves_no_wc(struct ub_packed_rrset_key * nsec,uint8_t * qname,size_t qnamelen)517 val_nsec_proves_no_wc(struct ub_packed_rrset_key* nsec, uint8_t* qname,
518 size_t qnamelen)
519 {
520 /* Determine if a NSEC record proves the non-existence of a
521 * wildcard that could have produced qname. */
522 int labs;
523 uint8_t* ce = nsec_closest_encloser(qname, nsec);
524 uint8_t* strip;
525 size_t striplen;
526 uint8_t buf[LDNS_MAX_DOMAINLEN+3];
527 if(!ce)
528 return 0;
529 /* we can subtract the closest encloser count - since that is the
530 * largest shared topdomain with owner and next NSEC name,
531 * because the NSEC is no proof for names shorter than the owner
532 * and next names. */
533 labs = dname_count_labels(qname) - dname_count_labels(ce);
534
535 if(labs > 0) {
536 /* i is number of labels to strip off qname, prepend * wild */
537 strip = qname;
538 striplen = qnamelen;
539 dname_remove_labels(&strip, &striplen, labs);
540 if(striplen > LDNS_MAX_DOMAINLEN-2)
541 return 0; /* too long to prepend wildcard */
542 buf[0] = 1;
543 buf[1] = (uint8_t)'*';
544 memmove(buf+2, strip, striplen);
545 if(val_nsec_proves_name_error(nsec, buf)) {
546 return 1;
547 }
548 }
549 return 0;
550 }
551