1 /*
2 * Copyright (C) 2011-2015 Internet Systems Consortium, Inc. ("ISC")
3 *
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
14 * PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 /*! \file */
18
19 #include <config.h>
20
21 #include <isc/buffer.h>
22 #include <isc/mem.h>
23 #include <isc/net.h>
24 #include <isc/netaddr.h>
25 #include <isc/print.h>
26 #include <isc/stdlib.h>
27 #include <isc/string.h>
28 #include <isc/util.h>
29
30 #include <dns/db.h>
31 #include <dns/fixedname.h>
32 #include <dns/log.h>
33 #include <dns/rdata.h>
34 #include <dns/rdataset.h>
35 #include <dns/rdatastruct.h>
36 #include <dns/result.h>
37 #include <dns/rpz.h>
38 #include <dns/view.h>
39
40
41 /*
42 * Parallel radix trees for databases of response policy IP addresses
43 *
44 * The radix or Patricia trees are somewhat specialized to handle response
45 * policy addresses by representing the two test of IP IP addresses and name
46 * server IP addresses in a single tree.
47 *
48 * Each leaf indicates that an IP address is listed in the IP address or the
49 * name server IP address policy sub-zone (or both) of the corresponding
50 * response response zone. The policy data such as a CNAME or an A record
51 * is kept in the policy zone. After an IP address has been found in a radix
52 * tree, the node in the policy zone's database is found by converting
53 * the IP address to a domain name in a canonical form.
54 *
55 * The response policy zone canonical form of IPv6 addresses is one of:
56 * prefix.W.W.W.W.W.W.W.W
57 * prefix.WORDS.zz
58 * prefix.WORDS.zz.WORDS
59 * prefix.zz.WORDS
60 * where
61 * prefix is the prefix length of the IPv6 address between 1 and 128
62 * W is a number between 0 and 65535
63 * WORDS is one or more numbers W separated with "."
64 * zz corresponds to :: in the standard IPv6 text representation
65 *
66 * The canonical form of IPv4 addresses is:
67 * prefix.B.B.B.B
68 * where
69 * prefix is the prefix length of the address between 1 and 32
70 * B is a number between 0 and 255
71 *
72 * IPv4 addresses are distinguished from IPv6 addresses by having
73 * 5 labels all of which are numbers, and a prefix between 1 and 32.
74 */
75
76
77 /*
78 * Use a private definition of IPv6 addresses because s6_addr32 is not
79 * always defined and our IPv6 addresses are in non-standard byte order
80 */
81 typedef isc_uint32_t dns_rpz_cidr_word_t;
82 #define DNS_RPZ_CIDR_WORD_BITS ((int)sizeof(dns_rpz_cidr_word_t)*8)
83 #define DNS_RPZ_CIDR_KEY_BITS ((int)sizeof(dns_rpz_cidr_key_t)*8)
84 #define DNS_RPZ_CIDR_WORDS (128/DNS_RPZ_CIDR_WORD_BITS)
85 typedef struct {
86 dns_rpz_cidr_word_t w[DNS_RPZ_CIDR_WORDS];
87 } dns_rpz_cidr_key_t;
88
89 #define ADDR_V4MAPPED 0xffff
90
91 #define DNS_RPZ_WORD_MASK(b) \
92 ((b) == 0 ? (dns_rpz_cidr_word_t)(-1) \
93 : ((dns_rpz_cidr_word_t)(-1) \
94 << (DNS_RPZ_CIDR_WORD_BITS - (b))))
95
96 #define DNS_RPZ_IP_BIT(ip, bitno) \
97 (1 & ((ip)->w[(bitno)/DNS_RPZ_CIDR_WORD_BITS] >> \
98 (DNS_RPZ_CIDR_WORD_BITS - 1 - ((bitno) % DNS_RPZ_CIDR_WORD_BITS))))
99
100 typedef struct dns_rpz_cidr_node dns_rpz_cidr_node_t;
101 typedef isc_uint8_t dns_rpz_cidr_flags_t;
102 struct dns_rpz_cidr_node {
103 dns_rpz_cidr_node_t *parent;
104 dns_rpz_cidr_node_t *child[2];
105 dns_rpz_cidr_key_t ip;
106 dns_rpz_cidr_bits_t bits;
107 dns_rpz_cidr_flags_t flags;
108 #define DNS_RPZ_CIDR_FG_IP 0x01 /* has IP data or is parent of IP */
109 #define DNS_RPZ_CIDR_FG_IP_DATA 0x02 /* has IP data */
110 #define DNS_RPZ_CIDR_FG_NSIPv4 0x04 /* has or is parent of NSIPv4 data */
111 #define DNS_RPZ_CIDR_FG_NSIPv6 0x08 /* has or is parent of NSIPv6 data */
112 #define DNS_RPZ_CIDR_FG_NSIP_DATA 0x10 /* has NSIP data */
113 };
114
115 struct dns_rpz_cidr {
116 isc_mem_t *mctx;
117 isc_boolean_t have_nsdname; /* zone has NSDNAME record */
118 dns_rpz_cidr_node_t *root;
119 dns_name_t ip_name; /* RPZ_IP_ZONE.origin. */
120 dns_name_t nsip_name; /* RPZ_NSIP_ZONE.origin. */
121 dns_name_t nsdname_name; /* RPZ_NSDNAME_ZONE.origin */
122 };
123
124 const char *
dns_rpz_type2str(dns_rpz_type_t type)125 dns_rpz_type2str(dns_rpz_type_t type) {
126 switch (type) {
127 case DNS_RPZ_TYPE_QNAME:
128 return ("QNAME");
129 case DNS_RPZ_TYPE_IP:
130 return ("IP");
131 case DNS_RPZ_TYPE_NSIP:
132 return ("NSIP");
133 case DNS_RPZ_TYPE_NSDNAME:
134 return ("NSDNAME");
135 case DNS_RPZ_TYPE_BAD:
136 break;
137 }
138 FATAL_ERROR(__FILE__, __LINE__,
139 "impossible rpz type %d", type);
140 return ("impossible");
141 }
142
143 dns_rpz_policy_t
dns_rpz_str2policy(const char * str)144 dns_rpz_str2policy(const char *str) {
145 if (str == NULL)
146 return (DNS_RPZ_POLICY_ERROR);
147 if (!strcasecmp(str, "given"))
148 return (DNS_RPZ_POLICY_GIVEN);
149 if (!strcasecmp(str, "disabled"))
150 return (DNS_RPZ_POLICY_DISABLED);
151 if (!strcasecmp(str, "passthru"))
152 return (DNS_RPZ_POLICY_PASSTHRU);
153 if (!strcasecmp(str, "nxdomain"))
154 return (DNS_RPZ_POLICY_NXDOMAIN);
155 if (!strcasecmp(str, "nodata"))
156 return (DNS_RPZ_POLICY_NODATA);
157 if (!strcasecmp(str, "cname"))
158 return (DNS_RPZ_POLICY_CNAME);
159 /*
160 * Obsolete
161 */
162 if (!strcasecmp(str, "no-op"))
163 return (DNS_RPZ_POLICY_PASSTHRU);
164 return (DNS_RPZ_POLICY_ERROR);
165 }
166
167 const char *
dns_rpz_policy2str(dns_rpz_policy_t policy)168 dns_rpz_policy2str(dns_rpz_policy_t policy) {
169 const char *str;
170
171 switch (policy) {
172 case DNS_RPZ_POLICY_PASSTHRU:
173 str = "PASSTHRU";
174 break;
175 case DNS_RPZ_POLICY_NXDOMAIN:
176 str = "NXDOMAIN";
177 break;
178 case DNS_RPZ_POLICY_NODATA:
179 str = "NODATA";
180 break;
181 case DNS_RPZ_POLICY_RECORD:
182 str = "Local-Data";
183 break;
184 case DNS_RPZ_POLICY_CNAME:
185 case DNS_RPZ_POLICY_WILDCNAME:
186 str = "CNAME";
187 break;
188 default:
189 str = "";
190 POST(str);
191 INSIST(0);
192 }
193 return (str);
194 }
195
196 /*
197 * Free the radix tree of a response policy database.
198 */
199 void
dns_rpz_cidr_free(dns_rpz_cidr_t ** cidrp)200 dns_rpz_cidr_free(dns_rpz_cidr_t **cidrp) {
201 dns_rpz_cidr_node_t *cur, *child, *parent;
202 dns_rpz_cidr_t *cidr;
203
204 REQUIRE(cidrp != NULL);
205
206 cidr = *cidrp;
207 if (cidr == NULL)
208 return;
209
210 cur = cidr->root;
211 while (cur != NULL) {
212 /* Depth first. */
213 child = cur->child[0];
214 if (child != NULL) {
215 cur = child;
216 continue;
217 }
218 child = cur->child[1];
219 if (child != NULL) {
220 cur = child;
221 continue;
222 }
223
224 /* Delete this leaf and go up. */
225 parent = cur->parent;
226 if (parent == NULL)
227 cidr->root = NULL;
228 else
229 parent->child[parent->child[1] == cur] = NULL;
230 isc_mem_put(cidr->mctx, cur, sizeof(*cur));
231 cur = parent;
232 }
233
234 dns_name_free(&cidr->ip_name, cidr->mctx);
235 dns_name_free(&cidr->nsip_name, cidr->mctx);
236 dns_name_free(&cidr->nsdname_name, cidr->mctx);
237 isc_mem_put(cidr->mctx, cidr, sizeof(*cidr));
238 *cidrp = NULL;
239 }
240
241 /*
242 * Forget a view's list of policy zones.
243 */
244 void
dns_rpz_view_destroy(dns_view_t * view)245 dns_rpz_view_destroy(dns_view_t *view) {
246 dns_rpz_zone_t *zone;
247
248 REQUIRE(view != NULL);
249
250 while (!ISC_LIST_EMPTY(view->rpz_zones)) {
251 zone = ISC_LIST_HEAD(view->rpz_zones);
252 ISC_LIST_UNLINK(view->rpz_zones, zone, link);
253 if (dns_name_dynamic(&zone->origin))
254 dns_name_free(&zone->origin, view->mctx);
255 if (dns_name_dynamic(&zone->passthru))
256 dns_name_free(&zone->passthru, view->mctx);
257 if (dns_name_dynamic(&zone->nsdname))
258 dns_name_free(&zone->nsdname, view->mctx);
259 if (dns_name_dynamic(&zone->cname))
260 dns_name_free(&zone->cname, view->mctx);
261 isc_mem_put(view->mctx, zone, sizeof(*zone));
262 }
263 }
264
265 /*
266 * Start a new radix tree for a response policy zone.
267 */
268 isc_result_t
dns_rpz_new_cidr(isc_mem_t * mctx,dns_name_t * origin,dns_rpz_cidr_t ** rbtdb_cidr)269 dns_rpz_new_cidr(isc_mem_t *mctx, dns_name_t *origin,
270 dns_rpz_cidr_t **rbtdb_cidr)
271 {
272 isc_result_t result;
273 dns_rpz_cidr_t *cidr;
274
275 REQUIRE(rbtdb_cidr != NULL && *rbtdb_cidr == NULL);
276
277 cidr = isc_mem_get(mctx, sizeof(*cidr));
278 if (cidr == NULL)
279 return (ISC_R_NOMEMORY);
280 memset(cidr, 0, sizeof(*cidr));
281 cidr->mctx = mctx;
282
283 dns_name_init(&cidr->ip_name, NULL);
284 result = dns_name_fromstring2(&cidr->ip_name, DNS_RPZ_IP_ZONE, origin,
285 DNS_NAME_DOWNCASE, mctx);
286 if (result != ISC_R_SUCCESS) {
287 isc_mem_put(mctx, cidr, sizeof(*cidr));
288 return (result);
289 }
290
291 dns_name_init(&cidr->nsip_name, NULL);
292 result = dns_name_fromstring2(&cidr->nsip_name, DNS_RPZ_NSIP_ZONE,
293 origin, DNS_NAME_DOWNCASE, mctx);
294 if (result != ISC_R_SUCCESS) {
295 dns_name_free(&cidr->ip_name, mctx);
296 isc_mem_put(mctx, cidr, sizeof(*cidr));
297 return (result);
298 }
299
300 dns_name_init(&cidr->nsdname_name, NULL);
301 result = dns_name_fromstring2(&cidr->nsdname_name, DNS_RPZ_NSDNAME_ZONE,
302 origin, DNS_NAME_DOWNCASE, mctx);
303 if (result != ISC_R_SUCCESS) {
304 dns_name_free(&cidr->nsip_name, mctx);
305 dns_name_free(&cidr->ip_name, mctx);
306 isc_mem_put(mctx, cidr, sizeof(*cidr));
307 return (result);
308 }
309
310 *rbtdb_cidr = cidr;
311 return (ISC_R_SUCCESS);
312 }
313
314 /*
315 * See if a policy zone has IP, NSIP, or NSDNAME rules or records.
316 */
317 void
dns_rpz_enabled_get(dns_rpz_cidr_t * cidr,dns_rpz_st_t * st)318 dns_rpz_enabled_get(dns_rpz_cidr_t *cidr, dns_rpz_st_t *st) {
319 if (cidr == NULL)
320 return;
321 if (cidr->root != NULL &&
322 (cidr->root->flags & DNS_RPZ_CIDR_FG_IP) != 0)
323 st->state |= DNS_RPZ_HAVE_IP;
324 if (cidr->root != NULL &&
325 (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv4) != 0)
326 st->state |= DNS_RPZ_HAVE_NSIPv4;
327 if (cidr->root != NULL &&
328 (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv6) != 0)
329 st->state |= DNS_RPZ_HAVE_NSIPv6;
330 if (cidr->have_nsdname)
331 st->state |= DNS_RPZ_HAVE_NSDNAME;
332 }
333
334 static inline dns_rpz_cidr_flags_t
get_flags(const dns_rpz_cidr_key_t * ip,dns_rpz_cidr_bits_t prefix,dns_rpz_type_t rpz_type)335 get_flags(const dns_rpz_cidr_key_t *ip, dns_rpz_cidr_bits_t prefix,
336 dns_rpz_type_t rpz_type)
337 {
338 if (rpz_type == DNS_RPZ_TYPE_NSIP) {
339 if (prefix >= 96 &&
340 ip->w[0] == 0 && ip->w[1] == 0 &&
341 ip->w[2] == ADDR_V4MAPPED)
342 return (DNS_RPZ_CIDR_FG_NSIP_DATA |
343 DNS_RPZ_CIDR_FG_NSIPv4);
344 else
345 return (DNS_RPZ_CIDR_FG_NSIP_DATA |
346 DNS_RPZ_CIDR_FG_NSIPv6);
347 } else {
348 return (DNS_RPZ_CIDR_FG_IP | DNS_RPZ_CIDR_FG_IP_DATA);
349 }
350 }
351
352 /*
353 * Mark a node as having IP or NSIP data and all of its parents
354 * as members of the IP or NSIP tree.
355 */
356 static void
set_node_flags(dns_rpz_cidr_node_t * node,dns_rpz_type_t rpz_type)357 set_node_flags(dns_rpz_cidr_node_t *node, dns_rpz_type_t rpz_type) {
358 dns_rpz_cidr_flags_t flags;
359
360 flags = get_flags(&node->ip, node->bits, rpz_type);
361 node->flags |= flags;
362 flags &= ~(DNS_RPZ_CIDR_FG_NSIP_DATA | DNS_RPZ_CIDR_FG_IP_DATA);
363 for (;;) {
364 node = node->parent;
365 if (node == NULL)
366 return;
367 node->flags |= flags;
368 }
369 }
370
371 /*
372 * Make a radix tree node.
373 */
374 static dns_rpz_cidr_node_t *
new_node(dns_rpz_cidr_t * cidr,const dns_rpz_cidr_key_t * ip,dns_rpz_cidr_bits_t bits,dns_rpz_cidr_flags_t flags)375 new_node(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *ip,
376 dns_rpz_cidr_bits_t bits, dns_rpz_cidr_flags_t flags)
377 {
378 dns_rpz_cidr_node_t *node;
379 int i, words, wlen;
380
381 node = isc_mem_get(cidr->mctx, sizeof(*node));
382 if (node == NULL)
383 return (NULL);
384 memset(node, 0, sizeof(*node));
385
386 node->flags = flags & ~(DNS_RPZ_CIDR_FG_IP_DATA |
387 DNS_RPZ_CIDR_FG_NSIP_DATA);
388
389 node->bits = bits;
390 words = bits / DNS_RPZ_CIDR_WORD_BITS;
391 wlen = bits % DNS_RPZ_CIDR_WORD_BITS;
392 i = 0;
393 while (i < words) {
394 node->ip.w[i] = ip->w[i];
395 ++i;
396 }
397 if (wlen != 0) {
398 node->ip.w[i] = ip->w[i] & DNS_RPZ_WORD_MASK(wlen);
399 ++i;
400 }
401 while (i < DNS_RPZ_CIDR_WORDS)
402 node->ip.w[i++] = 0;
403
404 return (node);
405 }
406
407 static void
badname(int level,dns_name_t * name,const char * str1,const char * str2)408 badname(int level, dns_name_t *name, const char *str1, const char *str2) {
409 char printname[DNS_NAME_FORMATSIZE];
410
411 /*
412 * bin/tests/system/rpz/tests.sh looks for "invalid rpz".
413 */
414 if (level < DNS_RPZ_DEBUG_QUIET
415 && isc_log_wouldlog(dns_lctx, level)) {
416 dns_name_format(name, printname, sizeof(printname));
417 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ,
418 DNS_LOGMODULE_RBTDB, level,
419 "invalid rpz IP address \"%s\"%s%s",
420 printname, str1, str2);
421 }
422 }
423
424 /*
425 * Convert an IP address from radix tree binary (host byte order) to
426 * to its canonical response policy domain name and its name in the
427 * policy zone.
428 */
429 static isc_result_t
ip2name(dns_rpz_cidr_t * cidr,const dns_rpz_cidr_key_t * tgt_ip,dns_rpz_cidr_bits_t tgt_prefix,dns_rpz_type_t type,dns_name_t * canon_name,dns_name_t * search_name)430 ip2name(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip,
431 dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type,
432 dns_name_t *canon_name, dns_name_t *search_name)
433 {
434 #ifndef INET6_ADDRSTRLEN
435 #define INET6_ADDRSTRLEN 46
436 #endif
437 int w[DNS_RPZ_CIDR_WORDS*2];
438 char str[1+8+1+INET6_ADDRSTRLEN+1];
439 isc_buffer_t buffer;
440 dns_name_t *name;
441 isc_result_t result;
442 isc_boolean_t zeros;
443 int i, n, len;
444
445 if (tgt_prefix > 96 &&
446 tgt_ip->w[0] == 0 &&
447 tgt_ip->w[1] == 0 &&
448 tgt_ip->w[2] == ADDR_V4MAPPED) {
449 len = snprintf(str, sizeof(str), "%d.%d.%d.%d.%d",
450 tgt_prefix - 96,
451 tgt_ip->w[3] & 0xff,
452 (tgt_ip->w[3]>>8) & 0xff,
453 (tgt_ip->w[3]>>16) & 0xff,
454 (tgt_ip->w[3]>>24) & 0xff);
455 if (len == -1 || len > (int)sizeof(str))
456 return (ISC_R_FAILURE);
457 } else {
458 for (i = 0; i < DNS_RPZ_CIDR_WORDS; i++) {
459 w[i*2+1] = ((tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] >> 16)
460 & 0xffff);
461 w[i*2] = tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] & 0xffff;
462 }
463 zeros = ISC_FALSE;
464 len = snprintf(str, sizeof(str), "%d", tgt_prefix);
465 if (len == -1)
466 return (ISC_R_FAILURE);
467 i = 0;
468 while (i < DNS_RPZ_CIDR_WORDS * 2) {
469 if (w[i] != 0 || zeros
470 || i >= DNS_RPZ_CIDR_WORDS * 2 - 1
471 || w[i+1] != 0) {
472 INSIST((size_t)len <= sizeof(str));
473 n = snprintf(&str[len], sizeof(str) - len,
474 ".%x", w[i++]);
475 if (n < 0)
476 return (ISC_R_FAILURE);
477 len += n;
478 } else {
479 zeros = ISC_TRUE;
480 INSIST((size_t)len <= sizeof(str));
481 n = snprintf(&str[len], sizeof(str) - len,
482 ".zz");
483 if (n < 0)
484 return (ISC_R_FAILURE);
485 len += n;
486 i += 2;
487 while (i < DNS_RPZ_CIDR_WORDS * 2 && w[i] == 0)
488 ++i;
489 }
490 if (len >= (int)sizeof(str))
491 return (ISC_R_FAILURE);
492 }
493 }
494
495 if (canon_name != NULL) {
496 isc_buffer_init(&buffer, str, sizeof(str));
497 isc_buffer_add(&buffer, len);
498 result = dns_name_fromtext(canon_name, &buffer,
499 dns_rootname, 0, NULL);
500 if (result != ISC_R_SUCCESS)
501 return (result);
502 }
503 if (search_name != NULL) {
504 isc_buffer_init(&buffer, str, sizeof(str));
505 isc_buffer_add(&buffer, len);
506 if (type == DNS_RPZ_TYPE_NSIP)
507 name = &cidr->nsip_name;
508 else
509 name = &cidr->ip_name;
510 result = dns_name_fromtext(search_name, &buffer, name, 0, NULL);
511 if (result != ISC_R_SUCCESS)
512 return (result);
513 }
514 return (ISC_R_SUCCESS);
515 }
516
517 /*
518 * Decide which kind of IP address response policy zone a name is in.
519 */
520 static dns_rpz_type_t
set_type(dns_rpz_cidr_t * cidr,dns_name_t * name)521 set_type(dns_rpz_cidr_t *cidr, dns_name_t *name) {
522
523 if (dns_name_issubdomain(name, &cidr->ip_name))
524 return (DNS_RPZ_TYPE_IP);
525
526 /*
527 * Require `./configure --enable-rpz-nsip` and nsdname
528 * until consistency problems are resolved.
529 */
530 #ifdef ENABLE_RPZ_NSIP
531 if (dns_name_issubdomain(name, &cidr->nsip_name))
532 return (DNS_RPZ_TYPE_NSIP);
533 #endif
534
535 #ifdef ENABLE_RPZ_NSDNAME
536 if (dns_name_issubdomain(name, &cidr->nsdname_name))
537 return (DNS_RPZ_TYPE_NSDNAME);
538 #endif
539
540 return (DNS_RPZ_TYPE_QNAME);
541 }
542
543 /*
544 * Convert an IP address from canonical response policy domain name form
545 * to radix tree binary (host byte order).
546 */
547 static isc_result_t
name2ipkey(dns_rpz_cidr_t * cidr,int level,dns_name_t * src_name,dns_rpz_type_t type,dns_rpz_cidr_key_t * tgt_ip,dns_rpz_cidr_bits_t * tgt_prefix)548 name2ipkey(dns_rpz_cidr_t *cidr, int level, dns_name_t *src_name,
549 dns_rpz_type_t type, dns_rpz_cidr_key_t *tgt_ip,
550 dns_rpz_cidr_bits_t *tgt_prefix)
551 {
552 isc_result_t result;
553 dns_fixedname_t fname;
554 dns_name_t *ipname;
555 char ipstr[DNS_NAME_FORMATSIZE];
556 const char *prefix_str, *cp, *end;
557 char *cp2;
558 int ip_labels;
559 dns_rpz_cidr_bits_t bits;
560 unsigned long prefix, l;
561 int i;
562
563 /*
564 * Need at least enough labels for the shortest name,
565 * :: or 128.*.RPZ_x_ZONE.rpz.LOCALHOST.
566 */
567 ip_labels = dns_name_countlabels(src_name);
568 ip_labels -= dns_name_countlabels(&cidr->ip_name);
569 ip_labels--;
570 if (ip_labels < 1) {
571 badname(level, src_name, "; too short", "");
572 return (ISC_R_FAILURE);
573 }
574
575 /*
576 * Get text for the IP address
577 */
578 dns_fixedname_init(&fname);
579 ipname = dns_fixedname_name(&fname);
580 dns_name_split(src_name, dns_name_countlabels(&cidr->ip_name),
581 ipname, NULL);
582 dns_name_format(ipname, ipstr, sizeof(ipstr));
583 end = &ipstr[strlen(ipstr)+1];
584 prefix_str = ipstr;
585
586 prefix = strtoul(prefix_str, &cp2, 10);
587 if (*cp2 != '.') {
588 badname(level, src_name,
589 "; invalid leading prefix length", "");
590 return (ISC_R_FAILURE);
591 }
592 *cp2 = '\0';
593 if (prefix < 1U || prefix > 128U) {
594 badname(level, src_name,
595 "; invalid prefix length of ", prefix_str);
596 return (ISC_R_FAILURE);
597 }
598 cp = cp2+1;
599
600 if (ip_labels == 4 && !strchr(cp, 'z')) {
601 /*
602 * Convert an IPv4 address
603 * from the form "prefix.w.z.y.x"
604 */
605 if (prefix > 32U) {
606 badname(level, src_name,
607 "; invalid IPv4 prefix length of ", prefix_str);
608 return (ISC_R_FAILURE);
609 }
610 prefix += 96;
611 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix;
612 tgt_ip->w[0] = 0;
613 tgt_ip->w[1] = 0;
614 tgt_ip->w[2] = ADDR_V4MAPPED;
615 tgt_ip->w[3] = 0;
616 for (i = 0; i < 32; i += 8) {
617 l = strtoul(cp, &cp2, 10);
618 if (l > 255U || (*cp2 != '.' && *cp2 != '\0')) {
619 if (*cp2 == '.')
620 *cp2 = '\0';
621 badname(level, src_name,
622 "; invalid IPv4 octet ", cp);
623 return (ISC_R_FAILURE);
624 }
625 tgt_ip->w[3] |= l << i;
626 cp = cp2 + 1;
627 }
628 } else {
629 /*
630 * Convert a text IPv6 address.
631 */
632 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix;
633 for (i = 0;
634 ip_labels > 0 && i < DNS_RPZ_CIDR_WORDS * 2;
635 ip_labels--) {
636 if (cp[0] == 'z' && cp[1] == 'z' &&
637 (cp[2] == '.' || cp[2] == '\0') &&
638 i <= 6) {
639 do {
640 if ((i & 1) == 0)
641 tgt_ip->w[3-i/2] = 0;
642 ++i;
643 } while (ip_labels + i <= 8);
644 cp += 3;
645 } else {
646 l = strtoul(cp, &cp2, 16);
647 if (l > 0xffffu ||
648 (*cp2 != '.' && *cp2 != '\0')) {
649 if (*cp2 == '.')
650 *cp2 = '\0';
651 badname(level, src_name,
652 "; invalid IPv6 word ", cp);
653 return (ISC_R_FAILURE);
654 }
655 if ((i & 1) == 0)
656 tgt_ip->w[3-i/2] = l;
657 else
658 tgt_ip->w[3-i/2] |= l << 16;
659 i++;
660 cp = cp2 + 1;
661 }
662 }
663 }
664 if (cp != end) {
665 badname(level, src_name, "", "");
666 return (ISC_R_FAILURE);
667 }
668
669 /*
670 * Check for 1s after the prefix length.
671 */
672 bits = (dns_rpz_cidr_bits_t)prefix;
673 while (bits < DNS_RPZ_CIDR_KEY_BITS) {
674 dns_rpz_cidr_word_t aword;
675
676 i = bits % DNS_RPZ_CIDR_WORD_BITS;
677 aword = tgt_ip->w[bits / DNS_RPZ_CIDR_WORD_BITS];
678 if ((aword & ~DNS_RPZ_WORD_MASK(i)) != 0) {
679 badname(level, src_name,
680 "; too small prefix length of ", prefix_str);
681 return (ISC_R_FAILURE);
682 }
683 bits -= i;
684 bits += DNS_RPZ_CIDR_WORD_BITS;
685 }
686
687 /*
688 * Convert the address back to a canonical policy domain name
689 * to ensure that it is in canonical form.
690 */
691 result = ip2name(cidr, tgt_ip, (dns_rpz_cidr_bits_t) prefix,
692 type, NULL, ipname);
693 if (result != ISC_R_SUCCESS || !dns_name_equal(src_name, ipname)) {
694 badname(level, src_name, "; not canonical", "");
695 return (ISC_R_FAILURE);
696 }
697
698 return (ISC_R_SUCCESS);
699 }
700
701 /*
702 * Find first differing bit.
703 */
704 static int
ffbit(dns_rpz_cidr_word_t w)705 ffbit(dns_rpz_cidr_word_t w) {
706 int bit;
707
708 bit = DNS_RPZ_CIDR_WORD_BITS-1;
709 if ((w & 0xffff0000) != 0) {
710 w >>= 16;
711 bit -= 16;
712 }
713 if ((w & 0xff00) != 0) {
714 w >>= 8;
715 bit -= 8;
716 }
717 if ((w & 0xf0) != 0) {
718 w >>= 4;
719 bit -= 4;
720 }
721 if ((w & 0xc) != 0) {
722 w >>= 2;
723 bit -= 2;
724 }
725 if ((w & 2) != 0)
726 --bit;
727 return (bit);
728 }
729
730 /*
731 * Find the first differing bit in two keys.
732 */
733 static int
diff_keys(const dns_rpz_cidr_key_t * key1,dns_rpz_cidr_bits_t bits1,const dns_rpz_cidr_key_t * key2,dns_rpz_cidr_bits_t bits2)734 diff_keys(const dns_rpz_cidr_key_t *key1, dns_rpz_cidr_bits_t bits1,
735 const dns_rpz_cidr_key_t *key2, dns_rpz_cidr_bits_t bits2)
736 {
737 dns_rpz_cidr_word_t delta;
738 dns_rpz_cidr_bits_t maxbit, bit;
739 int i;
740
741 bit = 0;
742 maxbit = ISC_MIN(bits1, bits2);
743
744 /*
745 * find the first differing words
746 */
747 for (i = 0;
748 bit < maxbit;
749 i++, bit += DNS_RPZ_CIDR_WORD_BITS) {
750 delta = key1->w[i] ^ key2->w[i];
751 if (delta != 0) {
752 bit += ffbit(delta);
753 break;
754 }
755 }
756 return (ISC_MIN(bit, maxbit));
757 }
758
759 /*
760 * Search a radix tree for an IP address for ordinary lookup
761 * or for a CIDR block adding or deleting an entry
762 * The tree read (for simple search) or write lock must be held by the caller.
763 *
764 * Return ISC_R_SUCCESS, ISC_R_NOTFOUND, DNS_R_PARTIALMATCH, ISC_R_EXISTS,
765 * ISC_R_NOMEMORY
766 */
767 static isc_result_t
search(dns_rpz_cidr_t * cidr,const dns_rpz_cidr_key_t * tgt_ip,dns_rpz_cidr_bits_t tgt_prefix,dns_rpz_type_t type,isc_boolean_t create,dns_rpz_cidr_node_t ** found)768 search(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip,
769 dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type,
770 isc_boolean_t create,
771 dns_rpz_cidr_node_t **found) /* NULL or longest match node */
772 {
773 dns_rpz_cidr_node_t *cur, *parent, *child, *new_parent, *sibling;
774 int cur_num, child_num;
775 dns_rpz_cidr_bits_t dbit;
776 dns_rpz_cidr_flags_t flags, data_flag;
777 isc_result_t find_result;
778
779 flags = get_flags(tgt_ip, tgt_prefix, type);
780 data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA |
781 DNS_RPZ_CIDR_FG_NSIP_DATA);
782
783 find_result = ISC_R_NOTFOUND;
784 if (found != NULL)
785 *found = NULL;
786 cur = cidr->root;
787 parent = NULL;
788 cur_num = 0;
789 for (;;) {
790 if (cur == NULL) {
791 /*
792 * No child so we cannot go down. Fail or
793 * add the target as a child of the current parent.
794 */
795 if (!create)
796 return (find_result);
797 child = new_node(cidr, tgt_ip, tgt_prefix, 0);
798 if (child == NULL)
799 return (ISC_R_NOMEMORY);
800 if (parent == NULL)
801 cidr->root = child;
802 else
803 parent->child[cur_num] = child;
804 child->parent = parent;
805 set_node_flags(child, type);
806 if (found != NULL)
807 *found = cur;
808 return (ISC_R_SUCCESS);
809 }
810
811 /*
812 * Pretend a node not in the correct tree does not exist
813 * if we are not adding to the tree,
814 * If we are adding, then continue down to eventually
815 * add a node and mark/put this node in the correct tree.
816 */
817 if ((cur->flags & flags) == 0 && !create)
818 return (find_result);
819
820 dbit = diff_keys(tgt_ip, tgt_prefix, &cur->ip, cur->bits);
821 /*
822 * dbit <= tgt_prefix and dbit <= cur->bits always.
823 * We are finished searching if we matched all of the target.
824 */
825 if (dbit == tgt_prefix) {
826 if (tgt_prefix == cur->bits) {
827 /*
828 * The current node matches the target exactly.
829 * It is the answer if it has data.
830 */
831 if ((cur->flags & data_flag) != 0) {
832 if (create)
833 return (ISC_R_EXISTS);
834 if (found != NULL)
835 *found = cur;
836 return (ISC_R_SUCCESS);
837 } else if (create) {
838 /*
839 * The node had no data but does now.
840 */
841 set_node_flags(cur, type);
842 if (found != NULL)
843 *found = cur;
844 return (ISC_R_SUCCESS);
845 }
846 return (find_result);
847 }
848
849 /*
850 * We know tgt_prefix < cur_bits which means that
851 * the target is shorter than the current node.
852 * Add the target as the current node's parent.
853 */
854 if (!create)
855 return (find_result);
856
857 new_parent = new_node(cidr, tgt_ip, tgt_prefix,
858 cur->flags);
859 if (new_parent == NULL)
860 return (ISC_R_NOMEMORY);
861 new_parent->parent = parent;
862 if (parent == NULL)
863 cidr->root = new_parent;
864 else
865 parent->child[cur_num] = new_parent;
866 child_num = DNS_RPZ_IP_BIT(&cur->ip, tgt_prefix+1);
867 new_parent->child[child_num] = cur;
868 cur->parent = new_parent;
869 set_node_flags(new_parent, type);
870 if (found != NULL)
871 *found = new_parent;
872 return (ISC_R_SUCCESS);
873 }
874
875 if (dbit == cur->bits) {
876 /*
877 * We have a partial match by matching of all of the
878 * current node but only part of the target.
879 * Try to go down.
880 */
881 if ((cur->flags & data_flag) != 0) {
882 find_result = DNS_R_PARTIALMATCH;
883 if (found != NULL)
884 *found = cur;
885 }
886
887 parent = cur;
888 cur_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
889 cur = cur->child[cur_num];
890 continue;
891 }
892
893
894 /*
895 * dbit < tgt_prefix and dbit < cur->bits,
896 * so we failed to match both the target and the current node.
897 * Insert a fork of a parent above the current node and
898 * add the target as a sibling of the current node
899 */
900 if (!create)
901 return (find_result);
902
903 sibling = new_node(cidr, tgt_ip, tgt_prefix, 0);
904 if (sibling == NULL)
905 return (ISC_R_NOMEMORY);
906 new_parent = new_node(cidr, tgt_ip, dbit, cur->flags);
907 if (new_parent == NULL) {
908 isc_mem_put(cidr->mctx, sibling, sizeof(*sibling));
909 return (ISC_R_NOMEMORY);
910 }
911 new_parent->parent = parent;
912 if (parent == NULL)
913 cidr->root = new_parent;
914 else
915 parent->child[cur_num] = new_parent;
916 child_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
917 new_parent->child[child_num] = sibling;
918 new_parent->child[1-child_num] = cur;
919 cur->parent = new_parent;
920 sibling->parent = new_parent;
921 set_node_flags(sibling, type);
922 if (found != NULL)
923 *found = sibling;
924 return (ISC_R_SUCCESS);
925 }
926 }
927
928 /*
929 * Add an IP address to the radix tree of a response policy database.
930 * The tree write lock must be held by the caller.
931 */
932 void
dns_rpz_cidr_addip(dns_rpz_cidr_t * cidr,dns_name_t * name)933 dns_rpz_cidr_addip(dns_rpz_cidr_t *cidr, dns_name_t *name) {
934 isc_result_t result;
935 dns_rpz_cidr_key_t tgt_ip;
936 dns_rpz_cidr_bits_t tgt_prefix;
937 dns_rpz_type_t type;
938
939 REQUIRE(cidr != NULL);
940
941 /*
942 * No worries if the new name is not an IP address.
943 */
944 type = set_type(cidr, name);
945 switch (type) {
946 case DNS_RPZ_TYPE_IP:
947 case DNS_RPZ_TYPE_NSIP:
948 break;
949 case DNS_RPZ_TYPE_NSDNAME:
950 cidr->have_nsdname = ISC_TRUE;
951 return;
952 case DNS_RPZ_TYPE_QNAME:
953 case DNS_RPZ_TYPE_BAD:
954 return;
955 }
956 result = name2ipkey(cidr, DNS_RPZ_ERROR_LEVEL, name,
957 type, &tgt_ip, &tgt_prefix);
958 if (result != ISC_R_SUCCESS)
959 return;
960
961 result = search(cidr, &tgt_ip, tgt_prefix, type, ISC_TRUE, NULL);
962 if (result == ISC_R_EXISTS &&
963 isc_log_wouldlog(dns_lctx, DNS_RPZ_ERROR_LEVEL))
964 {
965 char printname[DNS_NAME_FORMATSIZE];
966
967 /*
968 * bin/tests/system/rpz/tests.sh looks for "rpz.*failed".
969 */
970 dns_name_format(name, printname, sizeof(printname));
971 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ,
972 DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
973 "rpz add failed; \"%s\" is a duplicate name",
974 printname);
975 }
976 }
977
978 /*
979 * Delete an IP address from the radix tree of a response policy database.
980 * The tree write lock must be held by the caller.
981 */
982 void
dns_rpz_cidr_deleteip(dns_rpz_cidr_t * cidr,dns_name_t * name)983 dns_rpz_cidr_deleteip(dns_rpz_cidr_t *cidr, dns_name_t *name) {
984 isc_result_t result;
985 dns_rpz_cidr_key_t tgt_ip;
986 dns_rpz_cidr_bits_t tgt_prefix;
987 dns_rpz_type_t type;
988 dns_rpz_cidr_node_t *tgt = NULL, *parent, *child;
989 dns_rpz_cidr_flags_t flags, data_flag;
990
991 if (cidr == NULL)
992 return;
993
994 /*
995 * Decide which kind of policy zone IP address it is, if either
996 * and then find its node.
997 */
998 type = set_type(cidr, name);
999 switch (type) {
1000 case DNS_RPZ_TYPE_IP:
1001 case DNS_RPZ_TYPE_NSIP:
1002 break;
1003 case DNS_RPZ_TYPE_NSDNAME:
1004 /*
1005 * We cannot easily count nsdnames because
1006 * internal rbt nodes get deleted.
1007 */
1008 return;
1009 case DNS_RPZ_TYPE_QNAME:
1010 case DNS_RPZ_TYPE_BAD:
1011 return;
1012 }
1013
1014 /*
1015 * Do not get excited about the deletion of interior rbt nodes.
1016 */
1017 result = name2ipkey(cidr, DNS_RPZ_DEBUG_QUIET, name,
1018 type, &tgt_ip, &tgt_prefix);
1019 if (result != ISC_R_SUCCESS)
1020 return;
1021
1022 result = search(cidr, &tgt_ip, tgt_prefix, type, ISC_FALSE, &tgt);
1023 if (result != ISC_R_SUCCESS) {
1024 badname(DNS_RPZ_ERROR_LEVEL, name, "; missing rpz node", "");
1025 return;
1026 }
1027
1028 /*
1029 * Mark the node and its parents to reflect the deleted IP address.
1030 */
1031 flags = get_flags(&tgt_ip, tgt_prefix, type);
1032 data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA |
1033 DNS_RPZ_CIDR_FG_NSIP_DATA);
1034 tgt->flags &= ~data_flag;
1035 for (parent = tgt; parent != NULL; parent = parent->parent) {
1036 if ((parent->flags & data_flag) != 0 ||
1037 (parent->child[0] != NULL &&
1038 (parent->child[0]->flags & flags) != 0) ||
1039 (parent->child[1] != NULL &&
1040 (parent->child[1]->flags & flags) != 0))
1041 break;
1042 parent->flags &= ~flags;
1043 }
1044
1045 /*
1046 * We might need to delete 2 nodes.
1047 */
1048 do {
1049 /*
1050 * The node is now useless if it has no data of its own
1051 * and 0 or 1 children. We are finished if it is not useless.
1052 */
1053 if ((child = tgt->child[0]) != NULL) {
1054 if (tgt->child[1] != NULL)
1055 return;
1056 } else {
1057 child = tgt->child[1];
1058 }
1059 if ((tgt->flags & (DNS_RPZ_CIDR_FG_IP_DATA |
1060 DNS_RPZ_CIDR_FG_NSIP_DATA)) != 0)
1061 return;
1062
1063 /*
1064 * Replace the pointer to this node in the parent with
1065 * the remaining child or NULL.
1066 */
1067 parent = tgt->parent;
1068 if (parent == NULL) {
1069 cidr->root = child;
1070 } else {
1071 parent->child[parent->child[1] == tgt] = child;
1072 }
1073 /*
1074 * If the child exists fix up its parent pointer.
1075 */
1076 if (child != NULL)
1077 child->parent = parent;
1078 isc_mem_put(cidr->mctx, tgt, sizeof(*tgt));
1079
1080 tgt = parent;
1081 } while (tgt != NULL);
1082 }
1083
1084 /*
1085 * Caller must hold tree lock.
1086 * Return ISC_R_NOTFOUND
1087 * or ISC_R_SUCCESS and the found entry's canonical and search names
1088 * and its prefix length
1089 */
1090 isc_result_t
dns_rpz_cidr_find(dns_rpz_cidr_t * cidr,const isc_netaddr_t * netaddr,dns_rpz_type_t type,dns_name_t * canon_name,dns_name_t * search_name,dns_rpz_cidr_bits_t * prefix)1091 dns_rpz_cidr_find(dns_rpz_cidr_t *cidr, const isc_netaddr_t *netaddr,
1092 dns_rpz_type_t type, dns_name_t *canon_name,
1093 dns_name_t *search_name, dns_rpz_cidr_bits_t *prefix)
1094 {
1095 dns_rpz_cidr_key_t tgt_ip;
1096 isc_result_t result;
1097 dns_rpz_cidr_node_t *found;
1098 int i;
1099
1100 /*
1101 * Convert IP address to CIDR tree key.
1102 */
1103 if (netaddr->family == AF_INET) {
1104 tgt_ip.w[0] = 0;
1105 tgt_ip.w[1] = 0;
1106 tgt_ip.w[2] = ADDR_V4MAPPED;
1107 tgt_ip.w[3] = ntohl(netaddr->type.in.s_addr);
1108 } else if (netaddr->family == AF_INET6) {
1109 dns_rpz_cidr_key_t src_ip6;
1110
1111 /*
1112 * Given the int aligned struct in_addr member of netaddr->type
1113 * one could cast netaddr->type.in6 to dns_rpz_cidr_key_t *,
1114 * but there are objections.
1115 */
1116 memmove(src_ip6.w, &netaddr->type.in6, sizeof(src_ip6.w));
1117 for (i = 0; i < 4; i++) {
1118 tgt_ip.w[i] = ntohl(src_ip6.w[i]);
1119 }
1120 } else {
1121 return (ISC_R_NOTFOUND);
1122 }
1123
1124 result = search(cidr, &tgt_ip, 128, type, ISC_FALSE, &found);
1125 if (result != ISC_R_SUCCESS && result != DNS_R_PARTIALMATCH)
1126 return (result);
1127
1128 *prefix = found->bits;
1129 return (ip2name(cidr, &found->ip, found->bits, type,
1130 canon_name, search_name));
1131 }
1132
1133 /*
1134 * Translate CNAME rdata to a QNAME response policy action.
1135 */
1136 dns_rpz_policy_t
dns_rpz_decode_cname(dns_rpz_zone_t * rpz,dns_rdataset_t * rdataset,dns_name_t * selfname)1137 dns_rpz_decode_cname(dns_rpz_zone_t *rpz, dns_rdataset_t *rdataset,
1138 dns_name_t *selfname)
1139 {
1140 dns_rdata_t rdata = DNS_RDATA_INIT;
1141 dns_rdata_cname_t cname;
1142 isc_result_t result;
1143
1144 result = dns_rdataset_first(rdataset);
1145 RUNTIME_CHECK(result == ISC_R_SUCCESS);
1146 dns_rdataset_current(rdataset, &rdata);
1147 result = dns_rdata_tostruct(&rdata, &cname, NULL);
1148 RUNTIME_CHECK(result == ISC_R_SUCCESS);
1149 dns_rdata_reset(&rdata);
1150
1151 /*
1152 * CNAME . means NXDOMAIN
1153 */
1154 if (dns_name_equal(&cname.cname, dns_rootname))
1155 return (DNS_RPZ_POLICY_NXDOMAIN);
1156
1157 if (dns_name_iswildcard(&cname.cname)) {
1158 /*
1159 * CNAME *. means NODATA
1160 */
1161 if (dns_name_countlabels(&cname.cname) == 2)
1162 return (DNS_RPZ_POLICY_NODATA);
1163
1164 /*
1165 * A qname of www.evil.com and a policy of
1166 * *.evil.com CNAME *.garden.net
1167 * gives a result of
1168 * evil.com CNAME evil.com.garden.net
1169 */
1170 if (dns_name_countlabels(&cname.cname) > 2)
1171 return (DNS_RPZ_POLICY_WILDCNAME);
1172 }
1173
1174 /*
1175 * CNAME PASSTHRU.origin means "do not rewrite.
1176 */
1177 if (dns_name_equal(&cname.cname, &rpz->passthru))
1178 return (DNS_RPZ_POLICY_PASSTHRU);
1179
1180 /*
1181 * 128.1.0.127.rpz-ip CNAME 128.1.0.0.127. is obsolete PASSTHRU
1182 */
1183 if (selfname != NULL && dns_name_equal(&cname.cname, selfname))
1184 return (DNS_RPZ_POLICY_PASSTHRU);
1185
1186 /*
1187 * Any other rdata gives a response consisting of the rdata.
1188 */
1189 return (DNS_RPZ_POLICY_RECORD);
1190 }
1191