1/*	$NetBSD: nsec.c,v 1.10 2024/02/21 22:52:07 christos Exp $	*/
2
3/*
4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
5 *
6 * SPDX-License-Identifier: MPL-2.0
7 *
8 * This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
11 *
12 * See the COPYRIGHT file distributed with this work for additional
13 * information regarding copyright ownership.
14 */
15
16/*! \file */
17
18#include <stdbool.h>
19
20#include <isc/log.h>
21#include <isc/result.h>
22#include <isc/string.h>
23#include <isc/util.h>
24
25#include <dns/db.h>
26#include <dns/nsec.h>
27#include <dns/rdata.h>
28#include <dns/rdatalist.h>
29#include <dns/rdataset.h>
30#include <dns/rdatasetiter.h>
31#include <dns/rdatastruct.h>
32
33#include <dst/dst.h>
34
35#define RETERR(x)                            \
36	do {                                 \
37		result = (x);                \
38		if (result != ISC_R_SUCCESS) \
39			goto failure;        \
40	} while (0)
41
42void
43dns_nsec_setbit(unsigned char *array, unsigned int type, unsigned int bit) {
44	unsigned int shift, mask;
45
46	shift = 7 - (type % 8);
47	mask = 1 << shift;
48
49	if (bit != 0) {
50		array[type / 8] |= mask;
51	} else {
52		array[type / 8] &= (~mask & 0xFF);
53	}
54}
55
56bool
57dns_nsec_isset(const unsigned char *array, unsigned int type) {
58	unsigned int byte, shift, mask;
59
60	byte = array[type / 8];
61	shift = 7 - (type % 8);
62	mask = 1 << shift;
63
64	return ((byte & mask) != 0);
65}
66
67unsigned int
68dns_nsec_compressbitmap(unsigned char *map, const unsigned char *raw,
69			unsigned int max_type) {
70	unsigned char *start = map;
71	unsigned int window;
72	int octet;
73
74	if (raw == NULL) {
75		return (0);
76	}
77
78	for (window = 0; window < 256; window++) {
79		if (window * 256 > max_type) {
80			break;
81		}
82		for (octet = 31; octet >= 0; octet--) {
83			if (*(raw + octet) != 0) {
84				break;
85			}
86		}
87		if (octet < 0) {
88			raw += 32;
89			continue;
90		}
91		*map++ = window;
92		*map++ = octet + 1;
93		/*
94		 * Note: potential overlapping move.
95		 */
96		memmove(map, raw, octet + 1);
97		map += octet + 1;
98		raw += 32;
99	}
100	return ((unsigned int)(map - start));
101}
102
103isc_result_t
104dns_nsec_buildrdata(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node,
105		    const dns_name_t *target, unsigned char *buffer,
106		    dns_rdata_t *rdata) {
107	isc_result_t result;
108	dns_rdataset_t rdataset;
109	isc_region_t r;
110	unsigned int i;
111
112	unsigned char *nsec_bits, *bm;
113	unsigned int max_type;
114	dns_rdatasetiter_t *rdsiter;
115
116	REQUIRE(target != NULL);
117
118	memset(buffer, 0, DNS_NSEC_BUFFERSIZE);
119	dns_name_toregion(target, &r);
120	memmove(buffer, r.base, r.length);
121	r.base = buffer;
122	/*
123	 * Use the end of the space for a raw bitmap leaving enough
124	 * space for the window identifiers and length octets.
125	 */
126	bm = r.base + r.length + 512;
127	nsec_bits = r.base + r.length;
128	dns_nsec_setbit(bm, dns_rdatatype_rrsig, 1);
129	dns_nsec_setbit(bm, dns_rdatatype_nsec, 1);
130	max_type = dns_rdatatype_nsec;
131	dns_rdataset_init(&rdataset);
132	rdsiter = NULL;
133	result = dns_db_allrdatasets(db, node, version, 0, 0, &rdsiter);
134	if (result != ISC_R_SUCCESS) {
135		return (result);
136	}
137	for (result = dns_rdatasetiter_first(rdsiter); result == ISC_R_SUCCESS;
138	     result = dns_rdatasetiter_next(rdsiter))
139	{
140		dns_rdatasetiter_current(rdsiter, &rdataset);
141		if (rdataset.type != dns_rdatatype_nsec &&
142		    rdataset.type != dns_rdatatype_nsec3 &&
143		    rdataset.type != dns_rdatatype_rrsig)
144		{
145			if (rdataset.type > max_type) {
146				max_type = rdataset.type;
147			}
148			dns_nsec_setbit(bm, rdataset.type, 1);
149		}
150		dns_rdataset_disassociate(&rdataset);
151	}
152
153	/*
154	 * At zone cuts, deny the existence of glue in the parent zone.
155	 */
156	if (dns_nsec_isset(bm, dns_rdatatype_ns) &&
157	    !dns_nsec_isset(bm, dns_rdatatype_soa))
158	{
159		for (i = 0; i <= max_type; i++) {
160			if (dns_nsec_isset(bm, i) &&
161			    !dns_rdatatype_iszonecutauth((dns_rdatatype_t)i))
162			{
163				dns_nsec_setbit(bm, i, 0);
164			}
165		}
166	}
167
168	dns_rdatasetiter_destroy(&rdsiter);
169	if (result != ISC_R_NOMORE) {
170		return (result);
171	}
172
173	nsec_bits += dns_nsec_compressbitmap(nsec_bits, bm, max_type);
174
175	r.length = (unsigned int)(nsec_bits - r.base);
176	INSIST(r.length <= DNS_NSEC_BUFFERSIZE);
177	dns_rdata_fromregion(rdata, dns_db_class(db), dns_rdatatype_nsec, &r);
178
179	return (ISC_R_SUCCESS);
180}
181
182isc_result_t
183dns_nsec_build(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node,
184	       const dns_name_t *target, dns_ttl_t ttl) {
185	isc_result_t result;
186	dns_rdata_t rdata = DNS_RDATA_INIT;
187	unsigned char data[DNS_NSEC_BUFFERSIZE];
188	dns_rdatalist_t rdatalist;
189	dns_rdataset_t rdataset;
190
191	dns_rdataset_init(&rdataset);
192	dns_rdata_init(&rdata);
193
194	RETERR(dns_nsec_buildrdata(db, version, node, target, data, &rdata));
195
196	dns_rdatalist_init(&rdatalist);
197	rdatalist.rdclass = dns_db_class(db);
198	rdatalist.type = dns_rdatatype_nsec;
199	rdatalist.ttl = ttl;
200	ISC_LIST_APPEND(rdatalist.rdata, &rdata, link);
201	RETERR(dns_rdatalist_tordataset(&rdatalist, &rdataset));
202	result = dns_db_addrdataset(db, node, version, 0, &rdataset, 0, NULL);
203	if (result == DNS_R_UNCHANGED) {
204		result = ISC_R_SUCCESS;
205	}
206
207failure:
208	if (dns_rdataset_isassociated(&rdataset)) {
209		dns_rdataset_disassociate(&rdataset);
210	}
211	return (result);
212}
213
214bool
215dns_nsec_typepresent(dns_rdata_t *nsec, dns_rdatatype_t type) {
216	dns_rdata_nsec_t nsecstruct;
217	isc_result_t result;
218	bool present;
219	unsigned int i, len, window;
220
221	REQUIRE(nsec != NULL);
222	REQUIRE(nsec->type == dns_rdatatype_nsec);
223
224	/* This should never fail */
225	result = dns_rdata_tostruct(nsec, &nsecstruct, NULL);
226	INSIST(result == ISC_R_SUCCESS);
227
228	present = false;
229	for (i = 0; i < nsecstruct.len; i += len) {
230		INSIST(i + 2 <= nsecstruct.len);
231		window = nsecstruct.typebits[i];
232		len = nsecstruct.typebits[i + 1];
233		INSIST(len > 0 && len <= 32);
234		i += 2;
235		INSIST(i + len <= nsecstruct.len);
236		if (window * 256 > type) {
237			break;
238		}
239		if ((window + 1) * 256 <= type) {
240			continue;
241		}
242		if (type < (window * 256) + len * 8) {
243			present = dns_nsec_isset(&nsecstruct.typebits[i],
244						 type % 256);
245		}
246		break;
247	}
248	dns_rdata_freestruct(&nsecstruct);
249	return (present);
250}
251
252isc_result_t
253dns_nsec_nseconly(dns_db_t *db, dns_dbversion_t *version, dns_diff_t *diff,
254		  bool *answer) {
255	dns_dbnode_t *node = NULL;
256	dns_rdataset_t rdataset;
257	dns_rdata_dnskey_t dnskey;
258	isc_result_t result;
259
260	REQUIRE(answer != NULL);
261
262	dns_rdataset_init(&rdataset);
263
264	result = dns_db_getoriginnode(db, &node);
265	if (result != ISC_R_SUCCESS) {
266		return (result);
267	}
268
269	result = dns_db_findrdataset(db, node, version, dns_rdatatype_dnskey, 0,
270				     0, &rdataset, NULL);
271	dns_db_detachnode(db, &node);
272
273	if (result == ISC_R_NOTFOUND) {
274		*answer = false;
275	}
276	if (result != ISC_R_SUCCESS) {
277		return (result);
278	}
279	for (result = dns_rdataset_first(&rdataset); result == ISC_R_SUCCESS;
280	     result = dns_rdataset_next(&rdataset))
281	{
282		dns_rdata_t rdata = DNS_RDATA_INIT;
283
284		dns_rdataset_current(&rdataset, &rdata);
285		result = dns_rdata_tostruct(&rdata, &dnskey, NULL);
286		RUNTIME_CHECK(result == ISC_R_SUCCESS);
287
288		if (dnskey.algorithm == DST_ALG_RSAMD5 ||
289		    dnskey.algorithm == DST_ALG_DH ||
290		    dnskey.algorithm == DST_ALG_DSA ||
291		    dnskey.algorithm == DST_ALG_RSASHA1)
292		{
293			bool deleted = false;
294			if (diff != NULL) {
295				for (dns_difftuple_t *tuple =
296					     ISC_LIST_HEAD(diff->tuples);
297				     tuple != NULL;
298				     tuple = ISC_LIST_NEXT(tuple, link))
299				{
300					if (tuple->rdata.type !=
301						    dns_rdatatype_dnskey ||
302					    tuple->op != DNS_DIFFOP_DEL)
303					{
304						continue;
305					}
306
307					if (dns_rdata_compare(
308						    &rdata, &tuple->rdata) == 0)
309					{
310						deleted = true;
311						break;
312					}
313				}
314			}
315
316			if (!deleted) {
317				break;
318			}
319		}
320	}
321	dns_rdataset_disassociate(&rdataset);
322	if (result == ISC_R_SUCCESS) {
323		*answer = true;
324	}
325	if (result == ISC_R_NOMORE) {
326		*answer = false;
327		result = ISC_R_SUCCESS;
328	}
329	return (result);
330}
331
332/*%
333 * Return ISC_R_SUCCESS if we can determine that the name doesn't exist
334 * or we can determine whether there is data or not at the name.
335 * If the name does not exist return the wildcard name.
336 *
337 * Return ISC_R_IGNORE when the NSEC is not the appropriate one.
338 */
339isc_result_t
340dns_nsec_noexistnodata(dns_rdatatype_t type, const dns_name_t *name,
341		       const dns_name_t *nsecname, dns_rdataset_t *nsecset,
342		       bool *exists, bool *data, dns_name_t *wild,
343		       dns_nseclog_t logit, void *arg) {
344	int order;
345	dns_rdata_t rdata = DNS_RDATA_INIT;
346	isc_result_t result;
347	dns_namereln_t relation;
348	unsigned int olabels, nlabels, labels;
349	dns_rdata_nsec_t nsec;
350	bool atparent;
351	bool ns;
352	bool soa;
353
354	REQUIRE(exists != NULL);
355	REQUIRE(data != NULL);
356	REQUIRE(nsecset != NULL && nsecset->type == dns_rdatatype_nsec);
357
358	result = dns_rdataset_first(nsecset);
359	if (result != ISC_R_SUCCESS) {
360		(*logit)(arg, ISC_LOG_DEBUG(3), "failure processing NSEC set");
361		return (result);
362	}
363	dns_rdataset_current(nsecset, &rdata);
364
365#ifdef notyet
366	if (!dns_nsec_typepresent(&rdata, dns_rdatatype_rrsig) ||
367	    !dns_nsec_typepresent(&rdata, dns_rdatatype_nsec))
368	{
369		(*logit)(arg, ISC_LOG_DEBUG(3),
370			 "NSEC missing RRSIG and/or NSEC from type map");
371		return (ISC_R_IGNORE);
372	}
373#endif
374
375	(*logit)(arg, ISC_LOG_DEBUG(3), "looking for relevant NSEC");
376	relation = dns_name_fullcompare(name, nsecname, &order, &olabels);
377
378	if (order < 0) {
379		/*
380		 * The name is not within the NSEC range.
381		 */
382		(*logit)(arg, ISC_LOG_DEBUG(3),
383			 "NSEC does not cover name, before NSEC");
384		return (ISC_R_IGNORE);
385	}
386
387	if (order == 0) {
388		/*
389		 * The names are the same.   If we are validating "."
390		 * then atparent should not be set as there is no parent.
391		 */
392		atparent = (olabels != 1) && dns_rdatatype_atparent(type);
393		ns = dns_nsec_typepresent(&rdata, dns_rdatatype_ns);
394		soa = dns_nsec_typepresent(&rdata, dns_rdatatype_soa);
395		if (ns && !soa) {
396			if (!atparent) {
397				/*
398				 * This NSEC record is from somewhere higher in
399				 * the DNS, and at the parent of a delegation.
400				 * It can not be legitimately used here.
401				 */
402				(*logit)(arg, ISC_LOG_DEBUG(3),
403					 "ignoring parent nsec");
404				return (ISC_R_IGNORE);
405			}
406		} else if (atparent && ns && soa) {
407			/*
408			 * This NSEC record is from the child.
409			 * It can not be legitimately used here.
410			 */
411			(*logit)(arg, ISC_LOG_DEBUG(3), "ignoring child nsec");
412			return (ISC_R_IGNORE);
413		}
414		if (type == dns_rdatatype_cname || type == dns_rdatatype_nxt ||
415		    type == dns_rdatatype_nsec || type == dns_rdatatype_key ||
416		    !dns_nsec_typepresent(&rdata, dns_rdatatype_cname))
417		{
418			*exists = true;
419			*data = dns_nsec_typepresent(&rdata, type);
420			(*logit)(arg, ISC_LOG_DEBUG(3),
421				 "nsec proves name exists (owner) data=%d",
422				 *data);
423			return (ISC_R_SUCCESS);
424		}
425		(*logit)(arg, ISC_LOG_DEBUG(3), "NSEC proves CNAME exists");
426		return (ISC_R_IGNORE);
427	}
428
429	if (relation == dns_namereln_subdomain &&
430	    dns_nsec_typepresent(&rdata, dns_rdatatype_ns) &&
431	    !dns_nsec_typepresent(&rdata, dns_rdatatype_soa))
432	{
433		/*
434		 * This NSEC record is from somewhere higher in
435		 * the DNS, and at the parent of a delegation or
436		 * at a DNAME.
437		 * It can not be legitimately used here.
438		 */
439		(*logit)(arg, ISC_LOG_DEBUG(3), "ignoring parent nsec");
440		return (ISC_R_IGNORE);
441	}
442
443	if (relation == dns_namereln_subdomain &&
444	    dns_nsec_typepresent(&rdata, dns_rdatatype_dname))
445	{
446		(*logit)(arg, ISC_LOG_DEBUG(3), "nsec proves covered by dname");
447		*exists = false;
448		return (DNS_R_DNAME);
449	}
450
451	result = dns_rdata_tostruct(&rdata, &nsec, NULL);
452	if (result != ISC_R_SUCCESS) {
453		return (result);
454	}
455	relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels);
456	if (order == 0) {
457		dns_rdata_freestruct(&nsec);
458		(*logit)(arg, ISC_LOG_DEBUG(3),
459			 "ignoring nsec matches next name");
460		return (ISC_R_IGNORE);
461	}
462
463	if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) {
464		/*
465		 * The name is not within the NSEC range.
466		 */
467		dns_rdata_freestruct(&nsec);
468		(*logit)(arg, ISC_LOG_DEBUG(3),
469			 "ignoring nsec because name is past end of range");
470		return (ISC_R_IGNORE);
471	}
472
473	if (order > 0 && relation == dns_namereln_subdomain) {
474		(*logit)(arg, ISC_LOG_DEBUG(3),
475			 "nsec proves name exist (empty)");
476		dns_rdata_freestruct(&nsec);
477		*exists = true;
478		*data = false;
479		return (ISC_R_SUCCESS);
480	}
481	if (wild != NULL) {
482		dns_name_t common;
483		dns_name_init(&common, NULL);
484		if (olabels > nlabels) {
485			labels = dns_name_countlabels(nsecname);
486			dns_name_getlabelsequence(nsecname, labels - olabels,
487						  olabels, &common);
488		} else {
489			labels = dns_name_countlabels(&nsec.next);
490			dns_name_getlabelsequence(&nsec.next, labels - nlabels,
491						  nlabels, &common);
492		}
493		result = dns_name_concatenate(dns_wildcardname, &common, wild,
494					      NULL);
495		if (result != ISC_R_SUCCESS) {
496			dns_rdata_freestruct(&nsec);
497			(*logit)(arg, ISC_LOG_DEBUG(3),
498				 "failure generating wildcard name");
499			return (result);
500		}
501	}
502	dns_rdata_freestruct(&nsec);
503	(*logit)(arg, ISC_LOG_DEBUG(3), "nsec range ok");
504	*exists = false;
505	return (ISC_R_SUCCESS);
506}
507
508bool
509dns_nsec_requiredtypespresent(dns_rdataset_t *nsecset) {
510	dns_rdataset_t rdataset;
511	isc_result_t result;
512	bool found = false;
513
514	REQUIRE(DNS_RDATASET_VALID(nsecset));
515	REQUIRE(nsecset->type == dns_rdatatype_nsec);
516
517	dns_rdataset_init(&rdataset);
518	dns_rdataset_clone(nsecset, &rdataset);
519
520	for (result = dns_rdataset_first(&rdataset); result == ISC_R_SUCCESS;
521	     result = dns_rdataset_next(&rdataset))
522	{
523		dns_rdata_t rdata = DNS_RDATA_INIT;
524		dns_rdataset_current(&rdataset, &rdata);
525		if (!dns_nsec_typepresent(&rdata, dns_rdatatype_nsec) ||
526		    !dns_nsec_typepresent(&rdata, dns_rdatatype_rrsig))
527		{
528			dns_rdataset_disassociate(&rdataset);
529			return (false);
530		}
531		found = true;
532	}
533	dns_rdataset_disassociate(&rdataset);
534	return (found);
535}
536