Home | History | Annotate | Line # | Download | only in dns
zoneverify.c revision 1.1.1.6
      1 /*	$NetBSD: zoneverify.c,v 1.1.1.6 2021/02/19 16:37:14 christos Exp $	*/
      2 
      3 /*
      4  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
      5  *
      6  * This Source Code Form is subject to the terms of the Mozilla Public
      7  * License, v. 2.0. If a copy of the MPL was not distributed with this
      8  * file, you can obtain one at https://mozilla.org/MPL/2.0/.
      9  *
     10  * See the COPYRIGHT file distributed with this work for additional
     11  * information regarding copyright ownership.
     12  */
     13 
     14 /*! \file */
     15 
     16 #include <inttypes.h>
     17 #include <stdarg.h>
     18 #include <stdbool.h>
     19 #include <stdio.h>
     20 #include <string.h>
     21 
     22 #include <isc/base32.h>
     23 #include <isc/buffer.h>
     24 #include <isc/heap.h>
     25 #include <isc/iterated_hash.h>
     26 #include <isc/log.h>
     27 #include <isc/mem.h>
     28 #include <isc/region.h>
     29 #include <isc/result.h>
     30 #include <isc/types.h>
     31 #include <isc/util.h>
     32 
     33 #include <dns/db.h>
     34 #include <dns/dbiterator.h>
     35 #include <dns/dnssec.h>
     36 #include <dns/fixedname.h>
     37 #include <dns/keytable.h>
     38 #include <dns/keyvalues.h>
     39 #include <dns/log.h>
     40 #include <dns/name.h>
     41 #include <dns/nsec.h>
     42 #include <dns/nsec3.h>
     43 #include <dns/rdata.h>
     44 #include <dns/rdataset.h>
     45 #include <dns/rdatasetiter.h>
     46 #include <dns/rdatastruct.h>
     47 #include <dns/rdatatype.h>
     48 #include <dns/result.h>
     49 #include <dns/secalg.h>
     50 #include <dns/types.h>
     51 #include <dns/zone.h>
     52 #include <dns/zoneverify.h>
     53 
     54 #include <dst/dst.h>
     55 
     56 typedef struct vctx {
     57 	isc_mem_t *mctx;
     58 	dns_zone_t *zone;
     59 	dns_db_t *db;
     60 	dns_dbversion_t *ver;
     61 	dns_name_t *origin;
     62 	dns_keytable_t *secroots;
     63 	bool goodksk;
     64 	bool goodzsk;
     65 	dns_rdataset_t keyset;
     66 	dns_rdataset_t keysigs;
     67 	dns_rdataset_t soaset;
     68 	dns_rdataset_t soasigs;
     69 	dns_rdataset_t nsecset;
     70 	dns_rdataset_t nsecsigs;
     71 	dns_rdataset_t nsec3paramset;
     72 	dns_rdataset_t nsec3paramsigs;
     73 	unsigned char revoked_ksk[256];
     74 	unsigned char revoked_zsk[256];
     75 	unsigned char standby_ksk[256];
     76 	unsigned char standby_zsk[256];
     77 	unsigned char ksk_algorithms[256];
     78 	unsigned char zsk_algorithms[256];
     79 	unsigned char bad_algorithms[256];
     80 	unsigned char act_algorithms[256];
     81 	isc_heap_t *expected_chains;
     82 	isc_heap_t *found_chains;
     83 } vctx_t;
     84 
     85 struct nsec3_chain_fixed {
     86 	uint8_t hash;
     87 	uint8_t salt_length;
     88 	uint8_t next_length;
     89 	uint16_t iterations;
     90 	/*
     91 	 * The following non-fixed-length data is stored in memory after the
     92 	 * fields declared above for each NSEC3 chain element:
     93 	 *
     94 	 * unsigned char	salt[salt_length];
     95 	 * unsigned char	owner[next_length];
     96 	 * unsigned char	next[next_length];
     97 	 */
     98 };
     99 
    100 /*%
    101  * Log a zone verification error described by 'fmt' and the variable arguments
    102  * following it.  Either use dns_zone_logv() or print to stderr, depending on
    103  * whether the function was invoked from within named or by a standalone tool,
    104  * respectively.
    105  */
    106 static void
    107 zoneverify_log_error(const vctx_t *vctx, const char *fmt, ...) {
    108 	va_list ap;
    109 
    110 	va_start(ap, fmt);
    111 	if (vctx->zone != NULL) {
    112 		dns_zone_logv(vctx->zone, DNS_LOGCATEGORY_GENERAL,
    113 			      ISC_LOG_ERROR, NULL, fmt, ap);
    114 	} else {
    115 		vfprintf(stderr, fmt, ap);
    116 		fprintf(stderr, "\n");
    117 	}
    118 	va_end(ap);
    119 }
    120 
    121 static bool
    122 is_delegation(const vctx_t *vctx, const dns_name_t *name, dns_dbnode_t *node,
    123 	      uint32_t *ttlp) {
    124 	dns_rdataset_t nsset;
    125 	isc_result_t result;
    126 
    127 	if (dns_name_equal(name, vctx->origin)) {
    128 		return (false);
    129 	}
    130 
    131 	dns_rdataset_init(&nsset);
    132 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
    133 				     dns_rdatatype_ns, 0, 0, &nsset, NULL);
    134 	if (dns_rdataset_isassociated(&nsset)) {
    135 		if (ttlp != NULL) {
    136 			*ttlp = nsset.ttl;
    137 		}
    138 		dns_rdataset_disassociate(&nsset);
    139 	}
    140 
    141 	return ((result == ISC_R_SUCCESS));
    142 }
    143 
    144 /*%
    145  * Return true if version 'ver' of database 'db' contains a DNAME RRset at
    146  * 'node'; return false otherwise.
    147  */
    148 static bool
    149 has_dname(const vctx_t *vctx, dns_dbnode_t *node) {
    150 	dns_rdataset_t dnameset;
    151 	isc_result_t result;
    152 
    153 	dns_rdataset_init(&dnameset);
    154 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
    155 				     dns_rdatatype_dname, 0, 0, &dnameset,
    156 				     NULL);
    157 	if (dns_rdataset_isassociated(&dnameset)) {
    158 		dns_rdataset_disassociate(&dnameset);
    159 	}
    160 
    161 	return ((result == ISC_R_SUCCESS));
    162 }
    163 
    164 static bool
    165 goodsig(const vctx_t *vctx, dns_rdata_t *sigrdata, const dns_name_t *name,
    166 	dst_key_t **dstkeys, size_t nkeys, dns_rdataset_t *rdataset) {
    167 	dns_rdata_rrsig_t sig;
    168 	isc_result_t result;
    169 
    170 	result = dns_rdata_tostruct(sigrdata, &sig, NULL);
    171 	RUNTIME_CHECK(result == ISC_R_SUCCESS);
    172 
    173 	for (size_t key = 0; key < nkeys; key++) {
    174 		if (sig.algorithm != dst_key_alg(dstkeys[key]) ||
    175 		    sig.keyid != dst_key_id(dstkeys[key]) ||
    176 		    !dns_name_equal(&sig.signer, vctx->origin))
    177 		{
    178 			continue;
    179 		}
    180 		result = dns_dnssec_verify(name, rdataset, dstkeys[key], false,
    181 					   0, vctx->mctx, sigrdata, NULL);
    182 		if (result == ISC_R_SUCCESS || result == DNS_R_FROMWILDCARD) {
    183 			return (true);
    184 		}
    185 	}
    186 	return (false);
    187 }
    188 
    189 static bool
    190 nsec_bitmap_equal(dns_rdata_nsec_t *nsec, dns_rdata_t *rdata) {
    191 	isc_result_t result;
    192 	dns_rdata_nsec_t tmpnsec;
    193 
    194 	result = dns_rdata_tostruct(rdata, &tmpnsec, NULL);
    195 	RUNTIME_CHECK(result == ISC_R_SUCCESS);
    196 
    197 	if (nsec->len != tmpnsec.len ||
    198 	    memcmp(nsec->typebits, tmpnsec.typebits, nsec->len) != 0)
    199 	{
    200 		return (false);
    201 	}
    202 	return (true);
    203 }
    204 
    205 static isc_result_t
    206 verifynsec(const vctx_t *vctx, const dns_name_t *name, dns_dbnode_t *node,
    207 	   const dns_name_t *nextname, isc_result_t *vresult) {
    208 	unsigned char buffer[DNS_NSEC_BUFFERSIZE];
    209 	char namebuf[DNS_NAME_FORMATSIZE];
    210 	char nextbuf[DNS_NAME_FORMATSIZE];
    211 	char found[DNS_NAME_FORMATSIZE];
    212 	dns_rdataset_t rdataset;
    213 	dns_rdata_t rdata = DNS_RDATA_INIT;
    214 	dns_rdata_t tmprdata = DNS_RDATA_INIT;
    215 	dns_rdata_nsec_t nsec;
    216 	isc_result_t result;
    217 
    218 	dns_rdataset_init(&rdataset);
    219 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
    220 				     dns_rdatatype_nsec, 0, 0, &rdataset, NULL);
    221 	if (result != ISC_R_SUCCESS) {
    222 		dns_name_format(name, namebuf, sizeof(namebuf));
    223 		zoneverify_log_error(vctx, "Missing NSEC record for %s",
    224 				     namebuf);
    225 		*vresult = ISC_R_FAILURE;
    226 		result = ISC_R_SUCCESS;
    227 		goto done;
    228 	}
    229 
    230 	result = dns_rdataset_first(&rdataset);
    231 	if (result != ISC_R_SUCCESS) {
    232 		zoneverify_log_error(vctx, "dns_rdataset_first(): %s",
    233 				     isc_result_totext(result));
    234 		goto done;
    235 	}
    236 
    237 	dns_rdataset_current(&rdataset, &rdata);
    238 	result = dns_rdata_tostruct(&rdata, &nsec, NULL);
    239 	RUNTIME_CHECK(result == ISC_R_SUCCESS);
    240 
    241 	/* Check next name is consistent */
    242 	if (!dns_name_equal(&nsec.next, nextname)) {
    243 		dns_name_format(name, namebuf, sizeof(namebuf));
    244 		dns_name_format(nextname, nextbuf, sizeof(nextbuf));
    245 		dns_name_format(&nsec.next, found, sizeof(found));
    246 		zoneverify_log_error(vctx,
    247 				     "Bad NSEC record for %s, next name "
    248 				     "mismatch (expected:%s, found:%s)",
    249 				     namebuf, nextbuf, found);
    250 		*vresult = ISC_R_FAILURE;
    251 		goto done;
    252 	}
    253 
    254 	/* Check bit map is consistent */
    255 	result = dns_nsec_buildrdata(vctx->db, vctx->ver, node, nextname,
    256 				     buffer, &tmprdata);
    257 	if (result != ISC_R_SUCCESS) {
    258 		zoneverify_log_error(vctx, "dns_nsec_buildrdata(): %s",
    259 				     isc_result_totext(result));
    260 		goto done;
    261 	}
    262 	if (!nsec_bitmap_equal(&nsec, &tmprdata)) {
    263 		dns_name_format(name, namebuf, sizeof(namebuf));
    264 		zoneverify_log_error(vctx,
    265 				     "Bad NSEC record for %s, bit map "
    266 				     "mismatch",
    267 				     namebuf);
    268 		*vresult = ISC_R_FAILURE;
    269 		goto done;
    270 	}
    271 
    272 	result = dns_rdataset_next(&rdataset);
    273 	if (result != ISC_R_NOMORE) {
    274 		dns_name_format(name, namebuf, sizeof(namebuf));
    275 		zoneverify_log_error(vctx, "Multiple NSEC records for %s",
    276 				     namebuf);
    277 		*vresult = ISC_R_FAILURE;
    278 		goto done;
    279 	}
    280 
    281 	*vresult = ISC_R_SUCCESS;
    282 	result = ISC_R_SUCCESS;
    283 
    284 done:
    285 	if (dns_rdataset_isassociated(&rdataset)) {
    286 		dns_rdataset_disassociate(&rdataset);
    287 	}
    288 
    289 	return (result);
    290 }
    291 
    292 static isc_result_t
    293 check_no_rrsig(const vctx_t *vctx, const dns_rdataset_t *rdataset,
    294 	       const dns_name_t *name, dns_dbnode_t *node) {
    295 	char namebuf[DNS_NAME_FORMATSIZE];
    296 	char typebuf[DNS_RDATATYPE_FORMATSIZE];
    297 	dns_rdataset_t sigrdataset;
    298 	dns_rdatasetiter_t *rdsiter = NULL;
    299 	isc_result_t result;
    300 
    301 	dns_rdataset_init(&sigrdataset);
    302 	result = dns_db_allrdatasets(vctx->db, node, vctx->ver, 0, &rdsiter);
    303 	if (result != ISC_R_SUCCESS) {
    304 		zoneverify_log_error(vctx, "dns_db_allrdatasets(): %s",
    305 				     isc_result_totext(result));
    306 		return (result);
    307 	}
    308 	for (result = dns_rdatasetiter_first(rdsiter); result == ISC_R_SUCCESS;
    309 	     result = dns_rdatasetiter_next(rdsiter))
    310 	{
    311 		dns_rdatasetiter_current(rdsiter, &sigrdataset);
    312 		if (sigrdataset.type == dns_rdatatype_rrsig &&
    313 		    sigrdataset.covers == rdataset->type)
    314 		{
    315 			break;
    316 		}
    317 		dns_rdataset_disassociate(&sigrdataset);
    318 	}
    319 	if (result == ISC_R_SUCCESS) {
    320 		dns_name_format(name, namebuf, sizeof(namebuf));
    321 		dns_rdatatype_format(rdataset->type, typebuf, sizeof(typebuf));
    322 		zoneverify_log_error(vctx,
    323 				     "Warning: Found unexpected signatures "
    324 				     "for %s/%s",
    325 				     namebuf, typebuf);
    326 	}
    327 	if (dns_rdataset_isassociated(&sigrdataset)) {
    328 		dns_rdataset_disassociate(&sigrdataset);
    329 	}
    330 	dns_rdatasetiter_destroy(&rdsiter);
    331 
    332 	return (ISC_R_SUCCESS);
    333 }
    334 
    335 static bool
    336 chain_compare(void *arg1, void *arg2) {
    337 	struct nsec3_chain_fixed *e1 = arg1, *e2 = arg2;
    338 	size_t len;
    339 
    340 	/*
    341 	 * Do each element in turn to get a stable sort.
    342 	 */
    343 	if (e1->hash < e2->hash) {
    344 		return (true);
    345 	}
    346 	if (e1->hash > e2->hash) {
    347 		return (false);
    348 	}
    349 	if (e1->iterations < e2->iterations) {
    350 		return (true);
    351 	}
    352 	if (e1->iterations > e2->iterations) {
    353 		return (false);
    354 	}
    355 	if (e1->salt_length < e2->salt_length) {
    356 		return (true);
    357 	}
    358 	if (e1->salt_length > e2->salt_length) {
    359 		return (false);
    360 	}
    361 	if (e1->next_length < e2->next_length) {
    362 		return (true);
    363 	}
    364 	if (e1->next_length > e2->next_length) {
    365 		return (false);
    366 	}
    367 	len = e1->salt_length + 2 * e1->next_length;
    368 	if (memcmp(e1 + 1, e2 + 1, len) < 0) {
    369 		return (true);
    370 	}
    371 	return (false);
    372 }
    373 
    374 static bool
    375 chain_equal(const struct nsec3_chain_fixed *e1,
    376 	    const struct nsec3_chain_fixed *e2) {
    377 	size_t len;
    378 
    379 	if (e1->hash != e2->hash) {
    380 		return (false);
    381 	}
    382 	if (e1->iterations != e2->iterations) {
    383 		return (false);
    384 	}
    385 	if (e1->salt_length != e2->salt_length) {
    386 		return (false);
    387 	}
    388 	if (e1->next_length != e2->next_length) {
    389 		return (false);
    390 	}
    391 	len = e1->salt_length + 2 * e1->next_length;
    392 	if (memcmp(e1 + 1, e2 + 1, len) != 0) {
    393 		return (false);
    394 	}
    395 	return (true);
    396 }
    397 
    398 static isc_result_t
    399 record_nsec3(const vctx_t *vctx, const unsigned char *rawhash,
    400 	     const dns_rdata_nsec3_t *nsec3, isc_heap_t *chains) {
    401 	struct nsec3_chain_fixed *element;
    402 	size_t len;
    403 	unsigned char *cp;
    404 	isc_result_t result;
    405 
    406 	len = sizeof(*element) + nsec3->next_length * 2 + nsec3->salt_length;
    407 
    408 	element = isc_mem_get(vctx->mctx, len);
    409 	memset(element, 0, len);
    410 	element->hash = nsec3->hash;
    411 	element->salt_length = nsec3->salt_length;
    412 	element->next_length = nsec3->next_length;
    413 	element->iterations = nsec3->iterations;
    414 	cp = (unsigned char *)(element + 1);
    415 	memmove(cp, nsec3->salt, nsec3->salt_length);
    416 	cp += nsec3->salt_length;
    417 	memmove(cp, rawhash, nsec3->next_length);
    418 	cp += nsec3->next_length;
    419 	memmove(cp, nsec3->next, nsec3->next_length);
    420 	result = isc_heap_insert(chains, element);
    421 	if (result != ISC_R_SUCCESS) {
    422 		zoneverify_log_error(vctx, "isc_heap_insert failed: %s",
    423 				     isc_result_totext(result));
    424 		isc_mem_put(vctx->mctx, element, len);
    425 	}
    426 	return (result);
    427 }
    428 
    429 static isc_result_t
    430 match_nsec3(const vctx_t *vctx, const dns_name_t *name,
    431 	    const dns_rdata_nsec3param_t *nsec3param, dns_rdataset_t *rdataset,
    432 	    const unsigned char types[8192], unsigned int maxtype,
    433 	    const unsigned char *rawhash, size_t rhsize,
    434 	    isc_result_t *vresult) {
    435 	unsigned char cbm[8244];
    436 	char namebuf[DNS_NAME_FORMATSIZE];
    437 	dns_rdata_nsec3_t nsec3;
    438 	isc_result_t result;
    439 	unsigned int len;
    440 
    441 	/*
    442 	 * Find matching NSEC3 record.
    443 	 */
    444 	for (result = dns_rdataset_first(rdataset); result == ISC_R_SUCCESS;
    445 	     result = dns_rdataset_next(rdataset))
    446 	{
    447 		dns_rdata_t rdata = DNS_RDATA_INIT;
    448 		dns_rdataset_current(rdataset, &rdata);
    449 		result = dns_rdata_tostruct(&rdata, &nsec3, NULL);
    450 		RUNTIME_CHECK(result == ISC_R_SUCCESS);
    451 		if (nsec3.hash == nsec3param->hash &&
    452 		    nsec3.next_length == rhsize &&
    453 		    nsec3.iterations == nsec3param->iterations &&
    454 		    nsec3.salt_length == nsec3param->salt_length &&
    455 		    memcmp(nsec3.salt, nsec3param->salt,
    456 			   nsec3param->salt_length) == 0)
    457 		{
    458 			break;
    459 		}
    460 	}
    461 	if (result != ISC_R_SUCCESS) {
    462 		dns_name_format(name, namebuf, sizeof(namebuf));
    463 		zoneverify_log_error(vctx, "Missing NSEC3 record for %s",
    464 				     namebuf);
    465 		*vresult = result;
    466 		return (ISC_R_SUCCESS);
    467 	}
    468 
    469 	/*
    470 	 * Check the type list.
    471 	 */
    472 	len = dns_nsec_compressbitmap(cbm, types, maxtype);
    473 	if (nsec3.len != len || memcmp(cbm, nsec3.typebits, len) != 0) {
    474 		dns_name_format(name, namebuf, sizeof(namebuf));
    475 		zoneverify_log_error(vctx,
    476 				     "Bad NSEC3 record for %s, bit map "
    477 				     "mismatch",
    478 				     namebuf);
    479 		*vresult = ISC_R_FAILURE;
    480 		return (ISC_R_SUCCESS);
    481 	}
    482 
    483 	/*
    484 	 * Record chain.
    485 	 */
    486 	result = record_nsec3(vctx, rawhash, &nsec3, vctx->expected_chains);
    487 	if (result != ISC_R_SUCCESS) {
    488 		zoneverify_log_error(vctx, "record_nsec3(): %s",
    489 				     isc_result_totext(result));
    490 		return (result);
    491 	}
    492 
    493 	/*
    494 	 * Make sure there is only one NSEC3 record with this set of
    495 	 * parameters.
    496 	 */
    497 	for (result = dns_rdataset_next(rdataset); result == ISC_R_SUCCESS;
    498 	     result = dns_rdataset_next(rdataset))
    499 	{
    500 		dns_rdata_t rdata = DNS_RDATA_INIT;
    501 		dns_rdataset_current(rdataset, &rdata);
    502 		result = dns_rdata_tostruct(&rdata, &nsec3, NULL);
    503 		RUNTIME_CHECK(result == ISC_R_SUCCESS);
    504 		if (nsec3.hash == nsec3param->hash &&
    505 		    nsec3.iterations == nsec3param->iterations &&
    506 		    nsec3.salt_length == nsec3param->salt_length &&
    507 		    memcmp(nsec3.salt, nsec3param->salt, nsec3.salt_length) ==
    508 			    0)
    509 		{
    510 			dns_name_format(name, namebuf, sizeof(namebuf));
    511 			zoneverify_log_error(vctx,
    512 					     "Multiple NSEC3 records with the "
    513 					     "same parameter set for %s",
    514 					     namebuf);
    515 			*vresult = DNS_R_DUPLICATE;
    516 			return (ISC_R_SUCCESS);
    517 		}
    518 	}
    519 	if (result != ISC_R_NOMORE) {
    520 		return (result);
    521 	}
    522 
    523 	*vresult = ISC_R_SUCCESS;
    524 
    525 	return (ISC_R_SUCCESS);
    526 }
    527 
    528 static bool
    529 innsec3params(const dns_rdata_nsec3_t *nsec3, dns_rdataset_t *nsec3paramset) {
    530 	dns_rdata_nsec3param_t nsec3param;
    531 	isc_result_t result;
    532 
    533 	for (result = dns_rdataset_first(nsec3paramset);
    534 	     result == ISC_R_SUCCESS; result = dns_rdataset_next(nsec3paramset))
    535 	{
    536 		dns_rdata_t rdata = DNS_RDATA_INIT;
    537 
    538 		dns_rdataset_current(nsec3paramset, &rdata);
    539 		result = dns_rdata_tostruct(&rdata, &nsec3param, NULL);
    540 		RUNTIME_CHECK(result == ISC_R_SUCCESS);
    541 		if (nsec3param.flags == 0 && nsec3param.hash == nsec3->hash &&
    542 		    nsec3param.iterations == nsec3->iterations &&
    543 		    nsec3param.salt_length == nsec3->salt_length &&
    544 		    memcmp(nsec3param.salt, nsec3->salt, nsec3->salt_length) ==
    545 			    0)
    546 		{
    547 			return (true);
    548 		}
    549 	}
    550 	return (false);
    551 }
    552 
    553 static isc_result_t
    554 record_found(const vctx_t *vctx, const dns_name_t *name, dns_dbnode_t *node,
    555 	     dns_rdataset_t *nsec3paramset) {
    556 	unsigned char owner[NSEC3_MAX_HASH_LENGTH];
    557 	dns_rdata_nsec3_t nsec3;
    558 	dns_rdataset_t rdataset;
    559 	dns_label_t hashlabel;
    560 	isc_buffer_t b;
    561 	isc_result_t result;
    562 
    563 	if (nsec3paramset == NULL || !dns_rdataset_isassociated(nsec3paramset))
    564 	{
    565 		return (ISC_R_SUCCESS);
    566 	}
    567 
    568 	dns_rdataset_init(&rdataset);
    569 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
    570 				     dns_rdatatype_nsec3, 0, 0, &rdataset,
    571 				     NULL);
    572 	if (result != ISC_R_SUCCESS) {
    573 		return (ISC_R_SUCCESS);
    574 	}
    575 
    576 	dns_name_getlabel(name, 0, &hashlabel);
    577 	isc_region_consume(&hashlabel, 1);
    578 	isc_buffer_init(&b, owner, sizeof(owner));
    579 	result = isc_base32hex_decoderegion(&hashlabel, &b);
    580 	if (result != ISC_R_SUCCESS) {
    581 		result = ISC_R_SUCCESS;
    582 		goto cleanup;
    583 	}
    584 
    585 	for (result = dns_rdataset_first(&rdataset); result == ISC_R_SUCCESS;
    586 	     result = dns_rdataset_next(&rdataset))
    587 	{
    588 		dns_rdata_t rdata = DNS_RDATA_INIT;
    589 		dns_rdataset_current(&rdataset, &rdata);
    590 		result = dns_rdata_tostruct(&rdata, &nsec3, NULL);
    591 		RUNTIME_CHECK(result == ISC_R_SUCCESS);
    592 		if (nsec3.next_length != isc_buffer_usedlength(&b)) {
    593 			continue;
    594 		}
    595 		/*
    596 		 * We only care about NSEC3 records that match a NSEC3PARAM
    597 		 * record.
    598 		 */
    599 		if (!innsec3params(&nsec3, nsec3paramset)) {
    600 			continue;
    601 		}
    602 
    603 		/*
    604 		 * Record chain.
    605 		 */
    606 		result = record_nsec3(vctx, owner, &nsec3, vctx->found_chains);
    607 		if (result != ISC_R_SUCCESS) {
    608 			zoneverify_log_error(vctx, "record_nsec3(): %s",
    609 					     isc_result_totext(result));
    610 			goto cleanup;
    611 		}
    612 	}
    613 	result = ISC_R_SUCCESS;
    614 
    615 cleanup:
    616 	dns_rdataset_disassociate(&rdataset);
    617 	return (result);
    618 }
    619 
    620 static isc_result_t
    621 isoptout(const vctx_t *vctx, const dns_rdata_t *nsec3rdata, bool *optout) {
    622 	dns_rdataset_t rdataset;
    623 	dns_rdata_t rdata = DNS_RDATA_INIT;
    624 	dns_rdata_nsec3_t nsec3;
    625 	dns_rdata_nsec3param_t nsec3param;
    626 	dns_fixedname_t fixed;
    627 	dns_name_t *hashname;
    628 	isc_result_t result;
    629 	dns_dbnode_t *node = NULL;
    630 	unsigned char rawhash[NSEC3_MAX_HASH_LENGTH];
    631 	size_t rhsize = sizeof(rawhash);
    632 
    633 	result = dns_rdata_tostruct(nsec3rdata, &nsec3param, NULL);
    634 	RUNTIME_CHECK(result == ISC_R_SUCCESS);
    635 
    636 	dns_fixedname_init(&fixed);
    637 	result = dns_nsec3_hashname(&fixed, rawhash, &rhsize, vctx->origin,
    638 				    vctx->origin, nsec3param.hash,
    639 				    nsec3param.iterations, nsec3param.salt,
    640 				    nsec3param.salt_length);
    641 	if (result != ISC_R_SUCCESS) {
    642 		zoneverify_log_error(vctx, "dns_nsec3_hashname(): %s",
    643 				     isc_result_totext(result));
    644 		return (result);
    645 	}
    646 
    647 	dns_rdataset_init(&rdataset);
    648 	hashname = dns_fixedname_name(&fixed);
    649 	result = dns_db_findnsec3node(vctx->db, hashname, false, &node);
    650 	if (result == ISC_R_SUCCESS) {
    651 		result = dns_db_findrdataset(vctx->db, node, vctx->ver,
    652 					     dns_rdatatype_nsec3, 0, 0,
    653 					     &rdataset, NULL);
    654 	}
    655 	if (result != ISC_R_SUCCESS) {
    656 		*optout = false;
    657 		result = ISC_R_SUCCESS;
    658 		goto done;
    659 	}
    660 
    661 	result = dns_rdataset_first(&rdataset);
    662 	if (result != ISC_R_SUCCESS) {
    663 		zoneverify_log_error(vctx, "dns_rdataset_first(): %s",
    664 				     isc_result_totext(result));
    665 		goto done;
    666 	}
    667 
    668 	dns_rdataset_current(&rdataset, &rdata);
    669 
    670 	result = dns_rdata_tostruct(&rdata, &nsec3, NULL);
    671 	RUNTIME_CHECK(result == ISC_R_SUCCESS);
    672 	*optout = ((nsec3.flags & DNS_NSEC3FLAG_OPTOUT) != 0);
    673 
    674 done:
    675 	if (dns_rdataset_isassociated(&rdataset)) {
    676 		dns_rdataset_disassociate(&rdataset);
    677 	}
    678 	if (node != NULL) {
    679 		dns_db_detachnode(vctx->db, &node);
    680 	}
    681 
    682 	return (result);
    683 }
    684 
    685 static isc_result_t
    686 verifynsec3(const vctx_t *vctx, const dns_name_t *name,
    687 	    const dns_rdata_t *rdata, bool delegation, bool empty,
    688 	    const unsigned char types[8192], unsigned int maxtype,
    689 	    isc_result_t *vresult) {
    690 	char namebuf[DNS_NAME_FORMATSIZE];
    691 	char hashbuf[DNS_NAME_FORMATSIZE];
    692 	dns_rdataset_t rdataset;
    693 	dns_rdata_nsec3param_t nsec3param;
    694 	dns_fixedname_t fixed;
    695 	dns_name_t *hashname;
    696 	isc_result_t result, tvresult = ISC_R_UNSET;
    697 	dns_dbnode_t *node = NULL;
    698 	unsigned char rawhash[NSEC3_MAX_HASH_LENGTH];
    699 	size_t rhsize = sizeof(rawhash);
    700 	bool optout = false;
    701 
    702 	result = dns_rdata_tostruct(rdata, &nsec3param, NULL);
    703 	RUNTIME_CHECK(result == ISC_R_SUCCESS);
    704 
    705 	if (nsec3param.flags != 0) {
    706 		return (ISC_R_SUCCESS);
    707 	}
    708 
    709 	if (!dns_nsec3_supportedhash(nsec3param.hash)) {
    710 		return (ISC_R_SUCCESS);
    711 	}
    712 
    713 	result = isoptout(vctx, rdata, &optout);
    714 	if (result != ISC_R_SUCCESS) {
    715 		return (result);
    716 	}
    717 
    718 	dns_fixedname_init(&fixed);
    719 	result = dns_nsec3_hashname(
    720 		&fixed, rawhash, &rhsize, name, vctx->origin, nsec3param.hash,
    721 		nsec3param.iterations, nsec3param.salt, nsec3param.salt_length);
    722 	if (result != ISC_R_SUCCESS) {
    723 		zoneverify_log_error(vctx, "dns_nsec3_hashname(): %s",
    724 				     isc_result_totext(result));
    725 		return (result);
    726 	}
    727 
    728 	/*
    729 	 * We don't use dns_db_find() here as it works with the chosen
    730 	 * nsec3 chain and we may also be called with uncommitted data
    731 	 * from dnssec-signzone so the secure status of the zone may not
    732 	 * be up to date.
    733 	 */
    734 	dns_rdataset_init(&rdataset);
    735 	hashname = dns_fixedname_name(&fixed);
    736 	result = dns_db_findnsec3node(vctx->db, hashname, false, &node);
    737 	if (result == ISC_R_SUCCESS) {
    738 		result = dns_db_findrdataset(vctx->db, node, vctx->ver,
    739 					     dns_rdatatype_nsec3, 0, 0,
    740 					     &rdataset, NULL);
    741 	}
    742 	if (result != ISC_R_SUCCESS &&
    743 	    (!delegation || (empty && !optout) ||
    744 	     (!empty && dns_nsec_isset(types, dns_rdatatype_ds))))
    745 	{
    746 		dns_name_format(name, namebuf, sizeof(namebuf));
    747 		dns_name_format(hashname, hashbuf, sizeof(hashbuf));
    748 		zoneverify_log_error(vctx, "Missing NSEC3 record for %s (%s)",
    749 				     namebuf, hashbuf);
    750 	} else if (result == ISC_R_NOTFOUND && delegation && (!empty || optout))
    751 	{
    752 		result = ISC_R_SUCCESS;
    753 	} else if (result == ISC_R_SUCCESS) {
    754 		result = match_nsec3(vctx, name, &nsec3param, &rdataset, types,
    755 				     maxtype, rawhash, rhsize, &tvresult);
    756 		if (result != ISC_R_SUCCESS) {
    757 			goto done;
    758 		}
    759 		result = tvresult;
    760 	}
    761 
    762 	*vresult = result;
    763 	result = ISC_R_SUCCESS;
    764 
    765 done:
    766 	if (dns_rdataset_isassociated(&rdataset)) {
    767 		dns_rdataset_disassociate(&rdataset);
    768 	}
    769 	if (node != NULL) {
    770 		dns_db_detachnode(vctx->db, &node);
    771 	}
    772 
    773 	return (result);
    774 }
    775 
    776 static isc_result_t
    777 verifynsec3s(const vctx_t *vctx, const dns_name_t *name,
    778 	     dns_rdataset_t *nsec3paramset, bool delegation, bool empty,
    779 	     const unsigned char types[8192], unsigned int maxtype,
    780 	     isc_result_t *vresult) {
    781 	isc_result_t result;
    782 
    783 	for (result = dns_rdataset_first(nsec3paramset);
    784 	     result == ISC_R_SUCCESS; result = dns_rdataset_next(nsec3paramset))
    785 	{
    786 		dns_rdata_t rdata = DNS_RDATA_INIT;
    787 
    788 		dns_rdataset_current(nsec3paramset, &rdata);
    789 		result = verifynsec3(vctx, name, &rdata, delegation, empty,
    790 				     types, maxtype, vresult);
    791 		if (result != ISC_R_SUCCESS) {
    792 			return (result);
    793 		}
    794 		if (*vresult != ISC_R_SUCCESS) {
    795 			break;
    796 		}
    797 	}
    798 	if (result == ISC_R_NOMORE) {
    799 		result = ISC_R_SUCCESS;
    800 	}
    801 	return (result);
    802 }
    803 
    804 static isc_result_t
    805 verifyset(vctx_t *vctx, dns_rdataset_t *rdataset, const dns_name_t *name,
    806 	  dns_dbnode_t *node, dst_key_t **dstkeys, size_t nkeys) {
    807 	unsigned char set_algorithms[256];
    808 	char namebuf[DNS_NAME_FORMATSIZE];
    809 	char algbuf[DNS_SECALG_FORMATSIZE];
    810 	char typebuf[DNS_RDATATYPE_FORMATSIZE];
    811 	dns_rdataset_t sigrdataset;
    812 	dns_rdatasetiter_t *rdsiter = NULL;
    813 	isc_result_t result;
    814 	int i;
    815 
    816 	dns_rdataset_init(&sigrdataset);
    817 	result = dns_db_allrdatasets(vctx->db, node, vctx->ver, 0, &rdsiter);
    818 	if (result != ISC_R_SUCCESS) {
    819 		zoneverify_log_error(vctx, "dns_db_allrdatasets(): %s",
    820 				     isc_result_totext(result));
    821 		return (result);
    822 	}
    823 	for (result = dns_rdatasetiter_first(rdsiter); result == ISC_R_SUCCESS;
    824 	     result = dns_rdatasetiter_next(rdsiter))
    825 	{
    826 		dns_rdatasetiter_current(rdsiter, &sigrdataset);
    827 		if (sigrdataset.type == dns_rdatatype_rrsig &&
    828 		    sigrdataset.covers == rdataset->type)
    829 		{
    830 			break;
    831 		}
    832 		dns_rdataset_disassociate(&sigrdataset);
    833 	}
    834 	if (result != ISC_R_SUCCESS) {
    835 		dns_name_format(name, namebuf, sizeof(namebuf));
    836 		dns_rdatatype_format(rdataset->type, typebuf, sizeof(typebuf));
    837 		zoneverify_log_error(vctx, "No signatures for %s/%s", namebuf,
    838 				     typebuf);
    839 		for (i = 0; i < 256; i++) {
    840 			if (vctx->act_algorithms[i] != 0) {
    841 				vctx->bad_algorithms[i] = 1;
    842 			}
    843 		}
    844 		result = ISC_R_SUCCESS;
    845 		goto done;
    846 	}
    847 
    848 	memset(set_algorithms, 0, sizeof(set_algorithms));
    849 	for (result = dns_rdataset_first(&sigrdataset); result == ISC_R_SUCCESS;
    850 	     result = dns_rdataset_next(&sigrdataset))
    851 	{
    852 		dns_rdata_t rdata = DNS_RDATA_INIT;
    853 		dns_rdata_rrsig_t sig;
    854 
    855 		dns_rdataset_current(&sigrdataset, &rdata);
    856 		result = dns_rdata_tostruct(&rdata, &sig, NULL);
    857 		RUNTIME_CHECK(result == ISC_R_SUCCESS);
    858 		if (rdataset->ttl != sig.originalttl) {
    859 			dns_name_format(name, namebuf, sizeof(namebuf));
    860 			dns_rdatatype_format(rdataset->type, typebuf,
    861 					     sizeof(typebuf));
    862 			zoneverify_log_error(vctx,
    863 					     "TTL mismatch for "
    864 					     "%s %s keytag %u",
    865 					     namebuf, typebuf, sig.keyid);
    866 			continue;
    867 		}
    868 		if ((set_algorithms[sig.algorithm] != 0) ||
    869 		    (vctx->act_algorithms[sig.algorithm] == 0))
    870 		{
    871 			continue;
    872 		}
    873 		if (goodsig(vctx, &rdata, name, dstkeys, nkeys, rdataset)) {
    874 			dns_rdataset_settrust(rdataset, dns_trust_secure);
    875 			dns_rdataset_settrust(&sigrdataset, dns_trust_secure);
    876 			set_algorithms[sig.algorithm] = 1;
    877 		}
    878 	}
    879 	result = ISC_R_SUCCESS;
    880 
    881 	if (memcmp(set_algorithms, vctx->act_algorithms,
    882 		   sizeof(set_algorithms))) {
    883 		dns_name_format(name, namebuf, sizeof(namebuf));
    884 		dns_rdatatype_format(rdataset->type, typebuf, sizeof(typebuf));
    885 		for (i = 0; i < 256; i++) {
    886 			if ((vctx->act_algorithms[i] != 0) &&
    887 			    (set_algorithms[i] == 0)) {
    888 				dns_secalg_format(i, algbuf, sizeof(algbuf));
    889 				zoneverify_log_error(vctx,
    890 						     "No correct %s signature "
    891 						     "for %s %s",
    892 						     algbuf, namebuf, typebuf);
    893 				vctx->bad_algorithms[i] = 1;
    894 			}
    895 		}
    896 	}
    897 
    898 done:
    899 	if (dns_rdataset_isassociated(&sigrdataset)) {
    900 		dns_rdataset_disassociate(&sigrdataset);
    901 	}
    902 	dns_rdatasetiter_destroy(&rdsiter);
    903 
    904 	return (result);
    905 }
    906 
    907 static isc_result_t
    908 verifynode(vctx_t *vctx, const dns_name_t *name, dns_dbnode_t *node,
    909 	   bool delegation, dst_key_t **dstkeys, size_t nkeys,
    910 	   dns_rdataset_t *nsecset, dns_rdataset_t *nsec3paramset,
    911 	   const dns_name_t *nextname, isc_result_t *vresult) {
    912 	unsigned char types[8192];
    913 	unsigned int maxtype = 0;
    914 	dns_rdataset_t rdataset;
    915 	dns_rdatasetiter_t *rdsiter = NULL;
    916 	isc_result_t result, tvresult = ISC_R_UNSET;
    917 
    918 	REQUIRE(vresult != NULL || (nsecset == NULL && nsec3paramset == NULL));
    919 
    920 	memset(types, 0, sizeof(types));
    921 	result = dns_db_allrdatasets(vctx->db, node, vctx->ver, 0, &rdsiter);
    922 	if (result != ISC_R_SUCCESS) {
    923 		zoneverify_log_error(vctx, "dns_db_allrdatasets(): %s",
    924 				     isc_result_totext(result));
    925 		return (result);
    926 	}
    927 	result = dns_rdatasetiter_first(rdsiter);
    928 	dns_rdataset_init(&rdataset);
    929 	while (result == ISC_R_SUCCESS) {
    930 		dns_rdatasetiter_current(rdsiter, &rdataset);
    931 		/*
    932 		 * If we are not at a delegation then everything should be
    933 		 * signed.  If we are at a delegation then only the DS set
    934 		 * is signed.  The NS set is not signed at a delegation but
    935 		 * its existence is recorded in the bit map.  Anything else
    936 		 * other than NSEC and DS is not signed at a delegation.
    937 		 */
    938 		if (rdataset.type != dns_rdatatype_rrsig &&
    939 		    rdataset.type != dns_rdatatype_dnskey &&
    940 		    (!delegation || rdataset.type == dns_rdatatype_ds ||
    941 		     rdataset.type == dns_rdatatype_nsec))
    942 		{
    943 			result = verifyset(vctx, &rdataset, name, node, dstkeys,
    944 					   nkeys);
    945 			if (result != ISC_R_SUCCESS) {
    946 				dns_rdataset_disassociate(&rdataset);
    947 				dns_rdatasetiter_destroy(&rdsiter);
    948 				return (result);
    949 			}
    950 			dns_nsec_setbit(types, rdataset.type, 1);
    951 			if (rdataset.type > maxtype) {
    952 				maxtype = rdataset.type;
    953 			}
    954 		} else if (rdataset.type != dns_rdatatype_rrsig &&
    955 			   rdataset.type != dns_rdatatype_dnskey)
    956 		{
    957 			if (rdataset.type == dns_rdatatype_ns) {
    958 				dns_nsec_setbit(types, rdataset.type, 1);
    959 			}
    960 			result = check_no_rrsig(vctx, &rdataset, name, node);
    961 			if (result != ISC_R_SUCCESS) {
    962 				dns_rdataset_disassociate(&rdataset);
    963 				dns_rdatasetiter_destroy(&rdsiter);
    964 				return (result);
    965 			}
    966 		} else {
    967 			dns_nsec_setbit(types, rdataset.type, 1);
    968 		}
    969 		dns_rdataset_disassociate(&rdataset);
    970 		result = dns_rdatasetiter_next(rdsiter);
    971 	}
    972 	dns_rdatasetiter_destroy(&rdsiter);
    973 	if (result != ISC_R_NOMORE) {
    974 		zoneverify_log_error(vctx, "rdataset iteration failed: %s",
    975 				     isc_result_totext(result));
    976 		return (result);
    977 	}
    978 
    979 	if (vresult == NULL) {
    980 		return (ISC_R_SUCCESS);
    981 	}
    982 
    983 	*vresult = ISC_R_SUCCESS;
    984 
    985 	if (nsecset != NULL && dns_rdataset_isassociated(nsecset)) {
    986 		result = verifynsec(vctx, name, node, nextname, &tvresult);
    987 		if (result != ISC_R_SUCCESS) {
    988 			return (result);
    989 		}
    990 		*vresult = tvresult;
    991 	}
    992 
    993 	if (nsec3paramset != NULL && dns_rdataset_isassociated(nsec3paramset)) {
    994 		result = verifynsec3s(vctx, name, nsec3paramset, delegation,
    995 				      false, types, maxtype, &tvresult);
    996 		if (result != ISC_R_SUCCESS) {
    997 			return (result);
    998 		}
    999 		if (*vresult == ISC_R_SUCCESS) {
   1000 			*vresult = tvresult;
   1001 		}
   1002 	}
   1003 
   1004 	return (ISC_R_SUCCESS);
   1005 }
   1006 
   1007 static isc_result_t
   1008 is_empty(const vctx_t *vctx, dns_dbnode_t *node, bool *empty) {
   1009 	dns_rdatasetiter_t *rdsiter = NULL;
   1010 	isc_result_t result;
   1011 
   1012 	result = dns_db_allrdatasets(vctx->db, node, vctx->ver, 0, &rdsiter);
   1013 	if (result != ISC_R_SUCCESS) {
   1014 		zoneverify_log_error(vctx, "dns_db_allrdatasets(): %s",
   1015 				     isc_result_totext(result));
   1016 		return (result);
   1017 	}
   1018 	result = dns_rdatasetiter_first(rdsiter);
   1019 	dns_rdatasetiter_destroy(&rdsiter);
   1020 
   1021 	*empty = (result == ISC_R_NOMORE);
   1022 
   1023 	return (ISC_R_SUCCESS);
   1024 }
   1025 
   1026 static isc_result_t
   1027 check_no_nsec(const vctx_t *vctx, const dns_name_t *name, dns_dbnode_t *node) {
   1028 	bool nsec_exists = false;
   1029 	dns_rdataset_t rdataset;
   1030 	isc_result_t result;
   1031 
   1032 	dns_rdataset_init(&rdataset);
   1033 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
   1034 				     dns_rdatatype_nsec, 0, 0, &rdataset, NULL);
   1035 	if (result != ISC_R_NOTFOUND) {
   1036 		char namebuf[DNS_NAME_FORMATSIZE];
   1037 		dns_name_format(name, namebuf, sizeof(namebuf));
   1038 		zoneverify_log_error(vctx, "unexpected NSEC RRset at %s",
   1039 				     namebuf);
   1040 		nsec_exists = true;
   1041 	}
   1042 
   1043 	if (dns_rdataset_isassociated(&rdataset)) {
   1044 		dns_rdataset_disassociate(&rdataset);
   1045 	}
   1046 
   1047 	return (nsec_exists ? ISC_R_FAILURE : ISC_R_SUCCESS);
   1048 }
   1049 
   1050 static bool
   1051 newchain(const struct nsec3_chain_fixed *first,
   1052 	 const struct nsec3_chain_fixed *e) {
   1053 	if (first->hash != e->hash || first->iterations != e->iterations ||
   1054 	    first->salt_length != e->salt_length ||
   1055 	    first->next_length != e->next_length ||
   1056 	    memcmp(first + 1, e + 1, first->salt_length) != 0)
   1057 	{
   1058 		return (true);
   1059 	}
   1060 	return (false);
   1061 }
   1062 
   1063 static void
   1064 free_element(isc_mem_t *mctx, struct nsec3_chain_fixed *e) {
   1065 	size_t len;
   1066 
   1067 	len = sizeof(*e) + e->salt_length + 2 * e->next_length;
   1068 	isc_mem_put(mctx, e, len);
   1069 }
   1070 
   1071 static void
   1072 free_element_heap(void *element, void *uap) {
   1073 	struct nsec3_chain_fixed *e = (struct nsec3_chain_fixed *)element;
   1074 	isc_mem_t *mctx = (isc_mem_t *)uap;
   1075 
   1076 	free_element(mctx, e);
   1077 }
   1078 
   1079 static bool
   1080 _checknext(const vctx_t *vctx, const struct nsec3_chain_fixed *first,
   1081 	   const struct nsec3_chain_fixed *e) {
   1082 	char buf[512];
   1083 	const unsigned char *d1 = (const unsigned char *)(first + 1);
   1084 	const unsigned char *d2 = (const unsigned char *)(e + 1);
   1085 	isc_buffer_t b;
   1086 	isc_region_t sr;
   1087 
   1088 	d1 += first->salt_length + first->next_length;
   1089 	d2 += e->salt_length;
   1090 
   1091 	if (memcmp(d1, d2, first->next_length) == 0) {
   1092 		return (true);
   1093 	}
   1094 
   1095 	DE_CONST(d1 - first->next_length, sr.base);
   1096 	sr.length = first->next_length;
   1097 	isc_buffer_init(&b, buf, sizeof(buf));
   1098 	isc_base32hex_totext(&sr, 1, "", &b);
   1099 	zoneverify_log_error(vctx, "Break in NSEC3 chain at: %.*s",
   1100 			     (int)isc_buffer_usedlength(&b), buf);
   1101 
   1102 	DE_CONST(d1, sr.base);
   1103 	sr.length = first->next_length;
   1104 	isc_buffer_init(&b, buf, sizeof(buf));
   1105 	isc_base32hex_totext(&sr, 1, "", &b);
   1106 	zoneverify_log_error(vctx, "Expected: %.*s",
   1107 			     (int)isc_buffer_usedlength(&b), buf);
   1108 
   1109 	DE_CONST(d2, sr.base);
   1110 	sr.length = first->next_length;
   1111 	isc_buffer_init(&b, buf, sizeof(buf));
   1112 	isc_base32hex_totext(&sr, 1, "", &b);
   1113 	zoneverify_log_error(vctx, "Found: %.*s",
   1114 			     (int)isc_buffer_usedlength(&b), buf);
   1115 
   1116 	return (false);
   1117 }
   1118 
   1119 static inline bool
   1120 checknext(isc_mem_t *mctx, const vctx_t *vctx,
   1121 	  const struct nsec3_chain_fixed *first, struct nsec3_chain_fixed *prev,
   1122 	  const struct nsec3_chain_fixed *cur) {
   1123 	bool result = _checknext(vctx, prev, cur);
   1124 
   1125 	if (prev != first) {
   1126 		free_element(mctx, prev);
   1127 	}
   1128 
   1129 	return (result);
   1130 }
   1131 
   1132 static inline bool
   1133 checklast(isc_mem_t *mctx, const vctx_t *vctx, struct nsec3_chain_fixed *first,
   1134 	  struct nsec3_chain_fixed *prev) {
   1135 	bool result = _checknext(vctx, prev, first);
   1136 	if (prev != first) {
   1137 		free_element(mctx, prev);
   1138 	}
   1139 	free_element(mctx, first);
   1140 
   1141 	return (result);
   1142 }
   1143 
   1144 static isc_result_t
   1145 verify_nsec3_chains(const vctx_t *vctx, isc_mem_t *mctx) {
   1146 	isc_result_t result = ISC_R_SUCCESS;
   1147 	struct nsec3_chain_fixed *e, *f = NULL;
   1148 	struct nsec3_chain_fixed *first = NULL, *prev = NULL;
   1149 
   1150 	while ((e = isc_heap_element(vctx->expected_chains, 1)) != NULL) {
   1151 		isc_heap_delete(vctx->expected_chains, 1);
   1152 		if (f == NULL) {
   1153 			f = isc_heap_element(vctx->found_chains, 1);
   1154 		}
   1155 		if (f != NULL) {
   1156 			isc_heap_delete(vctx->found_chains, 1);
   1157 
   1158 			/*
   1159 			 * Check that they match.
   1160 			 */
   1161 			if (chain_equal(e, f)) {
   1162 				free_element(mctx, f);
   1163 				f = NULL;
   1164 			} else {
   1165 				if (result == ISC_R_SUCCESS) {
   1166 					zoneverify_log_error(vctx, "Expected "
   1167 								   "and found "
   1168 								   "NSEC3 "
   1169 								   "chains not "
   1170 								   "equal");
   1171 				}
   1172 				result = ISC_R_FAILURE;
   1173 				/*
   1174 				 * Attempt to resync found_chain.
   1175 				 */
   1176 				while (f != NULL && !chain_compare(e, f)) {
   1177 					free_element(mctx, f);
   1178 					f = isc_heap_element(vctx->found_chains,
   1179 							     1);
   1180 					if (f != NULL) {
   1181 						isc_heap_delete(
   1182 							vctx->found_chains, 1);
   1183 					}
   1184 					if (f != NULL && chain_equal(e, f)) {
   1185 						free_element(mctx, f);
   1186 						f = NULL;
   1187 						break;
   1188 					}
   1189 				}
   1190 			}
   1191 		} else if (result == ISC_R_SUCCESS) {
   1192 			zoneverify_log_error(vctx, "Expected and found NSEC3 "
   1193 						   "chains "
   1194 						   "not equal");
   1195 			result = ISC_R_FAILURE;
   1196 		}
   1197 
   1198 		if (first == NULL) {
   1199 			prev = first = e;
   1200 		} else if (newchain(first, e)) {
   1201 			if (!checklast(mctx, vctx, first, prev)) {
   1202 				result = ISC_R_FAILURE;
   1203 			}
   1204 
   1205 			prev = first = e;
   1206 		} else {
   1207 			if (!checknext(mctx, vctx, first, prev, e)) {
   1208 				result = ISC_R_FAILURE;
   1209 			}
   1210 
   1211 			prev = e;
   1212 		}
   1213 	}
   1214 	if (prev != NULL) {
   1215 		if (!checklast(mctx, vctx, first, prev)) {
   1216 			result = ISC_R_FAILURE;
   1217 		}
   1218 	}
   1219 	do {
   1220 		if (f != NULL) {
   1221 			if (result == ISC_R_SUCCESS) {
   1222 				zoneverify_log_error(vctx, "Expected and found "
   1223 							   "NSEC3 chains not "
   1224 							   "equal");
   1225 				result = ISC_R_FAILURE;
   1226 			}
   1227 			free_element(mctx, f);
   1228 		}
   1229 		f = isc_heap_element(vctx->found_chains, 1);
   1230 		if (f != NULL) {
   1231 			isc_heap_delete(vctx->found_chains, 1);
   1232 		}
   1233 	} while (f != NULL);
   1234 
   1235 	return (result);
   1236 }
   1237 
   1238 static isc_result_t
   1239 verifyemptynodes(const vctx_t *vctx, const dns_name_t *name,
   1240 		 const dns_name_t *prevname, bool isdelegation,
   1241 		 dns_rdataset_t *nsec3paramset, isc_result_t *vresult) {
   1242 	dns_namereln_t reln;
   1243 	int order;
   1244 	unsigned int labels, nlabels, i;
   1245 	dns_name_t suffix;
   1246 	isc_result_t result, tvresult = ISC_R_UNSET;
   1247 
   1248 	*vresult = ISC_R_SUCCESS;
   1249 
   1250 	reln = dns_name_fullcompare(prevname, name, &order, &labels);
   1251 	if (order >= 0) {
   1252 		return (ISC_R_SUCCESS);
   1253 	}
   1254 
   1255 	nlabels = dns_name_countlabels(name);
   1256 
   1257 	if (reln == dns_namereln_commonancestor ||
   1258 	    reln == dns_namereln_contains) {
   1259 		dns_name_init(&suffix, NULL);
   1260 		for (i = labels + 1; i < nlabels; i++) {
   1261 			dns_name_getlabelsequence(name, nlabels - i, i,
   1262 						  &suffix);
   1263 			if (nsec3paramset != NULL &&
   1264 			    dns_rdataset_isassociated(nsec3paramset)) {
   1265 				result = verifynsec3s(
   1266 					vctx, &suffix, nsec3paramset,
   1267 					isdelegation, true, NULL, 0, &tvresult);
   1268 				if (result != ISC_R_SUCCESS) {
   1269 					return (result);
   1270 				}
   1271 				if (*vresult == ISC_R_SUCCESS) {
   1272 					*vresult = tvresult;
   1273 				}
   1274 			}
   1275 		}
   1276 	}
   1277 
   1278 	return (ISC_R_SUCCESS);
   1279 }
   1280 
   1281 static isc_result_t
   1282 vctx_init(vctx_t *vctx, isc_mem_t *mctx, dns_zone_t *zone, dns_db_t *db,
   1283 	  dns_dbversion_t *ver, dns_name_t *origin, dns_keytable_t *secroots) {
   1284 	isc_result_t result;
   1285 
   1286 	memset(vctx, 0, sizeof(*vctx));
   1287 
   1288 	vctx->mctx = mctx;
   1289 	vctx->zone = zone;
   1290 	vctx->db = db;
   1291 	vctx->ver = ver;
   1292 	vctx->origin = origin;
   1293 	vctx->secroots = secroots;
   1294 	vctx->goodksk = false;
   1295 	vctx->goodzsk = false;
   1296 
   1297 	dns_rdataset_init(&vctx->keyset);
   1298 	dns_rdataset_init(&vctx->keysigs);
   1299 	dns_rdataset_init(&vctx->soaset);
   1300 	dns_rdataset_init(&vctx->soasigs);
   1301 	dns_rdataset_init(&vctx->nsecset);
   1302 	dns_rdataset_init(&vctx->nsecsigs);
   1303 	dns_rdataset_init(&vctx->nsec3paramset);
   1304 	dns_rdataset_init(&vctx->nsec3paramsigs);
   1305 
   1306 	vctx->expected_chains = NULL;
   1307 	result = isc_heap_create(mctx, chain_compare, NULL, 1024,
   1308 				 &vctx->expected_chains);
   1309 	if (result != ISC_R_SUCCESS) {
   1310 		return (result);
   1311 	}
   1312 
   1313 	vctx->found_chains = NULL;
   1314 	result = isc_heap_create(mctx, chain_compare, NULL, 1024,
   1315 				 &vctx->found_chains);
   1316 	if (result != ISC_R_SUCCESS) {
   1317 		isc_heap_destroy(&vctx->expected_chains);
   1318 		return (result);
   1319 	}
   1320 
   1321 	return (result);
   1322 }
   1323 
   1324 static void
   1325 vctx_destroy(vctx_t *vctx) {
   1326 	if (dns_rdataset_isassociated(&vctx->keyset)) {
   1327 		dns_rdataset_disassociate(&vctx->keyset);
   1328 	}
   1329 	if (dns_rdataset_isassociated(&vctx->keysigs)) {
   1330 		dns_rdataset_disassociate(&vctx->keysigs);
   1331 	}
   1332 	if (dns_rdataset_isassociated(&vctx->soaset)) {
   1333 		dns_rdataset_disassociate(&vctx->soaset);
   1334 	}
   1335 	if (dns_rdataset_isassociated(&vctx->soasigs)) {
   1336 		dns_rdataset_disassociate(&vctx->soasigs);
   1337 	}
   1338 	if (dns_rdataset_isassociated(&vctx->nsecset)) {
   1339 		dns_rdataset_disassociate(&vctx->nsecset);
   1340 	}
   1341 	if (dns_rdataset_isassociated(&vctx->nsecsigs)) {
   1342 		dns_rdataset_disassociate(&vctx->nsecsigs);
   1343 	}
   1344 	if (dns_rdataset_isassociated(&vctx->nsec3paramset)) {
   1345 		dns_rdataset_disassociate(&vctx->nsec3paramset);
   1346 	}
   1347 	if (dns_rdataset_isassociated(&vctx->nsec3paramsigs)) {
   1348 		dns_rdataset_disassociate(&vctx->nsec3paramsigs);
   1349 	}
   1350 	isc_heap_foreach(vctx->expected_chains, free_element_heap, vctx->mctx);
   1351 	isc_heap_destroy(&vctx->expected_chains);
   1352 	isc_heap_foreach(vctx->found_chains, free_element_heap, vctx->mctx);
   1353 	isc_heap_destroy(&vctx->found_chains);
   1354 }
   1355 
   1356 static isc_result_t
   1357 check_apex_rrsets(vctx_t *vctx) {
   1358 	dns_dbnode_t *node = NULL;
   1359 	isc_result_t result;
   1360 
   1361 	result = dns_db_findnode(vctx->db, vctx->origin, false, &node);
   1362 	if (result != ISC_R_SUCCESS) {
   1363 		zoneverify_log_error(vctx,
   1364 				     "failed to find the zone's origin: %s",
   1365 				     isc_result_totext(result));
   1366 		return (result);
   1367 	}
   1368 
   1369 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
   1370 				     dns_rdatatype_dnskey, 0, 0, &vctx->keyset,
   1371 				     &vctx->keysigs);
   1372 	if (result != ISC_R_SUCCESS) {
   1373 		zoneverify_log_error(vctx, "Zone contains no DNSSEC keys");
   1374 		goto done;
   1375 	}
   1376 
   1377 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
   1378 				     dns_rdatatype_soa, 0, 0, &vctx->soaset,
   1379 				     &vctx->soasigs);
   1380 	if (result != ISC_R_SUCCESS) {
   1381 		zoneverify_log_error(vctx, "Zone contains no SOA record");
   1382 		goto done;
   1383 	}
   1384 
   1385 	result = dns_db_findrdataset(vctx->db, node, vctx->ver,
   1386 				     dns_rdatatype_nsec, 0, 0, &vctx->nsecset,
   1387 				     &vctx->nsecsigs);
   1388 	if (result != ISC_R_SUCCESS && result != ISC_R_NOTFOUND) {
   1389 		zoneverify_log_error(vctx, "NSEC lookup failed");
   1390 		goto done;
   1391 	}
   1392 
   1393 	result = dns_db_findrdataset(
   1394 		vctx->db, node, vctx->ver, dns_rdatatype_nsec3param, 0, 0,
   1395 		&vctx->nsec3paramset, &vctx->nsec3paramsigs);
   1396 	if (result != ISC_R_SUCCESS && result != ISC_R_NOTFOUND) {
   1397 		zoneverify_log_error(vctx, "NSEC3PARAM lookup failed");
   1398 		goto done;
   1399 	}
   1400 
   1401 	if (!dns_rdataset_isassociated(&vctx->keysigs)) {
   1402 		zoneverify_log_error(vctx, "DNSKEY is not signed "
   1403 					   "(keys offline or inactive?)");
   1404 		result = ISC_R_FAILURE;
   1405 		goto done;
   1406 	}
   1407 
   1408 	if (!dns_rdataset_isassociated(&vctx->soasigs)) {
   1409 		zoneverify_log_error(vctx, "SOA is not signed "
   1410 					   "(keys offline or inactive?)");
   1411 		result = ISC_R_FAILURE;
   1412 		goto done;
   1413 	}
   1414 
   1415 	if (dns_rdataset_isassociated(&vctx->nsecset) &&
   1416 	    !dns_rdataset_isassociated(&vctx->nsecsigs))
   1417 	{
   1418 		zoneverify_log_error(vctx, "NSEC is not signed "
   1419 					   "(keys offline or inactive?)");
   1420 		result = ISC_R_FAILURE;
   1421 		goto done;
   1422 	}
   1423 
   1424 	if (dns_rdataset_isassociated(&vctx->nsec3paramset) &&
   1425 	    !dns_rdataset_isassociated(&vctx->nsec3paramsigs))
   1426 	{
   1427 		zoneverify_log_error(vctx, "NSEC3PARAM is not signed "
   1428 					   "(keys offline or inactive?)");
   1429 		result = ISC_R_FAILURE;
   1430 		goto done;
   1431 	}
   1432 
   1433 	if (!dns_rdataset_isassociated(&vctx->nsecset) &&
   1434 	    !dns_rdataset_isassociated(&vctx->nsec3paramset))
   1435 	{
   1436 		zoneverify_log_error(vctx, "No valid NSEC/NSEC3 chain for "
   1437 					   "testing");
   1438 		result = ISC_R_FAILURE;
   1439 		goto done;
   1440 	}
   1441 
   1442 	result = ISC_R_SUCCESS;
   1443 
   1444 done:
   1445 	dns_db_detachnode(vctx->db, &node);
   1446 
   1447 	return (result);
   1448 }
   1449 
   1450 /*%
   1451  * Update 'vctx' tables tracking active and standby key algorithms used in the
   1452  * verified zone based on the signatures made using 'dnskey' (prepared from
   1453  * 'rdata') found at zone apex.  Set 'vctx->goodksk' or 'vctx->goodzsk' to true
   1454  * if 'dnskey' correctly signs the DNSKEY RRset at zone apex and either
   1455  * 'vctx->secroots' is NULL or 'dnskey' is present in 'vctx->secroots'.
   1456  *
   1457  * The variables to update are chosen based on 'is_ksk', which is true when
   1458  * 'dnskey' is a KSK and false otherwise.
   1459  */
   1460 static void
   1461 check_dnskey_sigs(vctx_t *vctx, const dns_rdata_dnskey_t *dnskey,
   1462 		  dns_rdata_t *keyrdata, bool is_ksk) {
   1463 	unsigned char *active_keys = NULL, *standby_keys = NULL;
   1464 	dns_keynode_t *keynode = NULL;
   1465 	bool *goodkey = NULL;
   1466 	dst_key_t *key = NULL;
   1467 	isc_result_t result;
   1468 	dns_rdataset_t dsset;
   1469 
   1470 	active_keys = (is_ksk ? vctx->ksk_algorithms : vctx->zsk_algorithms);
   1471 	standby_keys = (is_ksk ? vctx->standby_ksk : vctx->standby_zsk);
   1472 	goodkey = (is_ksk ? &vctx->goodksk : &vctx->goodzsk);
   1473 
   1474 	/*
   1475 	 * First, does this key sign the DNSKEY rrset?
   1476 	 */
   1477 	if (!dns_dnssec_selfsigns(keyrdata, vctx->origin, &vctx->keyset,
   1478 				  &vctx->keysigs, false, vctx->mctx))
   1479 	{
   1480 		if (!is_ksk &&
   1481 		    dns_dnssec_signs(keyrdata, vctx->origin, &vctx->soaset,
   1482 				     &vctx->soasigs, false, vctx->mctx))
   1483 		{
   1484 			if (active_keys[dnskey->algorithm] != 255) {
   1485 				active_keys[dnskey->algorithm]++;
   1486 			}
   1487 		} else {
   1488 			if (standby_keys[dnskey->algorithm] != 255) {
   1489 				standby_keys[dnskey->algorithm]++;
   1490 			}
   1491 		}
   1492 		return;
   1493 	}
   1494 
   1495 	if (active_keys[dnskey->algorithm] != 255) {
   1496 		active_keys[dnskey->algorithm]++;
   1497 	}
   1498 
   1499 	/*
   1500 	 * If a trust anchor table was not supplied, a correctly self-signed
   1501 	 * DNSKEY RRset is good enough.
   1502 	 */
   1503 	if (vctx->secroots == NULL) {
   1504 		*goodkey = true;
   1505 		return;
   1506 	}
   1507 
   1508 	/*
   1509 	 * Convert the supplied key rdata to dst_key_t. (If this
   1510 	 * fails we can't go further.)
   1511 	 */
   1512 	result = dns_dnssec_keyfromrdata(vctx->origin, keyrdata, vctx->mctx,
   1513 					 &key);
   1514 	RUNTIME_CHECK(result == ISC_R_SUCCESS);
   1515 
   1516 	/*
   1517 	 * Look up the supplied key in the trust anchor table.
   1518 	 * If we don't find an exact match, or if the keynode data
   1519 	 * is NULL, then we have neither a DNSKEY nor a DS format
   1520 	 * trust anchor, and can give up.
   1521 	 */
   1522 	result = dns_keytable_find(vctx->secroots, vctx->origin, &keynode);
   1523 	if (result != ISC_R_SUCCESS) {
   1524 		/* No such trust anchor */
   1525 		goto cleanup;
   1526 	}
   1527 
   1528 	/*
   1529 	 * If the keynode has any DS format trust anchors, that means
   1530 	 * it doesn't have any DNSKEY ones. So, we can check for a DS
   1531 	 * match and then stop.
   1532 	 */
   1533 	dns_rdataset_init(&dsset);
   1534 	if (dns_keynode_dsset(keynode, &dsset)) {
   1535 		for (result = dns_rdataset_first(&dsset);
   1536 		     result == ISC_R_SUCCESS;
   1537 		     result = dns_rdataset_next(&dsset))
   1538 		{
   1539 			dns_rdata_t dsrdata = DNS_RDATA_INIT;
   1540 			dns_rdata_t newdsrdata = DNS_RDATA_INIT;
   1541 			unsigned char buf[DNS_DS_BUFFERSIZE];
   1542 			dns_rdata_ds_t ds;
   1543 
   1544 			dns_rdata_reset(&dsrdata);
   1545 			dns_rdataset_current(&dsset, &dsrdata);
   1546 			result = dns_rdata_tostruct(&dsrdata, &ds, NULL);
   1547 			RUNTIME_CHECK(result == ISC_R_SUCCESS);
   1548 
   1549 			if (ds.key_tag != dst_key_id(key) ||
   1550 			    ds.algorithm != dst_key_alg(key)) {
   1551 				continue;
   1552 			}
   1553 
   1554 			result = dns_ds_buildrdata(vctx->origin, keyrdata,
   1555 						   ds.digest_type, buf,
   1556 						   &newdsrdata);
   1557 			if (result != ISC_R_SUCCESS) {
   1558 				continue;
   1559 			}
   1560 
   1561 			if (dns_rdata_compare(&dsrdata, &newdsrdata) == 0) {
   1562 				dns_rdataset_settrust(&vctx->keyset,
   1563 						      dns_trust_secure);
   1564 				dns_rdataset_settrust(&vctx->keysigs,
   1565 						      dns_trust_secure);
   1566 				*goodkey = true;
   1567 				break;
   1568 			}
   1569 		}
   1570 		dns_rdataset_disassociate(&dsset);
   1571 
   1572 		goto cleanup;
   1573 	}
   1574 
   1575 cleanup:
   1576 	if (keynode != NULL) {
   1577 		dns_keytable_detachkeynode(vctx->secroots, &keynode);
   1578 	}
   1579 	if (key != NULL) {
   1580 		dst_key_free(&key);
   1581 	}
   1582 }
   1583 
   1584 /*%
   1585  * Check that the DNSKEY RR has at least one self signing KSK and one ZSK per
   1586  * algorithm in it (or, if -x was used, one self-signing KSK).
   1587  */
   1588 static isc_result_t
   1589 check_dnskey(vctx_t *vctx) {
   1590 	dns_rdata_t rdata = DNS_RDATA_INIT;
   1591 	dns_rdata_dnskey_t dnskey;
   1592 	isc_result_t result;
   1593 	bool is_ksk;
   1594 
   1595 	for (result = dns_rdataset_first(&vctx->keyset);
   1596 	     result == ISC_R_SUCCESS; result = dns_rdataset_next(&vctx->keyset))
   1597 	{
   1598 		dns_rdataset_current(&vctx->keyset, &rdata);
   1599 		result = dns_rdata_tostruct(&rdata, &dnskey, NULL);
   1600 		RUNTIME_CHECK(result == ISC_R_SUCCESS);
   1601 		is_ksk = ((dnskey.flags & DNS_KEYFLAG_KSK) != 0);
   1602 
   1603 		if ((dnskey.flags & DNS_KEYOWNER_ZONE) == 0) {
   1604 			/* Non zone key, skip. */
   1605 		} else if ((dnskey.flags & DNS_KEYFLAG_REVOKE) != 0) {
   1606 			if ((dnskey.flags & DNS_KEYFLAG_KSK) != 0 &&
   1607 			    !dns_dnssec_selfsigns(&rdata, vctx->origin,
   1608 						  &vctx->keyset, &vctx->keysigs,
   1609 						  false, vctx->mctx))
   1610 			{
   1611 				char namebuf[DNS_NAME_FORMATSIZE];
   1612 				char buffer[1024];
   1613 				isc_buffer_t buf;
   1614 
   1615 				dns_name_format(vctx->origin, namebuf,
   1616 						sizeof(namebuf));
   1617 				isc_buffer_init(&buf, buffer, sizeof(buffer));
   1618 				result = dns_rdata_totext(&rdata, NULL, &buf);
   1619 				if (result != ISC_R_SUCCESS) {
   1620 					zoneverify_log_error(
   1621 						vctx, "dns_rdata_totext: %s",
   1622 						isc_result_totext(result));
   1623 					return (ISC_R_FAILURE);
   1624 				}
   1625 				zoneverify_log_error(
   1626 					vctx,
   1627 					"revoked KSK is not self signed:\n"
   1628 					"%s DNSKEY %.*s",
   1629 					namebuf,
   1630 					(int)isc_buffer_usedlength(&buf),
   1631 					buffer);
   1632 				return (ISC_R_FAILURE);
   1633 			}
   1634 			if ((dnskey.flags & DNS_KEYFLAG_KSK) != 0 &&
   1635 			    vctx->revoked_ksk[dnskey.algorithm] != 255)
   1636 			{
   1637 				vctx->revoked_ksk[dnskey.algorithm]++;
   1638 			} else if ((dnskey.flags & DNS_KEYFLAG_KSK) == 0 &&
   1639 				   vctx->revoked_zsk[dnskey.algorithm] != 255)
   1640 			{
   1641 				vctx->revoked_zsk[dnskey.algorithm]++;
   1642 			}
   1643 		} else {
   1644 			check_dnskey_sigs(vctx, &dnskey, &rdata, is_ksk);
   1645 		}
   1646 		dns_rdata_freestruct(&dnskey);
   1647 		dns_rdata_reset(&rdata);
   1648 	}
   1649 
   1650 	return (ISC_R_SUCCESS);
   1651 }
   1652 
   1653 static void
   1654 determine_active_algorithms(vctx_t *vctx, bool ignore_kskflag,
   1655 			    bool keyset_kskonly,
   1656 			    void (*report)(const char *, ...)) {
   1657 	char algbuf[DNS_SECALG_FORMATSIZE];
   1658 	int i;
   1659 
   1660 	report("Verifying the zone using the following algorithms:");
   1661 
   1662 	for (i = 0; i < 256; i++) {
   1663 		if (ignore_kskflag) {
   1664 			vctx->act_algorithms[i] = (vctx->ksk_algorithms[i] !=
   1665 							   0 ||
   1666 						   vctx->zsk_algorithms[i] != 0)
   1667 							  ? 1
   1668 							  : 0;
   1669 		} else {
   1670 			vctx->act_algorithms[i] = vctx->ksk_algorithms[i] != 0
   1671 							  ? 1
   1672 							  : 0;
   1673 		}
   1674 		if (vctx->act_algorithms[i] != 0) {
   1675 			dns_secalg_format(i, algbuf, sizeof(algbuf));
   1676 			report("- %s", algbuf);
   1677 		}
   1678 	}
   1679 
   1680 	if (ignore_kskflag || keyset_kskonly) {
   1681 		return;
   1682 	}
   1683 
   1684 	for (i = 0; i < 256; i++) {
   1685 		/*
   1686 		 * The counts should both be zero or both be non-zero.  Mark
   1687 		 * the algorithm as bad if this is not met.
   1688 		 */
   1689 		if ((vctx->ksk_algorithms[i] != 0) ==
   1690 		    (vctx->zsk_algorithms[i] != 0)) {
   1691 			continue;
   1692 		}
   1693 		dns_secalg_format(i, algbuf, sizeof(algbuf));
   1694 		zoneverify_log_error(vctx, "Missing %s for algorithm %s",
   1695 				     (vctx->ksk_algorithms[i] != 0) ? "ZSK"
   1696 								    : "self-"
   1697 								      "signed "
   1698 								      "KSK",
   1699 				     algbuf);
   1700 		vctx->bad_algorithms[i] = 1;
   1701 	}
   1702 }
   1703 
   1704 /*%
   1705  * Check that all the records not yet verified were signed by keys that are
   1706  * present in the DNSKEY RRset.
   1707  */
   1708 static isc_result_t
   1709 verify_nodes(vctx_t *vctx, isc_result_t *vresult) {
   1710 	dns_fixedname_t fname, fnextname, fprevname, fzonecut;
   1711 	dns_name_t *name, *nextname, *prevname, *zonecut;
   1712 	dns_dbnode_t *node = NULL, *nextnode;
   1713 	dns_dbiterator_t *dbiter = NULL;
   1714 	dst_key_t **dstkeys;
   1715 	size_t count, nkeys = 0;
   1716 	bool done = false;
   1717 	isc_result_t tvresult = ISC_R_UNSET;
   1718 	isc_result_t result;
   1719 
   1720 	name = dns_fixedname_initname(&fname);
   1721 	nextname = dns_fixedname_initname(&fnextname);
   1722 	dns_fixedname_init(&fprevname);
   1723 	prevname = NULL;
   1724 	dns_fixedname_init(&fzonecut);
   1725 	zonecut = NULL;
   1726 
   1727 	count = dns_rdataset_count(&vctx->keyset);
   1728 	dstkeys = isc_mem_get(vctx->mctx, sizeof(*dstkeys) * count);
   1729 
   1730 	for (result = dns_rdataset_first(&vctx->keyset);
   1731 	     result == ISC_R_SUCCESS; result = dns_rdataset_next(&vctx->keyset))
   1732 	{
   1733 		dns_rdata_t rdata = DNS_RDATA_INIT;
   1734 		dns_rdataset_current(&vctx->keyset, &rdata);
   1735 		dstkeys[nkeys] = NULL;
   1736 		result = dns_dnssec_keyfromrdata(vctx->origin, &rdata,
   1737 						 vctx->mctx, &dstkeys[nkeys]);
   1738 		if (result == ISC_R_SUCCESS) {
   1739 			nkeys++;
   1740 		}
   1741 	}
   1742 
   1743 	result = dns_db_createiterator(vctx->db, DNS_DB_NONSEC3, &dbiter);
   1744 	if (result != ISC_R_SUCCESS) {
   1745 		zoneverify_log_error(vctx, "dns_db_createiterator(): %s",
   1746 				     isc_result_totext(result));
   1747 		goto done;
   1748 	}
   1749 
   1750 	result = dns_dbiterator_first(dbiter);
   1751 	if (result != ISC_R_SUCCESS) {
   1752 		zoneverify_log_error(vctx, "dns_dbiterator_first(): %s",
   1753 				     isc_result_totext(result));
   1754 		goto done;
   1755 	}
   1756 
   1757 	while (!done) {
   1758 		bool isdelegation = false;
   1759 
   1760 		result = dns_dbiterator_current(dbiter, &node, name);
   1761 		if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN) {
   1762 			zoneverify_log_error(vctx,
   1763 					     "dns_dbiterator_current(): %s",
   1764 					     isc_result_totext(result));
   1765 			goto done;
   1766 		}
   1767 		if (!dns_name_issubdomain(name, vctx->origin)) {
   1768 			result = check_no_nsec(vctx, name, node);
   1769 			if (result != ISC_R_SUCCESS) {
   1770 				dns_db_detachnode(vctx->db, &node);
   1771 				goto done;
   1772 			}
   1773 			dns_db_detachnode(vctx->db, &node);
   1774 			result = dns_dbiterator_next(dbiter);
   1775 			if (result == ISC_R_NOMORE) {
   1776 				done = true;
   1777 			} else if (result != ISC_R_SUCCESS) {
   1778 				zoneverify_log_error(vctx,
   1779 						     "dns_dbiterator_next(): "
   1780 						     "%s",
   1781 						     isc_result_totext(result));
   1782 				goto done;
   1783 			}
   1784 			continue;
   1785 		}
   1786 		if (is_delegation(vctx, name, node, NULL)) {
   1787 			zonecut = dns_fixedname_name(&fzonecut);
   1788 			dns_name_copynf(name, zonecut);
   1789 			isdelegation = true;
   1790 		} else if (has_dname(vctx, node)) {
   1791 			zonecut = dns_fixedname_name(&fzonecut);
   1792 			dns_name_copynf(name, zonecut);
   1793 		}
   1794 		nextnode = NULL;
   1795 		result = dns_dbiterator_next(dbiter);
   1796 		while (result == ISC_R_SUCCESS) {
   1797 			bool empty;
   1798 			result = dns_dbiterator_current(dbiter, &nextnode,
   1799 							nextname);
   1800 			if (result != ISC_R_SUCCESS &&
   1801 			    result != DNS_R_NEWORIGIN) {
   1802 				zoneverify_log_error(vctx,
   1803 						     "dns_dbiterator_current():"
   1804 						     " %s",
   1805 						     isc_result_totext(result));
   1806 				dns_db_detachnode(vctx->db, &node);
   1807 				goto done;
   1808 			}
   1809 			if (!dns_name_issubdomain(nextname, vctx->origin) ||
   1810 			    (zonecut != NULL &&
   1811 			     dns_name_issubdomain(nextname, zonecut)))
   1812 			{
   1813 				result = check_no_nsec(vctx, nextname,
   1814 						       nextnode);
   1815 				if (result != ISC_R_SUCCESS) {
   1816 					dns_db_detachnode(vctx->db, &node);
   1817 					dns_db_detachnode(vctx->db, &nextnode);
   1818 					goto done;
   1819 				}
   1820 				dns_db_detachnode(vctx->db, &nextnode);
   1821 				result = dns_dbiterator_next(dbiter);
   1822 				continue;
   1823 			}
   1824 			result = is_empty(vctx, nextnode, &empty);
   1825 			dns_db_detachnode(vctx->db, &nextnode);
   1826 			if (result != ISC_R_SUCCESS) {
   1827 				dns_db_detachnode(vctx->db, &node);
   1828 				goto done;
   1829 			}
   1830 			if (empty) {
   1831 				result = dns_dbiterator_next(dbiter);
   1832 				continue;
   1833 			}
   1834 			break;
   1835 		}
   1836 		if (result == ISC_R_NOMORE) {
   1837 			done = true;
   1838 			nextname = vctx->origin;
   1839 		} else if (result != ISC_R_SUCCESS) {
   1840 			zoneverify_log_error(vctx,
   1841 					     "iterating through the database "
   1842 					     "failed: %s",
   1843 					     isc_result_totext(result));
   1844 			dns_db_detachnode(vctx->db, &node);
   1845 			goto done;
   1846 		}
   1847 		result = verifynode(vctx, name, node, isdelegation, dstkeys,
   1848 				    nkeys, &vctx->nsecset, &vctx->nsec3paramset,
   1849 				    nextname, &tvresult);
   1850 		if (result != ISC_R_SUCCESS) {
   1851 			dns_db_detachnode(vctx->db, &node);
   1852 			goto done;
   1853 		}
   1854 		if (*vresult == ISC_R_UNSET) {
   1855 			*vresult = ISC_R_SUCCESS;
   1856 		}
   1857 		if (*vresult == ISC_R_SUCCESS) {
   1858 			*vresult = tvresult;
   1859 		}
   1860 		if (prevname != NULL) {
   1861 			result = verifyemptynodes(
   1862 				vctx, name, prevname, isdelegation,
   1863 				&vctx->nsec3paramset, &tvresult);
   1864 			if (result != ISC_R_SUCCESS) {
   1865 				dns_db_detachnode(vctx->db, &node);
   1866 				goto done;
   1867 			}
   1868 		} else {
   1869 			prevname = dns_fixedname_name(&fprevname);
   1870 		}
   1871 		dns_name_copynf(name, prevname);
   1872 		if (*vresult == ISC_R_SUCCESS) {
   1873 			*vresult = tvresult;
   1874 		}
   1875 		dns_db_detachnode(vctx->db, &node);
   1876 	}
   1877 
   1878 	dns_dbiterator_destroy(&dbiter);
   1879 
   1880 	result = dns_db_createiterator(vctx->db, DNS_DB_NSEC3ONLY, &dbiter);
   1881 	if (result != ISC_R_SUCCESS) {
   1882 		zoneverify_log_error(vctx, "dns_db_createiterator(): %s",
   1883 				     isc_result_totext(result));
   1884 		return (result);
   1885 	}
   1886 
   1887 	for (result = dns_dbiterator_first(dbiter); result == ISC_R_SUCCESS;
   1888 	     result = dns_dbiterator_next(dbiter))
   1889 	{
   1890 		result = dns_dbiterator_current(dbiter, &node, name);
   1891 		if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN) {
   1892 			zoneverify_log_error(vctx,
   1893 					     "dns_dbiterator_current(): %s",
   1894 					     isc_result_totext(result));
   1895 			goto done;
   1896 		}
   1897 		result = verifynode(vctx, name, node, false, dstkeys, nkeys,
   1898 				    NULL, NULL, NULL, NULL);
   1899 		if (result != ISC_R_SUCCESS) {
   1900 			zoneverify_log_error(vctx, "verifynode: %s",
   1901 					     isc_result_totext(result));
   1902 			dns_db_detachnode(vctx->db, &node);
   1903 			goto done;
   1904 		}
   1905 		result = record_found(vctx, name, node, &vctx->nsec3paramset);
   1906 		dns_db_detachnode(vctx->db, &node);
   1907 		if (result != ISC_R_SUCCESS) {
   1908 			goto done;
   1909 		}
   1910 	}
   1911 
   1912 	result = ISC_R_SUCCESS;
   1913 
   1914 done:
   1915 	while (nkeys-- > 0U) {
   1916 		dst_key_free(&dstkeys[nkeys]);
   1917 	}
   1918 	isc_mem_put(vctx->mctx, dstkeys, sizeof(*dstkeys) * count);
   1919 	if (dbiter != NULL) {
   1920 		dns_dbiterator_destroy(&dbiter);
   1921 	}
   1922 
   1923 	return (result);
   1924 }
   1925 
   1926 static isc_result_t
   1927 check_bad_algorithms(const vctx_t *vctx, void (*report)(const char *, ...)) {
   1928 	char algbuf[DNS_SECALG_FORMATSIZE];
   1929 	bool first = true;
   1930 	int i;
   1931 
   1932 	for (i = 0; i < 256; i++) {
   1933 		if (vctx->bad_algorithms[i] == 0) {
   1934 			continue;
   1935 		}
   1936 		if (first) {
   1937 			report("The zone is not fully signed "
   1938 			       "for the following algorithms:");
   1939 		}
   1940 		dns_secalg_format(i, algbuf, sizeof(algbuf));
   1941 		report(" %s", algbuf);
   1942 		first = false;
   1943 	}
   1944 
   1945 	if (!first) {
   1946 		report(".");
   1947 	}
   1948 
   1949 	return (first ? ISC_R_SUCCESS : ISC_R_FAILURE);
   1950 }
   1951 
   1952 static void
   1953 print_summary(const vctx_t *vctx, bool keyset_kskonly,
   1954 	      void (*report)(const char *, ...)) {
   1955 	char algbuf[DNS_SECALG_FORMATSIZE];
   1956 	int i;
   1957 
   1958 	report("Zone fully signed:");
   1959 	for (i = 0; i < 256; i++) {
   1960 		if ((vctx->ksk_algorithms[i] == 0) &&
   1961 		    (vctx->standby_ksk[i] == 0) &&
   1962 		    (vctx->revoked_ksk[i] == 0) &&
   1963 		    (vctx->zsk_algorithms[i] == 0) &&
   1964 		    (vctx->standby_zsk[i] == 0) && (vctx->revoked_zsk[i] == 0))
   1965 		{
   1966 			continue;
   1967 		}
   1968 		dns_secalg_format(i, algbuf, sizeof(algbuf));
   1969 		report("Algorithm: %s: KSKs: "
   1970 		       "%u active, %u stand-by, %u revoked",
   1971 		       algbuf, vctx->ksk_algorithms[i], vctx->standby_ksk[i],
   1972 		       vctx->revoked_ksk[i]);
   1973 		report("%*sZSKs: "
   1974 		       "%u active, %u %s, %u revoked",
   1975 		       (int)strlen(algbuf) + 13, "", vctx->zsk_algorithms[i],
   1976 		       vctx->standby_zsk[i],
   1977 		       keyset_kskonly ? "present" : "stand-by",
   1978 		       vctx->revoked_zsk[i]);
   1979 	}
   1980 }
   1981 
   1982 isc_result_t
   1983 dns_zoneverify_dnssec(dns_zone_t *zone, dns_db_t *db, dns_dbversion_t *ver,
   1984 		      dns_name_t *origin, dns_keytable_t *secroots,
   1985 		      isc_mem_t *mctx, bool ignore_kskflag, bool keyset_kskonly,
   1986 		      void (*report)(const char *, ...)) {
   1987 	const char *keydesc = (secroots == NULL ? "self-signed" : "trusted");
   1988 	isc_result_t result, vresult = ISC_R_UNSET;
   1989 	vctx_t vctx;
   1990 
   1991 	result = vctx_init(&vctx, mctx, zone, db, ver, origin, secroots);
   1992 	if (result != ISC_R_SUCCESS) {
   1993 		return (result);
   1994 	}
   1995 
   1996 	result = check_apex_rrsets(&vctx);
   1997 	if (result != ISC_R_SUCCESS) {
   1998 		goto done;
   1999 	}
   2000 
   2001 	result = check_dnskey(&vctx);
   2002 	if (result != ISC_R_SUCCESS) {
   2003 		goto done;
   2004 	}
   2005 
   2006 	if (ignore_kskflag) {
   2007 		if (!vctx.goodksk && !vctx.goodzsk) {
   2008 			zoneverify_log_error(&vctx, "No %s DNSKEY found",
   2009 					     keydesc);
   2010 			result = ISC_R_FAILURE;
   2011 			goto done;
   2012 		}
   2013 	} else if (!vctx.goodksk) {
   2014 		zoneverify_log_error(&vctx, "No %s KSK DNSKEY found", keydesc);
   2015 		result = ISC_R_FAILURE;
   2016 		goto done;
   2017 	}
   2018 
   2019 	determine_active_algorithms(&vctx, ignore_kskflag, keyset_kskonly,
   2020 				    report);
   2021 
   2022 	result = verify_nodes(&vctx, &vresult);
   2023 	if (result != ISC_R_SUCCESS) {
   2024 		goto done;
   2025 	}
   2026 
   2027 	result = verify_nsec3_chains(&vctx, mctx);
   2028 	if (vresult == ISC_R_UNSET) {
   2029 		vresult = ISC_R_SUCCESS;
   2030 	}
   2031 	if (result != ISC_R_SUCCESS && vresult == ISC_R_SUCCESS) {
   2032 		vresult = result;
   2033 	}
   2034 
   2035 	result = check_bad_algorithms(&vctx, report);
   2036 	if (result != ISC_R_SUCCESS) {
   2037 		report("DNSSEC completeness test failed.");
   2038 		goto done;
   2039 	}
   2040 
   2041 	result = vresult;
   2042 	if (result != ISC_R_SUCCESS) {
   2043 		report("DNSSEC completeness test failed (%s).",
   2044 		       dns_result_totext(result));
   2045 		goto done;
   2046 	}
   2047 
   2048 	if (vctx.goodksk || ignore_kskflag) {
   2049 		print_summary(&vctx, keyset_kskonly, report);
   2050 	}
   2051 
   2052 done:
   2053 	vctx_destroy(&vctx);
   2054 
   2055 	return (result);
   2056 }
   2057