xref: /freebsd/contrib/unbound/validator/val_nsec3.c (revision 46d2f61818f594174cafe31ee338c6e083fa1876)
1 /*
2  * validator/val_nsec3.c - validator NSEC3 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 NSEC3 checking, the different NSEC3 proofs
41  * for denial of existence, and proofs for presence of types.
42  */
43 #include "config.h"
44 #include <ctype.h>
45 #include "validator/val_nsec3.h"
46 #include "validator/val_secalgo.h"
47 #include "validator/validator.h"
48 #include "validator/val_kentry.h"
49 #include "services/cache/rrset.h"
50 #include "util/regional.h"
51 #include "util/rbtree.h"
52 #include "util/module.h"
53 #include "util/net_help.h"
54 #include "util/data/packed_rrset.h"
55 #include "util/data/dname.h"
56 #include "util/data/msgreply.h"
57 /* we include nsec.h for the bitmap_has_type function */
58 #include "validator/val_nsec.h"
59 #include "sldns/sbuffer.h"
60 #include "util/config_file.h"
61 
62 /**
63  * Max number of NSEC3 calculations at once, suspend query for later.
64  * 8 is low enough and allows for cases where multiple proofs are needed.
65  */
66 #define MAX_NSEC3_CALCULATIONS 8
67 /**
68  * When all allowed NSEC3 calculations at once resulted in error treat as
69  * bogus. NSEC3 hash errors are not cached and this helps breaks loops with
70  * erroneous data.
71  */
72 #define MAX_NSEC3_ERRORS -1
73 
74 /**
75  * This function we get from ldns-compat or from base system
76  * it returns the number of data bytes stored at the target, or <0 on error.
77  */
78 int sldns_b32_ntop_extended_hex(uint8_t const *src, size_t srclength,
79 	char *target, size_t targsize);
80 /**
81  * This function we get from ldns-compat or from base system
82  * it returns the number of data bytes stored at the target, or <0 on error.
83  */
84 int sldns_b32_pton_extended_hex(char const *src, size_t hashed_owner_str_len,
85 	uint8_t *target, size_t targsize);
86 
87 /**
88  * Closest encloser (ce) proof results
89  * Contains the ce and the next-closer (nc) proof.
90  */
91 struct ce_response {
92 	/** the closest encloser name */
93 	uint8_t* ce;
94 	/** length of ce */
95 	size_t ce_len;
96 	/** NSEC3 record that proved ce. rrset */
97 	struct ub_packed_rrset_key* ce_rrset;
98 	/** NSEC3 record that proved ce. rr number */
99 	int ce_rr;
100 	/** NSEC3 record that proved nc. rrset */
101 	struct ub_packed_rrset_key* nc_rrset;
102 	/** NSEC3 record that proved nc. rr*/
103 	int nc_rr;
104 };
105 
106 /**
107  * Filter conditions for NSEC3 proof
108  * Used to iterate over the applicable NSEC3 RRs.
109  */
110 struct nsec3_filter {
111 	/** Zone name, only NSEC3 records for this zone are considered */
112 	uint8_t* zone;
113 	/** length of the zonename */
114 	size_t zone_len;
115 	/** the list of NSEC3s to filter; array */
116 	struct ub_packed_rrset_key** list;
117 	/** number of rrsets in list */
118 	size_t num;
119 	/** class of records for the NSEC3, only this class applies */
120 	uint16_t fclass;
121 };
122 
123 /** return number of rrs in an rrset */
124 static size_t
rrset_get_count(struct ub_packed_rrset_key * rrset)125 rrset_get_count(struct ub_packed_rrset_key* rrset)
126 {
127         struct packed_rrset_data* d = (struct packed_rrset_data*)
128 	        rrset->entry.data;
129         if(!d) return 0;
130         return d->count;
131 }
132 
133 /** return if nsec3 RR has unknown flags */
134 static int
nsec3_unknown_flags(struct ub_packed_rrset_key * rrset,int r)135 nsec3_unknown_flags(struct ub_packed_rrset_key* rrset, int r)
136 {
137         struct packed_rrset_data* d = (struct packed_rrset_data*)
138 	        rrset->entry.data;
139 	log_assert(d && r < (int)d->count);
140 	if(d->rr_len[r] < 2+2)
141 		return 0; /* malformed */
142 	return (int)(d->rr_data[r][2+1] & NSEC3_UNKNOWN_FLAGS);
143 }
144 
145 int
nsec3_has_optout(struct ub_packed_rrset_key * rrset,int r)146 nsec3_has_optout(struct ub_packed_rrset_key* rrset, int r)
147 {
148         struct packed_rrset_data* d = (struct packed_rrset_data*)
149 	        rrset->entry.data;
150 	log_assert(d && r < (int)d->count);
151 	if(d->rr_len[r] < 2+2)
152 		return 0; /* malformed */
153 	return (int)(d->rr_data[r][2+1] & NSEC3_OPTOUT);
154 }
155 
156 /** return nsec3 RR algorithm */
157 static int
nsec3_get_algo(struct ub_packed_rrset_key * rrset,int r)158 nsec3_get_algo(struct ub_packed_rrset_key* rrset, int r)
159 {
160         struct packed_rrset_data* d = (struct packed_rrset_data*)
161 	        rrset->entry.data;
162 	log_assert(d && r < (int)d->count);
163 	if(d->rr_len[r] < 2+1)
164 		return 0; /* malformed */
165 	return (int)(d->rr_data[r][2+0]);
166 }
167 
168 /** return if nsec3 RR has known algorithm */
169 static int
nsec3_known_algo(struct ub_packed_rrset_key * rrset,int r)170 nsec3_known_algo(struct ub_packed_rrset_key* rrset, int r)
171 {
172         struct packed_rrset_data* d = (struct packed_rrset_data*)
173 	        rrset->entry.data;
174 	log_assert(d && r < (int)d->count);
175 	if(d->rr_len[r] < 2+1)
176 		return 0; /* malformed */
177 	switch(d->rr_data[r][2+0]) {
178 		case NSEC3_HASH_SHA1:
179 			return 1;
180 	}
181 	return 0;
182 }
183 
184 /** return nsec3 RR iteration count */
185 static size_t
nsec3_get_iter(struct ub_packed_rrset_key * rrset,int r)186 nsec3_get_iter(struct ub_packed_rrset_key* rrset, int r)
187 {
188 	uint16_t i;
189         struct packed_rrset_data* d = (struct packed_rrset_data*)
190 	        rrset->entry.data;
191 	log_assert(d && r < (int)d->count);
192 	if(d->rr_len[r] < 2+4)
193 		return 0; /* malformed */
194 	memmove(&i, d->rr_data[r]+2+2, sizeof(i));
195 	i = ntohs(i);
196 	return (size_t)i;
197 }
198 
199 /** return nsec3 RR salt */
200 static int
nsec3_get_salt(struct ub_packed_rrset_key * rrset,int r,uint8_t ** salt,size_t * saltlen)201 nsec3_get_salt(struct ub_packed_rrset_key* rrset, int r,
202 	uint8_t** salt, size_t* saltlen)
203 {
204         struct packed_rrset_data* d = (struct packed_rrset_data*)
205 	        rrset->entry.data;
206 	log_assert(d && r < (int)d->count);
207 	if(d->rr_len[r] < 2+5) {
208 		*salt = 0;
209 		*saltlen = 0;
210 		return 0; /* malformed */
211 	}
212 	*saltlen = (size_t)d->rr_data[r][2+4];
213 	if(d->rr_len[r] < 2+5+(size_t)*saltlen) {
214 		*salt = 0;
215 		*saltlen = 0;
216 		return 0; /* malformed */
217 	}
218 	*salt = d->rr_data[r]+2+5;
219 	return 1;
220 }
221 
nsec3_get_params(struct ub_packed_rrset_key * rrset,int r,int * algo,size_t * iter,uint8_t ** salt,size_t * saltlen)222 int nsec3_get_params(struct ub_packed_rrset_key* rrset, int r,
223 	int* algo, size_t* iter, uint8_t** salt, size_t* saltlen)
224 {
225 	if(!nsec3_known_algo(rrset, r) || nsec3_unknown_flags(rrset, r))
226 		return 0;
227 	if(!nsec3_get_salt(rrset, r, salt, saltlen))
228 		return 0;
229 	*algo = nsec3_get_algo(rrset, r);
230 	*iter = nsec3_get_iter(rrset, r);
231 	return 1;
232 }
233 
234 int
nsec3_get_nextowner(struct ub_packed_rrset_key * rrset,int r,uint8_t ** next,size_t * nextlen)235 nsec3_get_nextowner(struct ub_packed_rrset_key* rrset, int r,
236 	uint8_t** next, size_t* nextlen)
237 {
238 	size_t saltlen;
239         struct packed_rrset_data* d = (struct packed_rrset_data*)
240 	        rrset->entry.data;
241 	log_assert(d && r < (int)d->count);
242 	if(d->rr_len[r] < 2+5) {
243 		*next = 0;
244 		*nextlen = 0;
245 		return 0; /* malformed */
246 	}
247 	saltlen = (size_t)d->rr_data[r][2+4];
248 	if(d->rr_len[r] < 2+5+saltlen+1) {
249 		*next = 0;
250 		*nextlen = 0;
251 		return 0; /* malformed */
252 	}
253 	*nextlen = (size_t)d->rr_data[r][2+5+saltlen];
254 	if(d->rr_len[r] < 2+5+saltlen+1+*nextlen) {
255 		*next = 0;
256 		*nextlen = 0;
257 		return 0; /* malformed */
258 	}
259 	*next = d->rr_data[r]+2+5+saltlen+1;
260 	return 1;
261 }
262 
nsec3_hash_to_b32(uint8_t * hash,size_t hashlen,uint8_t * zone,size_t zonelen,uint8_t * buf,size_t max)263 size_t nsec3_hash_to_b32(uint8_t* hash, size_t hashlen, uint8_t* zone,
264 	size_t zonelen, uint8_t* buf, size_t max)
265 {
266 	/* write b32 of name, leave one for length */
267 	int ret;
268 	if(max < hashlen*2+1) /* quick approx of b32, as if hexb16 */
269 		return 0;
270 	ret = sldns_b32_ntop_extended_hex(hash, hashlen, (char*)buf+1, max-1);
271 	if(ret < 1)
272 		return 0;
273 	buf[0] = (uint8_t)ret; /* length of b32 label */
274 	ret++;
275 	if(max - ret < zonelen)
276 		return 0;
277 	memmove(buf+ret, zone, zonelen);
278 	return zonelen+(size_t)ret;
279 }
280 
nsec3_get_nextowner_b32(struct ub_packed_rrset_key * rrset,int r,uint8_t * buf,size_t max)281 size_t nsec3_get_nextowner_b32(struct ub_packed_rrset_key* rrset, int r,
282 	uint8_t* buf, size_t max)
283 {
284 	uint8_t* nm, *zone;
285 	size_t nmlen, zonelen;
286 	if(!nsec3_get_nextowner(rrset, r, &nm, &nmlen))
287 		return 0;
288 	/* append zone name; the owner name must be <b32>.zone */
289 	zone = rrset->rk.dname;
290 	zonelen = rrset->rk.dname_len;
291 	dname_remove_label(&zone, &zonelen);
292 	return nsec3_hash_to_b32(nm, nmlen, zone, zonelen, buf, max);
293 }
294 
295 int
nsec3_has_type(struct ub_packed_rrset_key * rrset,int r,uint16_t type)296 nsec3_has_type(struct ub_packed_rrset_key* rrset, int r, uint16_t type)
297 {
298 	uint8_t* bitmap;
299 	size_t bitlen, skiplen;
300         struct packed_rrset_data* d = (struct packed_rrset_data*)
301 	        rrset->entry.data;
302 	log_assert(d && r < (int)d->count);
303 	skiplen = 2+4;
304 	/* skip salt */
305 	if(d->rr_len[r] < skiplen+1)
306 		return 0; /* malformed, too short */
307 	skiplen += 1+(size_t)d->rr_data[r][skiplen];
308 	/* skip next hashed owner */
309 	if(d->rr_len[r] < skiplen+1)
310 		return 0; /* malformed, too short */
311 	skiplen += 1+(size_t)d->rr_data[r][skiplen];
312 	if(d->rr_len[r] < skiplen)
313 		return 0; /* malformed, too short */
314 	bitlen = d->rr_len[r] - skiplen;
315 	bitmap = d->rr_data[r]+skiplen;
316 	return nsecbitmap_has_type_rdata(bitmap, bitlen, type);
317 }
318 
319 /**
320  * Iterate through NSEC3 list, per RR
321  * This routine gives the next RR in the list (or sets rrset null).
322  * Usage:
323  *
324  * size_t rrsetnum;
325  * int rrnum;
326  * struct ub_packed_rrset_key* rrset;
327  * for(rrset=filter_first(filter, &rrsetnum, &rrnum); rrset;
328  *	rrset=filter_next(filter, &rrsetnum, &rrnum))
329  *		do_stuff;
330  *
331  * Also filters out
332  * 	o unknown flag NSEC3s
333  * 	o unknown algorithm NSEC3s.
334  * @param filter: nsec3 filter structure.
335  * @param rrsetnum: in/out rrset number to look at.
336  * @param rrnum: in/out rr number in rrset to look at.
337  * @returns ptr to the next rrset (or NULL at end).
338  */
339 static struct ub_packed_rrset_key*
filter_next(struct nsec3_filter * filter,size_t * rrsetnum,int * rrnum)340 filter_next(struct nsec3_filter* filter, size_t* rrsetnum, int* rrnum)
341 {
342 	size_t i;
343 	int r;
344 	uint8_t* nm;
345 	size_t nmlen;
346 	if(!filter->zone) /* empty list */
347 		return NULL;
348 	for(i=*rrsetnum; i<filter->num; i++) {
349 		/* see if RRset qualifies */
350 		if(ntohs(filter->list[i]->rk.type) != LDNS_RR_TYPE_NSEC3 ||
351 			ntohs(filter->list[i]->rk.rrset_class) !=
352 			filter->fclass)
353 			continue;
354 		/* check RRset zone */
355 		nm = filter->list[i]->rk.dname;
356 		nmlen = filter->list[i]->rk.dname_len;
357 		dname_remove_label(&nm, &nmlen);
358 		if(query_dname_compare(nm, filter->zone) != 0)
359 			continue;
360 		if(i == *rrsetnum)
361 			r = (*rrnum) + 1; /* continue at next RR */
362 		else	r = 0;		/* new RRset start at first RR */
363 		for(; r < (int)rrset_get_count(filter->list[i]); r++) {
364 			/* skip unknown flags, algo */
365 			if(nsec3_unknown_flags(filter->list[i], r) ||
366 				!nsec3_known_algo(filter->list[i], r))
367 				continue;
368 			/* this one is a good target */
369 			*rrsetnum = i;
370 			*rrnum = r;
371 			return filter->list[i];
372 		}
373 	}
374 	return NULL;
375 }
376 
377 /**
378  * Start iterating over NSEC3 records.
379  * @param filter: the filter structure, must have been filter_init-ed.
380  * @param rrsetnum: can be undefined on call, initialised.
381  * @param rrnum: can be undefined on call, initialised.
382  * @return first rrset of an NSEC3, together with rrnum this points to
383  *	the first RR to examine. Is NULL on empty list.
384  */
385 static struct ub_packed_rrset_key*
filter_first(struct nsec3_filter * filter,size_t * rrsetnum,int * rrnum)386 filter_first(struct nsec3_filter* filter, size_t* rrsetnum, int* rrnum)
387 {
388 	*rrsetnum = 0;
389 	*rrnum = -1;
390 	return filter_next(filter, rrsetnum, rrnum);
391 }
392 
393 /** see if at least one RR is known (flags, algo) */
394 static int
nsec3_rrset_has_known(struct ub_packed_rrset_key * s)395 nsec3_rrset_has_known(struct ub_packed_rrset_key* s)
396 {
397 	int r;
398 	for(r=0; r < (int)rrset_get_count(s); r++) {
399 		if(!nsec3_unknown_flags(s, r) && nsec3_known_algo(s, r))
400 			return 1;
401 	}
402 	return 0;
403 }
404 
405 /**
406  * Initialize the filter structure.
407  * Finds the zone by looking at available NSEC3 records and best match.
408  * 	(skips the unknown flag and unknown algo NSEC3s).
409  *
410  * @param filter: nsec3 filter structure.
411  * @param list: list of rrsets, an array of them.
412  * @param num: number of rrsets in list.
413  * @param qinfo:
414  *	query name to match a zone for.
415  *	query type (if DS a higher zone must be chosen)
416  *	qclass, to filter NSEC3s with.
417  */
418 static void
filter_init(struct nsec3_filter * filter,struct ub_packed_rrset_key ** list,size_t num,struct query_info * qinfo)419 filter_init(struct nsec3_filter* filter, struct ub_packed_rrset_key** list,
420 	size_t num, struct query_info* qinfo)
421 {
422 	size_t i;
423 	uint8_t* nm;
424 	size_t nmlen;
425 	filter->zone = NULL;
426 	filter->zone_len = 0;
427 	filter->list = list;
428 	filter->num = num;
429 	filter->fclass = qinfo->qclass;
430 	for(i=0; i<num; i++) {
431 		/* ignore other stuff in the list */
432 		if(ntohs(list[i]->rk.type) != LDNS_RR_TYPE_NSEC3 ||
433 			ntohs(list[i]->rk.rrset_class) != qinfo->qclass)
434 			continue;
435 		/* skip unknown flags, algo */
436 		if(!nsec3_rrset_has_known(list[i]))
437 			continue;
438 
439 		/* since NSEC3s are base32.zonename, we can find the zone
440 		 * name by stripping off the first label of the record */
441 		nm = list[i]->rk.dname;
442 		nmlen = list[i]->rk.dname_len;
443 		dname_remove_label(&nm, &nmlen);
444 		/* if we find a domain that can prove about the qname,
445 		 * and if this domain is closer to the qname */
446 		if(dname_subdomain_c(qinfo->qname, nm) && (!filter->zone ||
447 			dname_subdomain_c(nm, filter->zone))) {
448 			/* for a type DS do not accept a zone equal to qname*/
449 			if(qinfo->qtype == LDNS_RR_TYPE_DS &&
450 				query_dname_compare(qinfo->qname, nm) == 0 &&
451 				!dname_is_root(qinfo->qname))
452 				continue;
453 			filter->zone = nm;
454 			filter->zone_len = nmlen;
455 		}
456 	}
457 }
458 
459 /**
460  * Find max iteration count using config settings and key size
461  * @param ve: validator environment with iteration count config settings.
462  * @param bits: key size
463  * @return max iteration count
464  */
465 static size_t
get_max_iter(struct val_env * ve,size_t bits)466 get_max_iter(struct val_env* ve, size_t bits)
467 {
468 	int i;
469 	log_assert(ve->nsec3_keyiter_count > 0);
470 	/* round up to nearest config keysize, linear search, keep it small */
471 	for(i=0; i<ve->nsec3_keyiter_count; i++) {
472 		if(bits <= ve->nsec3_keysize[i])
473 			return ve->nsec3_maxiter[i];
474 	}
475 	/* else, use value for biggest key */
476 	return ve->nsec3_maxiter[ve->nsec3_keyiter_count-1];
477 }
478 
479 /**
480  * Determine if any of the NSEC3 rrs iteration count is too high, from key.
481  * @param ve: validator environment with iteration count config settings.
482  * @param filter: what NSEC3s to loop over.
483  * @param kkey: key entry used for verification; used for iteration counts.
484  * @return 1 if some nsec3s are above the max iteration count.
485  */
486 static int
nsec3_iteration_count_high(struct val_env * ve,struct nsec3_filter * filter,struct key_entry_key * kkey)487 nsec3_iteration_count_high(struct val_env* ve, struct nsec3_filter* filter,
488 	struct key_entry_key* kkey)
489 {
490 	size_t rrsetnum;
491 	int rrnum;
492 	struct ub_packed_rrset_key* rrset;
493 	/* first determine the max number of iterations */
494 	size_t bits = key_entry_keysize(kkey);
495 	size_t max_iter = get_max_iter(ve, bits);
496 	verbose(VERB_ALGO, "nsec3: keysize %d bits, max iterations %d",
497 		(int)bits, (int)max_iter);
498 
499 	for(rrset=filter_first(filter, &rrsetnum, &rrnum); rrset;
500 		rrset=filter_next(filter, &rrsetnum, &rrnum)) {
501 		if(nsec3_get_iter(rrset, rrnum) > max_iter)
502 			return 1;
503 	}
504 	return 0;
505 }
506 
507 /* nsec3_cache_compare for rbtree */
508 int
nsec3_hash_cmp(const void * c1,const void * c2)509 nsec3_hash_cmp(const void* c1, const void* c2)
510 {
511 	struct nsec3_cached_hash* h1 = (struct nsec3_cached_hash*)c1;
512 	struct nsec3_cached_hash* h2 = (struct nsec3_cached_hash*)c2;
513 	uint8_t* s1, *s2;
514 	size_t s1len, s2len;
515 	int c = query_dname_compare(h1->dname, h2->dname);
516 	if(c != 0)
517 		return c;
518 	/* compare parameters */
519 	/* if both malformed, its equal, robustness */
520 	if(nsec3_get_algo(h1->nsec3, h1->rr) !=
521 		nsec3_get_algo(h2->nsec3, h2->rr)) {
522 		if(nsec3_get_algo(h1->nsec3, h1->rr) <
523 			nsec3_get_algo(h2->nsec3, h2->rr))
524 			return -1;
525 		return 1;
526 	}
527 	if(nsec3_get_iter(h1->nsec3, h1->rr) !=
528 		nsec3_get_iter(h2->nsec3, h2->rr)) {
529 		if(nsec3_get_iter(h1->nsec3, h1->rr) <
530 			nsec3_get_iter(h2->nsec3, h2->rr))
531 			return -1;
532 		return 1;
533 	}
534 	(void)nsec3_get_salt(h1->nsec3, h1->rr, &s1, &s1len);
535 	(void)nsec3_get_salt(h2->nsec3, h2->rr, &s2, &s2len);
536 	if(s1len == 0 && s2len == 0)
537 		return 0;
538 	if(!s1) return -1;
539 	if(!s2) return 1;
540 	if(s1len != s2len) {
541 		if(s1len < s2len)
542 			return -1;
543 		return 1;
544 	}
545 	return memcmp(s1, s2, s1len);
546 }
547 
548 int
nsec3_cache_table_init(struct nsec3_cache_table * ct,struct regional * region)549 nsec3_cache_table_init(struct nsec3_cache_table* ct, struct regional* region)
550 {
551 	if(ct->ct) return 1;
552 	ct->ct = (rbtree_type*)regional_alloc(region, sizeof(*ct->ct));
553 	if(!ct->ct) return 0;
554 	ct->region = region;
555 	rbtree_init(ct->ct, &nsec3_hash_cmp);
556 	return 1;
557 }
558 
559 size_t
nsec3_get_hashed(sldns_buffer * buf,uint8_t * nm,size_t nmlen,int algo,size_t iter,uint8_t * salt,size_t saltlen,uint8_t * res,size_t max)560 nsec3_get_hashed(sldns_buffer* buf, uint8_t* nm, size_t nmlen, int algo,
561 	size_t iter, uint8_t* salt, size_t saltlen, uint8_t* res, size_t max)
562 {
563 	size_t i, hash_len;
564 	/* prepare buffer for first iteration */
565 	sldns_buffer_clear(buf);
566 	sldns_buffer_write(buf, nm, nmlen);
567 	query_dname_tolower(sldns_buffer_begin(buf));
568 	if(saltlen != 0)
569 		sldns_buffer_write(buf, salt, saltlen);
570 	sldns_buffer_flip(buf);
571 	hash_len = nsec3_hash_algo_size_supported(algo);
572 	if(hash_len == 0) {
573 		log_err("nsec3 hash of unknown algo %d", algo);
574 		return 0;
575 	}
576 	if(hash_len > max)
577 		return 0;
578 	if(!secalgo_nsec3_hash(algo, (unsigned char*)sldns_buffer_begin(buf),
579 		sldns_buffer_limit(buf), (unsigned char*)res))
580 		return 0;
581 	for(i=0; i<iter; i++) {
582 		sldns_buffer_clear(buf);
583 		sldns_buffer_write(buf, res, hash_len);
584 		if(saltlen != 0)
585 			sldns_buffer_write(buf, salt, saltlen);
586 		sldns_buffer_flip(buf);
587 		if(!secalgo_nsec3_hash(algo,
588 			(unsigned char*)sldns_buffer_begin(buf),
589 			sldns_buffer_limit(buf), (unsigned char*)res))
590 			return 0;
591 	}
592 	return hash_len;
593 }
594 
595 /** perform hash of name */
596 static int
nsec3_calc_hash(struct regional * region,sldns_buffer * buf,struct nsec3_cached_hash * c)597 nsec3_calc_hash(struct regional* region, sldns_buffer* buf,
598 	struct nsec3_cached_hash* c)
599 {
600 	int algo = nsec3_get_algo(c->nsec3, c->rr);
601 	size_t iter = nsec3_get_iter(c->nsec3, c->rr);
602 	uint8_t* salt;
603 	size_t saltlen, i;
604 	if(!nsec3_get_salt(c->nsec3, c->rr, &salt, &saltlen))
605 		return -1;
606 	/* prepare buffer for first iteration */
607 	sldns_buffer_clear(buf);
608 	sldns_buffer_write(buf, c->dname, c->dname_len);
609 	query_dname_tolower(sldns_buffer_begin(buf));
610 	sldns_buffer_write(buf, salt, saltlen);
611 	sldns_buffer_flip(buf);
612 	c->hash_len = nsec3_hash_algo_size_supported(algo);
613 	if(c->hash_len == 0) {
614 		log_err("nsec3 hash of unknown algo %d", algo);
615 		return -1;
616 	}
617 	c->hash = (uint8_t*)regional_alloc(region, c->hash_len);
618 	if(!c->hash)
619 		return 0;
620 	(void)secalgo_nsec3_hash(algo, (unsigned char*)sldns_buffer_begin(buf),
621 		sldns_buffer_limit(buf), (unsigned char*)c->hash);
622 	for(i=0; i<iter; i++) {
623 		sldns_buffer_clear(buf);
624 		sldns_buffer_write(buf, c->hash, c->hash_len);
625 		sldns_buffer_write(buf, salt, saltlen);
626 		sldns_buffer_flip(buf);
627 		(void)secalgo_nsec3_hash(algo,
628 			(unsigned char*)sldns_buffer_begin(buf),
629 			sldns_buffer_limit(buf), (unsigned char*)c->hash);
630 	}
631 	return 1;
632 }
633 
634 /** perform b32 encoding of hash */
635 static int
nsec3_calc_b32(struct regional * region,sldns_buffer * buf,struct nsec3_cached_hash * c)636 nsec3_calc_b32(struct regional* region, sldns_buffer* buf,
637 	struct nsec3_cached_hash* c)
638 {
639 	int r;
640 	sldns_buffer_clear(buf);
641 	r = sldns_b32_ntop_extended_hex(c->hash, c->hash_len,
642 		(char*)sldns_buffer_begin(buf), sldns_buffer_limit(buf));
643 	if(r < 1) {
644 		log_err("b32_ntop_extended_hex: error in encoding: %d", r);
645 		return 0;
646 	}
647 	c->b32_len = (size_t)r;
648 	c->b32 = regional_alloc_init(region, sldns_buffer_begin(buf),
649 		c->b32_len);
650 	if(!c->b32)
651 		return 0;
652 	return 1;
653 }
654 
655 int
nsec3_hash_name(rbtree_type * table,struct regional * region,sldns_buffer * buf,struct ub_packed_rrset_key * nsec3,int rr,uint8_t * dname,size_t dname_len,struct nsec3_cached_hash ** hash)656 nsec3_hash_name(rbtree_type* table, struct regional* region, sldns_buffer* buf,
657 	struct ub_packed_rrset_key* nsec3, int rr, uint8_t* dname,
658 	size_t dname_len, struct nsec3_cached_hash** hash)
659 {
660 	struct nsec3_cached_hash* c;
661 	struct nsec3_cached_hash looki;
662 #ifdef UNBOUND_DEBUG
663 	rbnode_type* n;
664 #endif
665 	int r;
666 	looki.node.key = &looki;
667 	looki.nsec3 = nsec3;
668 	looki.rr = rr;
669 	looki.dname = dname;
670 	looki.dname_len = dname_len;
671 	/* lookup first in cache */
672 	c = (struct nsec3_cached_hash*)rbtree_search(table, &looki);
673 	if(c) {
674 		*hash = c;
675 		return 2;
676 	}
677 	/* create a new entry */
678 	c = (struct nsec3_cached_hash*)regional_alloc(region, sizeof(*c));
679 	if(!c) return 0;
680 	c->node.key = c;
681 	c->nsec3 = nsec3;
682 	c->rr = rr;
683 	c->dname = dname;
684 	c->dname_len = dname_len;
685 	r = nsec3_calc_hash(region, buf, c);
686 	if(r != 1)
687 		return r;  /* returns -1 or 0 */
688 	r = nsec3_calc_b32(region, buf, c);
689 	if(r != 1)
690 		return r;  /* returns 0 */
691 #ifdef UNBOUND_DEBUG
692 	n =
693 #else
694 	(void)
695 #endif
696 	rbtree_insert(table, &c->node);
697 	log_assert(n); /* cannot be duplicate, just did lookup */
698 	*hash = c;
699 	return 1;
700 }
701 
702 /**
703  * compare a label lowercased
704  */
705 static int
label_compare_lower(uint8_t * lab1,uint8_t * lab2,size_t lablen)706 label_compare_lower(uint8_t* lab1, uint8_t* lab2, size_t lablen)
707 {
708 	size_t i;
709 	for(i=0; i<lablen; i++) {
710 		if(tolower((unsigned char)*lab1) != tolower((unsigned char)*lab2)) {
711 			if(tolower((unsigned char)*lab1) < tolower((unsigned char)*lab2))
712 				return -1;
713 			return 1;
714 		}
715 		lab1++;
716 		lab2++;
717 	}
718 	return 0;
719 }
720 
721 /**
722  * Compare a hashed name with the owner name of an NSEC3 RRset.
723  * @param flt: filter with zone name.
724  * @param hash: the hashed name.
725  * @param s: rrset with owner name.
726  * @return true if matches exactly, false if not.
727  */
728 static int
nsec3_hash_matches_owner(struct nsec3_filter * flt,struct nsec3_cached_hash * hash,struct ub_packed_rrset_key * s)729 nsec3_hash_matches_owner(struct nsec3_filter* flt,
730 	struct nsec3_cached_hash* hash, struct ub_packed_rrset_key* s)
731 {
732 	uint8_t* nm = s->rk.dname;
733 	if(!hash) return 0; /* please clang */
734 	/* compare, does hash of name based on params in this NSEC3
735 	 * match the owner name of this NSEC3?
736 	 * name must be: <hashlength>base32 . zone name
737 	 * so; first label must not be root label (not zero length),
738 	 * and match the b32 encoded hash length,
739 	 * and the label content match the b32 encoded hash
740 	 * and the rest must be the zone name.
741 	 */
742 	if(hash->b32_len != 0 && (size_t)nm[0] == hash->b32_len &&
743 		label_compare_lower(nm+1, hash->b32, hash->b32_len) == 0 &&
744 		query_dname_compare(nm+(size_t)nm[0]+1, flt->zone) == 0) {
745 		return 1;
746 	}
747 	return 0;
748 }
749 
750 /**
751  * Find matching NSEC3
752  * Find the NSEC3Record that matches a hash of a name.
753  * @param env: module environment with temporary region and buffer.
754  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
755  * @param ct: cached hashes table.
756  * @param nm: name to look for.
757  * @param nmlen: length of name.
758  * @param rrset: nsec3 that matches is returned here.
759  * @param rr: rr number in nsec3 rrset that matches.
760  * @param calculations: current hash calculations.
761  * @return true if a matching NSEC3 is found, false if not.
762  */
763 static int
find_matching_nsec3(struct module_env * env,struct nsec3_filter * flt,struct nsec3_cache_table * ct,uint8_t * nm,size_t nmlen,struct ub_packed_rrset_key ** rrset,int * rr,int * calculations)764 find_matching_nsec3(struct module_env* env, struct nsec3_filter* flt,
765 	struct nsec3_cache_table* ct, uint8_t* nm, size_t nmlen,
766 	struct ub_packed_rrset_key** rrset, int* rr,
767 	int* calculations)
768 {
769 	size_t i_rs;
770 	int i_rr;
771 	struct ub_packed_rrset_key* s;
772 	struct nsec3_cached_hash* hash = NULL;
773 	int r;
774 	int calc_errors = 0;
775 
776 	/* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
777 	for(s=filter_first(flt, &i_rs, &i_rr); s;
778 		s=filter_next(flt, &i_rs, &i_rr)) {
779 		/* check if we are allowed more calculations */
780 		if(*calculations >= MAX_NSEC3_CALCULATIONS) {
781 			if(calc_errors == *calculations) {
782 				*calculations = MAX_NSEC3_ERRORS;
783 			}
784 			break;
785 		}
786 		/* get name hashed for this NSEC3 RR */
787 		r = nsec3_hash_name(ct->ct, ct->region, env->scratch_buffer,
788 			s, i_rr, nm, nmlen, &hash);
789 		if(r == 0) {
790 			log_err("nsec3: malloc failure");
791 			break; /* alloc failure */
792 		} else if(r < 0) {
793 			/* malformed NSEC3 */
794 			calc_errors++;
795 			(*calculations)++;
796 			continue;
797 		} else {
798 			if(r == 1) (*calculations)++;
799 			if(nsec3_hash_matches_owner(flt, hash, s)) {
800 				*rrset = s; /* rrset with this name */
801 				*rr = i_rr; /* matches hash with these parameters */
802 				return 1;
803 			}
804 		}
805 	}
806 	*rrset = NULL;
807 	*rr = 0;
808 	return 0;
809 }
810 
811 int
nsec3_covers(uint8_t * zone,struct nsec3_cached_hash * hash,struct ub_packed_rrset_key * rrset,int rr,sldns_buffer * buf)812 nsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash,
813 	struct ub_packed_rrset_key* rrset, int rr, sldns_buffer* buf)
814 {
815 	uint8_t* next, *owner;
816 	size_t nextlen;
817 	int len;
818 	if(!nsec3_get_nextowner(rrset, rr, &next, &nextlen))
819 		return 0; /* malformed RR proves nothing */
820 
821 	if(!hash) return 0; /* please clang */
822 	/* check the owner name is a hashed value . apex
823 	 * base32 encoded values must have equal length.
824 	 * hash_value and next hash value must have equal length. */
825 	if(nextlen != hash->hash_len || hash->hash_len==0||hash->b32_len==0||
826 		(size_t)*rrset->rk.dname != hash->b32_len ||
827 		query_dname_compare(rrset->rk.dname+1+
828 			(size_t)*rrset->rk.dname, zone) != 0)
829 		return 0; /* bad lengths or owner name */
830 
831 	/* This is the "normal case: owner < next and owner < hash < next */
832 	if(label_compare_lower(rrset->rk.dname+1, hash->b32,
833 		hash->b32_len) < 0 &&
834 		memcmp(hash->hash, next, nextlen) < 0)
835 		return 1;
836 
837 	/* convert owner name from text to binary */
838 	sldns_buffer_clear(buf);
839 	owner = sldns_buffer_begin(buf);
840 	len = sldns_b32_pton_extended_hex((char*)rrset->rk.dname+1,
841 		hash->b32_len, owner, sldns_buffer_limit(buf));
842 	if(len<1)
843 		return 0; /* bad owner name in some way */
844 	if((size_t)len != hash->hash_len || (size_t)len != nextlen)
845 		return 0; /* wrong length */
846 
847 	/* this is the end of zone case: next <= owner &&
848 	 * 	(hash > owner || hash < next)
849 	 * this also covers the only-apex case of next==owner.
850 	 */
851 	if(memcmp(next, owner, nextlen) <= 0 &&
852 		( memcmp(hash->hash, owner, nextlen) > 0 ||
853 		  memcmp(hash->hash, next, nextlen) < 0)) {
854 		return 1;
855 	}
856 	return 0;
857 }
858 
859 /**
860  * findCoveringNSEC3
861  * Given a name, find a covering NSEC3 from among a list of NSEC3s.
862  *
863  * @param env: module environment with temporary region and buffer.
864  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
865  * @param ct: cached hashes table.
866  * @param nm: name to check if covered.
867  * @param nmlen: length of name.
868  * @param rrset: covering NSEC3 rrset is returned here.
869  * @param rr: rr of cover is returned here.
870  * @param calculations: current hash calculations.
871  * @return true if a covering NSEC3 is found, false if not.
872  */
873 static int
find_covering_nsec3(struct module_env * env,struct nsec3_filter * flt,struct nsec3_cache_table * ct,uint8_t * nm,size_t nmlen,struct ub_packed_rrset_key ** rrset,int * rr,int * calculations)874 find_covering_nsec3(struct module_env* env, struct nsec3_filter* flt,
875 	struct nsec3_cache_table* ct, uint8_t* nm, size_t nmlen,
876 	struct ub_packed_rrset_key** rrset, int* rr,
877 	int* calculations)
878 {
879 	size_t i_rs;
880 	int i_rr;
881 	struct ub_packed_rrset_key* s;
882 	struct nsec3_cached_hash* hash = NULL;
883 	int r;
884 	int calc_errors = 0;
885 
886 	/* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
887 	for(s=filter_first(flt, &i_rs, &i_rr); s;
888 		s=filter_next(flt, &i_rs, &i_rr)) {
889 		/* check if we are allowed more calculations */
890 		if(*calculations >= MAX_NSEC3_CALCULATIONS) {
891 			if(calc_errors == *calculations) {
892 				*calculations = MAX_NSEC3_ERRORS;
893 			}
894 			break;
895 		}
896 		/* get name hashed for this NSEC3 RR */
897 		r = nsec3_hash_name(ct->ct, ct->region, env->scratch_buffer,
898 			s, i_rr, nm, nmlen, &hash);
899 		if(r == 0) {
900 			log_err("nsec3: malloc failure");
901 			break; /* alloc failure */
902 		} else if(r < 0) {
903 			/* malformed NSEC3 */
904 			calc_errors++;
905 			(*calculations)++;
906 			continue;
907 		} else {
908 			if(r == 1) (*calculations)++;
909 			if(nsec3_covers(flt->zone, hash, s, i_rr,
910 				env->scratch_buffer)) {
911 				*rrset = s; /* rrset with this name */
912 				*rr = i_rr; /* covers hash with these parameters */
913 				return 1;
914 			}
915 		}
916 	}
917 	*rrset = NULL;
918 	*rr = 0;
919 	return 0;
920 }
921 
922 /**
923  * findClosestEncloser
924  * Given a name and a list of NSEC3s, find the candidate closest encloser.
925  * This will be the first ancestor of 'name' (including itself) to have a
926  * matching NSEC3 RR.
927  * @param env: module environment with temporary region and buffer.
928  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
929  * @param ct: cached hashes table.
930  * @param qinfo: query that is verified for.
931  * @param ce: closest encloser information is returned in here.
932  * @param calculations: current hash calculations.
933  * @return true if a closest encloser candidate is found, false if not.
934  */
935 static int
nsec3_find_closest_encloser(struct module_env * env,struct nsec3_filter * flt,struct nsec3_cache_table * ct,struct query_info * qinfo,struct ce_response * ce,int * calculations)936 nsec3_find_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
937 	struct nsec3_cache_table* ct, struct query_info* qinfo,
938 	struct ce_response* ce, int* calculations)
939 {
940 	uint8_t* nm = qinfo->qname;
941 	size_t nmlen = qinfo->qname_len;
942 
943 	/* This scans from longest name to shortest, so the first match
944 	 * we find is the only viable candidate. */
945 
946 	/* (David:) FIXME: modify so that the NSEC3 matching the zone apex need
947 	 * not be present. (Mark Andrews idea).
948 	 * (Wouter:) But make sure you check for DNAME bit in zone apex,
949 	 * if the NSEC3 you find is the only NSEC3 in the zone, then this
950 	 * may be the case. */
951 
952 	while(dname_subdomain_c(nm, flt->zone)) {
953 		if(*calculations >= MAX_NSEC3_CALCULATIONS ||
954 			*calculations == MAX_NSEC3_ERRORS) {
955 			return 0;
956 		}
957 		if(find_matching_nsec3(env, flt, ct, nm, nmlen,
958 			&ce->ce_rrset, &ce->ce_rr, calculations)) {
959 			ce->ce = nm;
960 			ce->ce_len = nmlen;
961 			return 1;
962 		}
963 		dname_remove_label(&nm, &nmlen);
964 	}
965 	return 0;
966 }
967 
968 /**
969  * Given a qname and its proven closest encloser, calculate the "next
970  * closest" name. Basically, this is the name that is one label longer than
971  * the closest encloser that is still a subdomain of qname.
972  *
973  * @param qname: query name.
974  * @param qnamelen: length of qname.
975  * @param ce: closest encloser
976  * @param nm: result name.
977  * @param nmlen: length of nm.
978  */
979 static void
next_closer(uint8_t * qname,size_t qnamelen,uint8_t * ce,uint8_t ** nm,size_t * nmlen)980 next_closer(uint8_t* qname, size_t qnamelen, uint8_t* ce,
981 	uint8_t** nm, size_t* nmlen)
982 {
983 	int strip = dname_count_labels(qname) - dname_count_labels(ce) -1;
984 	*nm = qname;
985 	*nmlen = qnamelen;
986 	if(strip>0)
987 		dname_remove_labels(nm, nmlen, strip);
988 }
989 
990 /**
991  * proveClosestEncloser
992  * Given a List of nsec3 RRs, find and prove the closest encloser to qname.
993  * @param env: module environment with temporary region and buffer.
994  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
995  * @param ct: cached hashes table.
996  * @param qinfo: query that is verified for.
997  * @param prove_does_not_exist: If true, then if the closest encloser
998  * 	turns out to be qname, then null is returned.
999  * 	If set true, and the return value is true, then you can be
1000  * 	certain that the ce.nc_rrset and ce.nc_rr are set properly.
1001  * @param ce: closest encloser information is returned in here.
1002  * @param calculations: pointer to the current NSEC3 hash calculations.
1003  * @return bogus if no closest encloser could be proven.
1004  * 	secure if a closest encloser could be proven, ce is set.
1005  * 	insecure if the closest-encloser candidate turns out to prove
1006  * 		that an insecure delegation exists above the qname.
1007  *	unchecked if no more hash calculations are allowed at this point.
1008  */
1009 static enum sec_status
nsec3_prove_closest_encloser(struct module_env * env,struct nsec3_filter * flt,struct nsec3_cache_table * ct,struct query_info * qinfo,int prove_does_not_exist,struct ce_response * ce,int * calculations)1010 nsec3_prove_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
1011 	struct nsec3_cache_table* ct, struct query_info* qinfo,
1012 	int prove_does_not_exist, struct ce_response* ce, int* calculations)
1013 {
1014 	uint8_t* nc;
1015 	size_t nc_len;
1016 	/* robust: clean out ce, in case it gets abused later */
1017 	memset(ce, 0, sizeof(*ce));
1018 
1019 	if(!nsec3_find_closest_encloser(env, flt, ct, qinfo, ce, calculations)) {
1020 		if(*calculations == MAX_NSEC3_ERRORS) {
1021 			verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could "
1022 				"not find a candidate for the closest "
1023 				"encloser; all attempted hash calculations "
1024 				"were erroneous; bogus");
1025 			return sec_status_bogus;
1026 		} else if(*calculations >= MAX_NSEC3_CALCULATIONS) {
1027 			verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could "
1028 				"not find a candidate for the closest "
1029 				"encloser; reached MAX_NSEC3_CALCULATIONS "
1030 				"(%d); unchecked still",
1031 				MAX_NSEC3_CALCULATIONS);
1032 			return sec_status_unchecked;
1033 		}
1034 		verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could "
1035 			"not find a candidate for the closest encloser.");
1036 		return sec_status_bogus;
1037 	}
1038 	log_nametypeclass(VERB_ALGO, "ce candidate", ce->ce, 0, 0);
1039 
1040 	if(query_dname_compare(ce->ce, qinfo->qname) == 0) {
1041 		if(prove_does_not_exist) {
1042 			verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
1043 				"proved that qname existed, bad");
1044 			return sec_status_bogus;
1045 		}
1046 		/* otherwise, we need to nothing else to prove that qname
1047 		 * is its own closest encloser. */
1048 		return sec_status_secure;
1049 	}
1050 
1051 	/* If the closest encloser is actually a delegation, then the
1052 	 * response should have been a referral. If it is a DNAME, then
1053 	 * it should have been a DNAME response. */
1054 	if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_NS) &&
1055 		!nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_SOA)) {
1056 		if(!nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DS)) {
1057 			verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
1058 				"closest encloser is insecure delegation");
1059 			return sec_status_insecure;
1060 		}
1061 		verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
1062 			"encloser was a delegation, bad");
1063 		return sec_status_bogus;
1064 	}
1065 	if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DNAME)) {
1066 		verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
1067 			"encloser was a DNAME, bad");
1068 		return sec_status_bogus;
1069 	}
1070 
1071 	/* Otherwise, we need to show that the next closer name is covered. */
1072 	next_closer(qinfo->qname, qinfo->qname_len, ce->ce, &nc, &nc_len);
1073 	if(!find_covering_nsec3(env, flt, ct, nc, nc_len,
1074 		&ce->nc_rrset, &ce->nc_rr, calculations)) {
1075 		if(*calculations == MAX_NSEC3_ERRORS) {
1076 			verbose(VERB_ALGO, "nsec3: Could not find proof that the "
1077 				"candidate encloser was the closest encloser; "
1078 				"all attempted hash calculations were "
1079 				"erroneous; bogus");
1080 			return sec_status_bogus;
1081 		} else if(*calculations >= MAX_NSEC3_CALCULATIONS) {
1082 			verbose(VERB_ALGO, "nsec3: Could not find proof that the "
1083 				"candidate encloser was the closest encloser; "
1084 				"reached MAX_NSEC3_CALCULATIONS (%d); "
1085 				"unchecked still",
1086 				MAX_NSEC3_CALCULATIONS);
1087 			return sec_status_unchecked;
1088 		}
1089 		verbose(VERB_ALGO, "nsec3: Could not find proof that the "
1090 			"candidate encloser was the closest encloser");
1091 		return sec_status_bogus;
1092 	}
1093 	return sec_status_secure;
1094 }
1095 
1096 /** allocate a wildcard for the closest encloser */
1097 static uint8_t*
nsec3_ce_wildcard(struct regional * region,uint8_t * ce,size_t celen,size_t * len)1098 nsec3_ce_wildcard(struct regional* region, uint8_t* ce, size_t celen,
1099 	size_t* len)
1100 {
1101 	uint8_t* nm;
1102 	if(celen > LDNS_MAX_DOMAINLEN - 2)
1103 		return 0; /* too long */
1104 	nm = (uint8_t*)regional_alloc(region, celen+2);
1105 	if(!nm) {
1106 		log_err("nsec3 wildcard: out of memory");
1107 		return 0; /* alloc failure */
1108 	}
1109 	nm[0] = 1;
1110 	nm[1] = (uint8_t)'*'; /* wildcard label */
1111 	memmove(nm+2, ce, celen);
1112 	*len = celen+2;
1113 	return nm;
1114 }
1115 
1116 /** Do the name error proof */
1117 static enum sec_status
nsec3_do_prove_nameerror(struct module_env * env,struct nsec3_filter * flt,struct nsec3_cache_table * ct,struct query_info * qinfo,int * calc)1118 nsec3_do_prove_nameerror(struct module_env* env, struct nsec3_filter* flt,
1119 	struct nsec3_cache_table* ct, struct query_info* qinfo, int* calc)
1120 {
1121 	struct ce_response ce;
1122 	uint8_t* wc;
1123 	size_t wclen;
1124 	struct ub_packed_rrset_key* wc_rrset;
1125 	int wc_rr;
1126 	enum sec_status sec;
1127 
1128 	/* First locate and prove the closest encloser to qname. We will
1129 	 * use the variant that fails if the closest encloser turns out
1130 	 * to be qname. */
1131 	sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce, calc);
1132 	if(sec != sec_status_secure) {
1133 		if(sec == sec_status_bogus)
1134 			verbose(VERB_ALGO, "nsec3 nameerror proof: failed "
1135 				"to prove a closest encloser");
1136 		else if(sec == sec_status_unchecked)
1137 			verbose(VERB_ALGO, "nsec3 nameerror proof: will "
1138 				"continue proving closest encloser after "
1139 				"suspend");
1140 		else 	verbose(VERB_ALGO, "nsec3 nameerror proof: closest "
1141 				"nsec3 is an insecure delegation");
1142 		return sec;
1143 	}
1144 	log_nametypeclass(VERB_ALGO, "nsec3 nameerror: proven ce=", ce.ce,0,0);
1145 
1146 	/* At this point, we know that qname does not exist. Now we need
1147 	 * to prove that the wildcard does not exist. */
1148 	log_assert(ce.ce);
1149 	wc = nsec3_ce_wildcard(ct->region, ce.ce, ce.ce_len, &wclen);
1150 	if(!wc) {
1151 		verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove "
1152 			"that the applicable wildcard did not exist.");
1153 		return sec_status_bogus;
1154 	}
1155 	if(!find_covering_nsec3(env, flt, ct, wc, wclen, &wc_rrset, &wc_rr, calc)) {
1156 		if(*calc == MAX_NSEC3_ERRORS) {
1157 			verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove "
1158 				"that the applicable wildcard did not exist; "
1159 				"all attempted hash calculations were "
1160 				"erroneous; bogus");
1161 			return sec_status_bogus;
1162 		} else if(*calc >= MAX_NSEC3_CALCULATIONS) {
1163 			verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove "
1164 				"that the applicable wildcard did not exist; "
1165 				"reached MAX_NSEC3_CALCULATIONS (%d); "
1166 				"unchecked still",
1167 				MAX_NSEC3_CALCULATIONS);
1168 			return sec_status_unchecked;
1169 		}
1170 		verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove "
1171 			"that the applicable wildcard did not exist.");
1172 		return sec_status_bogus;
1173 	}
1174 
1175 	if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1176 		verbose(VERB_ALGO, "nsec3 nameerror proof: nc has optout");
1177 		return sec_status_insecure;
1178 	}
1179 	return sec_status_secure;
1180 }
1181 
1182 enum sec_status
nsec3_prove_nameerror(struct module_env * env,struct val_env * ve,struct ub_packed_rrset_key ** list,size_t num,struct query_info * qinfo,struct key_entry_key * kkey,struct nsec3_cache_table * ct,int * calc)1183 nsec3_prove_nameerror(struct module_env* env, struct val_env* ve,
1184 	struct ub_packed_rrset_key** list, size_t num,
1185 	struct query_info* qinfo, struct key_entry_key* kkey,
1186 	struct nsec3_cache_table* ct, int* calc)
1187 {
1188 	struct nsec3_filter flt;
1189 
1190 	if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1191 		return sec_status_bogus; /* no valid NSEC3s, bogus */
1192 	filter_init(&flt, list, num, qinfo); /* init RR iterator */
1193 	if(!flt.zone)
1194 		return sec_status_bogus; /* no RRs */
1195 	if(nsec3_iteration_count_high(ve, &flt, kkey))
1196 		return sec_status_insecure; /* iteration count too high */
1197 	log_nametypeclass(VERB_ALGO, "start nsec3 nameerror proof, zone",
1198 		flt.zone, 0, 0);
1199 	return nsec3_do_prove_nameerror(env, &flt, ct, qinfo, calc);
1200 }
1201 
1202 /*
1203  * No code to handle qtype=NSEC3 specially.
1204  * This existed in early drafts, but was later (-05) removed.
1205  */
1206 
1207 /** Do the nodata proof */
1208 static enum sec_status
nsec3_do_prove_nodata(struct module_env * env,struct nsec3_filter * flt,struct nsec3_cache_table * ct,struct query_info * qinfo,int * calc)1209 nsec3_do_prove_nodata(struct module_env* env, struct nsec3_filter* flt,
1210 	struct nsec3_cache_table* ct, struct query_info* qinfo,
1211 	int* calc)
1212 {
1213 	struct ce_response ce;
1214 	uint8_t* wc;
1215 	size_t wclen;
1216 	struct ub_packed_rrset_key* rrset;
1217 	int rr;
1218 	enum sec_status sec;
1219 
1220 	if(find_matching_nsec3(env, flt, ct, qinfo->qname, qinfo->qname_len,
1221 		&rrset, &rr, calc)) {
1222 		/* cases 1 and 2 */
1223 		if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1224 			verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1225 				"proved that type existed, bogus");
1226 			return sec_status_bogus;
1227 		} else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1228 			verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1229 				"proved that a CNAME existed, bogus");
1230 			return sec_status_bogus;
1231 		}
1232 
1233 		/*
1234 		 * If type DS: filter_init zone find already found a parent
1235 		 *   zone, so this nsec3 is from a parent zone.
1236 		 *   o can be not a delegation (unusual query for normal name,
1237 		 *   	no DS anyway, but we can verify that).
1238 		 *   o can be a delegation (which is the usual DS check).
1239 		 *   o may not have the SOA bit set (only the top of the
1240 		 *   	zone, which must have been above the name, has that).
1241 		 *   	Except for the root; which is checked by itself.
1242 		 *
1243 		 * If not type DS: matching nsec3 must not be a delegation.
1244 		 */
1245 		if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1246 			&& nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1247 			!dname_is_root(qinfo->qname)) {
1248 			verbose(VERB_ALGO, "proveNodata: apex NSEC3 "
1249 				"abused for no DS proof, bogus");
1250 			return sec_status_bogus;
1251 		} else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1252 			nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1253 			!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1254 			if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1255 				verbose(VERB_ALGO, "proveNodata: matching "
1256 					"NSEC3 is insecure delegation");
1257 				return sec_status_insecure;
1258 			}
1259 			verbose(VERB_ALGO, "proveNodata: matching "
1260 				"NSEC3 is a delegation, bogus");
1261 			return sec_status_bogus;
1262 		}
1263 		return sec_status_secure;
1264 	}
1265 	if(*calc == MAX_NSEC3_ERRORS) {
1266 		verbose(VERB_ALGO, "proveNodata: all attempted hash "
1267 			"calculations were erroneous while finding a matching "
1268 			"NSEC3, bogus");
1269 		return sec_status_bogus;
1270 	} else if(*calc >= MAX_NSEC3_CALCULATIONS) {
1271 		verbose(VERB_ALGO, "proveNodata: reached "
1272 			"MAX_NSEC3_CALCULATIONS (%d) while finding a "
1273 			"matching NSEC3; unchecked still",
1274 			MAX_NSEC3_CALCULATIONS);
1275 		return sec_status_unchecked;
1276 	}
1277 
1278 	/* For cases 3 - 5, we need the proven closest encloser, and it
1279 	 * can't match qname. Although, at this point, we know that it
1280 	 * won't since we just checked that. */
1281 	sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce, calc);
1282 	if(sec == sec_status_bogus) {
1283 		verbose(VERB_ALGO, "proveNodata: did not match qname, "
1284 		          "nor found a proven closest encloser.");
1285 		return sec_status_bogus;
1286 	} else if(sec==sec_status_insecure && qinfo->qtype!=LDNS_RR_TYPE_DS){
1287 		verbose(VERB_ALGO, "proveNodata: closest nsec3 is insecure "
1288 		          "delegation.");
1289 		return sec_status_insecure;
1290 	} else if(sec==sec_status_unchecked) {
1291 		return sec_status_unchecked;
1292 	}
1293 
1294 	/* Case 3: removed */
1295 
1296 	/* Case 4: */
1297 	log_assert(ce.ce);
1298 	wc = nsec3_ce_wildcard(ct->region, ce.ce, ce.ce_len, &wclen);
1299 	if(wc && find_matching_nsec3(env, flt, ct, wc, wclen, &rrset, &rr,
1300 		calc)) {
1301 		/* found wildcard */
1302 		if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1303 			verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1304 				"wildcard had qtype, bogus");
1305 			return sec_status_bogus;
1306 		} else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1307 			verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1308 				"wildcard had a CNAME, bogus");
1309 			return sec_status_bogus;
1310 		}
1311 		if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1312 			&& nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1313 			verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1314 				"wildcard for no DS proof has a SOA, bogus");
1315 			return sec_status_bogus;
1316 		} else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1317 			nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1318 			!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1319 			verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1320 				"wildcard is a delegation, bogus");
1321 			return sec_status_bogus;
1322 		}
1323 		/* everything is peachy keen, except for optout spans */
1324 		if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1325 			verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1326 				"wildcard is in optout range, insecure");
1327 			return sec_status_insecure;
1328 		}
1329 		return sec_status_secure;
1330 	}
1331 	if(*calc == MAX_NSEC3_ERRORS) {
1332 		verbose(VERB_ALGO, "nsec3 nodata proof: all attempted hash "
1333 			"calculations were erroneous while matching "
1334 			"wildcard, bogus");
1335 		return sec_status_bogus;
1336 	} else if(*calc >= MAX_NSEC3_CALCULATIONS) {
1337 		verbose(VERB_ALGO, "nsec3 nodata proof: reached "
1338 			"MAX_NSEC3_CALCULATIONS (%d) while matching "
1339 			"wildcard, unchecked still",
1340 			MAX_NSEC3_CALCULATIONS);
1341 		return sec_status_unchecked;
1342 	}
1343 
1344 	/* Case 5: */
1345 	/* Due to forwarders, cnames, and other collating effects, we
1346 	 * can see the ordinary unsigned data from a zone beneath an
1347 	 * insecure delegation under an optout here */
1348 	if(!ce.nc_rrset) {
1349 		verbose(VERB_ALGO, "nsec3 nodata proof: no next closer nsec3");
1350 		return sec_status_bogus;
1351 	}
1352 
1353 	/* We need to make sure that the covering NSEC3 is opt-out. */
1354 	log_assert(ce.nc_rrset);
1355 	if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1356 		if(qinfo->qtype == LDNS_RR_TYPE_DS)
1357 		  verbose(VERB_ALGO, "proveNodata: covering NSEC3 was not "
1358 			"opt-out in an opt-out DS NOERROR/NODATA case.");
1359 		else verbose(VERB_ALGO, "proveNodata: could not find matching "
1360 			"NSEC3, nor matching wildcard, nor optout NSEC3 "
1361 			"-- no more options, bogus.");
1362 		return sec_status_bogus;
1363 	}
1364 	/* RFC5155 section 9.2: if nc has optout then no AD flag set */
1365 	return sec_status_insecure;
1366 }
1367 
1368 enum sec_status
nsec3_prove_nodata(struct module_env * env,struct val_env * ve,struct ub_packed_rrset_key ** list,size_t num,struct query_info * qinfo,struct key_entry_key * kkey,struct nsec3_cache_table * ct,int * calc)1369 nsec3_prove_nodata(struct module_env* env, struct val_env* ve,
1370 	struct ub_packed_rrset_key** list, size_t num,
1371 	struct query_info* qinfo, struct key_entry_key* kkey,
1372 	struct nsec3_cache_table* ct, int* calc)
1373 {
1374 	struct nsec3_filter flt;
1375 
1376 	if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1377 		return sec_status_bogus; /* no valid NSEC3s, bogus */
1378 	filter_init(&flt, list, num, qinfo); /* init RR iterator */
1379 	if(!flt.zone)
1380 		return sec_status_bogus; /* no RRs */
1381 	if(nsec3_iteration_count_high(ve, &flt, kkey))
1382 		return sec_status_insecure; /* iteration count too high */
1383 	return nsec3_do_prove_nodata(env, &flt, ct, qinfo, calc);
1384 }
1385 
1386 enum sec_status
nsec3_prove_wildcard(struct module_env * env,struct val_env * ve,struct ub_packed_rrset_key ** list,size_t num,struct query_info * qinfo,struct key_entry_key * kkey,uint8_t * wc,struct nsec3_cache_table * ct,int * calc)1387 nsec3_prove_wildcard(struct module_env* env, struct val_env* ve,
1388         struct ub_packed_rrset_key** list, size_t num,
1389 	struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc,
1390 	struct nsec3_cache_table* ct, int* calc)
1391 {
1392 	struct nsec3_filter flt;
1393 	struct ce_response ce;
1394 	uint8_t* nc;
1395 	size_t nc_len;
1396 	size_t wclen;
1397 	(void)dname_count_size_labels(wc, &wclen);
1398 
1399 	if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1400 		return sec_status_bogus; /* no valid NSEC3s, bogus */
1401 	filter_init(&flt, list, num, qinfo); /* init RR iterator */
1402 	if(!flt.zone)
1403 		return sec_status_bogus; /* no RRs */
1404 	if(nsec3_iteration_count_high(ve, &flt, kkey))
1405 		return sec_status_insecure; /* iteration count too high */
1406 
1407 	/* We know what the (purported) closest encloser is by just
1408 	 * looking at the supposed generating wildcard.
1409 	 * The *. has already been removed from the wc name.
1410 	 */
1411 	memset(&ce, 0, sizeof(ce));
1412 	ce.ce = wc;
1413 	ce.ce_len = wclen;
1414 
1415 	/* Now we still need to prove that the original data did not exist.
1416 	 * Otherwise, we need to show that the next closer name is covered. */
1417 	next_closer(qinfo->qname, qinfo->qname_len, ce.ce, &nc, &nc_len);
1418 	if(!find_covering_nsec3(env, &flt, ct, nc, nc_len,
1419 		&ce.nc_rrset, &ce.nc_rr, calc)) {
1420 		if(*calc == MAX_NSEC3_ERRORS) {
1421 			verbose(VERB_ALGO, "proveWildcard: did not find a "
1422 				"covering NSEC3 that covered the next closer "
1423 				"name; all attempted hash calculations were "
1424 				"erroneous; bogus");
1425 			return sec_status_bogus;
1426 		} else if(*calc >= MAX_NSEC3_CALCULATIONS) {
1427 			verbose(VERB_ALGO, "proveWildcard: did not find a "
1428 				"covering NSEC3 that covered the next closer "
1429 				"name; reached MAX_NSEC3_CALCULATIONS "
1430 				"(%d); unchecked still",
1431 				MAX_NSEC3_CALCULATIONS);
1432 			return sec_status_unchecked;
1433 		}
1434 		verbose(VERB_ALGO, "proveWildcard: did not find a covering "
1435 			"NSEC3 that covered the next closer name.");
1436 		return sec_status_bogus;
1437 	}
1438 	if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1439 		verbose(VERB_ALGO, "proveWildcard: NSEC3 optout");
1440 		return sec_status_insecure;
1441 	}
1442 	return sec_status_secure;
1443 }
1444 
1445 /** test if list is all secure */
1446 static int
list_is_secure(struct module_env * env,struct val_env * ve,struct ub_packed_rrset_key ** list,size_t num,struct key_entry_key * kkey,char ** reason,sldns_ede_code * reason_bogus,struct module_qstate * qstate,char * reasonbuf,size_t reasonlen)1447 list_is_secure(struct module_env* env, struct val_env* ve,
1448 	struct ub_packed_rrset_key** list, size_t num,
1449 	struct key_entry_key* kkey, char** reason, sldns_ede_code *reason_bogus,
1450 	struct module_qstate* qstate, char* reasonbuf, size_t reasonlen)
1451 {
1452 	struct packed_rrset_data* d;
1453 	size_t i;
1454 	int verified = 0;
1455 	for(i=0; i<num; i++) {
1456 		d = (struct packed_rrset_data*)list[i]->entry.data;
1457 		if(list[i]->rk.type != htons(LDNS_RR_TYPE_NSEC3))
1458 			continue;
1459 		if(d->security == sec_status_secure)
1460 			continue;
1461 		rrset_check_sec_status(env->rrset_cache, list[i], *env->now);
1462 		if(d->security == sec_status_secure)
1463 			continue;
1464 		d->security = val_verify_rrset_entry(env, ve, list[i], kkey,
1465 			reason, reason_bogus, LDNS_SECTION_AUTHORITY, qstate,
1466 			&verified, reasonbuf, reasonlen);
1467 		if(d->security != sec_status_secure) {
1468 			verbose(VERB_ALGO, "NSEC3 did not verify");
1469 			return 0;
1470 		}
1471 		rrset_update_sec_status(env->rrset_cache, list[i], *env->now);
1472 	}
1473 	return 1;
1474 }
1475 
1476 enum sec_status
nsec3_prove_nods(struct module_env * env,struct val_env * ve,struct ub_packed_rrset_key ** list,size_t num,struct query_info * qinfo,struct key_entry_key * kkey,char ** reason,sldns_ede_code * reason_bogus,struct module_qstate * qstate,struct nsec3_cache_table * ct,char * reasonbuf,size_t reasonlen)1477 nsec3_prove_nods(struct module_env* env, struct val_env* ve,
1478 	struct ub_packed_rrset_key** list, size_t num,
1479 	struct query_info* qinfo, struct key_entry_key* kkey, char** reason,
1480 	sldns_ede_code* reason_bogus, struct module_qstate* qstate,
1481 	struct nsec3_cache_table* ct, char* reasonbuf, size_t reasonlen)
1482 {
1483 	struct nsec3_filter flt;
1484 	struct ce_response ce;
1485 	struct ub_packed_rrset_key* rrset;
1486 	int rr;
1487 	int calc = 0;
1488 	enum sec_status sec;
1489 
1490 	log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);
1491 
1492 	if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) {
1493 		*reason = "no valid NSEC3s";
1494 		return sec_status_bogus; /* no valid NSEC3s, bogus */
1495 	}
1496 	if(!list_is_secure(env, ve, list, num, kkey, reason, reason_bogus,
1497 		qstate, reasonbuf, reasonlen)) {
1498 		*reason = "not all NSEC3 records secure";
1499 		return sec_status_bogus; /* not all NSEC3 records secure */
1500 	}
1501 	filter_init(&flt, list, num, qinfo); /* init RR iterator */
1502 	if(!flt.zone) {
1503 		*reason = "no NSEC3 records";
1504 		return sec_status_bogus; /* no RRs */
1505 	}
1506 	if(nsec3_iteration_count_high(ve, &flt, kkey))
1507 		return sec_status_insecure; /* iteration count too high */
1508 
1509 	/* Look for a matching NSEC3 to qname -- this is the normal
1510 	 * NODATA case. */
1511 	if(find_matching_nsec3(env, &flt, ct, qinfo->qname, qinfo->qname_len,
1512 		&rrset, &rr, &calc)) {
1513 		/* If the matching NSEC3 has the SOA bit set, it is from
1514 		 * the wrong zone (the child instead of the parent). If
1515 		 * it has the DS bit set, then we were lied to. */
1516 		if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1517 			qinfo->qname_len != 1) {
1518 			verbose(VERB_ALGO, "nsec3 provenods: NSEC3 is from"
1519 				" child zone, bogus");
1520 			*reason = "NSEC3 from child zone";
1521 			return sec_status_bogus;
1522 		} else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1523 			verbose(VERB_ALGO, "nsec3 provenods: NSEC3 has qtype"
1524 				" DS, bogus");
1525 			*reason = "NSEC3 has DS in bitmap";
1526 			return sec_status_bogus;
1527 		}
1528 		/* If the NSEC3 RR doesn't have the NS bit set, then
1529 		 * this wasn't a delegation point. */
1530 		if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS))
1531 			return sec_status_indeterminate;
1532 		/* Otherwise, this proves no DS. */
1533 		return sec_status_secure;
1534 	}
1535 	if(calc == MAX_NSEC3_ERRORS) {
1536 		verbose(VERB_ALGO, "nsec3 provenods: all attempted hash "
1537 			"calculations were erroneous while finding a matching "
1538 			"NSEC3, bogus");
1539 		return sec_status_bogus;
1540 	} else if(calc >= MAX_NSEC3_CALCULATIONS) {
1541 		verbose(VERB_ALGO, "nsec3 provenods: reached "
1542 			"MAX_NSEC3_CALCULATIONS (%d) while finding a "
1543 			"matching NSEC3, unchecked still",
1544 			MAX_NSEC3_CALCULATIONS);
1545 		return sec_status_unchecked;
1546 	}
1547 
1548 	/* Otherwise, we are probably in the opt-out case. */
1549 	sec = nsec3_prove_closest_encloser(env, &flt, ct, qinfo, 1, &ce, &calc);
1550 	if(sec == sec_status_unchecked) {
1551 		return sec_status_unchecked;
1552 	} else if(sec != sec_status_secure) {
1553 		/* an insecure delegation *above* the qname does not prove
1554 		 * anything about this qname exactly, and bogus is bogus */
1555 		verbose(VERB_ALGO, "nsec3 provenods: did not match qname, "
1556 		          "nor found a proven closest encloser.");
1557 		*reason = "no NSEC3 closest encloser";
1558 		return sec_status_bogus;
1559 	}
1560 
1561 	/* robust extra check */
1562 	if(!ce.nc_rrset) {
1563 		verbose(VERB_ALGO, "nsec3 nods proof: no next closer nsec3");
1564 		*reason = "no NSEC3 next closer";
1565 		return sec_status_bogus;
1566 	}
1567 
1568 	/* we had the closest encloser proof, then we need to check that the
1569 	 * covering NSEC3 was opt-out -- the proveClosestEncloser step already
1570 	 * checked to see if the closest encloser was a delegation or DNAME.
1571 	 */
1572 	log_assert(ce.nc_rrset);
1573 	if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1574 		verbose(VERB_ALGO, "nsec3 provenods: covering NSEC3 was not "
1575 			"opt-out in an opt-out DS NOERROR/NODATA case.");
1576 		*reason = "covering NSEC3 was not opt-out in an opt-out "
1577 			"DS NOERROR/NODATA case";
1578 		return sec_status_bogus;
1579 	}
1580 	/* RFC5155 section 9.2: if nc has optout then no AD flag set */
1581 	return sec_status_insecure;
1582 }
1583 
1584 enum sec_status
nsec3_prove_nxornodata(struct module_env * env,struct val_env * ve,struct ub_packed_rrset_key ** list,size_t num,struct query_info * qinfo,struct key_entry_key * kkey,int * nodata,struct nsec3_cache_table * ct,int * calc)1585 nsec3_prove_nxornodata(struct module_env* env, struct val_env* ve,
1586 	struct ub_packed_rrset_key** list, size_t num,
1587 	struct query_info* qinfo, struct key_entry_key* kkey, int* nodata,
1588 	struct  nsec3_cache_table* ct, int* calc)
1589 {
1590 	enum sec_status sec, secnx;
1591 	struct nsec3_filter flt;
1592 	*nodata = 0;
1593 
1594 	if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1595 		return sec_status_bogus; /* no valid NSEC3s, bogus */
1596 	filter_init(&flt, list, num, qinfo); /* init RR iterator */
1597 	if(!flt.zone)
1598 		return sec_status_bogus; /* no RRs */
1599 	if(nsec3_iteration_count_high(ve, &flt, kkey))
1600 		return sec_status_insecure; /* iteration count too high */
1601 
1602 	/* try nxdomain and nodata after another, while keeping the
1603 	 * hash cache intact */
1604 
1605 	secnx = nsec3_do_prove_nameerror(env, &flt, ct, qinfo, calc);
1606 	if(secnx==sec_status_secure)
1607 		return sec_status_secure;
1608 	else if(secnx == sec_status_unchecked)
1609 		return sec_status_unchecked;
1610 	sec = nsec3_do_prove_nodata(env, &flt, ct, qinfo, calc);
1611 	if(sec==sec_status_secure) {
1612 		*nodata = 1;
1613 	} else if(sec == sec_status_insecure) {
1614 		*nodata = 1;
1615 	} else if(secnx == sec_status_insecure) {
1616 		sec = sec_status_insecure;
1617 	} else if(sec == sec_status_unchecked) {
1618 		return sec_status_unchecked;
1619 	}
1620 	return sec;
1621 }
1622