4 * Copyright (c) 2006 VeriSign. All rights reserved.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer. 2. Redistributions in
11 * binary form must reproduce the above copyright notice, this list of
12 * conditions and the following disclaimer in the documentation and/or other
13 * materials provided with the distribution. 3. The name of the author may not
14 * be used to endorse or promote products derived from this software without
15 * specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
20 * NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 package com.versign.tat.dnssec;
32 import java.security.NoSuchAlgorithmException;
35 import org.xbill.DNS.*;
36 import org.xbill.DNS.utils.base32;
38 import com.versign.tat.dnssec.SignUtils.ByteArrayComparator;
40 public class NSEC3ValUtils {
42 // FIXME: should probably refactor to handle different NSEC3 parameters more
44 // Given a list of NSEC3 RRs, they should be grouped according to
45 // parameters. The idea is to hash and compare for each group independently,
46 // instead of having to skip NSEC3 RRs with the wrong parameters.
48 private static Name asterisk_label = Name.fromConstantString("*");
51 * This is a class to encapsulate a unique set of NSEC3 parameters:
52 * algorithm, iterations, and salt.
54 private static class NSEC3Parameters {
57 public int iterations;
59 public NSEC3Parameters(NSEC3Record r) {
60 alg = r.getHashAlgorithm();
62 iterations = r.getIterations();
65 public boolean match(NSEC3Record r, ByteArrayComparator bac) {
66 if (r.getHashAlgorithm() != alg) return false;
67 if (r.getIterations() != iterations) return false;
69 if (salt == null && r.getSalt() != null) return false;
71 if (bac == null) bac = new ByteArrayComparator();
72 return bac.compare(r.getSalt(), salt) == 0;
77 * This is just a simple class to encapsulate the response to a closest
80 private static class CEResponse {
81 public Name closestEncloser;
82 public NSEC3Record ce_nsec3;
83 public NSEC3Record nc_nsec3;
85 public CEResponse(Name ce, NSEC3Record nsec3) {
86 this.closestEncloser = ce;
87 this.ce_nsec3 = nsec3;
91 public static boolean supportsHashAlgorithm(int alg) {
92 if (alg == NSEC3Record.SHA1_DIGEST_ID) return true;
96 public static void stripUnknownAlgNSEC3s(List<NSEC3Record> nsec3s) {
97 if (nsec3s == null) return;
98 for (ListIterator<NSEC3Record> i = nsec3s.listIterator(); i.hasNext();) {
99 NSEC3Record nsec3 = i.next();
100 if (!supportsHashAlgorithm(nsec3.getHashAlgorithm())) {
107 * Given a list of NSEC3Records that are part of a message, determine the
108 * NSEC3 parameters (hash algorithm, iterations, and salt) present. If there
109 * is more than one distinct grouping, return null;
112 * A list of NSEC3Record object.
113 * @return A set containing a number of objects (NSEC3Parameter objects)
114 * that correspond to each distinct set of parameters, or null if
115 * the nsec3s list was empty.
117 public static NSEC3Parameters nsec3Parameters(List<NSEC3Record> nsec3s) {
118 if (nsec3s == null || nsec3s.size() == 0) return null;
120 NSEC3Parameters params = new NSEC3Parameters(
121 (NSEC3Record) nsec3s.get(0));
122 ByteArrayComparator bac = new ByteArrayComparator();
124 for (NSEC3Record nsec3 : nsec3s) {
125 if (!params.match(nsec3, bac)) return null;
133 * Given a hash and an a zone name, construct an NSEC3 ownername.
136 * The hash of an original name.
138 * The zone to use in constructing the NSEC3 name.
139 * @return The NSEC3 name.
141 private static Name hashName(byte[] hash, Name zonename) {
143 return new Name(base32.toString(hash).toLowerCase(), zonename);
144 } catch (TextParseException e) {
145 // Note, this should never happen.
151 * Given a set of NSEC3 parameters, hash a name.
156 * The parameters to hash with.
159 private static byte[] hash(Name name, NSEC3Parameters params) {
161 return NSEC3Record.hash(name, params.alg, params.iterations,
163 } catch (NoSuchAlgorithmException e) {
164 // st_log.debug("Did not recognize hash algorithm: " + params.alg);
170 * Given the name of a closest encloser, return the name *.closest_encloser.
172 * @param closestEncloser
173 * The name to start with.
174 * @return The wildcard name.
176 private static Name ceWildcard(Name closestEncloser) {
178 Name wc = Name.concatenate(asterisk_label, closestEncloser);
180 } catch (NameTooLongException e) {
186 * Given a qname and its proven closest encloser, calculate the "next
187 * closest" name. Basically, this is the name that is one label longer than
188 * the closest encloser that is still a subdomain of qname.
192 * @param closestEncloser
193 * The closest encloser name.
194 * @return The next closer name.
196 private static Name nextClosest(Name qname, Name closestEncloser) {
197 int strip = qname.labels() - closestEncloser.labels() - 1;
198 return (strip > 0) ? new Name(qname, strip) : qname;
202 * Find the NSEC3Record that matches a hash of a name.
205 * The pre-calculated hash of a name.
207 * The name of the zone that the NSEC3s are from.
209 * A list of NSEC3Records from a given message.
211 * The parameters used for calculating the hash.
213 * An already allocated ByteArrayComparator, for reuse. This may
216 * @return The matching NSEC3Record, if one is present.
218 private static NSEC3Record findMatchingNSEC3(byte[] hash, Name zonename,
219 List<NSEC3Record> nsec3s,
220 NSEC3Parameters params,
221 ByteArrayComparator bac) {
222 Name n = hashName(hash, zonename);
224 for (NSEC3Record nsec3 : nsec3s) {
225 // Skip nsec3 records that are using different parameters.
226 if (!params.match(nsec3, bac)) continue;
227 if (n.equals(nsec3.getName())) return nsec3;
233 * Given a hash and a candidate NSEC3Record, determine if that NSEC3Record
234 * covers the hash. Covers specifically means that the hash is in between
235 * the owner and next hashes and does not equal either.
238 * The candidate NSEC3Record.
240 * The precalculated hash.
242 * An already allocated comparator. This may be null.
243 * @return True if the NSEC3Record covers the hash.
245 private static boolean nsec3Covers(NSEC3Record nsec3, byte[] hash,
246 ByteArrayComparator bac) {
247 byte[] owner = nsec3.getOwner();
248 byte[] next = nsec3.getNext();
250 // This is the "normal case: owner < next and owner < hash < next
251 if (bac.compare(owner, hash) < 0 && bac.compare(hash, next) < 0)
254 // this is the end of zone case: next < owner && hash > owner || hash <
256 if (bac.compare(next, owner) <= 0
257 && (bac.compare(hash, next) < 0 || bac.compare(owner, hash) < 0))
260 // Otherwise, the NSEC3 does not cover the hash.
265 * Given a pre-hashed name, find a covering NSEC3 from among a list of
269 * The hash to consider.
271 * The name of the zone.
273 * The list of NSEC3s present in a message.
275 * The NSEC3 parameters used to generate the hash -- NSEC3s that
276 * do not use those parameters will be skipped.
278 * @return A covering NSEC3 if one is present, null otherwise.
280 private static NSEC3Record findCoveringNSEC3(byte[] hash, Name zonename,
281 List<NSEC3Record> nsec3s,
282 NSEC3Parameters params,
283 ByteArrayComparator bac) {
284 ByteArrayComparator comparator = new ByteArrayComparator();
286 for (NSEC3Record nsec3 : nsec3s) {
287 if (!params.match(nsec3, bac)) continue;
288 if (nsec3Covers(nsec3, hash, comparator)) return nsec3;
295 * Given a name and a list of NSEC3s, find the candidate closest encloser.
296 * This will be the first ancestor of 'name' (including itself) to have a
300 * The name the start with.
302 * The name of the zone that the NSEC3s came from.
304 * The list of NSEC3s.
306 * The NSEC3 parameters.
308 * A pre-allocated comparator. May be null.
310 * @return A CEResponse containing the closest encloser name and the NSEC3
311 * RR that matched it, or null if there wasn't one.
313 private static CEResponse findClosestEncloser(Name name, Name zonename,
314 List<NSEC3Record> nsec3s,
315 NSEC3Parameters params,
316 ByteArrayComparator bac) {
321 // This scans from longest name to shortest, so the first match we find
323 // the only viable candidate.
324 // FIXME: modify so that the NSEC3 matching the zone apex need not be
326 while (n.labels() >= zonename.labels()) {
327 nsec3 = findMatchingNSEC3(hash(n, params), zonename, nsec3s,
329 if (nsec3 != null) return new CEResponse(n, nsec3);
337 * Given a List of nsec3 RRs, find and prove the closest encloser to qname.
340 * The qname in question.
342 * The name of the zone that the NSEC3 RRs come from.
344 * The list of NSEC3s found the this response (already verified).
346 * The NSEC3 parameters found in the response.
348 * A pre-allocated comparator. May be null.
349 * @param proveDoesNotExist
350 * If true, then if the closest encloser turns out to be qname,
351 * then null is returned.
352 * @return null if the proof isn't completed. Otherwise, return a CEResponse
353 * object which contains the closest encloser name and the NSEC3
356 private static CEResponse proveClosestEncloser(Name qname, Name zonename,
357 List<NSEC3Record> nsec3s,
358 NSEC3Parameters params,
359 ByteArrayComparator bac,
360 boolean proveDoesNotExist) {
361 CEResponse candidate = findClosestEncloser(qname, zonename, nsec3s,
364 if (candidate == null) {
365 // st_log.debug("proveClosestEncloser: could not find a "
366 // + "candidate for the closest encloser.");
370 if (candidate.closestEncloser.equals(qname)) {
371 if (proveDoesNotExist) {
372 // st_log.debug("proveClosestEncloser: proved that qname existed!");
375 // otherwise, we need to nothing else to prove that qname is its own
380 // If the closest encloser is actually a delegation, then the response
381 // should have been a referral. If it is a DNAME, then it should have
384 if (candidate.ce_nsec3.hasType(Type.NS)
385 && !candidate.ce_nsec3.hasType(Type.SOA)) {
386 // st_log.debug("proveClosestEncloser: closest encloser "
387 // + "was a delegation!");
390 if (candidate.ce_nsec3.hasType(Type.DNAME)) {
391 // st_log.debug("proveClosestEncloser: closest encloser was a DNAME!");
395 // Otherwise, we need to show that the next closer name is covered.
396 Name nextClosest = nextClosest(qname, candidate.closestEncloser);
398 byte[] nc_hash = hash(nextClosest, params);
399 candidate.nc_nsec3 = findCoveringNSEC3(nc_hash, zonename, nsec3s,
401 if (candidate.nc_nsec3 == null) {
402 // st_log.debug("Could not find proof that the "
403 // + "closest encloser was the closest encloser");
410 private static int maxIterations(int baseAlg, int keysize) {
412 case DnsSecVerifier.RSA:
413 if (keysize == 0) return 2500; // the max at 4096
414 if (keysize > 2048) return 2500;
415 if (keysize > 1024) return 500;
416 if (keysize > 0) return 150;
418 case DnsSecVerifier.DSA:
419 if (keysize == 0) return 5000; // the max at 2048;
420 if (keysize > 1024) return 5000;
421 if (keysize > 0) return 1500;
427 @SuppressWarnings("unchecked")
428 private static boolean validIterations(NSEC3Parameters nsec3params,
430 DnsSecVerifier verifier) {
431 // for now, we return the maximum iterations based simply on the key
432 // algorithms that may have been used to sign the NSEC3 RRsets.
434 int max_iterations = 0;
435 for (Iterator i = dnskey_rrset.rrs(); i.hasNext();) {
436 DNSKEYRecord dnskey = (DNSKEYRecord) i.next();
437 int baseAlg = verifier.baseAlgorithm(dnskey.getAlgorithm());
438 int iters = maxIterations(baseAlg, 0);
439 max_iterations = max_iterations < iters ? iters : max_iterations;
442 if (nsec3params.iterations > max_iterations) return false;
448 * Determine if all of the NSEC3s in a response are legally ignoreable
449 * (i.e., their presence should lead to an INSECURE result). Currently, this
450 * is solely based on iterations.
453 * The list of NSEC3s. If there is more than one set of NSEC3
454 * parameters present, this test will not be performed.
455 * @param dnskey_rrset
456 * The set of validating DNSKEYs.
458 * The verifier used to verify the NSEC3 RRsets. This is solely
459 * used to map algorithm aliases.
460 * @return true if all of the NSEC3s can be legally ignored, false if not.
462 public static boolean allNSEC3sIgnoreable(List<NSEC3Record> nsec3s,
464 DnsSecVerifier verifier) {
465 NSEC3Parameters params = nsec3Parameters(nsec3s);
466 if (params == null) return false;
468 return !validIterations(params, dnskey_rrset, verifier);
472 * Determine if the set of NSEC3 records provided with a response prove NAME
473 * ERROR. This means that the NSEC3s prove a) the closest encloser exists,
474 * b) the direct child of the closest encloser towards qname doesn't exist,
475 * and c) *.closest encloser does not exist.
478 * The list of NSEC3s.
480 * The query name to check against.
482 * This is the name of the zone that the NSEC3s belong to. This
483 * may be discovered in any number of ways. A good one is to use
484 * the signerName from the NSEC3 record's RRSIG.
485 * @return SecurityStatus.SECURE of the Name Error is proven by the NSEC3
486 * RRs, BOGUS if not, INSECURE if all of the NSEC3s could be validly
489 public static boolean proveNameError(List<NSEC3Record> nsec3s, Name qname,
491 if (nsec3s == null || nsec3s.size() == 0) return false;
493 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
494 if (nsec3params == null) {
495 // st_log.debug("Could not find a single set of " +
496 // "NSEC3 parameters (multiple parameters present).");
500 ByteArrayComparator bac = new ByteArrayComparator();
502 // First locate and prove the closest encloser to qname. We will use the
503 // variant that fails if the closest encloser turns out to be qname.
504 CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
505 nsec3params, bac, true);
508 // st_log.debug("proveNameError: failed to prove a closest encloser.");
512 // At this point, we know that qname does not exist. Now we need to
514 // that the wildcard does not exist.
515 Name wc = ceWildcard(ce.closestEncloser);
516 byte[] wc_hash = hash(wc, nsec3params);
517 NSEC3Record nsec3 = findCoveringNSEC3(wc_hash, zonename, nsec3s,
520 // st_log.debug("proveNameError: could not prove that the "
521 // + "applicable wildcard did not exist.");
530 * Determine if the NSEC3s provided in a response prove the NOERROR/NODATA
531 * status. There are a number of different variants to this:
533 * 1) Normal NODATA -- qname is matched to an NSEC3 record, type is not
536 * 2) ENT NODATA -- because there must be NSEC3 record for
537 * empty-non-terminals, this is the same as #1.
539 * 3) NSEC3 ownername NODATA -- qname matched an existing, lone NSEC3
540 * ownername, but qtype was not NSEC3. NOTE: as of nsec-05, this case no
543 * 4) Wildcard NODATA -- A wildcard matched the name, but not the type.
545 * 5) Opt-In DS NODATA -- the qname is covered by an opt-in span and qtype
546 * == DS. (or maybe some future record with the same parent-side-only
550 * The NSEC3Records to consider.
552 * The qname in question.
554 * The qtype in question.
556 * The name of the zone that the NSEC3s came from.
557 * @return true if the NSEC3s prove the proposition.
559 public static boolean proveNodata(List<NSEC3Record> nsec3s, Name qname,
560 int qtype, Name zonename) {
561 if (nsec3s == null || nsec3s.size() == 0) return false;
563 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
564 if (nsec3params == null) {
565 // st_log.debug("could not find a single set of "
566 // + "NSEC3 parameters (multiple parameters present)");
569 ByteArrayComparator bac = new ByteArrayComparator();
571 NSEC3Record nsec3 = findMatchingNSEC3(hash(qname, nsec3params),
572 zonename, nsec3s, nsec3params,
576 if (nsec3.hasType(qtype)) {
577 // st_log.debug("proveNodata: Matching NSEC3 proved that type existed!");
580 if (nsec3.hasType(Type.CNAME)) {
581 // st_log.debug("proveNodata: Matching NSEC3 proved "
582 // + "that a CNAME existed!");
588 // For cases 3 - 5, we need the proven closest encloser, and it can't
589 // match qname. Although, at this point, we know that it won't since we
590 // just checked that.
591 CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
592 nsec3params, bac, true);
594 // At this point, not finding a match or a proven closest encloser is a
597 // st_log.debug("proveNodata: did not match qname, "
598 // + "nor found a proven closest encloser.");
605 Name wc = ceWildcard(ce.closestEncloser);
606 nsec3 = findMatchingNSEC3(hash(wc, nsec3params), zonename, nsec3s,
610 if (nsec3.hasType(qtype)) {
611 // st_log.debug("proveNodata: matching wildcard had qtype!");
618 if (qtype != Type.DS) {
619 // st_log.debug("proveNodata: could not find matching NSEC3, "
621 // "nor matching wildcard, and qtype is not DS -- no more options.");
625 // We need to make sure that the covering NSEC3 is opt-in.
626 if (!ce.nc_nsec3.getOptInFlag()) {
627 // st_log.debug("proveNodata: covering NSEC3 was not "
628 // + "opt-in in an opt-in DS NOERROR/NODATA case.");
636 * Prove that a positive wildcard match was appropriate (no direct match
640 * The NSEC3 records to work with.
642 * The qname that was matched to the wildcard
644 * The name of the zone that the NSEC3s come from.
646 * The purported wildcard that matched.
647 * @return true if the NSEC3 records prove this case.
649 public static boolean proveWildcard(List<NSEC3Record> nsec3s, Name qname,
650 Name zonename, Name wildcard) {
651 if (nsec3s == null || nsec3s.size() == 0) return false;
652 if (qname == null || wildcard == null) return false;
654 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
655 if (nsec3params == null) {
656 // st_log.debug("couldn't find a single set of NSEC3 parameters (multiple parameters present).");
660 ByteArrayComparator bac = new ByteArrayComparator();
662 // We know what the (purported) closest encloser is by just looking at
664 // supposed generating wildcard.
665 CEResponse candidate = new CEResponse(new Name(wildcard, 1), null);
667 // Now we still need to prove that the original data did not exist.
668 // Otherwise, we need to show that the next closer name is covered.
669 Name nextClosest = nextClosest(qname, candidate.closestEncloser);
670 candidate.nc_nsec3 = findCoveringNSEC3(hash(nextClosest, nsec3params),
671 zonename, nsec3s, nsec3params,
674 if (candidate.nc_nsec3 == null) {
675 // st_log.debug("proveWildcard: did not find a covering NSEC3 "
676 // + "that covered the next closer name to " + qname + " from "
677 // + candidate.closestEncloser + " (derived from wildcard " +
687 * Prove that a DS response either had no DS, or wasn't a delegation point.
689 * Fundamentally there are two cases here: normal NODATA and Opt-In NODATA.
692 * The NSEC3 RRs to examine.
694 * The name of the DS in question.
696 * The name of the zone that the NSEC3 RRs come from.
698 * @return SecurityStatus.SECURE if it was proven that there is no DS in a
699 * secure (i.e., not opt-in) way, SecurityStatus.INSECURE if there
700 * was no DS in an insecure (i.e., opt-in) way,
701 * SecurityStatus.INDETERMINATE if it was clear that this wasn't a
702 * delegation point, and SecurityStatus.BOGUS if the proofs don't
705 public static int proveNoDS(List<NSEC3Record> nsec3s, Name qname,
707 if (nsec3s == null || nsec3s.size() == 0) return SecurityStatus.BOGUS;
709 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
710 if (nsec3params == null) {
711 // st_log.debug("couldn't find a single set of " +
712 // "NSEC3 parameters (multiple parameters present).");
713 return SecurityStatus.BOGUS;
715 ByteArrayComparator bac = new ByteArrayComparator();
717 // Look for a matching NSEC3 to qname -- this is the normal NODATA case.
718 NSEC3Record nsec3 = findMatchingNSEC3(hash(qname, nsec3params),
719 zonename, nsec3s, nsec3params,
723 // If the matching NSEC3 has the SOA bit set, it is from the wrong
725 // (the child instead of the parent). If it has the DS bit set, then
728 if (nsec3.hasType(Type.SOA) || nsec3.hasType(Type.DS)) {
729 return SecurityStatus.BOGUS;
731 // If the NSEC3 RR doesn't have the NS bit set, then this wasn't a
733 if (!nsec3.hasType(Type.NS)) return SecurityStatus.INDETERMINATE;
735 // Otherwise, this proves no DS.
736 return SecurityStatus.SECURE;
739 // Otherwise, we are probably in the opt-in case.
740 CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
741 nsec3params, bac, true);
743 return SecurityStatus.BOGUS;
746 // If we had the closest encloser proof, then we need to check that the
747 // covering NSEC3 was opt-in -- the proveClosestEncloser step already
748 // checked to see if the closest encloser was a delegation or DNAME.
749 if (ce.nc_nsec3.getOptInFlag()) {
750 return SecurityStatus.SECURE;
753 return SecurityStatus.BOGUS;