1 /* $NetBSD: nsec.c,v 1.9 2014/12/10 04:37:58 christos Exp $ */
2
3 /*
4 * Copyright (C) 2004, 2005, 2007-2009, 2011-2014 Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (C) 1999-2001, 2003 Internet Software Consortium.
6 *
7 * Permission to use, copy, modify, and/or distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
12 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
13 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
15 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
16 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17 * PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 /* Id */
21
22 /*! \file */
23
24 #include <config.h>
25
26 #include <isc/log.h>
27 #include <isc/string.h>
28 #include <isc/util.h>
29
30 #include <dns/db.h>
31 #include <dns/nsec.h>
32 #include <dns/rdata.h>
33 #include <dns/rdatalist.h>
34 #include <dns/rdataset.h>
35 #include <dns/rdatasetiter.h>
36 #include <dns/rdatastruct.h>
37 #include <dns/result.h>
38
39 #include <dst/dst.h>
40
41 #define RETERR(x) do { \
42 result = (x); \
43 if (result != ISC_R_SUCCESS) \
44 goto failure; \
45 } while (/*CONSTCOND*/0)
46
47 void
dns_nsec_setbit(unsigned char * array,unsigned int type,unsigned int bit)48 dns_nsec_setbit(unsigned char *array, unsigned int type, unsigned int bit) {
49 unsigned int shift, mask;
50
51 shift = 7 - (type % 8);
52 mask = 1 << shift;
53
54 if (bit != 0)
55 array[type / 8] |= mask;
56 else
57 array[type / 8] &= (~mask & 0xFF);
58 }
59
60 isc_boolean_t
dns_nsec_isset(const unsigned char * array,unsigned int type)61 dns_nsec_isset(const unsigned char *array, unsigned int type) {
62 unsigned int byte, shift, mask;
63
64 byte = array[type / 8];
65 shift = 7 - (type % 8);
66 mask = 1 << shift;
67
68 return (ISC_TF(byte & mask));
69 }
70
71 unsigned int
dns_nsec_compressbitmap(unsigned char * map,const unsigned char * raw,unsigned int max_type)72 dns_nsec_compressbitmap(unsigned char *map, const unsigned char *raw,
73 unsigned int max_type)
74 {
75 unsigned char *start = map;
76 unsigned int window;
77 int octet;
78
79 if (raw == NULL)
80 return (0);
81
82 for (window = 0; window < 256; window++) {
83 if (window * 256 > max_type)
84 break;
85 for (octet = 31; octet >= 0; octet--)
86 if (*(raw + octet) != 0)
87 break;
88 if (octet < 0) {
89 raw += 32;
90 continue;
91 }
92 *map++ = window;
93 *map++ = octet + 1;
94 /*
95 * Note: potential overlapping move.
96 */
97 memmove(map, raw, octet + 1);
98 map += octet + 1;
99 raw += 32;
100 }
101 return (unsigned int)(map - start);
102 }
103
104 isc_result_t
dns_nsec_buildrdata(dns_db_t * db,dns_dbversion_t * version,dns_dbnode_t * node,dns_name_t * target,unsigned char * buffer,dns_rdata_t * rdata)105 dns_nsec_buildrdata(dns_db_t *db, dns_dbversion_t *version,
106 dns_dbnode_t *node, dns_name_t *target,
107 unsigned char *buffer, dns_rdata_t *rdata)
108 {
109 isc_result_t result;
110 dns_rdataset_t rdataset;
111 isc_region_t r;
112 unsigned int i;
113
114 unsigned char *nsec_bits, *bm;
115 unsigned int max_type;
116 dns_rdatasetiter_t *rdsiter;
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, &rdsiter);
134 if (result != ISC_R_SUCCESS)
135 return (result);
136 for (result = dns_rdatasetiter_first(rdsiter);
137 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 if (rdataset.type > max_type)
145 max_type = rdataset.type;
146 dns_nsec_setbit(bm, rdataset.type, 1);
147 }
148 dns_rdataset_disassociate(&rdataset);
149 }
150
151 /*
152 * At zone cuts, deny the existence of glue in the parent zone.
153 */
154 if (dns_nsec_isset(bm, dns_rdatatype_ns) &&
155 ! dns_nsec_isset(bm, dns_rdatatype_soa)) {
156 for (i = 0; i <= max_type; i++) {
157 if (dns_nsec_isset(bm, i) &&
158 ! dns_rdatatype_iszonecutauth((dns_rdatatype_t)i))
159 dns_nsec_setbit(bm, i, 0);
160 }
161 }
162
163 dns_rdatasetiter_destroy(&rdsiter);
164 if (result != ISC_R_NOMORE)
165 return (result);
166
167 nsec_bits += dns_nsec_compressbitmap(nsec_bits, bm, max_type);
168
169 r.length = (unsigned int)(nsec_bits - r.base);
170 INSIST(r.length <= DNS_NSEC_BUFFERSIZE);
171 dns_rdata_fromregion(rdata,
172 dns_db_class(db),
173 dns_rdatatype_nsec,
174 &r);
175
176 return (ISC_R_SUCCESS);
177 }
178
179 isc_result_t
dns_nsec_build(dns_db_t * db,dns_dbversion_t * version,dns_dbnode_t * node,dns_name_t * target,dns_ttl_t ttl)180 dns_nsec_build(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node,
181 dns_name_t *target, dns_ttl_t ttl)
182 {
183 isc_result_t result;
184 dns_rdata_t rdata = DNS_RDATA_INIT;
185 unsigned char data[DNS_NSEC_BUFFERSIZE];
186 dns_rdatalist_t rdatalist;
187 dns_rdataset_t rdataset;
188
189 dns_rdataset_init(&rdataset);
190 dns_rdata_init(&rdata);
191
192 RETERR(dns_nsec_buildrdata(db, version, node, target, data, &rdata));
193
194 rdatalist.rdclass = dns_db_class(db);
195 rdatalist.type = dns_rdatatype_nsec;
196 rdatalist.covers = 0;
197 rdatalist.ttl = ttl;
198 ISC_LIST_INIT(rdatalist.rdata);
199 ISC_LIST_APPEND(rdatalist.rdata, &rdata, link);
200 RETERR(dns_rdatalist_tordataset(&rdatalist, &rdataset));
201 result = dns_db_addrdataset(db, node, version, 0, &rdataset,
202 0, NULL);
203 if (result == DNS_R_UNCHANGED)
204 result = ISC_R_SUCCESS;
205
206 failure:
207 if (dns_rdataset_isassociated(&rdataset))
208 dns_rdataset_disassociate(&rdataset);
209 return (result);
210 }
211
212 isc_boolean_t
dns_nsec_typepresent(dns_rdata_t * nsec,dns_rdatatype_t type)213 dns_nsec_typepresent(dns_rdata_t *nsec, dns_rdatatype_t type) {
214 dns_rdata_nsec_t nsecstruct;
215 isc_result_t result;
216 isc_boolean_t present;
217 unsigned int i, len, window;
218
219 REQUIRE(nsec != NULL);
220 REQUIRE(nsec->type == dns_rdatatype_nsec);
221
222 /* This should never fail */
223 result = dns_rdata_tostruct(nsec, &nsecstruct, NULL);
224 INSIST(result == ISC_R_SUCCESS);
225
226 present = ISC_FALSE;
227 for (i = 0; i < nsecstruct.len; i += len) {
228 INSIST(i + 2 <= nsecstruct.len);
229 window = nsecstruct.typebits[i];
230 len = nsecstruct.typebits[i + 1];
231 INSIST(len > 0 && len <= 32);
232 i += 2;
233 INSIST(i + len <= nsecstruct.len);
234 if (window * 256 > type)
235 break;
236 if ((window + 1) * 256 <= type)
237 continue;
238 if (type < (window * 256) + len * 8)
239 present = ISC_TF(dns_nsec_isset(&nsecstruct.typebits[i],
240 type % 256));
241 break;
242 }
243 dns_rdata_freestruct(&nsecstruct);
244 return (present);
245 }
246
247 isc_result_t
dns_nsec_nseconly(dns_db_t * db,dns_dbversion_t * version,isc_boolean_t * answer)248 dns_nsec_nseconly(dns_db_t *db, dns_dbversion_t *version,
249 isc_boolean_t *answer)
250 {
251 dns_dbnode_t *node = NULL;
252 dns_rdataset_t rdataset;
253 dns_rdata_dnskey_t dnskey;
254 isc_result_t result;
255
256 REQUIRE(answer != NULL);
257
258 dns_rdataset_init(&rdataset);
259
260 result = dns_db_getoriginnode(db, &node);
261 if (result != ISC_R_SUCCESS)
262 return (result);
263
264 result = dns_db_findrdataset(db, node, version, dns_rdatatype_dnskey,
265 0, 0, &rdataset, NULL);
266 dns_db_detachnode(db, &node);
267
268 if (result == ISC_R_NOTFOUND)
269 *answer = ISC_FALSE;
270 if (result != ISC_R_SUCCESS)
271 return (result);
272 for (result = dns_rdataset_first(&rdataset);
273 result == ISC_R_SUCCESS;
274 result = dns_rdataset_next(&rdataset)) {
275 dns_rdata_t rdata = DNS_RDATA_INIT;
276
277 dns_rdataset_current(&rdataset, &rdata);
278 result = dns_rdata_tostruct(&rdata, &dnskey, NULL);
279 RUNTIME_CHECK(result == ISC_R_SUCCESS);
280
281 if (dnskey.algorithm == DST_ALG_RSAMD5 ||
282 dnskey.algorithm == DST_ALG_RSASHA1 ||
283 dnskey.algorithm == DST_ALG_DSA ||
284 dnskey.algorithm == DST_ALG_ECC)
285 break;
286 }
287 dns_rdataset_disassociate(&rdataset);
288 if (result == ISC_R_SUCCESS)
289 *answer = ISC_TRUE;
290 if (result == ISC_R_NOMORE) {
291 *answer = ISC_FALSE;
292 result = ISC_R_SUCCESS;
293 }
294 return (result);
295 }
296
297 /*%
298 * Return ISC_R_SUCCESS if we can determine that the name doesn't exist
299 * or we can determine whether there is data or not at the name.
300 * If the name does not exist return the wildcard name.
301 *
302 * Return ISC_R_IGNORE when the NSEC is not the appropriate one.
303 */
304 isc_result_t
dns_nsec_noexistnodata(dns_rdatatype_t type,dns_name_t * name,dns_name_t * nsecname,dns_rdataset_t * nsecset,isc_boolean_t * exists,isc_boolean_t * data,dns_name_t * wild,dns_nseclog_t logit,void * arg)305 dns_nsec_noexistnodata(dns_rdatatype_t type, dns_name_t *name,
306 dns_name_t *nsecname, dns_rdataset_t *nsecset,
307 isc_boolean_t *exists, isc_boolean_t *data,
308 dns_name_t *wild, dns_nseclog_t logit, void *arg)
309 {
310 int order;
311 dns_rdata_t rdata = DNS_RDATA_INIT;
312 isc_result_t result;
313 dns_namereln_t relation;
314 unsigned int olabels, nlabels, labels;
315 dns_rdata_nsec_t nsec;
316 isc_boolean_t atparent;
317 isc_boolean_t ns;
318 isc_boolean_t soa;
319
320 REQUIRE(exists != NULL);
321 REQUIRE(data != NULL);
322 REQUIRE(nsecset != NULL &&
323 nsecset->type == dns_rdatatype_nsec);
324
325 result = dns_rdataset_first(nsecset);
326 if (result != ISC_R_SUCCESS) {
327 (*logit)(arg, ISC_LOG_DEBUG(3), "failure processing NSEC set");
328 return (result);
329 }
330 dns_rdataset_current(nsecset, &rdata);
331
332 (*logit)(arg, ISC_LOG_DEBUG(3), "looking for relevant NSEC");
333 relation = dns_name_fullcompare(name, nsecname, &order, &olabels);
334
335 if (order < 0) {
336 /*
337 * The name is not within the NSEC range.
338 */
339 (*logit)(arg, ISC_LOG_DEBUG(3),
340 "NSEC does not cover name, before NSEC");
341 return (ISC_R_IGNORE);
342 }
343
344 if (order == 0) {
345 /*
346 * The names are the same. If we are validating "."
347 * then atparent should not be set as there is no parent.
348 */
349 atparent = (olabels != 1) && dns_rdatatype_atparent(type);
350 ns = dns_nsec_typepresent(&rdata, dns_rdatatype_ns);
351 soa = dns_nsec_typepresent(&rdata, dns_rdatatype_soa);
352 if (ns && !soa) {
353 if (!atparent) {
354 /*
355 * This NSEC record is from somewhere higher in
356 * the DNS, and at the parent of a delegation.
357 * It can not be legitimately used here.
358 */
359 (*logit)(arg, ISC_LOG_DEBUG(3),
360 "ignoring parent nsec");
361 return (ISC_R_IGNORE);
362 }
363 } else if (atparent && ns && soa) {
364 /*
365 * This NSEC record is from the child.
366 * It can not be legitimately used here.
367 */
368 (*logit)(arg, ISC_LOG_DEBUG(3),
369 "ignoring child nsec");
370 return (ISC_R_IGNORE);
371 }
372 if (type == dns_rdatatype_cname || type == dns_rdatatype_nxt ||
373 type == dns_rdatatype_nsec || type == dns_rdatatype_key ||
374 !dns_nsec_typepresent(&rdata, dns_rdatatype_cname)) {
375 *exists = ISC_TRUE;
376 *data = dns_nsec_typepresent(&rdata, type);
377 (*logit)(arg, ISC_LOG_DEBUG(3),
378 "nsec proves name exists (owner) data=%d",
379 *data);
380 return (ISC_R_SUCCESS);
381 }
382 (*logit)(arg, ISC_LOG_DEBUG(3), "NSEC proves CNAME exists");
383 return (ISC_R_IGNORE);
384 }
385
386 if (relation == dns_namereln_subdomain &&
387 dns_nsec_typepresent(&rdata, dns_rdatatype_ns) &&
388 !dns_nsec_typepresent(&rdata, dns_rdatatype_soa))
389 {
390 /*
391 * This NSEC record is from somewhere higher in
392 * the DNS, and at the parent of a delegation.
393 * It can not be legitimately used here.
394 */
395 (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring parent nsec");
396 return (ISC_R_IGNORE);
397 }
398
399 result = dns_rdata_tostruct(&rdata, &nsec, NULL);
400 if (result != ISC_R_SUCCESS)
401 return (result);
402 relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels);
403 if (order == 0) {
404 dns_rdata_freestruct(&nsec);
405 (*logit)(arg, ISC_LOG_DEBUG(3),
406 "ignoring nsec matches next name");
407 return (ISC_R_IGNORE);
408 }
409
410 if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) {
411 /*
412 * The name is not within the NSEC range.
413 */
414 dns_rdata_freestruct(&nsec);
415 (*logit)(arg, ISC_LOG_DEBUG(3),
416 "ignoring nsec because name is past end of range");
417 return (ISC_R_IGNORE);
418 }
419
420 if (order > 0 && relation == dns_namereln_subdomain) {
421 (*logit)(arg, ISC_LOG_DEBUG(3),
422 "nsec proves name exist (empty)");
423 dns_rdata_freestruct(&nsec);
424 *exists = ISC_TRUE;
425 *data = ISC_FALSE;
426 return (ISC_R_SUCCESS);
427 }
428 if (wild != NULL) {
429 dns_name_t common;
430 dns_name_init(&common, NULL);
431 if (olabels > nlabels) {
432 labels = dns_name_countlabels(nsecname);
433 dns_name_getlabelsequence(nsecname, labels - olabels,
434 olabels, &common);
435 } else {
436 labels = dns_name_countlabels(&nsec.next);
437 dns_name_getlabelsequence(&nsec.next, labels - nlabels,
438 nlabels, &common);
439 }
440 result = dns_name_concatenate(dns_wildcardname, &common,
441 wild, NULL);
442 if (result != ISC_R_SUCCESS) {
443 dns_rdata_freestruct(&nsec);
444 (*logit)(arg, ISC_LOG_DEBUG(3),
445 "failure generating wildcard name");
446 return (result);
447 }
448 }
449 dns_rdata_freestruct(&nsec);
450 (*logit)(arg, ISC_LOG_DEBUG(3), "nsec range ok");
451 *exists = ISC_FALSE;
452 return (ISC_R_SUCCESS);
453 }
454