1/*
2 * validator/val_nsec3.h - validator NSEC3 denial of existance functions.
3 *
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
18 *
19 * Neither the name of the NLNET LABS nor the names of its contributors may
20 * be used to endorse or promote products derived from this software without
21 * specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
34 */
35
36/**
37 * \file
38 *
39 * This file contains helper functions for the validator module.
40 * The functions help with NSEC3 checking, the different NSEC3 proofs
41 * for denial of existance, and proofs for presence of types.
42 *
43 * NSEC3
44 *                      1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
45 *  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
46 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
47 * |   Hash Alg.   |     Flags     |          Iterations           |
48 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
49 * |  Salt Length  |                     Salt                      /
50 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
51 * |  Hash Length  |             Next Hashed Owner Name            /
52 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
53 * /                         Type Bit Maps                         /
54 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
55 *
56 * NSEC3PARAM
57 *                      1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
58 *  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
59 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
60 * |   Hash Alg.   |     Flags     |          Iterations           |
61 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
62 * |  Salt Length  |                     Salt                      /
63 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
64 *
65 */
66
67#ifndef VALIDATOR_VAL_NSEC3_H
68#define VALIDATOR_VAL_NSEC3_H
69#include "util/rbtree.h"
70#include "util/data/packed_rrset.h"
71struct val_env;
72struct regional;
73struct module_env;
74struct ub_packed_rrset_key;
75struct reply_info;
76struct query_info;
77struct key_entry_key;
78
79/**
80 *     0 1 2 3 4 5 6 7
81 *    +-+-+-+-+-+-+-+-+
82 *    |             |O|
83 *    +-+-+-+-+-+-+-+-+
84 * The OPT-OUT bit in the NSEC3 flags field.
85 * If enabled, there can be zero or more unsigned delegations in the span.
86 * If disabled, there are zero unsigned delegations in the span.
87 */
88#define NSEC3_OPTOUT	0x01
89/**
90 * The unknown flags in the NSEC3 flags field.
91 * They must be zero, or the NSEC3 is ignored.
92 */
93#define NSEC3_UNKNOWN_FLAGS 0xFE
94
95/** The SHA1 hash algorithm for NSEC3 */
96#define NSEC3_HASH_SHA1	0x01
97
98/**
99 * Determine if the set of NSEC3 records provided with a response prove NAME
100 * ERROR. This means that the NSEC3s prove a) the closest encloser exists,
101 * b) the direct child of the closest encloser towards qname doesn't exist,
102 * and c) *.closest encloser does not exist.
103 *
104 * @param env: module environment with temporary region and buffer.
105 * @param ve: validator environment, with iteration count settings.
106 * @param list: array of RRsets, some of which are NSEC3s.
107 * @param num: number of RRsets in the array to examine.
108 * @param qinfo: query that is verified for.
109 * @param kkey: key entry that signed the NSEC3s.
110 * @return:
111 * 	sec_status SECURE of the Name Error is proven by the NSEC3 RRs,
112 * 	BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored.
113 */
114enum sec_status
115nsec3_prove_nameerror(struct module_env* env, struct val_env* ve,
116	struct ub_packed_rrset_key** list, size_t num,
117	struct query_info* qinfo, struct key_entry_key* kkey);
118
119/**
120 * Determine if the NSEC3s provided in a response prove the NOERROR/NODATA
121 * status. There are a number of different variants to this:
122 *
123 * 1) Normal NODATA -- qname is matched to an NSEC3 record, type is not
124 * present.
125 *
126 * 2) ENT NODATA -- because there must be NSEC3 record for
127 * empty-non-terminals, this is the same as #1.
128 *
129 * 3) NSEC3 ownername NODATA -- qname matched an existing, lone NSEC3
130 * ownername, but qtype was not NSEC3. NOTE: as of nsec-05, this case no
131 * longer exists.
132 *
133 * 4) Wildcard NODATA -- A wildcard matched the name, but not the type.
134 *
135 * 5) Opt-In DS NODATA -- the qname is covered by an opt-in span and qtype ==
136 * DS. (or maybe some future record with the same parent-side-only property)
137 *
138 * @param env: module environment with temporary region and buffer.
139 * @param ve: validator environment, with iteration count settings.
140 * @param list: array of RRsets, some of which are NSEC3s.
141 * @param num: number of RRsets in the array to examine.
142 * @param qinfo: query that is verified for.
143 * @param kkey: key entry that signed the NSEC3s.
144 * @return:
145 * 	sec_status SECURE of the proposition is proven by the NSEC3 RRs,
146 * 	BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored.
147 */
148enum sec_status
149nsec3_prove_nodata(struct module_env* env, struct val_env* ve,
150	struct ub_packed_rrset_key** list, size_t num,
151	struct query_info* qinfo, struct key_entry_key* kkey);
152
153
154/**
155 * Prove that a positive wildcard match was appropriate (no direct match
156 * RRset).
157 *
158 * @param env: module environment with temporary region and buffer.
159 * @param ve: validator environment, with iteration count settings.
160 * @param list: array of RRsets, some of which are NSEC3s.
161 * @param num: number of RRsets in the array to examine.
162 * @param qinfo: query that is verified for.
163 * @param kkey: key entry that signed the NSEC3s.
164 * @param wc: The purported wildcard that matched. This is the wildcard name
165 * 	as *.wildcard.name., with the *. label already removed.
166 * @return:
167 * 	sec_status SECURE of the proposition is proven by the NSEC3 RRs,
168 * 	BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored.
169 */
170enum sec_status
171nsec3_prove_wildcard(struct module_env* env, struct val_env* ve,
172	struct ub_packed_rrset_key** list, size_t num,
173	struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc);
174
175/**
176 * Prove that a DS response either had no DS, or wasn't a delegation point.
177 *
178 * Fundamentally there are two cases here: normal NODATA and Opt-In NODATA.
179 *
180 * @param env: module environment with temporary region and buffer.
181 * @param ve: validator environment, with iteration count settings.
182 * @param list: array of RRsets, some of which are NSEC3s.
183 * @param num: number of RRsets in the array to examine.
184 * @param qinfo: query that is verified for.
185 * @param kkey: key entry that signed the NSEC3s.
186 * @param reason: string for bogus result.
187 * @return:
188 * 	sec_status SECURE of the proposition is proven by the NSEC3 RRs,
189 * 	BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored.
190 * 	or if there was no DS in an insecure (i.e., opt-in) way,
191 * 	INDETERMINATE if it was clear that this wasn't a delegation point.
192 */
193enum sec_status
194nsec3_prove_nods(struct module_env* env, struct val_env* ve,
195	struct ub_packed_rrset_key** list, size_t num,
196	struct query_info* qinfo, struct key_entry_key* kkey, char** reason);
197
198/**
199 * Prove NXDOMAIN or NODATA.
200 *
201 * @param env: module environment with temporary region and buffer.
202 * @param ve: validator environment, with iteration count settings.
203 * @param list: array of RRsets, some of which are NSEC3s.
204 * @param num: number of RRsets in the array to examine.
205 * @param qinfo: query that is verified for.
206 * @param kkey: key entry that signed the NSEC3s.
207 * @param nodata: if return value is secure, this indicates if nodata or
208 * 	nxdomain was proven.
209 * @return:
210 * 	sec_status SECURE of the proposition is proven by the NSEC3 RRs,
211 * 	BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored.
212 */
213enum sec_status
214nsec3_prove_nxornodata(struct module_env* env, struct val_env* ve,
215	struct ub_packed_rrset_key** list, size_t num,
216	struct query_info* qinfo, struct key_entry_key* kkey, int* nodata);
217
218/**
219 * The NSEC3 hash result storage.
220 * Consists of an rbtree, with these nodes in it.
221 * The nodes detail how a set of parameters (from nsec3 rr) plus
222 * a dname result in a hash.
223 */
224struct nsec3_cached_hash {
225	/** rbtree node, key is this structure */
226	rbnode_t node;
227	/** where are the parameters for conversion, in this rrset data */
228	struct ub_packed_rrset_key* nsec3;
229	/** where are the parameters for conversion, this RR number in data */
230	int rr;
231	/** the name to convert */
232	uint8_t* dname;
233	/** length of the dname */
234	size_t dname_len;
235	/** the hash result (not base32 encoded) */
236	uint8_t* hash;
237	/** length of hash in bytes */
238	size_t hash_len;
239	/** the hash result in base32 encoding */
240	uint8_t* b32;
241	/** length of base32 encoding (as a label) */
242	size_t b32_len;
243};
244
245/**
246 * Rbtree for hash cache comparison function.
247 * @param c1: key 1.
248 * @param c2: key 2.
249 * @return: comparison code, -1, 0, 1, of the keys.
250 */
251int nsec3_hash_cmp(const void* c1, const void* c2);
252
253/**
254 * Obtain the hash of an owner name.
255 * Used internally by the nsec3 proof functions in this file.
256 * published to enable unit testing of hash algorithms and cache.
257 *
258 * @param table: the cache table. Must be inited at start.
259 * @param region: scratch region to use for allocation.
260 * 	This region holds the tree, if you wipe the region, reinit the tree.
261 * @param buf: temporary buffer.
262 * @param nsec3: the rrset with parameters
263 * @param rr: rr number from d that has the NSEC3 parameters to hash to.
264 * @param dname: name to hash
265 * 	This pointer is used inside the tree, assumed region-alloced.
266 * @param dname_len: the length of the name.
267 * @param hash: the hash node is returned on success.
268 * @return:
269 * 	1 on success, either from cache or newly hashed hash is returned.
270 * 	0 on a malloc failure.
271 * 	-1 if the NSEC3 rr was badly formatted (i.e. formerr).
272 */
273int nsec3_hash_name(rbtree_t* table, struct regional* region, ldns_buffer* buf,
274	struct ub_packed_rrset_key* nsec3, int rr, uint8_t* dname,
275	size_t dname_len, struct nsec3_cached_hash** hash);
276
277/**
278 * Get next owner name, converted to base32 encoding and with the
279 * zone name (taken from the nsec3 owner name) appended.
280 * @param rrset: the NSEC3 rrset.
281 * @param r: the rr num of the nsec3 in the rrset.
282 * @param buf: buffer to store name in
283 * @param max: size of buffer.
284 * @return length of name on success. 0 on failure (buffer too short or
285 *	bad format nsec3 record).
286 */
287size_t nsec3_get_nextowner_b32(struct ub_packed_rrset_key* rrset, int r,
288	uint8_t* buf, size_t max);
289
290/**
291 * Convert hash into base32 encoding and with the
292 * zone name appended.
293 * @param hash: hashed buffer
294 * @param hashlen: length of hash
295 * @param zone: name of zone
296 * @param zonelen: length of zonename.
297 * @param buf: buffer to store name in
298 * @param max: size of buffer.
299 * @return length of name on success. 0 on failure (buffer too short or
300 *	bad format nsec3 record).
301 */
302size_t nsec3_hash_to_b32(uint8_t* hash, size_t hashlen, uint8_t* zone,
303	size_t zonelen, uint8_t* buf, size_t max);
304
305/**
306 * Get NSEC3 parameters out of rr.
307 * @param rrset: the NSEC3 rrset.
308 * @param r: the rr num of the nsec3 in the rrset.
309 * @param algo: nsec3 hash algo.
310 * @param iter: iteration count.
311 * @param salt: ptr to salt inside rdata.
312 * @param saltlen: length of salt.
313 * @return 0 if bad formatted, unknown nsec3 hash algo, or unknown flags set.
314 */
315int nsec3_get_params(struct ub_packed_rrset_key* rrset, int r,
316	int* algo, size_t* iter, uint8_t** salt, size_t* saltlen);
317
318/**
319 * Get NSEC3 hashed in a buffer
320 * @param buf: buffer for temp use.
321 * @param nm: name to hash
322 * @param nmlen: length of nm.
323 * @param algo: algo to use, must be known.
324 * @param iter: iterations
325 * @param salt: salt for nsec3
326 * @param saltlen: length of salt.
327 * @param res: result of hash stored here.
328 * @param max: maximum space for result.
329 * @return 0 on failure, otherwise bytelength stored.
330 */
331size_t nsec3_get_hashed(ldns_buffer* buf, uint8_t* nm, size_t nmlen, int algo,
332	size_t iter, uint8_t* salt, size_t saltlen, uint8_t* res, size_t max);
333
334/**
335 * see if NSEC3 RR contains given type
336 * @param rrset: NSEC3 rrset
337 * @param r: RR in rrset
338 * @param type: in host order to check bit for.
339 * @return true if bit set, false if not or error.
340 */
341int nsec3_has_type(struct ub_packed_rrset_key* rrset, int r, uint16_t type);
342
343/**
344 * return if nsec3 RR has the optout flag
345 * @param rrset: NSEC3 rrset
346 * @param r: RR in rrset
347 * @return true if optout, false on error or not optout
348 */
349int nsec3_has_optout(struct ub_packed_rrset_key* rrset, int r);
350
351/**
352 * Return nsec3 RR next hashed owner name
353 * @param rrset: NSEC3 rrset
354 * @param r: RR in rrset
355 * @param next: ptr into rdata to next owner hash
356 * @param nextlen: length of hash.
357 * @return false on malformed
358 */
359int nsec3_get_nextowner(struct ub_packed_rrset_key* rrset, int r,
360	uint8_t** next, size_t* nextlen);
361
362/**
363 * nsec3Covers
364 * Given a hash and a candidate NSEC3Record, determine if that NSEC3Record
365 * covers the hash. Covers specifically means that the hash is in between
366 * the owner and next hashes and does not equal either.
367 *
368 * @param zone: the zone name.
369 * @param hash: the hash of the name
370 * @param rrset: the rrset of the NSEC3.
371 * @param rr: which rr in the rrset.
372 * @param buf: temporary buffer.
373 * @return true if covers, false if not.
374 */
375int nsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash,
376	struct ub_packed_rrset_key* rrset, int rr, ldns_buffer* buf);
377
378#endif /* VALIDATOR_VAL_NSEC3_H */
379