xref: /freebsd/contrib/unbound/validator/val_sigcrypt.c (revision 13ea0450a9c8742119d36f3bf8f47accdce46e54)
1 /*
2  * validator/val_sigcrypt.c - validator signature crypto 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 signature verification and checking, the
41  * bridging between RR wireformat data and crypto calls.
42  */
43 #include "config.h"
44 #include "validator/val_sigcrypt.h"
45 #include "validator/val_secalgo.h"
46 #include "validator/validator.h"
47 #include "util/data/msgreply.h"
48 #include "util/data/msgparse.h"
49 #include "util/data/dname.h"
50 #include "util/rbtree.h"
51 #include "util/module.h"
52 #include "util/net_help.h"
53 #include "util/regional.h"
54 #include "util/config_file.h"
55 #include "sldns/keyraw.h"
56 #include "sldns/sbuffer.h"
57 #include "sldns/parseutil.h"
58 #include "sldns/wire2str.h"
59 
60 #include <ctype.h>
61 #if !defined(HAVE_SSL) && !defined(HAVE_NSS) && !defined(HAVE_NETTLE)
62 #error "Need crypto library to do digital signature cryptography"
63 #endif
64 
65 #ifdef HAVE_OPENSSL_ERR_H
66 #include <openssl/err.h>
67 #endif
68 
69 #ifdef HAVE_OPENSSL_RAND_H
70 #include <openssl/rand.h>
71 #endif
72 
73 #ifdef HAVE_OPENSSL_CONF_H
74 #include <openssl/conf.h>
75 #endif
76 
77 #ifdef HAVE_OPENSSL_ENGINE_H
78 #include <openssl/engine.h>
79 #endif
80 
81 /** return number of rrs in an rrset */
82 static size_t
83 rrset_get_count(struct ub_packed_rrset_key* rrset)
84 {
85 	struct packed_rrset_data* d = (struct packed_rrset_data*)
86 	rrset->entry.data;
87 	if(!d) return 0;
88 	return d->count;
89 }
90 
91 /**
92  * Get RR signature count
93  */
94 static size_t
95 rrset_get_sigcount(struct ub_packed_rrset_key* k)
96 {
97 	struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
98 	return d->rrsig_count;
99 }
100 
101 /**
102  * Get signature keytag value
103  * @param k: rrset (with signatures)
104  * @param sig_idx: signature index.
105  * @return keytag or 0 if malformed rrsig.
106  */
107 static uint16_t
108 rrset_get_sig_keytag(struct ub_packed_rrset_key* k, size_t sig_idx)
109 {
110 	uint16_t t;
111 	struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
112 	log_assert(sig_idx < d->rrsig_count);
113 	if(d->rr_len[d->count + sig_idx] < 2+18)
114 		return 0;
115 	memmove(&t, d->rr_data[d->count + sig_idx]+2+16, 2);
116 	return ntohs(t);
117 }
118 
119 /**
120  * Get signature signing algorithm value
121  * @param k: rrset (with signatures)
122  * @param sig_idx: signature index.
123  * @return algo or 0 if malformed rrsig.
124  */
125 static int
126 rrset_get_sig_algo(struct ub_packed_rrset_key* k, size_t sig_idx)
127 {
128 	struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
129 	log_assert(sig_idx < d->rrsig_count);
130 	if(d->rr_len[d->count + sig_idx] < 2+3)
131 		return 0;
132 	return (int)d->rr_data[d->count + sig_idx][2+2];
133 }
134 
135 /** get rdata pointer and size */
136 static void
137 rrset_get_rdata(struct ub_packed_rrset_key* k, size_t idx, uint8_t** rdata,
138 	size_t* len)
139 {
140 	struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
141 	log_assert(d && idx < (d->count + d->rrsig_count));
142 	*rdata = d->rr_data[idx];
143 	*len = d->rr_len[idx];
144 }
145 
146 uint16_t
147 dnskey_get_flags(struct ub_packed_rrset_key* k, size_t idx)
148 {
149 	uint8_t* rdata;
150 	size_t len;
151 	uint16_t f;
152 	rrset_get_rdata(k, idx, &rdata, &len);
153 	if(len < 2+2)
154 		return 0;
155 	memmove(&f, rdata+2, 2);
156 	f = ntohs(f);
157 	return f;
158 }
159 
160 /**
161  * Get DNSKEY protocol value from rdata
162  * @param k: DNSKEY rrset.
163  * @param idx: which key.
164  * @return protocol octet value
165  */
166 static int
167 dnskey_get_protocol(struct ub_packed_rrset_key* k, size_t idx)
168 {
169 	uint8_t* rdata;
170 	size_t len;
171 	rrset_get_rdata(k, idx, &rdata, &len);
172 	if(len < 2+4)
173 		return 0;
174 	return (int)rdata[2+2];
175 }
176 
177 int
178 dnskey_get_algo(struct ub_packed_rrset_key* k, size_t idx)
179 {
180 	uint8_t* rdata;
181 	size_t len;
182 	rrset_get_rdata(k, idx, &rdata, &len);
183 	if(len < 2+4)
184 		return 0;
185 	return (int)rdata[2+3];
186 }
187 
188 /** get public key rdata field from a dnskey RR and do some checks */
189 static void
190 dnskey_get_pubkey(struct ub_packed_rrset_key* k, size_t idx,
191 	unsigned char** pk, unsigned int* pklen)
192 {
193 	uint8_t* rdata;
194 	size_t len;
195 	rrset_get_rdata(k, idx, &rdata, &len);
196 	if(len < 2+5) {
197 		*pk = NULL;
198 		*pklen = 0;
199 		return;
200 	}
201 	*pk = (unsigned char*)rdata+2+4;
202 	*pklen = (unsigned)len-2-4;
203 }
204 
205 int
206 ds_get_key_algo(struct ub_packed_rrset_key* k, size_t idx)
207 {
208 	uint8_t* rdata;
209 	size_t len;
210 	rrset_get_rdata(k, idx, &rdata, &len);
211 	if(len < 2+3)
212 		return 0;
213 	return (int)rdata[2+2];
214 }
215 
216 int
217 ds_get_digest_algo(struct ub_packed_rrset_key* k, size_t idx)
218 {
219 	uint8_t* rdata;
220 	size_t len;
221 	rrset_get_rdata(k, idx, &rdata, &len);
222 	if(len < 2+4)
223 		return 0;
224 	return (int)rdata[2+3];
225 }
226 
227 uint16_t
228 ds_get_keytag(struct ub_packed_rrset_key* ds_rrset, size_t ds_idx)
229 {
230 	uint16_t t;
231 	uint8_t* rdata;
232 	size_t len;
233 	rrset_get_rdata(ds_rrset, ds_idx, &rdata, &len);
234 	if(len < 2+2)
235 		return 0;
236 	memmove(&t, rdata+2, 2);
237 	return ntohs(t);
238 }
239 
240 /**
241  * Return pointer to the digest in a DS RR.
242  * @param k: DS rrset.
243  * @param idx: which DS.
244  * @param digest: digest data is returned.
245  *	on error, this is NULL.
246  * @param len: length of digest is returned.
247  *	on error, the length is 0.
248  */
249 static void
250 ds_get_sigdata(struct ub_packed_rrset_key* k, size_t idx, uint8_t** digest,
251         size_t* len)
252 {
253 	uint8_t* rdata;
254 	size_t rdlen;
255 	rrset_get_rdata(k, idx, &rdata, &rdlen);
256 	if(rdlen < 2+5) {
257 		*digest = NULL;
258 		*len = 0;
259 		return;
260 	}
261 	*digest = rdata + 2 + 4;
262 	*len = rdlen - 2 - 4;
263 }
264 
265 /**
266  * Return size of DS digest according to its hash algorithm.
267  * @param k: DS rrset.
268  * @param idx: which DS.
269  * @return size in bytes of digest, or 0 if not supported.
270  */
271 static size_t
272 ds_digest_size_algo(struct ub_packed_rrset_key* k, size_t idx)
273 {
274 	return ds_digest_size_supported(ds_get_digest_algo(k, idx));
275 }
276 
277 /**
278  * Create a DS digest for a DNSKEY entry.
279  *
280  * @param env: module environment. Uses scratch space.
281  * @param dnskey_rrset: DNSKEY rrset.
282  * @param dnskey_idx: index of RR in rrset.
283  * @param ds_rrset: DS rrset
284  * @param ds_idx: index of RR in DS rrset.
285  * @param digest: digest is returned in here (must be correctly sized).
286  * @return false on error.
287  */
288 static int
289 ds_create_dnskey_digest(struct module_env* env,
290 	struct ub_packed_rrset_key* dnskey_rrset, size_t dnskey_idx,
291 	struct ub_packed_rrset_key* ds_rrset, size_t ds_idx,
292 	uint8_t* digest)
293 {
294 	sldns_buffer* b = env->scratch_buffer;
295 	uint8_t* dnskey_rdata;
296 	size_t dnskey_len;
297 	rrset_get_rdata(dnskey_rrset, dnskey_idx, &dnskey_rdata, &dnskey_len);
298 
299 	/* create digest source material in buffer
300 	 * digest = digest_algorithm( DNSKEY owner name | DNSKEY RDATA);
301 	 *	DNSKEY RDATA = Flags | Protocol | Algorithm | Public Key. */
302 	sldns_buffer_clear(b);
303 	sldns_buffer_write(b, dnskey_rrset->rk.dname,
304 		dnskey_rrset->rk.dname_len);
305 	query_dname_tolower(sldns_buffer_begin(b));
306 	sldns_buffer_write(b, dnskey_rdata+2, dnskey_len-2); /* skip rdatalen*/
307 	sldns_buffer_flip(b);
308 
309 	return secalgo_ds_digest(ds_get_digest_algo(ds_rrset, ds_idx),
310 		(unsigned char*)sldns_buffer_begin(b), sldns_buffer_limit(b),
311 		(unsigned char*)digest);
312 }
313 
314 int ds_digest_match_dnskey(struct module_env* env,
315 	struct ub_packed_rrset_key* dnskey_rrset, size_t dnskey_idx,
316 	struct ub_packed_rrset_key* ds_rrset, size_t ds_idx)
317 {
318 	uint8_t* ds;	/* DS digest */
319 	size_t dslen;
320 	uint8_t* digest; /* generated digest */
321 	size_t digestlen = ds_digest_size_algo(ds_rrset, ds_idx);
322 
323 	if(digestlen == 0) {
324 		verbose(VERB_QUERY, "DS fail: not supported, or DS RR "
325 			"format error");
326 		return 0; /* not supported, or DS RR format error */
327 	}
328 #ifndef USE_SHA1
329 	if(fake_sha1 && ds_get_digest_algo(ds_rrset, ds_idx)==LDNS_SHA1)
330 		return 1;
331 #endif
332 
333 	/* check digest length in DS with length from hash function */
334 	ds_get_sigdata(ds_rrset, ds_idx, &ds, &dslen);
335 	if(!ds || dslen != digestlen) {
336 		verbose(VERB_QUERY, "DS fail: DS RR algo and digest do not "
337 			"match each other");
338 		return 0; /* DS algorithm and digest do not match */
339 	}
340 
341 	digest = regional_alloc(env->scratch, digestlen);
342 	if(!digest) {
343 		verbose(VERB_QUERY, "DS fail: out of memory");
344 		return 0; /* mem error */
345 	}
346 	if(!ds_create_dnskey_digest(env, dnskey_rrset, dnskey_idx, ds_rrset,
347 		ds_idx, digest)) {
348 		verbose(VERB_QUERY, "DS fail: could not calc key digest");
349 		return 0; /* digest algo failed */
350 	}
351 	if(memcmp(digest, ds, dslen) != 0) {
352 		verbose(VERB_QUERY, "DS fail: digest is different");
353 		return 0; /* digest different */
354 	}
355 	return 1;
356 }
357 
358 int
359 ds_digest_algo_is_supported(struct ub_packed_rrset_key* ds_rrset,
360 	size_t ds_idx)
361 {
362 	return (ds_digest_size_algo(ds_rrset, ds_idx) != 0);
363 }
364 
365 int
366 ds_key_algo_is_supported(struct ub_packed_rrset_key* ds_rrset,
367 	size_t ds_idx)
368 {
369 	return dnskey_algo_id_is_supported(ds_get_key_algo(ds_rrset, ds_idx));
370 }
371 
372 uint16_t
373 dnskey_calc_keytag(struct ub_packed_rrset_key* dnskey_rrset, size_t dnskey_idx)
374 {
375 	uint8_t* data;
376 	size_t len;
377 	rrset_get_rdata(dnskey_rrset, dnskey_idx, &data, &len);
378 	/* do not pass rdatalen to ldns */
379 	return sldns_calc_keytag_raw(data+2, len-2);
380 }
381 
382 int dnskey_algo_is_supported(struct ub_packed_rrset_key* dnskey_rrset,
383         size_t dnskey_idx)
384 {
385 	return dnskey_algo_id_is_supported(dnskey_get_algo(dnskey_rrset,
386 		dnskey_idx));
387 }
388 
389 void algo_needs_init_dnskey_add(struct algo_needs* n,
390         struct ub_packed_rrset_key* dnskey, uint8_t* sigalg)
391 {
392 	uint8_t algo;
393 	size_t i, total = n->num;
394 	size_t num = rrset_get_count(dnskey);
395 
396 	for(i=0; i<num; i++) {
397 		algo = (uint8_t)dnskey_get_algo(dnskey, i);
398 		if(!dnskey_algo_id_is_supported((int)algo))
399 			continue;
400 		if(n->needs[algo] == 0) {
401 			n->needs[algo] = 1;
402 			sigalg[total] = algo;
403 			total++;
404 		}
405 	}
406 	sigalg[total] = 0;
407 	n->num = total;
408 }
409 
410 void algo_needs_init_list(struct algo_needs* n, uint8_t* sigalg)
411 {
412 	uint8_t algo;
413 	size_t total = 0;
414 
415 	memset(n->needs, 0, sizeof(uint8_t)*ALGO_NEEDS_MAX);
416 	while( (algo=*sigalg++) != 0) {
417 		log_assert(dnskey_algo_id_is_supported((int)algo));
418 		log_assert(n->needs[algo] == 0);
419 		n->needs[algo] = 1;
420 		total++;
421 	}
422 	n->num = total;
423 }
424 
425 void algo_needs_init_ds(struct algo_needs* n, struct ub_packed_rrset_key* ds,
426 	int fav_ds_algo, uint8_t* sigalg)
427 {
428 	uint8_t algo;
429 	size_t i, total = 0;
430 	size_t num = rrset_get_count(ds);
431 
432 	memset(n->needs, 0, sizeof(uint8_t)*ALGO_NEEDS_MAX);
433 	for(i=0; i<num; i++) {
434 		if(ds_get_digest_algo(ds, i) != fav_ds_algo)
435 			continue;
436 		algo = (uint8_t)ds_get_key_algo(ds, i);
437 		if(!dnskey_algo_id_is_supported((int)algo))
438 			continue;
439 		log_assert(algo != 0); /* we do not support 0 and is EOS */
440 		if(n->needs[algo] == 0) {
441 			n->needs[algo] = 1;
442 			sigalg[total] = algo;
443 			total++;
444 		}
445 	}
446 	sigalg[total] = 0;
447 	n->num = total;
448 }
449 
450 int algo_needs_set_secure(struct algo_needs* n, uint8_t algo)
451 {
452 	if(n->needs[algo]) {
453 		n->needs[algo] = 0;
454 		n->num --;
455 		if(n->num == 0) /* done! */
456 			return 1;
457 	}
458 	return 0;
459 }
460 
461 void algo_needs_set_bogus(struct algo_needs* n, uint8_t algo)
462 {
463 	if(n->needs[algo]) n->needs[algo] = 2; /* need it, but bogus */
464 }
465 
466 size_t algo_needs_num_missing(struct algo_needs* n)
467 {
468 	return n->num;
469 }
470 
471 int algo_needs_missing(struct algo_needs* n)
472 {
473 	int i;
474 	/* first check if a needed algo was bogus - report that */
475 	for(i=0; i<ALGO_NEEDS_MAX; i++)
476 		if(n->needs[i] == 2)
477 			return 0;
478 	/* now check which algo is missing */
479 	for(i=0; i<ALGO_NEEDS_MAX; i++)
480 		if(n->needs[i] == 1)
481 			return i;
482 	return 0;
483 }
484 
485 enum sec_status
486 dnskeyset_verify_rrset(struct module_env* env, struct val_env* ve,
487 	struct ub_packed_rrset_key* rrset, struct ub_packed_rrset_key* dnskey,
488 	uint8_t* sigalg, char** reason, sldns_pkt_section section,
489 	struct module_qstate* qstate)
490 {
491 	enum sec_status sec;
492 	size_t i, num;
493 	rbtree_type* sortree = NULL;
494 	/* make sure that for all DNSKEY algorithms there are valid sigs */
495 	struct algo_needs needs;
496 	int alg;
497 
498 	num = rrset_get_sigcount(rrset);
499 	if(num == 0) {
500 		verbose(VERB_QUERY, "rrset failed to verify due to a lack of "
501 			"signatures");
502 		*reason = "no signatures";
503 		return sec_status_bogus;
504 	}
505 
506 	if(sigalg) {
507 		algo_needs_init_list(&needs, sigalg);
508 		if(algo_needs_num_missing(&needs) == 0) {
509 			verbose(VERB_QUERY, "zone has no known algorithms");
510 			*reason = "zone has no known algorithms";
511 			return sec_status_insecure;
512 		}
513 	}
514 	for(i=0; i<num; i++) {
515 		sec = dnskeyset_verify_rrset_sig(env, ve, *env->now, rrset,
516 			dnskey, i, &sortree, reason, section, qstate);
517 		/* see which algorithm has been fixed up */
518 		if(sec == sec_status_secure) {
519 			if(!sigalg)
520 				return sec; /* done! */
521 			else if(algo_needs_set_secure(&needs,
522 				(uint8_t)rrset_get_sig_algo(rrset, i)))
523 				return sec; /* done! */
524 		} else if(sigalg && sec == sec_status_bogus) {
525 			algo_needs_set_bogus(&needs,
526 				(uint8_t)rrset_get_sig_algo(rrset, i));
527 		}
528 	}
529 	if(sigalg && (alg=algo_needs_missing(&needs)) != 0) {
530 		verbose(VERB_ALGO, "rrset failed to verify: "
531 			"no valid signatures for %d algorithms",
532 			(int)algo_needs_num_missing(&needs));
533 		algo_needs_reason(env, alg, reason, "no signatures");
534 	} else {
535 		verbose(VERB_ALGO, "rrset failed to verify: "
536 			"no valid signatures");
537 	}
538 	return sec_status_bogus;
539 }
540 
541 void algo_needs_reason(struct module_env* env, int alg, char** reason, char* s)
542 {
543 	char buf[256];
544 	sldns_lookup_table *t = sldns_lookup_by_id(sldns_algorithms, alg);
545 	if(t&&t->name)
546 		snprintf(buf, sizeof(buf), "%s with algorithm %s", s, t->name);
547 	else	snprintf(buf, sizeof(buf), "%s with algorithm ALG%u", s,
548 			(unsigned)alg);
549 	*reason = regional_strdup(env->scratch, buf);
550 	if(!*reason)
551 		*reason = s;
552 }
553 
554 enum sec_status
555 dnskey_verify_rrset(struct module_env* env, struct val_env* ve,
556         struct ub_packed_rrset_key* rrset, struct ub_packed_rrset_key* dnskey,
557 	size_t dnskey_idx, char** reason, sldns_pkt_section section,
558 	struct module_qstate* qstate)
559 {
560 	enum sec_status sec;
561 	size_t i, num, numchecked = 0;
562 	rbtree_type* sortree = NULL;
563 	int buf_canon = 0;
564 	uint16_t tag = dnskey_calc_keytag(dnskey, dnskey_idx);
565 	int algo = dnskey_get_algo(dnskey, dnskey_idx);
566 
567 	num = rrset_get_sigcount(rrset);
568 	if(num == 0) {
569 		verbose(VERB_QUERY, "rrset failed to verify due to a lack of "
570 			"signatures");
571 		*reason = "no signatures";
572 		return sec_status_bogus;
573 	}
574 	for(i=0; i<num; i++) {
575 		/* see if sig matches keytag and algo */
576 		if(algo != rrset_get_sig_algo(rrset, i) ||
577 			tag != rrset_get_sig_keytag(rrset, i))
578 			continue;
579 		buf_canon = 0;
580 		sec = dnskey_verify_rrset_sig(env->scratch,
581 			env->scratch_buffer, ve, *env->now, rrset,
582 			dnskey, dnskey_idx, i, &sortree, &buf_canon, reason,
583 			section, qstate);
584 		if(sec == sec_status_secure)
585 			return sec;
586 		numchecked ++;
587 	}
588 	verbose(VERB_ALGO, "rrset failed to verify: all signatures are bogus");
589 	if(!numchecked) *reason = "signature missing";
590 	return sec_status_bogus;
591 }
592 
593 enum sec_status
594 dnskeyset_verify_rrset_sig(struct module_env* env, struct val_env* ve,
595 	time_t now, struct ub_packed_rrset_key* rrset,
596 	struct ub_packed_rrset_key* dnskey, size_t sig_idx,
597 	struct rbtree_type** sortree, char** reason, sldns_pkt_section section,
598 	struct module_qstate* qstate)
599 {
600 	/* find matching keys and check them */
601 	enum sec_status sec = sec_status_bogus;
602 	uint16_t tag = rrset_get_sig_keytag(rrset, sig_idx);
603 	int algo = rrset_get_sig_algo(rrset, sig_idx);
604 	size_t i, num = rrset_get_count(dnskey);
605 	size_t numchecked = 0;
606 	int buf_canon = 0;
607 	verbose(VERB_ALGO, "verify sig %d %d", (int)tag, algo);
608 	if(!dnskey_algo_id_is_supported(algo)) {
609 		verbose(VERB_QUERY, "verify sig: unknown algorithm");
610 		return sec_status_insecure;
611 	}
612 
613 	for(i=0; i<num; i++) {
614 		/* see if key matches keytag and algo */
615 		if(algo != dnskey_get_algo(dnskey, i) ||
616 			tag != dnskey_calc_keytag(dnskey, i))
617 			continue;
618 		numchecked ++;
619 
620 		/* see if key verifies */
621 		sec = dnskey_verify_rrset_sig(env->scratch,
622 			env->scratch_buffer, ve, now, rrset, dnskey, i,
623 			sig_idx, sortree, &buf_canon, reason, section, qstate);
624 		if(sec == sec_status_secure)
625 			return sec;
626 	}
627 	if(numchecked == 0) {
628 		*reason = "signatures from unknown keys";
629 		verbose(VERB_QUERY, "verify: could not find appropriate key");
630 		return sec_status_bogus;
631 	}
632 	return sec_status_bogus;
633 }
634 
635 /**
636  * RR entries in a canonical sorted tree of RRs
637  */
638 struct canon_rr {
639 	/** rbtree node, key is this structure */
640 	rbnode_type node;
641 	/** rrset the RR is in */
642 	struct ub_packed_rrset_key* rrset;
643 	/** which RR in the rrset */
644 	size_t rr_idx;
645 };
646 
647 /**
648  * Compare two RR for canonical order, in a field-style sweep.
649  * @param d: rrset data
650  * @param desc: ldns wireformat descriptor.
651  * @param i: first RR to compare
652  * @param j: first RR to compare
653  * @return comparison code.
654  */
655 static int
656 canonical_compare_byfield(struct packed_rrset_data* d,
657 	const sldns_rr_descriptor* desc, size_t i, size_t j)
658 {
659 	/* sweep across rdata, keep track of some state:
660 	 * 	which rr field, and bytes left in field.
661 	 * 	current position in rdata, length left.
662 	 * 	are we in a dname, length left in a label.
663 	 */
664 	int wfi = -1;	/* current wireformat rdata field (rdf) */
665 	int wfj = -1;
666 	uint8_t* di = d->rr_data[i]+2; /* ptr to current rdata byte */
667 	uint8_t* dj = d->rr_data[j]+2;
668 	size_t ilen = d->rr_len[i]-2; /* length left in rdata */
669 	size_t jlen = d->rr_len[j]-2;
670 	int dname_i = 0;  /* true if these bytes are part of a name */
671 	int dname_j = 0;
672 	size_t lablen_i = 0; /* 0 for label length byte,for first byte of rdf*/
673 	size_t lablen_j = 0; /* otherwise remaining length of rdf or label */
674 	int dname_num_i = (int)desc->_dname_count; /* decreased at root label */
675 	int dname_num_j = (int)desc->_dname_count;
676 
677 	/* loop while there are rdata bytes available for both rrs,
678 	 * and still some lowercasing needs to be done; either the dnames
679 	 * have not been reached yet, or they are currently being processed */
680 	while(ilen > 0 && jlen > 0 && (dname_num_i > 0 || dname_num_j > 0)) {
681 		/* compare these two bytes */
682 		/* lowercase if in a dname and not a label length byte */
683 		if( ((dname_i && lablen_i)?(uint8_t)tolower((int)*di):*di)
684 		 != ((dname_j && lablen_j)?(uint8_t)tolower((int)*dj):*dj)
685 		 ) {
686 		  if(((dname_i && lablen_i)?(uint8_t)tolower((int)*di):*di)
687 		  < ((dname_j && lablen_j)?(uint8_t)tolower((int)*dj):*dj))
688 		 	return -1;
689 		    return 1;
690 		}
691 		ilen--;
692 		jlen--;
693 		/* bytes are equal */
694 
695 		/* advance field i */
696 		/* lablen 0 means that this byte is the first byte of the
697 		 * next rdata field; inspect this rdata field and setup
698 		 * to process the rest of this rdata field.
699 		 * The reason to first read the byte, then setup the rdf,
700 		 * is that we are then sure the byte is available and short
701 		 * rdata is handled gracefully (even if it is a formerr). */
702 		if(lablen_i == 0) {
703 			if(dname_i) {
704 				/* scan this dname label */
705 				/* capture length to lowercase */
706 				lablen_i = (size_t)*di;
707 				if(lablen_i == 0) {
708 					/* end root label */
709 					dname_i = 0;
710 					dname_num_i--;
711 					/* if dname num is 0, then the
712 					 * remainder is binary only */
713 					if(dname_num_i == 0)
714 						lablen_i = ilen;
715 				}
716 			} else {
717 				/* scan this rdata field */
718 				wfi++;
719 				if(desc->_wireformat[wfi]
720 					== LDNS_RDF_TYPE_DNAME) {
721 					dname_i = 1;
722 					lablen_i = (size_t)*di;
723 					if(lablen_i == 0) {
724 						dname_i = 0;
725 						dname_num_i--;
726 						if(dname_num_i == 0)
727 							lablen_i = ilen;
728 					}
729 				} else if(desc->_wireformat[wfi]
730 					== LDNS_RDF_TYPE_STR)
731 					lablen_i = (size_t)*di;
732 				else	lablen_i = get_rdf_size(
733 					desc->_wireformat[wfi]) - 1;
734 			}
735 		} else	lablen_i--;
736 
737 		/* advance field j; same as for i */
738 		if(lablen_j == 0) {
739 			if(dname_j) {
740 				lablen_j = (size_t)*dj;
741 				if(lablen_j == 0) {
742 					dname_j = 0;
743 					dname_num_j--;
744 					if(dname_num_j == 0)
745 						lablen_j = jlen;
746 				}
747 			} else {
748 				wfj++;
749 				if(desc->_wireformat[wfj]
750 					== LDNS_RDF_TYPE_DNAME) {
751 					dname_j = 1;
752 					lablen_j = (size_t)*dj;
753 					if(lablen_j == 0) {
754 						dname_j = 0;
755 						dname_num_j--;
756 						if(dname_num_j == 0)
757 							lablen_j = jlen;
758 					}
759 				} else if(desc->_wireformat[wfj]
760 					== LDNS_RDF_TYPE_STR)
761 					lablen_j = (size_t)*dj;
762 				else	lablen_j = get_rdf_size(
763 					desc->_wireformat[wfj]) - 1;
764 			}
765 		} else	lablen_j--;
766 		di++;
767 		dj++;
768 	}
769 	/* end of the loop; because we advanced byte by byte; now we have
770 	 * that the rdata has ended, or that there is a binary remainder */
771 	/* shortest first */
772 	if(ilen == 0 && jlen == 0)
773 		return 0;
774 	if(ilen == 0)
775 		return -1;
776 	if(jlen == 0)
777 		return 1;
778 	/* binary remainder, capture comparison in wfi variable */
779 	if((wfi = memcmp(di, dj, (ilen<jlen)?ilen:jlen)) != 0)
780 		return wfi;
781 	if(ilen < jlen)
782 		return -1;
783 	if(jlen < ilen)
784 		return 1;
785 	return 0;
786 }
787 
788 /**
789  * Compare two RRs in the same RRset and determine their relative
790  * canonical order.
791  * @param rrset: the rrset in which to perform compares.
792  * @param i: first RR to compare
793  * @param j: first RR to compare
794  * @return 0 if RR i== RR j, -1 if <, +1 if >.
795  */
796 static int
797 canonical_compare(struct ub_packed_rrset_key* rrset, size_t i, size_t j)
798 {
799 	struct packed_rrset_data* d = (struct packed_rrset_data*)
800 		rrset->entry.data;
801 	const sldns_rr_descriptor* desc;
802 	uint16_t type = ntohs(rrset->rk.type);
803 	size_t minlen;
804 	int c;
805 
806 	if(i==j)
807 		return 0;
808 
809 	switch(type) {
810 		/* These RR types have only a name as RDATA.
811 		 * This name has to be canonicalized.*/
812 		case LDNS_RR_TYPE_NS:
813 		case LDNS_RR_TYPE_MD:
814 		case LDNS_RR_TYPE_MF:
815 		case LDNS_RR_TYPE_CNAME:
816 		case LDNS_RR_TYPE_MB:
817 		case LDNS_RR_TYPE_MG:
818 		case LDNS_RR_TYPE_MR:
819 		case LDNS_RR_TYPE_PTR:
820 		case LDNS_RR_TYPE_DNAME:
821 			/* the wireread function has already checked these
822 			 * dname's for correctness, and this double checks */
823 			if(!dname_valid(d->rr_data[i]+2, d->rr_len[i]-2) ||
824 				!dname_valid(d->rr_data[j]+2, d->rr_len[j]-2))
825 				return 0;
826 			return query_dname_compare(d->rr_data[i]+2,
827 				d->rr_data[j]+2);
828 
829 		/* These RR types have STR and fixed size rdata fields
830 		 * before one or more name fields that need canonicalizing,
831 		 * and after that a byte-for byte remainder can be compared.
832 		 */
833 		/* type starts with the name; remainder is binary compared */
834 		case LDNS_RR_TYPE_NXT:
835 		/* use rdata field formats */
836 		case LDNS_RR_TYPE_MINFO:
837 		case LDNS_RR_TYPE_RP:
838 		case LDNS_RR_TYPE_SOA:
839 		case LDNS_RR_TYPE_RT:
840 		case LDNS_RR_TYPE_AFSDB:
841 		case LDNS_RR_TYPE_KX:
842 		case LDNS_RR_TYPE_MX:
843 		case LDNS_RR_TYPE_SIG:
844 		/* RRSIG signer name has to be downcased */
845 		case LDNS_RR_TYPE_RRSIG:
846 		case LDNS_RR_TYPE_PX:
847 		case LDNS_RR_TYPE_NAPTR:
848 		case LDNS_RR_TYPE_SRV:
849 			desc = sldns_rr_descript(type);
850 			log_assert(desc);
851 			/* this holds for the types that need canonicalizing */
852 			log_assert(desc->_minimum == desc->_maximum);
853 			return canonical_compare_byfield(d, desc, i, j);
854 
855 		case LDNS_RR_TYPE_HINFO: /* no longer downcased */
856 		case LDNS_RR_TYPE_NSEC:
857 	default:
858 		/* For unknown RR types, or types not listed above,
859 		 * no canonicalization is needed, do binary compare */
860 		/* byte for byte compare, equal means shortest first*/
861 		minlen = d->rr_len[i]-2;
862 		if(minlen > d->rr_len[j]-2)
863 			minlen = d->rr_len[j]-2;
864 		c = memcmp(d->rr_data[i]+2, d->rr_data[j]+2, minlen);
865 		if(c!=0)
866 			return c;
867 		/* rdata equal, shortest is first */
868 		if(d->rr_len[i] < d->rr_len[j])
869 			return -1;
870 		if(d->rr_len[i] > d->rr_len[j])
871 			return 1;
872 		/* rdata equal, length equal */
873 		break;
874 	}
875 	return 0;
876 }
877 
878 int
879 canonical_tree_compare(const void* k1, const void* k2)
880 {
881 	struct canon_rr* r1 = (struct canon_rr*)k1;
882 	struct canon_rr* r2 = (struct canon_rr*)k2;
883 	log_assert(r1->rrset == r2->rrset);
884 	return canonical_compare(r1->rrset, r1->rr_idx, r2->rr_idx);
885 }
886 
887 /**
888  * Sort RRs for rrset in canonical order.
889  * Does not actually canonicalize the RR rdatas.
890  * Does not touch rrsigs.
891  * @param rrset: to sort.
892  * @param d: rrset data.
893  * @param sortree: tree to sort into.
894  * @param rrs: rr storage.
895  */
896 static void
897 canonical_sort(struct ub_packed_rrset_key* rrset, struct packed_rrset_data* d,
898 	rbtree_type* sortree, struct canon_rr* rrs)
899 {
900 	size_t i;
901 	/* insert into rbtree to sort and detect duplicates */
902 	for(i=0; i<d->count; i++) {
903 		rrs[i].node.key = &rrs[i];
904 		rrs[i].rrset = rrset;
905 		rrs[i].rr_idx = i;
906 		if(!rbtree_insert(sortree, &rrs[i].node)) {
907 			/* this was a duplicate */
908 		}
909 	}
910 }
911 
912 /**
913  * Insert canonical owner name into buffer.
914  * @param buf: buffer to insert into at current position.
915  * @param k: rrset with its owner name.
916  * @param sig: signature with signer name and label count.
917  * 	must be length checked, at least 18 bytes long.
918  * @param can_owner: position in buffer returned for future use.
919  * @param can_owner_len: length of canonical owner name.
920  */
921 static void
922 insert_can_owner(sldns_buffer* buf, struct ub_packed_rrset_key* k,
923 	uint8_t* sig, uint8_t** can_owner, size_t* can_owner_len)
924 {
925 	int rrsig_labels = (int)sig[3];
926 	int fqdn_labels = dname_signame_label_count(k->rk.dname);
927 	*can_owner = sldns_buffer_current(buf);
928 	if(rrsig_labels == fqdn_labels) {
929 		/* no change */
930 		sldns_buffer_write(buf, k->rk.dname, k->rk.dname_len);
931 		query_dname_tolower(*can_owner);
932 		*can_owner_len = k->rk.dname_len;
933 		return;
934 	}
935 	log_assert(rrsig_labels < fqdn_labels);
936 	/* *. | fqdn(rightmost rrsig_labels) */
937 	if(rrsig_labels < fqdn_labels) {
938 		int i;
939 		uint8_t* nm = k->rk.dname;
940 		size_t len = k->rk.dname_len;
941 		/* so skip fqdn_labels-rrsig_labels */
942 		for(i=0; i<fqdn_labels-rrsig_labels; i++) {
943 			dname_remove_label(&nm, &len);
944 		}
945 		*can_owner_len = len+2;
946 		sldns_buffer_write(buf, (uint8_t*)"\001*", 2);
947 		sldns_buffer_write(buf, nm, len);
948 		query_dname_tolower(*can_owner);
949 	}
950 }
951 
952 /**
953  * Canonicalize Rdata in buffer.
954  * @param buf: buffer at position just after the rdata.
955  * @param rrset: rrset with type.
956  * @param len: length of the rdata (including rdatalen uint16).
957  */
958 static void
959 canonicalize_rdata(sldns_buffer* buf, struct ub_packed_rrset_key* rrset,
960 	size_t len)
961 {
962 	uint8_t* datstart = sldns_buffer_current(buf)-len+2;
963 	switch(ntohs(rrset->rk.type)) {
964 		case LDNS_RR_TYPE_NXT:
965 		case LDNS_RR_TYPE_NS:
966 		case LDNS_RR_TYPE_MD:
967 		case LDNS_RR_TYPE_MF:
968 		case LDNS_RR_TYPE_CNAME:
969 		case LDNS_RR_TYPE_MB:
970 		case LDNS_RR_TYPE_MG:
971 		case LDNS_RR_TYPE_MR:
972 		case LDNS_RR_TYPE_PTR:
973 		case LDNS_RR_TYPE_DNAME:
974 			/* type only has a single argument, the name */
975 			query_dname_tolower(datstart);
976 			return;
977 		case LDNS_RR_TYPE_MINFO:
978 		case LDNS_RR_TYPE_RP:
979 		case LDNS_RR_TYPE_SOA:
980 			/* two names after another */
981 			query_dname_tolower(datstart);
982 			query_dname_tolower(datstart +
983 				dname_valid(datstart, len-2));
984 			return;
985 		case LDNS_RR_TYPE_RT:
986 		case LDNS_RR_TYPE_AFSDB:
987 		case LDNS_RR_TYPE_KX:
988 		case LDNS_RR_TYPE_MX:
989 			/* skip fixed part */
990 			if(len < 2+2+1) /* rdlen, skiplen, 1byteroot */
991 				return;
992 			datstart += 2;
993 			query_dname_tolower(datstart);
994 			return;
995 		case LDNS_RR_TYPE_SIG:
996 		/* downcase the RRSIG, compat with BIND (kept it from SIG) */
997 		case LDNS_RR_TYPE_RRSIG:
998 			/* skip fixed part */
999 			if(len < 2+18+1)
1000 				return;
1001 			datstart += 18;
1002 			query_dname_tolower(datstart);
1003 			return;
1004 		case LDNS_RR_TYPE_PX:
1005 			/* skip, then two names after another */
1006 			if(len < 2+2+1)
1007 				return;
1008 			datstart += 2;
1009 			query_dname_tolower(datstart);
1010 			query_dname_tolower(datstart +
1011 				dname_valid(datstart, len-2-2));
1012 			return;
1013 		case LDNS_RR_TYPE_NAPTR:
1014 			if(len < 2+4)
1015 				return;
1016 			len -= 2+4;
1017 			datstart += 4;
1018 			if(len < (size_t)datstart[0]+1) /* skip text field */
1019 				return;
1020 			len -= (size_t)datstart[0]+1;
1021 			datstart += (size_t)datstart[0]+1;
1022 			if(len < (size_t)datstart[0]+1) /* skip text field */
1023 				return;
1024 			len -= (size_t)datstart[0]+1;
1025 			datstart += (size_t)datstart[0]+1;
1026 			if(len < (size_t)datstart[0]+1) /* skip text field */
1027 				return;
1028 			len -= (size_t)datstart[0]+1;
1029 			datstart += (size_t)datstart[0]+1;
1030 			if(len < 1)	/* check name is at least 1 byte*/
1031 				return;
1032 			query_dname_tolower(datstart);
1033 			return;
1034 		case LDNS_RR_TYPE_SRV:
1035 			/* skip fixed part */
1036 			if(len < 2+6+1)
1037 				return;
1038 			datstart += 6;
1039 			query_dname_tolower(datstart);
1040 			return;
1041 
1042 		/* do not canonicalize NSEC rdata name, compat with
1043 		 * from bind 9.4 signer, where it does not do so */
1044 		case LDNS_RR_TYPE_NSEC: /* type starts with the name */
1045 		case LDNS_RR_TYPE_HINFO: /* not downcased */
1046 		/* A6 not supported */
1047 		default:
1048 			/* nothing to do for unknown types */
1049 			return;
1050 	}
1051 }
1052 
1053 int rrset_canonical_equal(struct regional* region,
1054 	struct ub_packed_rrset_key* k1, struct ub_packed_rrset_key* k2)
1055 {
1056 	struct rbtree_type sortree1, sortree2;
1057 	struct canon_rr *rrs1, *rrs2, *p1, *p2;
1058 	struct packed_rrset_data* d1=(struct packed_rrset_data*)k1->entry.data;
1059 	struct packed_rrset_data* d2=(struct packed_rrset_data*)k2->entry.data;
1060 	struct ub_packed_rrset_key fk;
1061 	struct packed_rrset_data fd;
1062 	size_t flen[2];
1063 	uint8_t* fdata[2];
1064 
1065 	/* basic compare */
1066 	if(k1->rk.dname_len != k2->rk.dname_len ||
1067 		k1->rk.flags != k2->rk.flags ||
1068 		k1->rk.type != k2->rk.type ||
1069 		k1->rk.rrset_class != k2->rk.rrset_class ||
1070 		query_dname_compare(k1->rk.dname, k2->rk.dname) != 0)
1071 		return 0;
1072 	if(d1->ttl != d2->ttl ||
1073 		d1->count != d2->count ||
1074 		d1->rrsig_count != d2->rrsig_count ||
1075 		d1->trust != d2->trust ||
1076 		d1->security != d2->security)
1077 		return 0;
1078 
1079 	/* init */
1080 	memset(&fk, 0, sizeof(fk));
1081 	memset(&fd, 0, sizeof(fd));
1082 	fk.entry.data = &fd;
1083 	fd.count = 2;
1084 	fd.rr_len = flen;
1085 	fd.rr_data = fdata;
1086 	rbtree_init(&sortree1, &canonical_tree_compare);
1087 	rbtree_init(&sortree2, &canonical_tree_compare);
1088 	if(d1->count > RR_COUNT_MAX || d2->count > RR_COUNT_MAX)
1089 		return 1; /* protection against integer overflow */
1090 	rrs1 = regional_alloc(region, sizeof(struct canon_rr)*d1->count);
1091 	rrs2 = regional_alloc(region, sizeof(struct canon_rr)*d2->count);
1092 	if(!rrs1 || !rrs2) return 1; /* alloc failure */
1093 
1094 	/* sort */
1095 	canonical_sort(k1, d1, &sortree1, rrs1);
1096 	canonical_sort(k2, d2, &sortree2, rrs2);
1097 
1098 	/* compare canonical-sorted RRs for canonical-equality */
1099 	if(sortree1.count != sortree2.count)
1100 		return 0;
1101 	p1 = (struct canon_rr*)rbtree_first(&sortree1);
1102 	p2 = (struct canon_rr*)rbtree_first(&sortree2);
1103 	while(p1 != (struct canon_rr*)RBTREE_NULL &&
1104 		p2 != (struct canon_rr*)RBTREE_NULL) {
1105 		flen[0] = d1->rr_len[p1->rr_idx];
1106 		flen[1] = d2->rr_len[p2->rr_idx];
1107 		fdata[0] = d1->rr_data[p1->rr_idx];
1108 		fdata[1] = d2->rr_data[p2->rr_idx];
1109 
1110 		if(canonical_compare(&fk, 0, 1) != 0)
1111 			return 0;
1112 		p1 = (struct canon_rr*)rbtree_next(&p1->node);
1113 		p2 = (struct canon_rr*)rbtree_next(&p2->node);
1114 	}
1115 	return 1;
1116 }
1117 
1118 /**
1119  * Create canonical form of rrset in the scratch buffer.
1120  * @param region: temporary region.
1121  * @param buf: the buffer to use.
1122  * @param k: the rrset to insert.
1123  * @param sig: RRSIG rdata to include.
1124  * @param siglen: RRSIG rdata len excluding signature field, but inclusive
1125  * 	signer name length.
1126  * @param sortree: if NULL is passed a new sorted rrset tree is built.
1127  * 	Otherwise it is reused.
1128  * @param section: section of packet where this rrset comes from.
1129  * @param qstate: qstate with region.
1130  * @return false on alloc error.
1131  */
1132 static int
1133 rrset_canonical(struct regional* region, sldns_buffer* buf,
1134 	struct ub_packed_rrset_key* k, uint8_t* sig, size_t siglen,
1135 	struct rbtree_type** sortree, sldns_pkt_section section,
1136 	struct module_qstate* qstate)
1137 {
1138 	struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
1139 	uint8_t* can_owner = NULL;
1140 	size_t can_owner_len = 0;
1141 	struct canon_rr* walk;
1142 	struct canon_rr* rrs;
1143 
1144 	if(!*sortree) {
1145 		*sortree = (struct rbtree_type*)regional_alloc(region,
1146 			sizeof(rbtree_type));
1147 		if(!*sortree)
1148 			return 0;
1149 		if(d->count > RR_COUNT_MAX)
1150 			return 0; /* integer overflow protection */
1151 		rrs = regional_alloc(region, sizeof(struct canon_rr)*d->count);
1152 		if(!rrs) {
1153 			*sortree = NULL;
1154 			return 0;
1155 		}
1156 		rbtree_init(*sortree, &canonical_tree_compare);
1157 		canonical_sort(k, d, *sortree, rrs);
1158 	}
1159 
1160 	sldns_buffer_clear(buf);
1161 	sldns_buffer_write(buf, sig, siglen);
1162 	/* canonicalize signer name */
1163 	query_dname_tolower(sldns_buffer_begin(buf)+18);
1164 	RBTREE_FOR(walk, struct canon_rr*, (*sortree)) {
1165 		/* see if there is enough space left in the buffer */
1166 		if(sldns_buffer_remaining(buf) < can_owner_len + 2 + 2 + 4
1167 			+ d->rr_len[walk->rr_idx]) {
1168 			log_err("verify: failed to canonicalize, "
1169 				"rrset too big");
1170 			return 0;
1171 		}
1172 		/* determine canonical owner name */
1173 		if(can_owner)
1174 			sldns_buffer_write(buf, can_owner, can_owner_len);
1175 		else	insert_can_owner(buf, k, sig, &can_owner,
1176 				&can_owner_len);
1177 		sldns_buffer_write(buf, &k->rk.type, 2);
1178 		sldns_buffer_write(buf, &k->rk.rrset_class, 2);
1179 		sldns_buffer_write(buf, sig+4, 4);
1180 		sldns_buffer_write(buf, d->rr_data[walk->rr_idx],
1181 			d->rr_len[walk->rr_idx]);
1182 		canonicalize_rdata(buf, k, d->rr_len[walk->rr_idx]);
1183 	}
1184 	sldns_buffer_flip(buf);
1185 
1186 	/* Replace RR owner with canonical owner for NSEC records in authority
1187 	 * section, to prevent that a wildcard synthesized NSEC can be used in
1188 	 * the non-existence proves. */
1189 	if(ntohs(k->rk.type) == LDNS_RR_TYPE_NSEC &&
1190 		section == LDNS_SECTION_AUTHORITY) {
1191 		k->rk.dname = regional_alloc_init(qstate->region, can_owner,
1192 			can_owner_len);
1193 		if(!k->rk.dname)
1194 			return 0;
1195 		k->rk.dname_len = can_owner_len;
1196 	}
1197 
1198 
1199 	return 1;
1200 }
1201 
1202 /** pretty print rrsig error with dates */
1203 static void
1204 sigdate_error(const char* str, int32_t expi, int32_t incep, int32_t now)
1205 {
1206 	struct tm tm;
1207 	char expi_buf[16];
1208 	char incep_buf[16];
1209 	char now_buf[16];
1210 	time_t te, ti, tn;
1211 
1212 	if(verbosity < VERB_QUERY)
1213 		return;
1214 	te = (time_t)expi;
1215 	ti = (time_t)incep;
1216 	tn = (time_t)now;
1217 	memset(&tm, 0, sizeof(tm));
1218 	if(gmtime_r(&te, &tm) && strftime(expi_buf, 15, "%Y%m%d%H%M%S", &tm)
1219 	 &&gmtime_r(&ti, &tm) && strftime(incep_buf, 15, "%Y%m%d%H%M%S", &tm)
1220 	 &&gmtime_r(&tn, &tm) && strftime(now_buf, 15, "%Y%m%d%H%M%S", &tm)) {
1221 		log_info("%s expi=%s incep=%s now=%s", str, expi_buf,
1222 			incep_buf, now_buf);
1223 	} else
1224 		log_info("%s expi=%u incep=%u now=%u", str, (unsigned)expi,
1225 			(unsigned)incep, (unsigned)now);
1226 }
1227 
1228 /** RFC 1918 comparison, uses unsigned integers, and tries to avoid
1229  * compiler optimization (eg. by avoiding a-b<0 comparisons),
1230  * this routine matches compare_serial(), for SOA serial number checks */
1231 static int
1232 compare_1918(uint32_t a, uint32_t b)
1233 {
1234 	/* for 32 bit values */
1235         const uint32_t cutoff = ((uint32_t) 1 << (32 - 1));
1236 
1237         if (a == b) {
1238                 return 0;
1239         } else if ((a < b && b - a < cutoff) || (a > b && a - b > cutoff)) {
1240                 return -1;
1241         } else {
1242                 return 1;
1243         }
1244 }
1245 
1246 /** if we know that b is larger than a, return the difference between them,
1247  * that is the distance between them. in RFC1918 arith */
1248 static uint32_t
1249 subtract_1918(uint32_t a, uint32_t b)
1250 {
1251 	/* for 32 bit values */
1252         const uint32_t cutoff = ((uint32_t) 1 << (32 - 1));
1253 
1254 	if(a == b)
1255 		return 0;
1256 	if(a < b && b - a < cutoff) {
1257 		return b-a;
1258 	}
1259 	if(a > b && a - b > cutoff) {
1260 		return ((uint32_t)0xffffffff) - (a-b-1);
1261 	}
1262 	/* wrong case, b smaller than a */
1263 	return 0;
1264 }
1265 
1266 /** check rrsig dates */
1267 static int
1268 check_dates(struct val_env* ve, uint32_t unow,
1269 	uint8_t* expi_p, uint8_t* incep_p, char** reason)
1270 {
1271 	/* read out the dates */
1272 	uint32_t expi, incep, now;
1273 	memmove(&expi, expi_p, sizeof(expi));
1274 	memmove(&incep, incep_p, sizeof(incep));
1275 	expi = ntohl(expi);
1276 	incep = ntohl(incep);
1277 
1278 	/* get current date */
1279 	if(ve->date_override) {
1280 		if(ve->date_override == -1) {
1281 			verbose(VERB_ALGO, "date override: ignore date");
1282 			return 1;
1283 		}
1284 		now = ve->date_override;
1285 		verbose(VERB_ALGO, "date override option %d", (int)now);
1286 	} else	now = unow;
1287 
1288 	/* check them */
1289 	if(compare_1918(incep, expi) > 0) {
1290 		sigdate_error("verify: inception after expiration, "
1291 			"signature bad", expi, incep, now);
1292 		*reason = "signature inception after expiration";
1293 		return 0;
1294 	}
1295 	if(compare_1918(incep, now) > 0) {
1296 		/* within skew ? (calc here to avoid calculation normally) */
1297 		uint32_t skew = subtract_1918(incep, expi)/10;
1298 		if(skew < (uint32_t)ve->skew_min) skew = ve->skew_min;
1299 		if(skew > (uint32_t)ve->skew_max) skew = ve->skew_max;
1300 		if(subtract_1918(now, incep) > skew) {
1301 			sigdate_error("verify: signature bad, current time is"
1302 				" before inception date", expi, incep, now);
1303 			*reason = "signature before inception date";
1304 			return 0;
1305 		}
1306 		sigdate_error("verify warning suspicious signature inception "
1307 			" or bad local clock", expi, incep, now);
1308 	}
1309 	if(compare_1918(now, expi) > 0) {
1310 		uint32_t skew = subtract_1918(incep, expi)/10;
1311 		if(skew < (uint32_t)ve->skew_min) skew = ve->skew_min;
1312 		if(skew > (uint32_t)ve->skew_max) skew = ve->skew_max;
1313 		if(subtract_1918(expi, now) > skew) {
1314 			sigdate_error("verify: signature expired", expi,
1315 				incep, now);
1316 			*reason = "signature expired";
1317 			return 0;
1318 		}
1319 		sigdate_error("verify warning suspicious signature expiration "
1320 			" or bad local clock", expi, incep, now);
1321 	}
1322 	return 1;
1323 }
1324 
1325 /** adjust rrset TTL for verified rrset, compare to original TTL and expi */
1326 static void
1327 adjust_ttl(struct val_env* ve, uint32_t unow,
1328 	struct ub_packed_rrset_key* rrset, uint8_t* orig_p,
1329 	uint8_t* expi_p, uint8_t* incep_p)
1330 {
1331 	struct packed_rrset_data* d =
1332 		(struct packed_rrset_data*)rrset->entry.data;
1333 	/* read out the dates */
1334 	int32_t origttl, expittl, expi, incep, now;
1335 	memmove(&origttl, orig_p, sizeof(origttl));
1336 	memmove(&expi, expi_p, sizeof(expi));
1337 	memmove(&incep, incep_p, sizeof(incep));
1338 	expi = ntohl(expi);
1339 	incep = ntohl(incep);
1340 	origttl = ntohl(origttl);
1341 
1342 	/* get current date */
1343 	if(ve->date_override) {
1344 		now = ve->date_override;
1345 	} else	now = (int32_t)unow;
1346 	expittl = expi - now;
1347 
1348 	/* so now:
1349 	 * d->ttl: rrset ttl read from message or cache. May be reduced
1350 	 * origttl: original TTL from signature, authoritative TTL max.
1351 	 * MIN_TTL: minimum TTL from config.
1352 	 * expittl: TTL until the signature expires.
1353 	 *
1354 	 * Use the smallest of these, but don't let origttl set the TTL
1355 	 * below the minimum.
1356 	 */
1357 	if(MIN_TTL > (time_t)origttl && d->ttl > MIN_TTL) {
1358 		verbose(VERB_QUERY, "rrset TTL larger than original and minimum"
1359 			" TTL, adjusting TTL downwards to minimum ttl");
1360 		d->ttl = MIN_TTL;
1361 	}
1362 	else if(MIN_TTL <= origttl && d->ttl > (time_t)origttl) {
1363 		verbose(VERB_QUERY, "rrset TTL larger than original TTL, "
1364 		"adjusting TTL downwards to original ttl");
1365 		d->ttl = origttl;
1366 	}
1367 
1368 	if(expittl > 0 && d->ttl > (time_t)expittl) {
1369 		verbose(VERB_ALGO, "rrset TTL larger than sig expiration ttl,"
1370 			" adjusting TTL downwards");
1371 		d->ttl = expittl;
1372 	}
1373 }
1374 
1375 enum sec_status
1376 dnskey_verify_rrset_sig(struct regional* region, sldns_buffer* buf,
1377 	struct val_env* ve, time_t now,
1378         struct ub_packed_rrset_key* rrset, struct ub_packed_rrset_key* dnskey,
1379         size_t dnskey_idx, size_t sig_idx,
1380 	struct rbtree_type** sortree, int* buf_canon, char** reason,
1381 	sldns_pkt_section section, struct module_qstate* qstate)
1382 {
1383 	enum sec_status sec;
1384 	uint8_t* sig;		/* RRSIG rdata */
1385 	size_t siglen;
1386 	size_t rrnum = rrset_get_count(rrset);
1387 	uint8_t* signer;	/* rrsig signer name */
1388 	size_t signer_len;
1389 	unsigned char* sigblock; /* signature rdata field */
1390 	unsigned int sigblock_len;
1391 	uint16_t ktag;		/* DNSKEY key tag */
1392 	unsigned char* key;	/* public key rdata field */
1393 	unsigned int keylen;
1394 	rrset_get_rdata(rrset, rrnum + sig_idx, &sig, &siglen);
1395 	/* min length of rdatalen, fixed rrsig, root signer, 1 byte sig */
1396 	if(siglen < 2+20) {
1397 		verbose(VERB_QUERY, "verify: signature too short");
1398 		*reason = "signature too short";
1399 		return sec_status_bogus;
1400 	}
1401 
1402 	if(!(dnskey_get_flags(dnskey, dnskey_idx) & DNSKEY_BIT_ZSK)) {
1403 		verbose(VERB_QUERY, "verify: dnskey without ZSK flag");
1404 		*reason = "dnskey without ZSK flag";
1405 		return sec_status_bogus;
1406 	}
1407 
1408 	if(dnskey_get_protocol(dnskey, dnskey_idx) != LDNS_DNSSEC_KEYPROTO) {
1409 		/* RFC 4034 says DNSKEY PROTOCOL MUST be 3 */
1410 		verbose(VERB_QUERY, "verify: dnskey has wrong key protocol");
1411 		*reason = "dnskey has wrong protocolnumber";
1412 		return sec_status_bogus;
1413 	}
1414 
1415 	/* verify as many fields in rrsig as possible */
1416 	signer = sig+2+18;
1417 	signer_len = dname_valid(signer, siglen-2-18);
1418 	if(!signer_len) {
1419 		verbose(VERB_QUERY, "verify: malformed signer name");
1420 		*reason = "signer name malformed";
1421 		return sec_status_bogus; /* signer name invalid */
1422 	}
1423 	if(!dname_subdomain_c(rrset->rk.dname, signer)) {
1424 		verbose(VERB_QUERY, "verify: signer name is off-tree");
1425 		*reason = "signer name off-tree";
1426 		return sec_status_bogus; /* signer name offtree */
1427 	}
1428 	sigblock = (unsigned char*)signer+signer_len;
1429 	if(siglen < 2+18+signer_len+1) {
1430 		verbose(VERB_QUERY, "verify: too short, no signature data");
1431 		*reason = "signature too short, no signature data";
1432 		return sec_status_bogus; /* sig rdf is < 1 byte */
1433 	}
1434 	sigblock_len = (unsigned int)(siglen - 2 - 18 - signer_len);
1435 
1436 	/* verify key dname == sig signer name */
1437 	if(query_dname_compare(signer, dnskey->rk.dname) != 0) {
1438 		verbose(VERB_QUERY, "verify: wrong key for rrsig");
1439 		log_nametypeclass(VERB_QUERY, "RRSIG signername is",
1440 			signer, 0, 0);
1441 		log_nametypeclass(VERB_QUERY, "the key name is",
1442 			dnskey->rk.dname, 0, 0);
1443 		*reason = "signer name mismatches key name";
1444 		return sec_status_bogus;
1445 	}
1446 
1447 	/* verify covered type */
1448 	/* memcmp works because type is in network format for rrset */
1449 	if(memcmp(sig+2, &rrset->rk.type, 2) != 0) {
1450 		verbose(VERB_QUERY, "verify: wrong type covered");
1451 		*reason = "signature covers wrong type";
1452 		return sec_status_bogus;
1453 	}
1454 	/* verify keytag and sig algo (possibly again) */
1455 	if((int)sig[2+2] != dnskey_get_algo(dnskey, dnskey_idx)) {
1456 		verbose(VERB_QUERY, "verify: wrong algorithm");
1457 		*reason = "signature has wrong algorithm";
1458 		return sec_status_bogus;
1459 	}
1460 	ktag = htons(dnskey_calc_keytag(dnskey, dnskey_idx));
1461 	if(memcmp(sig+2+16, &ktag, 2) != 0) {
1462 		verbose(VERB_QUERY, "verify: wrong keytag");
1463 		*reason = "signature has wrong keytag";
1464 		return sec_status_bogus;
1465 	}
1466 
1467 	/* verify labels is in a valid range */
1468 	if((int)sig[2+3] > dname_signame_label_count(rrset->rk.dname)) {
1469 		verbose(VERB_QUERY, "verify: labelcount out of range");
1470 		*reason = "signature labelcount out of range";
1471 		return sec_status_bogus;
1472 	}
1473 
1474 	/* original ttl, always ok */
1475 
1476 	if(!*buf_canon) {
1477 		/* create rrset canonical format in buffer, ready for
1478 		 * signature */
1479 		if(!rrset_canonical(region, buf, rrset, sig+2,
1480 			18 + signer_len, sortree, section, qstate)) {
1481 			log_err("verify: failed due to alloc error");
1482 			return sec_status_unchecked;
1483 		}
1484 		*buf_canon = 1;
1485 	}
1486 
1487 	/* check that dnskey is available */
1488 	dnskey_get_pubkey(dnskey, dnskey_idx, &key, &keylen);
1489 	if(!key) {
1490 		verbose(VERB_QUERY, "verify: short DNSKEY RR");
1491 		return sec_status_unchecked;
1492 	}
1493 
1494 	/* verify */
1495 	sec = verify_canonrrset(buf, (int)sig[2+2],
1496 		sigblock, sigblock_len, key, keylen, reason);
1497 
1498 	if(sec == sec_status_secure) {
1499 		/* check if TTL is too high - reduce if so */
1500 		adjust_ttl(ve, now, rrset, sig+2+4, sig+2+8, sig+2+12);
1501 
1502 		/* verify inception, expiration dates
1503 		 * Do this last so that if you ignore expired-sigs the
1504 		 * rest is sure to be OK. */
1505 		if(!check_dates(ve, now, sig+2+8, sig+2+12, reason)) {
1506 			return sec_status_bogus;
1507 		}
1508 	}
1509 
1510 	return sec;
1511 }
1512