1 /* 2 * validator/val_nsec3.h - validator NSEC3 denial of existence 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 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33 * SOFTWARE, EVEN IF ADVISED OF THE 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 existence, 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" 71 #include "sldns/rrdef.h" 72 struct val_env; 73 struct regional; 74 struct module_env; 75 struct module_qstate; 76 struct ub_packed_rrset_key; 77 struct reply_info; 78 struct query_info; 79 struct key_entry_key; 80 struct sldns_buffer; 81 82 /** 83 * 0 1 2 3 4 5 6 7 84 * +-+-+-+-+-+-+-+-+ 85 * | |O| 86 * +-+-+-+-+-+-+-+-+ 87 * The OPT-OUT bit in the NSEC3 flags field. 88 * If enabled, there can be zero or more unsigned delegations in the span. 89 * If disabled, there are zero unsigned delegations in the span. 90 */ 91 #define NSEC3_OPTOUT 0x01 92 /** 93 * The unknown flags in the NSEC3 flags field. 94 * They must be zero, or the NSEC3 is ignored. 95 */ 96 #define NSEC3_UNKNOWN_FLAGS 0xFE 97 98 /** The SHA1 hash algorithm for NSEC3 */ 99 #define NSEC3_HASH_SHA1 0x01 100 101 /** 102 * Cache table for NSEC3 hashes. 103 * It keeps a *pointer* to the region its items are allocated. 104 */ 105 struct nsec3_cache_table { 106 rbtree_type* ct; 107 struct regional* region; 108 }; 109 110 /** 111 * Determine if the set of NSEC3 records provided with a response prove NAME 112 * ERROR. This means that the NSEC3s prove a) the closest encloser exists, 113 * b) the direct child of the closest encloser towards qname doesn't exist, 114 * and c) *.closest encloser does not exist. 115 * 116 * @param env: module environment with temporary region and buffer. 117 * @param ve: validator environment, with iteration count settings. 118 * @param list: array of RRsets, some of which are NSEC3s. 119 * @param num: number of RRsets in the array to examine. 120 * @param qinfo: query that is verified for. 121 * @param kkey: key entry that signed the NSEC3s. 122 * @param ct: cached hashes table. 123 * @param calc: current hash calculations. 124 * @return: 125 * sec_status SECURE of the Name Error is proven by the NSEC3 RRs, 126 * BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored, 127 * UNCHECKED if no more hash calculations are allowed at this point. 128 */ 129 enum sec_status 130 nsec3_prove_nameerror(struct module_env* env, struct val_env* ve, 131 struct ub_packed_rrset_key** list, size_t num, 132 struct query_info* qinfo, struct key_entry_key* kkey, 133 struct nsec3_cache_table* ct, int* calc); 134 135 /** 136 * Determine if the NSEC3s provided in a response prove the NOERROR/NODATA 137 * status. There are a number of different variants to this: 138 * 139 * 1) Normal NODATA -- qname is matched to an NSEC3 record, type is not 140 * present. 141 * 142 * 2) ENT NODATA -- because there must be NSEC3 record for 143 * empty-non-terminals, this is the same as #1. 144 * 145 * 3) NSEC3 ownername NODATA -- qname matched an existing, lone NSEC3 146 * ownername, but qtype was not NSEC3. NOTE: as of nsec-05, this case no 147 * longer exists. 148 * 149 * 4) Wildcard NODATA -- A wildcard matched the name, but not the type. 150 * 151 * 5) Opt-In DS NODATA -- the qname is covered by an opt-in span and qtype == 152 * DS. (or maybe some future record with the same parent-side-only property) 153 * 154 * @param env: module environment with temporary region and buffer. 155 * @param ve: validator environment, with iteration count settings. 156 * @param list: array of RRsets, some of which are NSEC3s. 157 * @param num: number of RRsets in the array to examine. 158 * @param qinfo: query that is verified for. 159 * @param kkey: key entry that signed the NSEC3s. 160 * @param ct: cached hashes table. 161 * @param calc: current hash calculations. 162 * @return: 163 * sec_status SECURE of the proposition is proven by the NSEC3 RRs, 164 * BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored, 165 * UNCHECKED if no more hash calculations are allowed at this point. 166 */ 167 enum sec_status 168 nsec3_prove_nodata(struct module_env* env, struct val_env* ve, 169 struct ub_packed_rrset_key** list, size_t num, 170 struct query_info* qinfo, struct key_entry_key* kkey, 171 struct nsec3_cache_table* ct, int* calc); 172 173 /** 174 * Prove that a positive wildcard match was appropriate (no direct match 175 * RRset). 176 * 177 * @param env: module environment with temporary region and buffer. 178 * @param ve: validator environment, with iteration count settings. 179 * @param list: array of RRsets, some of which are NSEC3s. 180 * @param num: number of RRsets in the array to examine. 181 * @param qinfo: query that is verified for. 182 * @param kkey: key entry that signed the NSEC3s. 183 * @param wc: The purported wildcard that matched. This is the wildcard name 184 * as *.wildcard.name., with the *. label already removed. 185 * @param ct: cached hashes table. 186 * @param calc: current hash calculations. 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 * UNCHECKED if no more hash calculations are allowed at this point. 191 */ 192 enum sec_status 193 nsec3_prove_wildcard(struct module_env* env, struct val_env* ve, 194 struct ub_packed_rrset_key** list, size_t num, 195 struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc, 196 struct nsec3_cache_table* ct, int* calc); 197 198 /** 199 * Prove that a DS response either had no DS, or wasn't a delegation point. 200 * 201 * Fundamentally there are two cases here: normal NODATA and Opt-In NODATA. 202 * 203 * @param env: module environment with temporary region and buffer. 204 * @param ve: validator environment, with iteration count settings. 205 * @param list: array of RRsets, some of which are NSEC3s. 206 * @param num: number of RRsets in the array to examine. 207 * @param qinfo: query that is verified for. 208 * @param kkey: key entry that signed the NSEC3s. 209 * @param reason: string for bogus result. 210 * @param reason_bogus: EDE (RFC8914) code paired with the reason of failure. 211 * @param qstate: qstate with region. 212 * @param ct: cached hashes table. 213 * @param reasonbuf: buffer to use for fail reason string print. 214 * @param reasonlen: length of reasonbuf. 215 * @return: 216 * sec_status SECURE of the proposition is proven by the NSEC3 RRs, 217 * BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored. 218 * or if there was no DS in an insecure (i.e., opt-in) way, 219 * INDETERMINATE if it was clear that this wasn't a delegation point, 220 * UNCHECKED if no more hash calculations are allowed at this point. 221 */ 222 enum sec_status 223 nsec3_prove_nods(struct module_env* env, struct val_env* ve, 224 struct ub_packed_rrset_key** list, size_t num, 225 struct query_info* qinfo, struct key_entry_key* kkey, char** reason, 226 sldns_ede_code* reason_bogus, struct module_qstate* qstate, 227 struct nsec3_cache_table* ct, char* reasonbuf, size_t reasonlen); 228 229 /** 230 * Prove NXDOMAIN or NODATA. 231 * 232 * @param env: module environment with temporary region and buffer. 233 * @param ve: validator environment, with iteration count settings. 234 * @param list: array of RRsets, some of which are NSEC3s. 235 * @param num: number of RRsets in the array to examine. 236 * @param qinfo: query that is verified for. 237 * @param kkey: key entry that signed the NSEC3s. 238 * @param nodata: if return value is secure, this indicates if nodata or 239 * nxdomain was proven. 240 * @param ct: cached hashes table. 241 * @param calc: current hash calculations. 242 * @return: 243 * sec_status SECURE of the proposition is proven by the NSEC3 RRs, 244 * BOGUS if not, INSECURE if all of the NSEC3s could be validly ignored, 245 * UNCHECKED if no more hash calculations are allowed at this point. 246 */ 247 enum sec_status 248 nsec3_prove_nxornodata(struct module_env* env, struct val_env* ve, 249 struct ub_packed_rrset_key** list, size_t num, 250 struct query_info* qinfo, struct key_entry_key* kkey, int* nodata, 251 struct nsec3_cache_table* ct, int* calc); 252 253 /** 254 * The NSEC3 hash result storage. 255 * Consists of an rbtree, with these nodes in it. 256 * The nodes detail how a set of parameters (from nsec3 rr) plus 257 * a dname result in a hash. 258 */ 259 struct nsec3_cached_hash { 260 /** rbtree node, key is this structure */ 261 rbnode_type node; 262 /** where are the parameters for conversion, in this rrset data */ 263 struct ub_packed_rrset_key* nsec3; 264 /** where are the parameters for conversion, this RR number in data */ 265 int rr; 266 /** the name to convert */ 267 uint8_t* dname; 268 /** length of the dname */ 269 size_t dname_len; 270 /** the hash result (not base32 encoded) */ 271 uint8_t* hash; 272 /** length of hash in bytes */ 273 size_t hash_len; 274 /** the hash result in base32 encoding */ 275 uint8_t* b32; 276 /** length of base32 encoding (as a label) */ 277 size_t b32_len; 278 }; 279 280 /** 281 * Rbtree for hash cache comparison function. 282 * @param c1: key 1. 283 * @param c2: key 2. 284 * @return: comparison code, -1, 0, 1, of the keys. 285 */ 286 int nsec3_hash_cmp(const void* c1, const void* c2); 287 288 /** 289 * Initialise the NSEC3 cache table. 290 * @param ct: the nsec3 cache table. 291 * @param region: the region where allocations for the table will happen. 292 * @return true on success, false on malloc error. 293 */ 294 int nsec3_cache_table_init(struct nsec3_cache_table* ct, struct regional* region); 295 296 /** 297 * Obtain the hash of an owner name. 298 * Used internally by the nsec3 proof functions in this file. 299 * published to enable unit testing of hash algorithms and cache. 300 * 301 * @param table: the cache table. Must be initialised at start. 302 * @param region: scratch region to use for allocation. 303 * This region holds the tree, if you wipe the region, reinit the tree. 304 * @param buf: temporary buffer. 305 * @param nsec3: the rrset with parameters 306 * @param rr: rr number from d that has the NSEC3 parameters to hash to. 307 * @param dname: name to hash 308 * This pointer is used inside the tree, assumed region-alloced. 309 * @param dname_len: the length of the name. 310 * @param hash: the hash node is returned on success. 311 * @return: 312 * 2 on success, hash from cache is returned. 313 * 1 on success, newly computed hash is returned. 314 * 0 on a malloc failure. 315 * -1 if the NSEC3 rr was badly formatted (i.e. formerr). 316 */ 317 int nsec3_hash_name(rbtree_type* table, struct regional* region, 318 struct sldns_buffer* buf, struct ub_packed_rrset_key* nsec3, int rr, 319 uint8_t* dname, size_t dname_len, struct nsec3_cached_hash** hash); 320 321 /** 322 * Get next owner name, converted to base32 encoding and with the 323 * zone name (taken from the nsec3 owner name) appended. 324 * @param rrset: the NSEC3 rrset. 325 * @param r: the rr num of the nsec3 in the rrset. 326 * @param buf: buffer to store name in 327 * @param max: size of buffer. 328 * @return length of name on success. 0 on failure (buffer too short or 329 * bad format nsec3 record). 330 */ 331 size_t nsec3_get_nextowner_b32(struct ub_packed_rrset_key* rrset, int r, 332 uint8_t* buf, size_t max); 333 334 /** 335 * Convert hash into base32 encoding and with the 336 * zone name appended. 337 * @param hash: hashed buffer 338 * @param hashlen: length of hash 339 * @param zone: name of zone 340 * @param zonelen: length of zonename. 341 * @param buf: buffer to store name in 342 * @param max: size of buffer. 343 * @return length of name on success. 0 on failure (buffer too short or 344 * bad format nsec3 record). 345 */ 346 size_t nsec3_hash_to_b32(uint8_t* hash, size_t hashlen, uint8_t* zone, 347 size_t zonelen, uint8_t* buf, size_t max); 348 349 /** 350 * Get NSEC3 parameters out of rr. 351 * @param rrset: the NSEC3 rrset. 352 * @param r: the rr num of the nsec3 in the rrset. 353 * @param algo: nsec3 hash algo. 354 * @param iter: iteration count. 355 * @param salt: ptr to salt inside rdata. 356 * @param saltlen: length of salt. 357 * @return 0 if bad formatted, unknown nsec3 hash algo, or unknown flags set. 358 */ 359 int nsec3_get_params(struct ub_packed_rrset_key* rrset, int r, 360 int* algo, size_t* iter, uint8_t** salt, size_t* saltlen); 361 362 /** 363 * Get NSEC3 hashed in a buffer 364 * @param buf: buffer for temp use. 365 * @param nm: name to hash 366 * @param nmlen: length of nm. 367 * @param algo: algo to use, must be known. 368 * @param iter: iterations 369 * @param salt: salt for nsec3 370 * @param saltlen: length of salt. 371 * @param res: result of hash stored here. 372 * @param max: maximum space for result. 373 * @return 0 on failure, otherwise bytelength stored. 374 */ 375 size_t nsec3_get_hashed(struct sldns_buffer* buf, uint8_t* nm, size_t nmlen, 376 int algo, size_t iter, uint8_t* salt, size_t saltlen, uint8_t* res, 377 size_t max); 378 379 /** 380 * see if NSEC3 RR contains given type 381 * @param rrset: NSEC3 rrset 382 * @param r: RR in rrset 383 * @param type: in host order to check bit for. 384 * @return true if bit set, false if not or error. 385 */ 386 int nsec3_has_type(struct ub_packed_rrset_key* rrset, int r, uint16_t type); 387 388 /** 389 * return if nsec3 RR has the optout flag 390 * @param rrset: NSEC3 rrset 391 * @param r: RR in rrset 392 * @return true if optout, false on error or not optout 393 */ 394 int nsec3_has_optout(struct ub_packed_rrset_key* rrset, int r); 395 396 /** 397 * Return nsec3 RR next hashed owner name 398 * @param rrset: NSEC3 rrset 399 * @param r: RR in rrset 400 * @param next: ptr into rdata to next owner hash 401 * @param nextlen: length of hash. 402 * @return false on malformed 403 */ 404 int nsec3_get_nextowner(struct ub_packed_rrset_key* rrset, int r, 405 uint8_t** next, size_t* nextlen); 406 407 /** 408 * nsec3Covers 409 * Given a hash and a candidate NSEC3Record, determine if that NSEC3Record 410 * covers the hash. Covers specifically means that the hash is in between 411 * the owner and next hashes and does not equal either. 412 * 413 * @param zone: the zone name. 414 * @param hash: the hash of the name 415 * @param rrset: the rrset of the NSEC3. 416 * @param rr: which rr in the rrset. 417 * @param buf: temporary buffer. 418 * @return true if covers, false if not. 419 */ 420 int nsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash, 421 struct ub_packed_rrset_key* rrset, int rr, struct sldns_buffer* buf); 422 423 #endif /* VALIDATOR_VAL_NSEC3_H */ 424