1 /***************************** -*- Java -*- ********************************\
3 * Copyright (c) 2009 VeriSign, Inc. All rights reserved. *
5 * This software is provided solely in connection with the terms of the *
6 * license agreement. Any other use without the prior express written *
7 * permission of VeriSign is completely prohibited. The software and *
8 * documentation are "Commercial Items", as that term is defined in 48 *
9 * C.F.R. section 2.101, consisting of "Commercial Computer Software" and *
10 * "Commercial Computer Software Documentation" as such terms are defined *
11 * in 48 C.F.R. section 252.227-7014(a)(5) and 48 C.F.R. section *
12 * 252.227-7014(a)(1), and used in 48 C.F.R. section 12.212 and 48 C.F.R. *
13 * section 227.7202, as applicable. Pursuant to the above and other *
14 * relevant sections of the Code of Federal Regulations, as applicable, *
15 * VeriSign's publications, commercial computer software, and commercial *
16 * computer software documentation are distributed and licensed to United *
17 * States Government end users with only those rights as granted to all *
18 * other end users, according to the terms and conditions contained in the *
19 * license agreement(s) that accompany the products and software *
22 \***************************************************************************/
24 package com.verisign.tat.dnssec;
26 import com.verisign.tat.dnssec.SignUtils.ByteArrayComparator;
28 import org.apache.log4j.Logger;
30 import org.xbill.DNS.*;
31 import org.xbill.DNS.utils.base32;
33 import java.security.NoSuchAlgorithmException;
37 public class NSEC3ValUtils {
38 // FIXME: should probably refactor to handle different NSEC3 parameters more
40 // Given a list of NSEC3 RRs, they should be grouped according to
41 // parameters. The idea is to hash and compare for each group independently,
42 // instead of having to skip NSEC3 RRs with the wrong parameters.
43 private static Name asterisk_label = Name.fromConstantString("*");
44 private static Logger st_log = Logger.getLogger(NSEC3ValUtils.class);
45 private static final base32 b32 = new base32(base32.Alphabet.BASE32HEX,
48 public static boolean supportsHashAlgorithm(int alg) {
49 if (alg == NSEC3Record.SHA1_DIGEST_ID) {
56 public static void stripUnknownAlgNSEC3s(List<NSEC3Record> nsec3s) {
61 for (ListIterator<NSEC3Record> i = nsec3s.listIterator(); i.hasNext();) {
62 NSEC3Record nsec3 = i.next();
64 if (!supportsHashAlgorithm(nsec3.getHashAlgorithm())) {
70 public static boolean isOptOut(NSEC3Record nsec3) {
71 return (nsec3.getFlags() & NSEC3Record.Flags.OPT_OUT) == NSEC3Record.Flags.OPT_OUT;
75 * Given a list of NSEC3Records that are part of a message, determine the
76 * NSEC3 parameters (hash algorithm, iterations, and salt) present. If there
77 * is more than one distinct grouping, return null;
80 * A list of NSEC3Record object.
81 * @return A set containing a number of objects (NSEC3Parameter objects)
82 * that correspond to each distinct set of parameters, or null if
83 * the nsec3s list was empty.
85 public static NSEC3Parameters nsec3Parameters(List<NSEC3Record> nsec3s) {
86 if ((nsec3s == null) || (nsec3s.size() == 0)) {
90 NSEC3Parameters params = new NSEC3Parameters((NSEC3Record) nsec3s
92 ByteArrayComparator bac = new ByteArrayComparator();
94 for (NSEC3Record nsec3 : nsec3s) {
95 if (!params.match(nsec3, bac)) {
104 * Given a hash and an a zone name, construct an NSEC3 ownername.
107 * The hash of an original name.
109 * The zone to use in constructing the NSEC3 name.
110 * @return The NSEC3 name.
112 private static Name hashName(byte[] hash, Name zonename) {
114 return new Name(b32.toString(hash).toLowerCase(), zonename);
115 } catch (TextParseException e) {
116 // Note, this should never happen.
122 * Given a set of NSEC3 parameters, hash a name.
127 * The parameters to hash with.
130 private static byte[] hash(Name name, NSEC3Parameters params) {
132 return params.hash(name);
133 } catch (NoSuchAlgorithmException e) {
134 st_log.warn("Did not recognize hash algorithm: " + params.alg);
140 private static byte[] hash(Name name, NSEC3Record nsec3) {
142 return nsec3.hashName(name);
143 } catch (NoSuchAlgorithmException e) {
144 st_log.warn("Did not recognize hash algorithm: "
145 + nsec3.getHashAlgorithm());
152 * Given the name of a closest encloser, return the name *.closest_encloser.
154 * @param closestEncloser
155 * The name to start with.
156 * @return The wildcard name.
158 private static Name ceWildcard(Name closestEncloser) {
160 Name wc = Name.concatenate(asterisk_label, closestEncloser);
163 } catch (NameTooLongException e) {
169 * Given a qname and its proven closest encloser, calculate the "next
170 * closest" name. Basically, this is the name that is one label longer than
171 * the closest encloser that is still a subdomain of qname.
175 * @param closestEncloser
176 * The closest encloser name.
177 * @return The next closer name.
179 private static Name nextClosest(Name qname, Name closestEncloser) {
180 int strip = qname.labels() - closestEncloser.labels() - 1;
182 return (strip > 0) ? new Name(qname, strip) : qname;
186 * Find the NSEC3Record that matches a hash of a name.
189 * The pre-calculated hash of a name.
191 * The name of the zone that the NSEC3s are from.
193 * A list of NSEC3Records from a given message.
195 * The parameters used for calculating the hash.
197 * An already allocated ByteArrayComparator, for reuse. This may
200 * @return The matching NSEC3Record, if one is present.
202 private static NSEC3Record findMatchingNSEC3(byte[] hash, Name zonename,
203 List<NSEC3Record> nsec3s, NSEC3Parameters params,
204 ByteArrayComparator bac) {
205 Name n = hashName(hash, zonename);
207 for (NSEC3Record nsec3 : nsec3s) {
208 // Skip nsec3 records that are using different parameters.
209 if (!params.match(nsec3, bac)) {
213 if (n.equals(nsec3.getName())) {
222 * Given a hash and a candidate NSEC3Record, determine if that NSEC3Record
223 * covers the hash. Covers specifically means that the hash is in between
224 * the owner and next hashes and does not equal either.
227 * The candidate NSEC3Record.
229 * The precalculated hash.
231 * An already allocated comparator. This may be null.
232 * @return True if the NSEC3Record covers the hash.
234 private static boolean nsec3Covers(NSEC3Record nsec3, byte [] hash,
235 ByteArrayComparator bac) {
236 Name ownerName = nsec3.getName();
237 byte [] owner = b32.fromString(ownerName.getLabelString(0));
238 byte [] next = nsec3.getNext();
240 // This is the "normal case: owner < next and owner < hash < next
241 if ((bac.compare(owner, hash) < 0) && (bac.compare(hash, next) < 0)) {
244 // this is the end of zone case: next < owner && hash > owner || hash <
246 if ((bac.compare(next, owner) <= 0)
247 && ((bac.compare(hash, next) < 0) || (bac.compare(owner, hash) < 0))) {
251 // Otherwise, the NSEC3 does not cover the hash.
256 * Given a pre-hashed name, find a covering NSEC3 from among a list of
260 * The hash to consider.
262 * The name of the zone.
264 * The list of NSEC3s present in a message.
266 * The NSEC3 parameters used to generate the hash -- NSEC3s that
267 * do not use those parameters will be skipped.
269 * @return A covering NSEC3 if one is present, null otherwise.
271 private static NSEC3Record findCoveringNSEC3(byte[] hash, Name zonename,
272 List<NSEC3Record> nsec3s, NSEC3Parameters params,
273 ByteArrayComparator bac) {
274 ByteArrayComparator comparator = new ByteArrayComparator();
276 for (NSEC3Record nsec3 : nsec3s) {
277 if (!params.match(nsec3, bac)) {
281 if (nsec3Covers(nsec3, hash, comparator)) {
290 * Given a name and a list of NSEC3s, find the candidate closest encloser.
291 * This will be the first ancestor of 'name' (including itself) to have a
295 * The name the start with.
297 * The name of the zone that the NSEC3s came from.
299 * The list of NSEC3s.
301 * The NSEC3 parameters.
303 * A pre-allocated comparator. May be null.
305 * @return A CEResponse containing the closest encloser name and the NSEC3
306 * RR that matched it, or null if there wasn't one.
308 private static CEResponse findClosestEncloser(Name name, Name zonename,
309 List<NSEC3Record> nsec3s, NSEC3Parameters params,
310 ByteArrayComparator bac) {
315 // This scans from longest name to shortest, so the first match we find
316 // is the only viable candidate.
317 // FIXME: modify so that the NSEC3 matching the zone apex need not be
319 while (n.labels() >= zonename.labels()) {
320 nsec3 = findMatchingNSEC3(hash(n, params), zonename,
321 nsec3s, params, bac);
324 return new CEResponse(n, nsec3);
334 * Given a List of nsec3 RRs, find and prove the closest encloser to qname.
337 * The qname in question.
339 * The name of the zone that the NSEC3 RRs come from.
341 * The list of NSEC3s found the this response (already verified).
343 * The NSEC3 parameters found in the response.
345 * A pre-allocated comparator. May be null.
346 * @param proveDoesNotExist
347 * If true, then if the closest encloser turns out to be qname,
348 * then null is returned.
349 * @return null if the proof isn't completed. Otherwise, return a CEResponse
350 * object which contains the closest encloser name and the NSEC3
353 private static CEResponse proveClosestEncloser(Name qname, Name zonename,
354 List<NSEC3Record> nsec3s, NSEC3Parameters params,
355 ByteArrayComparator bac, boolean proveDoesNotExist, List<String> errorList) {
356 CEResponse candidate = findClosestEncloser(qname, zonename, nsec3s,
359 if (candidate == null) {
360 errorList.add("Could not find a candidate for the closest encloser");
361 st_log.debug("proveClosestEncloser: could not find a " +
362 "candidate for the closest encloser.");
367 if (candidate.closestEncloser.equals(qname)) {
368 if (proveDoesNotExist) {
369 errorList.add("Proven closest encloser proved that the qname existed and should not have");
370 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 errorList.add("Proven closest encloser was a delegation");
387 st_log.debug("proveClosestEncloser: closest encloser " +
388 "was a delegation!");
393 if (candidate.ce_nsec3.hasType(Type.DNAME)) {
394 errorList.add("Proven closest encloser was a DNAME");
395 st_log.debug("proveClosestEncloser: closest encloser was a DNAME!");
400 // Otherwise, we need to show that the next closer name is covered.
401 Name nextClosest = nextClosest(qname, candidate.closestEncloser);
403 byte[] nc_hash = hash(nextClosest, params);
404 candidate.nc_nsec3 = findCoveringNSEC3(nc_hash, zonename, nsec3s,
407 if (candidate.nc_nsec3 == null) {
408 errorList.add("Could not find proof that the closest encloser was the closest encloser");
409 errorList.add("hash " + hashName(nc_hash, zonename) + " is not covered by any NSEC3 RRs");
410 st_log.debug("Could not find proof that the " +
411 "closest encloser was the closest encloser");
419 private static int maxIterations(int baseAlg, int keysize) {
421 case DnsSecVerifier.RSA:
424 return 2500; // the max at 4096
427 if (keysize > 2048) {
431 if (keysize > 1024) {
441 case DnsSecVerifier.DSA:
444 return 5000; // the max at 2048;
447 if (keysize > 1024) {
461 @SuppressWarnings("unchecked")
462 private static boolean validIterations(NSEC3Parameters nsec3params,
463 RRset dnskey_rrset, DnsSecVerifier verifier) {
464 // for now, we return the maximum iterations based simply on the key
465 // algorithms that may have been used to sign the NSEC3 RRsets.
466 int max_iterations = 0;
468 for (Iterator i = dnskey_rrset.rrs(); i.hasNext();) {
469 DNSKEYRecord dnskey = (DNSKEYRecord) i.next();
470 int baseAlg = verifier.baseAlgorithm(dnskey.getAlgorithm());
471 int iters = maxIterations(baseAlg, 0);
472 max_iterations = (max_iterations < iters) ? iters : max_iterations;
475 if (nsec3params.iterations > max_iterations) {
483 * Determine if all of the NSEC3s in a response are legally ignoreable
484 * (i.e., their presence should lead to an INSECURE result). Currently, this
485 * is solely based on iterations.
488 * The list of NSEC3s. If there is more than one set of NSEC3
489 * parameters present, this test will not be performed.
490 * @param dnskey_rrset
491 * The set of validating DNSKEYs.
493 * The verifier used to verify the NSEC3 RRsets. This is solely
494 * used to map algorithm aliases.
495 * @return true if all of the NSEC3s can be legally ignored, false if not.
497 public static boolean allNSEC3sIgnoreable(List<NSEC3Record> nsec3s,
498 RRset dnskey_rrset, DnsSecVerifier verifier) {
499 NSEC3Parameters params = nsec3Parameters(nsec3s);
501 if (params == null) {
505 return !validIterations(params, dnskey_rrset, verifier);
509 * Determine if the set of NSEC3 records provided with a response prove NAME
510 * ERROR. This means that the NSEC3s prove a) the closest encloser exists,
511 * b) the direct child of the closest encloser towards qname doesn't exist,
512 * and c) *.closest encloser does not exist.
515 * The list of NSEC3s.
517 * The query name to check against.
519 * This is the name of the zone that the NSEC3s belong to. This
520 * may be discovered in any number of ways. A good one is to use
521 * the signerName from the NSEC3 record's RRSIG.
522 * @return SecurityStatus.SECURE of the Name Error is proven by the NSEC3
523 * RRs, BOGUS if not, INSECURE if all of the NSEC3s could be validly
526 public static boolean proveNameError(List<NSEC3Record> nsec3s, Name qname,
527 Name zonename, List<String> errorList) {
528 if ((nsec3s == null) || (nsec3s.size() == 0)) {
532 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
534 if (nsec3params == null) {
535 errorList.add("Could not find a single set of NSEC3 parameters (multiple parameters present");
536 st_log.debug("Could not find a single set of " +
537 "NSEC3 parameters (multiple parameters present).");
542 ByteArrayComparator bac = new ByteArrayComparator();
544 // First locate and prove the closest encloser to qname. We will use the
545 // variant that fails if the closest encloser turns out to be qname.
546 CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
547 nsec3params, bac, true, errorList);
550 errorList.add("Failed to find the closest encloser as part of the NSEC3 proof");
551 st_log.debug("proveNameError: failed to prove a closest encloser.");
556 // At this point, we know that qname does not exist. Now we need to
558 // that the wildcard does not exist.
559 Name wc = ceWildcard(ce.closestEncloser);
560 byte[] wc_hash = hash(wc, nsec3params);
561 NSEC3Record nsec3 = findCoveringNSEC3(wc_hash, zonename, nsec3s,
565 errorList.add("Failed to prove that the applicable wildcard did not exist");
566 st_log.debug("proveNameError: could not prove that the " +
567 "applicable wildcard did not exist.");
576 * Determine if the NSEC3s provided in a response prove the NOERROR/NODATA
577 * status. There are a number of different variants to this:
579 * 1) Normal NODATA -- qname is matched to an NSEC3 record, type is not
582 * 2) ENT NODATA -- because there must be NSEC3 record for
583 * empty-non-terminals, this is the same as #1.
585 * 3) NSEC3 ownername NODATA -- qname matched an existing, lone NSEC3
586 * ownername, but qtype was not NSEC3. NOTE: as of nsec-05, this case no
589 * 4) Wildcard NODATA -- A wildcard matched the name, but not the type.
591 * 5) Opt-In DS NODATA -- the qname is covered by an opt-in span and qtype
592 * == DS. (or maybe some future record with the same parent-side-only
596 * The NSEC3Records to consider.
598 * The qname in question.
600 * The qtype in question.
602 * The name of the zone that the NSEC3s came from.
603 * @return true if the NSEC3s prove the proposition.
605 public static boolean proveNodata(List<NSEC3Record> nsec3s, Name qname,
606 int qtype, Name zonename, List<String> errorList) {
607 if ((nsec3s == null) || (nsec3s.size() == 0)) {
611 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
613 if (nsec3params == null) {
614 st_log.debug("could not find a single set of "
615 + "NSEC3 parameters (multiple parameters present)");
620 ByteArrayComparator bac = new ByteArrayComparator();
622 NSEC3Record nsec3 = findMatchingNSEC3(hash(qname, nsec3params),
623 zonename, nsec3s, nsec3params, bac);
627 if (nsec3.hasType(qtype)) {
629 .debug("proveNodata: Matching NSEC3 proved that type existed!");
634 if (nsec3.hasType(Type.CNAME)) {
635 st_log.debug("proveNodata: Matching NSEC3 proved "
636 + "that a CNAME existed!");
644 // For cases 3 - 5, we need the proven closest encloser, and it can't
645 // match qname. Although, at this point, we know that it won't since we
646 // just checked that.
647 CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
648 nsec3params, bac, true, errorList);
650 // At this point, not finding a match or a proven closest encloser is a
653 st_log.debug("proveNodata: did not match qname, "
654 + "nor found a proven closest encloser.");
662 Name wc = ceWildcard(ce.closestEncloser);
663 nsec3 = findMatchingNSEC3(hash(wc, nsec3params), zonename, nsec3s,
667 if (nsec3.hasType(qtype)) {
668 st_log.debug("proveNodata: matching wildcard had qtype!");
677 if (qtype != Type.DS) {
679 .debug("proveNodata: could not find matching NSEC3, "
680 + "nor matching wildcard, and qtype is not DS -- no more options.");
685 // We need to make sure that the covering NSEC3 is opt-in.
686 if (!isOptOut(ce.nc_nsec3)) {
687 st_log.debug("proveNodata: covering NSEC3 was not "
688 + "opt-in in an opt-in DS NOERROR/NODATA case.");
697 * Prove that a positive wildcard match was appropriate (no direct match
701 * The NSEC3 records to work with.
703 * The qname that was matched to the wildcard
705 * The name of the zone that the NSEC3s come from.
707 * The purported wildcard that matched.
708 * @return true if the NSEC3 records prove this case.
710 public static boolean proveWildcard(List<NSEC3Record> nsec3s, Name qname,
711 Name zonename, Name wildcard, List<String> errorList) {
712 if ((nsec3s == null) || (nsec3s.size() == 0)) {
716 if ((qname == null) || (wildcard == null)) {
720 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
722 if (nsec3params == null) {
723 errorList.add("Could not find a single set of NSEC3 parameters (multiple parameters present)");
725 "couldn't find a single set of NSEC3 parameters (multiple parameters present).");
730 ByteArrayComparator bac = new ByteArrayComparator();
732 // We know what the (purported) closest encloser is by just looking at
734 // supposed generating wildcard.
735 CEResponse candidate = new CEResponse(new Name(wildcard, 1), null);
737 // Now we still need to prove that the original data did not exist.
738 // Otherwise, we need to show that the next closer name is covered.
739 Name nextClosest = nextClosest(qname, candidate.closestEncloser);
740 candidate.nc_nsec3 = findCoveringNSEC3(hash(nextClosest, nsec3params),
741 zonename, nsec3s, nsec3params, bac);
743 if (candidate.nc_nsec3 == null) {
744 errorList.add("Did not find a NSEC3 that covered the next closer name to '" +
745 qname + "' from '" + candidate.closestEncloser + "' (derived from the wildcard: " +
747 st_log.debug("proveWildcard: did not find a covering NSEC3 " +
748 "that covered the next closer name to " + qname + " from " +
749 candidate.closestEncloser + " (derived from wildcard " +
759 * Prove that a DS response either had no DS, or wasn't a delegation point.
761 * Fundamentally there are two cases here: normal NODATA and Opt-In NODATA.
764 * The NSEC3 RRs to examine.
766 * The name of the DS in question.
768 * The name of the zone that the NSEC3 RRs come from.
770 * @return SecurityStatus.SECURE if it was proven that there is no DS in a
771 * secure (i.e., not opt-in) way, SecurityStatus.INSECURE if there
772 * was no DS in an insecure (i.e., opt-in) way,
773 * SecurityStatus.INDETERMINATE if it was clear that this wasn't a
774 * delegation point, and SecurityStatus.BOGUS if the proofs don't
777 public static byte proveNoDS(List<NSEC3Record> nsec3s, Name qname,
778 Name zonename, List<String> errorList) {
779 if ((nsec3s == null) || (nsec3s.size() == 0)) {
780 return SecurityStatus.BOGUS;
783 NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
785 if (nsec3params == null) {
786 errorList.add("Could not find a single set of NSEC3 parameters (multiple parameters present)");
787 st_log.debug("couldn't find a single set of " +
788 "NSEC3 parameters (multiple parameters present).");
790 return SecurityStatus.BOGUS;
793 ByteArrayComparator bac = new ByteArrayComparator();
795 // Look for a matching NSEC3 to qname -- this is the normal NODATA case.
796 NSEC3Record nsec3 = findMatchingNSEC3(hash(qname, nsec3params),
797 zonename, nsec3s, nsec3params, bac);
800 // If the matching NSEC3 has the SOA bit set, it is from the wrong
801 // zone (the child instead of the parent). If it has the DS bit set,
802 // then we were lied to.
803 if (nsec3.hasType(Type.SOA) || nsec3.hasType(Type.DS)) {
804 errorList.add("Matching NSEC3 is incorrectly from the child instead of the parent (SOA or DS bit set)");
805 return SecurityStatus.BOGUS;
808 // If the NSEC3 RR doesn't have the NS bit set, then this wasn't a
810 if (!nsec3.hasType(Type.NS)) {
811 return SecurityStatus.INDETERMINATE;
814 // Otherwise, this proves no DS.
815 return SecurityStatus.SECURE;
818 // Otherwise, we are probably in the opt-in case.
819 CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
820 nsec3params, bac, true, errorList);
823 errorList.add("Failed to prove the closest encloser as part of a 'No DS' proof");
824 return SecurityStatus.BOGUS;
827 // If we had the closest encloser proof, then we need to check that the
828 // covering NSEC3 was opt-in -- the proveClosestEncloser step already
829 // checked to see if the closest encloser was a delegation or DNAME.
830 if (isOptOut(ce.nc_nsec3)) {
831 return SecurityStatus.SECURE;
834 errorList.add("Failed to find a covering NSEC3 for 'No DS' proof");
835 return SecurityStatus.BOGUS;
839 * This is a class to encapsulate a unique set of NSEC3 parameters:
840 * algorithm, iterations, and salt.
842 private static class NSEC3Parameters {
845 public int iterations;
846 private NSEC3PARAMRecord nsec3paramrec;
848 public NSEC3Parameters(NSEC3Record r) {
849 alg = r.getHashAlgorithm();
851 iterations = r.getIterations();
853 nsec3paramrec = new NSEC3PARAMRecord(Name.root, DClass.IN, 0, alg,
854 0, iterations, salt);
857 public boolean match(NSEC3Record r, ByteArrayComparator bac) {
858 if (r.getHashAlgorithm() != alg) {
862 if (r.getIterations() != iterations) {
866 if ((salt == null) && (r.getSalt() != null)) {
875 bac = new ByteArrayComparator();
878 return bac.compare(r.getSalt(), salt) == 0;
881 public byte[] hash(Name name) throws NoSuchAlgorithmException {
882 return nsec3paramrec.hashName(name);
887 * This is just a simple class to encapsulate the response to a closest
890 private static class CEResponse {
891 public Name closestEncloser;
892 public NSEC3Record ce_nsec3;
893 public NSEC3Record nc_nsec3;
895 public CEResponse(Name ce, NSEC3Record nsec3) {
896 this.closestEncloser = ce;
897 this.ce_nsec3 = nsec3;