src/com/verisign/tat/dnssec/NSEC3ValUtils.java

   1 /***************************** -*- Java -*- ********************************\
   2  *                                                                         *
   3  *   Copyright (c) 2009 VeriSign, Inc. All rights reserved.                *
   4  *                                                                         *
   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           *
  20  * documentation.                                                          *
  21  *                                                                         *
  22 \***************************************************************************/
  23
  24 package com.verisign.tat.dnssec;
  25
  26 import com.verisign.tat.dnssec.SignUtils.ByteArrayComparator;
  27
  28 import org.apache.log4j.Logger;
  29
  30 import org.xbill.DNS.*;
  31 import org.xbill.DNS.utils.base32;
  32
  33 import java.security.NoSuchAlgorithmException;
  34
  35 import java.util.*;
  36
  37 public class NSEC3ValUtils {
  38     // FIXME: should probably refactor to handle different NSEC3 parameters more
  39     // efficiently.
  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,
  46             false, false);
  47
  48     public static boolean supportsHashAlgorithm(int alg) {
  49         if (alg == NSEC3Record.SHA1_DIGEST_ID) {
  50             return true;
  51         }
  52
  53         return false;
  54     }
  55
  56     public static void stripUnknownAlgNSEC3s(List<NSEC3Record> nsec3s) {
  57         if (nsec3s == null) {
  58             return;
  59         }
  60
  61         for (ListIterator<NSEC3Record> i = nsec3s.listIterator(); i.hasNext();) {
  62             NSEC3Record nsec3 = i.next();
  63
  64             if (!supportsHashAlgorithm(nsec3.getHashAlgorithm())) {
  65                 i.remove();
  66             }
  67         }
  68     }
  69
  70     public static boolean isOptOut(NSEC3Record nsec3) {
  71         return (nsec3.getFlags() & NSEC3Record.Flags.OPT_OUT) == NSEC3Record.Flags.OPT_OUT;
  72     }
  73
  74     /**
  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;
  78      *
  79      * @param nsec3s
  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.
  84      */
  85     public static NSEC3Parameters nsec3Parameters(List<NSEC3Record> nsec3s) {
  86         if ((nsec3s == null) || (nsec3s.size() == 0)) {
  87             return null;
  88         }
  89
  90         NSEC3Parameters params = new NSEC3Parameters((NSEC3Record) nsec3s
  91                 .get(0));
  92         ByteArrayComparator bac = new ByteArrayComparator();
  93
  94         for (NSEC3Record nsec3 : nsec3s) {
  95             if (!params.match(nsec3, bac)) {
  96                 return null;
  97             }
  98         }
  99
 100         return params;
 101     }
 102
 103     /**
 104      * Given a hash and an a zone name, construct an NSEC3 ownername.
 105      *
 106      * @param hash
 107      *            The hash of an original name.
 108      * @param zonename
 109      *            The zone to use in constructing the NSEC3 name.
 110      * @return The NSEC3 name.
 111      */
 112     private static Name hashName(byte[] hash, Name zonename) {
 113         try {
 114             return new Name(b32.toString(hash).toLowerCase(), zonename);
 115         } catch (TextParseException e) {
 116             // Note, this should never happen.
 117             return null;
 118         }
 119     }
 120
 121     /**
 122      * Given a set of NSEC3 parameters, hash a name.
 123      *
 124      * @param name
 125      *            The name to hash.
 126      * @param params
 127      *            The parameters to hash with.
 128      * @return The hash.
 129      */
 130     private static byte[] hash(Name name, NSEC3Parameters params) {
 131         try {
 132             return params.hash(name);
 133         } catch (NoSuchAlgorithmException e) {
 134             st_log.warn("Did not recognize hash algorithm: " + params.alg);
 135
 136             return null;
 137         }
 138     }
 139
 140     /**
 141      * Given the name of a closest encloser, return the name *.closest_encloser.
 142      *
 143      * @param closestEncloser
 144      *            The name to start with.
 145      * @return The wildcard name.
 146      */
 147     private static Name ceWildcard(Name closestEncloser) {
 148         try {
 149             Name wc = Name.concatenate(asterisk_label, closestEncloser);
 150
 151             return wc;
 152         } catch (NameTooLongException e) {
 153             return null;
 154         }
 155     }
 156
 157     /**
 158      * Given a qname and its proven closest encloser, calculate the "next
 159      * closest" name. Basically, this is the name that is one label longer than
 160      * the closest encloser that is still a subdomain of qname.
 161      *
 162      * @param qname
 163      *            The qname.
 164      * @param closestEncloser
 165      *            The closest encloser name.
 166      * @return The next closer name.
 167      */
 168     private static Name nextClosest(Name qname, Name closestEncloser) {
 169         int strip = qname.labels() - closestEncloser.labels() - 1;
 170
 171         return (strip > 0) ? new Name(qname, strip) : qname;
 172     }
 173
 174     /**
 175      * Find the NSEC3Record that matches a hash of a name.
 176      *
 177      * @param hash
 178      *            The pre-calculated hash of a name.
 179      * @param zonename
 180      *            The name of the zone that the NSEC3s are from.
 181      * @param nsec3s
 182      *            A list of NSEC3Records from a given message.
 183      * @param params
 184      *            The parameters used for calculating the hash.
 185      * @param bac
 186      *            An already allocated ByteArrayComparator, for reuse. This may
 187      *            be null.
 188      *
 189      * @return The matching NSEC3Record, if one is present.
 190      */
 191     private static NSEC3Record findMatchingNSEC3(byte[] hash, Name zonename,
 192             List<NSEC3Record> nsec3s, NSEC3Parameters params,
 193             ByteArrayComparator bac) {
 194         Name n = hashName(hash, zonename);
 195
 196         for (NSEC3Record nsec3 : nsec3s) {
 197             // Skip nsec3 records that are using different parameters.
 198             if (!params.match(nsec3, bac)) {
 199                 continue;
 200             }
 201
 202             if (n.equals(nsec3.getName())) {
 203                 return nsec3;
 204             }
 205         }
 206
 207         return null;
 208     }
 209
 210     /**
 211      * Given a hash and a candidate NSEC3Record, determine if that NSEC3Record
 212      * covers the hash. Covers specifically means that the hash is in between
 213      * the owner and next hashes and does not equal either.
 214      *
 215      * @param nsec3
 216      *            The candidate NSEC3Record.
 217      * @param hash
 218      *            The precalculated hash.
 219      * @param bac
 220      *            An already allocated comparator. This may be null.
 221      * @return True if the NSEC3Record covers the hash.
 222      */
 223     private static boolean nsec3Covers(NSEC3Record nsec3, byte [] hash,
 224         ByteArrayComparator bac) {
 225         Name ownerName = nsec3.getName();
 226         byte [] owner = b32.fromString(ownerName.getLabelString(0));
 227         byte [] next  = nsec3.getNext();
 228
 229         // This is the "normal case: owner < next and owner < hash < next
 230         if ((bac.compare(owner, hash) < 0) && (bac.compare(hash, next) < 0)) {
 231             return true;
 232         }
 233         // this is the end of zone case: next < owner && hash > owner || hash <
 234         // next
 235         if ((bac.compare(next, owner) <= 0)
 236                 && ((bac.compare(hash, next) < 0) || (bac.compare(owner, hash) < 0))) {
 237             return true;
 238         }
 239
 240         // Otherwise, the NSEC3 does not cover the hash.
 241         return false;
 242     }
 243
 244     /**
 245      * Given a pre-hashed name, find a covering NSEC3 from among a list of
 246      * NSEC3s.
 247      *
 248      * @param hash
 249      *            The hash to consider.
 250      * @param zonename
 251      *            The name of the zone.
 252      * @param nsec3s
 253      *            The list of NSEC3s present in a message.
 254      * @param params
 255      *            The NSEC3 parameters used to generate the hash -- NSEC3s that
 256      *            do not use those parameters will be skipped.
 257      *
 258      * @return A covering NSEC3 if one is present, null otherwise.
 259      */
 260     private static NSEC3Record findCoveringNSEC3(byte[] hash, Name zonename,
 261             List<NSEC3Record> nsec3s, NSEC3Parameters params,
 262             ByteArrayComparator bac) {
 263         ByteArrayComparator comparator = new ByteArrayComparator();
 264
 265         for (NSEC3Record nsec3 : nsec3s) {
 266             if (!params.match(nsec3, bac)) {
 267                 continue;
 268             }
 269
 270             if (nsec3Covers(nsec3, hash, comparator)) {
 271                 return nsec3;
 272             }
 273         }
 274
 275         return null;
 276     }
 277
 278     /**
 279      * Given a name and a list of NSEC3s, find the candidate closest encloser.
 280      * This will be the first ancestor of 'name' (including itself) to have a
 281      * matching NSEC3 RR.
 282      *
 283      * @param name
 284      *            The name the start with.
 285      * @param zonename
 286      *            The name of the zone that the NSEC3s came from.
 287      * @param nsec3s
 288      *            The list of NSEC3s.
 289      * @param nsec3params
 290      *            The NSEC3 parameters.
 291      * @param bac
 292      *            A pre-allocated comparator. May be null.
 293      *
 294      * @return A CEResponse containing the closest encloser name and the NSEC3
 295      *         RR that matched it, or null if there wasn't one.
 296      */
 297     private static CEResponse findClosestEncloser(Name name, Name zonename,
 298             List<NSEC3Record> nsec3s, NSEC3Parameters params,
 299             ByteArrayComparator bac) {
 300         Name n = name;
 301
 302         NSEC3Record nsec3;
 303
 304         // This scans from longest name to shortest, so the first match we find
 305         // is the only viable candidate.
 306         // FIXME: modify so that the NSEC3 matching the zone apex need not be
 307         // present.
 308         while (n.labels() >= zonename.labels()) {
 309             nsec3 = findMatchingNSEC3(hash(n, params), zonename,
 310                     nsec3s, params, bac);
 311
 312             if (nsec3 != null) {
 313                 return new CEResponse(n, nsec3);
 314             }
 315
 316             n = new Name(n, 1);
 317         }
 318
 319         return null;
 320     }
 321
 322     /**
 323      * Given a List of nsec3 RRs, find and prove the closest encloser to qname.
 324      *
 325      * @param qname
 326      *            The qname in question.
 327      * @param zonename
 328      *            The name of the zone that the NSEC3 RRs come from.
 329      * @param nsec3s
 330      *            The list of NSEC3s found the this response (already verified).
 331      * @param params
 332      *            The NSEC3 parameters found in the response.
 333      * @param bac
 334      *            A pre-allocated comparator. May be null.
 335      * @param proveDoesNotExist
 336      *            If true, then if the closest encloser turns out to be qname,
 337      *            then null is returned.
 338      * @return null if the proof isn't completed. Otherwise, return a CEResponse
 339      *         object which contains the closest encloser name and the NSEC3
 340      *         that matches it.
 341      */
 342     private static CEResponse proveClosestEncloser(Name qname, Name zonename,
 343         List<NSEC3Record> nsec3s, NSEC3Parameters params,
 344         ByteArrayComparator bac, boolean proveDoesNotExist, List<String> errorList) {
 345         CEResponse candidate = findClosestEncloser(qname, zonename, nsec3s,
 346                 params, bac);
 347
 348         if (candidate == null) {
 349             errorList.add("Could not find a candidate for the closest encloser");
 350             st_log.debug("proveClosestEncloser: could not find a " +
 351                 "candidate for the closest encloser.");
 352
 353             return null;
 354         }
 355
 356         if (candidate.closestEncloser.equals(qname)) {
 357             if (proveDoesNotExist) {
 358                 errorList.add("Proven closest encloser proved that the qname existed and should not have");
 359                 st_log.debug("proveClosestEncloser: proved that qname existed!");
 360
 361                 return null;
 362             }
 363
 364             // otherwise, we need to nothing else to prove that qname is its own
 365             // closest encloser.
 366             return candidate;
 367         }
 368
 369         // If the closest encloser is actually a delegation, then the response
 370         // should have been a referral. If it is a DNAME, then it should have
 371         // been
 372         // a DNAME response.
 373         if (candidate.ce_nsec3.hasType(Type.NS) &&
 374                 !candidate.ce_nsec3.hasType(Type.SOA)) {
 375             errorList.add("Proven closest encloser was a delegation");
 376             st_log.debug("proveClosestEncloser: closest encloser " +
 377                 "was a delegation!");
 378
 379             return null;
 380         }
 381
 382         if (candidate.ce_nsec3.hasType(Type.DNAME)) {
 383             errorList.add("Proven closest encloser was a DNAME");
 384             st_log.debug("proveClosestEncloser: closest encloser was a DNAME!");
 385
 386             return null;
 387         }
 388
 389         // Otherwise, we need to show that the next closer name is covered.
 390         Name nextClosest = nextClosest(qname, candidate.closestEncloser);
 391
 392         byte[] nc_hash = hash(nextClosest, params);
 393         candidate.nc_nsec3 = findCoveringNSEC3(nc_hash, zonename, nsec3s,
 394                 params, bac);
 395
 396         if (candidate.nc_nsec3 == null) {
 397             errorList.add("Could not find proof that the closest encloser was the closest encloser");
 398             errorList.add("hash " + hashName(nc_hash, zonename) + " is not covered by any NSEC3 RRs");
 399             st_log.debug("Could not find proof that the " +
 400                 "closest encloser was the closest encloser");
 401
 402             return null;
 403         }
 404
 405         return candidate;
 406     }
 407
 408     private static int maxIterations(int baseAlg, int keysize) {
 409         switch (baseAlg) {
 410         case DnsSecVerifier.RSA:
 411
 412             if (keysize == 0) {
 413                 return 2500; // the max at 4096
 414             }
 415
 416             if (keysize > 2048) {
 417                 return 2500;
 418             }
 419
 420             if (keysize > 1024) {
 421                 return 500;
 422             }
 423
 424             if (keysize > 0) {
 425                 return 150;
 426             }
 427
 428             break;
 429
 430         case DnsSecVerifier.DSA:
 431
 432             if (keysize == 0) {
 433                 return 5000; // the max at 2048;
 434             }
 435
 436             if (keysize > 1024) {
 437                 return 5000;
 438             }
 439
 440             if (keysize > 0) {
 441                 return 1500;
 442             }
 443
 444             break;
 445         }
 446
 447         return -1;
 448     }
 449
 450     @SuppressWarnings("rawtypes")
 451     private static boolean validIterations(NSEC3Parameters nsec3params,
 452             RRset dnskey_rrset, DnsSecVerifier verifier) {
 453         // for now, we return the maximum iterations based simply on the key
 454         // algorithms that may have been used to sign the NSEC3 RRsets.
 455         int max_iterations = 0;
 456
 457         for (Iterator i = dnskey_rrset.rrs(); i.hasNext();) {
 458             DNSKEYRecord dnskey = (DNSKEYRecord) i.next();
 459             int baseAlg = verifier.baseAlgorithm(dnskey.getAlgorithm());
 460             int iters = maxIterations(baseAlg, 0);
 461             max_iterations = (max_iterations < iters) ? iters : max_iterations;
 462         }
 463
 464         if (nsec3params.iterations > max_iterations) {
 465             return false;
 466         }
 467
 468         return true;
 469     }
 470
 471     /**
 472      * Determine if all of the NSEC3s in a response are legally ignoreable
 473      * (i.e., their presence should lead to an INSECURE result). Currently, this
 474      * is solely based on iterations.
 475      *
 476      * @param nsec3s
 477      *            The list of NSEC3s. If there is more than one set of NSEC3
 478      *            parameters present, this test will not be performed.
 479      * @param dnskey_rrset
 480      *            The set of validating DNSKEYs.
 481      * @param verifier
 482      *            The verifier used to verify the NSEC3 RRsets. This is solely
 483      *            used to map algorithm aliases.
 484      * @return true if all of the NSEC3s can be legally ignored, false if not.
 485      */
 486     public static boolean allNSEC3sIgnoreable(List<NSEC3Record> nsec3s,
 487             RRset dnskey_rrset, DnsSecVerifier verifier) {
 488         NSEC3Parameters params = nsec3Parameters(nsec3s);
 489
 490         if (params == null) {
 491             return false;
 492         }
 493
 494         return !validIterations(params, dnskey_rrset, verifier);
 495     }
 496
 497     /**
 498      * Determine if the set of NSEC3 records provided with a response prove NAME
 499      * ERROR. This means that the NSEC3s prove a) the closest encloser exists,
 500      * b) the direct child of the closest encloser towards qname doesn't exist,
 501      * and c) *.closest encloser does not exist.
 502      *
 503      * @param nsec3s
 504      *            The list of NSEC3s.
 505      * @param qname
 506      *            The query name to check against.
 507      * @param zonename
 508      *            This is the name of the zone that the NSEC3s belong to. This
 509      *            may be discovered in any number of ways. A good one is to use
 510      *            the signerName from the NSEC3 record's RRSIG.
 511      * @return SecurityStatus.SECURE of the Name Error is proven by the NSEC3
 512      *         RRs, BOGUS if not, INSECURE if all of the NSEC3s could be validly
 513      *         ignored.
 514      */
 515     public static boolean proveNameError(List<NSEC3Record> nsec3s, Name qname,
 516         Name zonename, List<String> errorList) {
 517         if ((nsec3s == null) || (nsec3s.size() == 0)) {
 518             return false;
 519         }
 520
 521         NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
 522
 523         if (nsec3params == null) {
 524             errorList.add("Could not find a single set of NSEC3 parameters (multiple parameters present");
 525             st_log.debug("Could not find a single set of " +
 526                 "NSEC3 parameters (multiple parameters present).");
 527
 528             return false;
 529         }
 530
 531         ByteArrayComparator bac = new ByteArrayComparator();
 532
 533         // First locate and prove the closest encloser to qname. We will use the
 534         // variant that fails if the closest encloser turns out to be qname.
 535         CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
 536                 nsec3params, bac, true, errorList);
 537
 538         if (ce == null) {
 539             errorList.add("Failed to find the closest encloser as part of the NSEC3 proof");
 540             st_log.debug("proveNameError: failed to prove a closest encloser.");
 541
 542             return false;
 543         }
 544
 545         // At this point, we know that qname does not exist. Now we need to
 546         // prove
 547         // that the wildcard does not exist.
 548         Name wc = ceWildcard(ce.closestEncloser);
 549         byte[] wc_hash = hash(wc, nsec3params);
 550         NSEC3Record nsec3 = findCoveringNSEC3(wc_hash, zonename, nsec3s,
 551                 nsec3params, bac);
 552
 553         if (nsec3 == null) {
 554             errorList.add("Failed to prove that the applicable wildcard did not exist");
 555             st_log.debug("proveNameError: could not prove that the " +
 556                 "applicable wildcard did not exist.");
 557
 558             return false;
 559         }
 560
 561         return true;
 562     }
 563
 564     /**
 565      * Determine if the NSEC3s provided in a response prove the NOERROR/NODATA
 566      * status. There are a number of different variants to this:
 567      *
 568      * 1) Normal NODATA -- qname is matched to an NSEC3 record, type is not
 569      * present.
 570      *
 571      * 2) ENT NODATA -- because there must be NSEC3 record for
 572      * empty-non-terminals, this is the same as #1.
 573      *
 574      * 3) NSEC3 ownername NODATA -- qname matched an existing, lone NSEC3
 575      * ownername, but qtype was not NSEC3. NOTE: as of nsec-05, this case no
 576      * longer exists.
 577      *
 578      * 4) Wildcard NODATA -- A wildcard matched the name, but not the type.
 579      *
 580      * 5) Opt-In DS NODATA -- the qname is covered by an opt-in span and qtype
 581      * == DS. (or maybe some future record with the same parent-side-only
 582      * property)
 583      *
 584      * @param nsec3s
 585      *            The NSEC3Records to consider.
 586      * @param qname
 587      *            The qname in question.
 588      * @param qtype
 589      *            The qtype in question.
 590      * @param zonename
 591      *            The name of the zone that the NSEC3s came from.
 592      * @return true if the NSEC3s prove the proposition.
 593      */
 594     public static boolean proveNodata(List<NSEC3Record> nsec3s, Name qname,
 595         int qtype, Name zonename, List<String> errorList) {
 596         if ((nsec3s == null) || (nsec3s.size() == 0)) {
 597             return false;
 598         }
 599
 600         NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
 601
 602         if (nsec3params == null) {
 603             st_log.debug("could not find a single set of "
 604                     + "NSEC3 parameters (multiple parameters present)");
 605
 606             return false;
 607         }
 608
 609         ByteArrayComparator bac = new ByteArrayComparator();
 610
 611         NSEC3Record nsec3 = findMatchingNSEC3(hash(qname, nsec3params),
 612                 zonename, nsec3s, nsec3params, bac);
 613
 614         // Cases 1 & 2.
 615         if (nsec3 != null) {
 616             if (nsec3.hasType(qtype)) {
 617                 st_log
 618                         .debug("proveNodata: Matching NSEC3 proved that type existed!");
 619
 620                 return false;
 621             }
 622
 623             if (nsec3.hasType(Type.CNAME)) {
 624                 st_log.debug("proveNodata: Matching NSEC3 proved "
 625                         + "that a CNAME existed!");
 626
 627                 return false;
 628             }
 629
 630             return true;
 631         }
 632
 633         // For cases 3 - 5, we need the proven closest encloser, and it can't
 634         // match qname. Although, at this point, we know that it won't since we
 635         // just checked that.
 636         CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
 637                 nsec3params, bac, true, errorList);
 638
 639         // At this point, not finding a match or a proven closest encloser is a
 640         // problem.
 641         if (ce == null) {
 642             st_log.debug("proveNodata: did not match qname, "
 643                     + "nor found a proven closest encloser.");
 644
 645             return false;
 646         }
 647
 648         // Case 3: REMOVED
 649
 650         // Case 4:
 651         Name wc = ceWildcard(ce.closestEncloser);
 652         nsec3 = findMatchingNSEC3(hash(wc, nsec3params), zonename, nsec3s,
 653                 nsec3params, bac);
 654
 655         if (nsec3 != null) {
 656             if (nsec3.hasType(qtype)) {
 657                 st_log.debug("proveNodata: matching wildcard had qtype!");
 658
 659                 return false;
 660             }
 661
 662             return true;
 663         }
 664
 665         // Case 5.
 666         if (qtype != Type.DS) {
 667             st_log
 668                     .debug("proveNodata: could not find matching NSEC3, "
 669                             + "nor matching wildcard, and qtype is not DS -- no more options.");
 670
 671             return false;
 672         }
 673
 674         // We need to make sure that the covering NSEC3 is opt-in.
 675         if (!isOptOut(ce.nc_nsec3)) {
 676             st_log.debug("proveNodata: covering NSEC3 was not "
 677                     + "opt-in in an opt-in DS NOERROR/NODATA case.");
 678
 679             return false;
 680         }
 681
 682         return true;
 683     }
 684
 685     /**
 686      * Prove that a positive wildcard match was appropriate (no direct match
 687      * RRset).
 688      *
 689      * @param nsec3s
 690      *            The NSEC3 records to work with.
 691      * @param qname
 692      *            The qname that was matched to the wildcard
 693      * @param zonename
 694      *            The name of the zone that the NSEC3s come from.
 695      * @param wildcard
 696      *            The purported wildcard that matched.
 697      * @return true if the NSEC3 records prove this case.
 698      */
 699     public static boolean proveWildcard(List<NSEC3Record> nsec3s, Name qname,
 700         Name zonename, Name wildcard, List<String> errorList) {
 701         if ((nsec3s == null) || (nsec3s.size() == 0)) {
 702             return false;
 703         }
 704
 705         if ((qname == null) || (wildcard == null)) {
 706             return false;
 707         }
 708
 709         NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
 710
 711         if (nsec3params == null) {
 712             errorList.add("Could not find a single set of NSEC3 parameters (multiple parameters present)");
 713             st_log.debug(
 714                 "couldn't find a single set of NSEC3 parameters (multiple parameters present).");
 715
 716             return false;
 717         }
 718
 719         ByteArrayComparator bac = new ByteArrayComparator();
 720
 721         // We know what the (purported) closest encloser is by just looking at
 722         // the
 723         // supposed generating wildcard.
 724         CEResponse candidate = new CEResponse(new Name(wildcard, 1), null);
 725
 726         // Now we still need to prove that the original data did not exist.
 727         // Otherwise, we need to show that the next closer name is covered.
 728         Name nextClosest = nextClosest(qname, candidate.closestEncloser);
 729         candidate.nc_nsec3 = findCoveringNSEC3(hash(nextClosest, nsec3params),
 730                 zonename, nsec3s, nsec3params, bac);
 731
 732         if (candidate.nc_nsec3 == null) {
 733             errorList.add("Did not find a NSEC3 that covered the next closer name to '" +
 734                           qname + "' from '" + candidate.closestEncloser + "' (derived from the wildcard: " +
 735                           wildcard + ")");
 736             st_log.debug("proveWildcard: did not find a covering NSEC3 " +
 737                 "that covered the next closer name to " + qname + " from " +
 738                 candidate.closestEncloser + " (derived from wildcard " +
 739                 wildcard + ")");
 740
 741             return false;
 742         }
 743
 744         return true;
 745     }
 746
 747     /**
 748      * Prove that a DS response either had no DS, or wasn't a delegation point.
 749      *
 750      * Fundamentally there are two cases here: normal NODATA and Opt-In NODATA.
 751      *
 752      * @param nsec3s
 753      *            The NSEC3 RRs to examine.
 754      * @param qname
 755      *            The name of the DS in question.
 756      * @param zonename
 757      *            The name of the zone that the NSEC3 RRs come from.
 758      *
 759      * @return SecurityStatus.SECURE if it was proven that there is no DS in a
 760      *         secure (i.e., not opt-in) way, SecurityStatus.INSECURE if there
 761      *         was no DS in an insecure (i.e., opt-in) way,
 762      *         SecurityStatus.INDETERMINATE if it was clear that this wasn't a
 763      *         delegation point, and SecurityStatus.BOGUS if the proofs don't
 764      *         work out.
 765      */
 766     public static byte proveNoDS(List<NSEC3Record> nsec3s, Name qname,
 767         Name zonename, List<String> errorList) {
 768         if ((nsec3s == null) || (nsec3s.size() == 0)) {
 769             return SecurityStatus.BOGUS;
 770         }
 771
 772         NSEC3Parameters nsec3params = nsec3Parameters(nsec3s);
 773
 774         if (nsec3params == null) {
 775             errorList.add("Could not find a single set of NSEC3 parameters (multiple parameters present)");
 776             st_log.debug("couldn't find a single set of " +
 777                 "NSEC3 parameters (multiple parameters present).");
 778
 779             return SecurityStatus.BOGUS;
 780         }
 781
 782         ByteArrayComparator bac = new ByteArrayComparator();
 783
 784         // Look for a matching NSEC3 to qname -- this is the normal NODATA case.
 785         NSEC3Record nsec3 = findMatchingNSEC3(hash(qname, nsec3params),
 786                 zonename, nsec3s, nsec3params, bac);
 787
 788         if (nsec3 != null) {
 789             // If the matching NSEC3 has the SOA bit set, it is from the wrong
 790             // zone (the child instead of the parent). If it has the DS bit set,
 791             // then we were lied to.
 792             if (nsec3.hasType(Type.SOA) || nsec3.hasType(Type.DS)) {
 793                 errorList.add("Matching NSEC3 is incorrectly from the child instead of the parent (SOA or DS bit set)");
 794                 return SecurityStatus.BOGUS;
 795             }
 796
 797             // If the NSEC3 RR doesn't have the NS bit set, then this wasn't a
 798             // delegation point.
 799             if (!nsec3.hasType(Type.NS)) {
 800                 return SecurityStatus.INDETERMINATE;
 801             }
 802
 803             // Otherwise, this proves no DS.
 804             return SecurityStatus.SECURE;
 805         }
 806
 807         // Otherwise, we are probably in the opt-in case.
 808         CEResponse ce = proveClosestEncloser(qname, zonename, nsec3s,
 809                 nsec3params, bac, true, errorList);
 810
 811         if (ce == null) {
 812             errorList.add("Failed to prove the closest encloser as part of a 'No DS' proof");
 813             return SecurityStatus.BOGUS;
 814         }
 815
 816         // If we had the closest encloser proof, then we need to check that the
 817         // covering NSEC3 was opt-in -- the proveClosestEncloser step already
 818         // checked to see if the closest encloser was a delegation or DNAME.
 819         if (isOptOut(ce.nc_nsec3)) {
 820             return SecurityStatus.SECURE;
 821         }
 822
 823         errorList.add("Failed to find a covering NSEC3 for 'No DS' proof");
 824         return SecurityStatus.BOGUS;
 825     }
 826
 827     /**
 828      * This is a class to encapsulate a unique set of NSEC3 parameters:
 829      * algorithm, iterations, and salt.
 830      */
 831     private static class NSEC3Parameters {
 832         public int alg;
 833         public byte[] salt;
 834         public int iterations;
 835         private NSEC3PARAMRecord nsec3paramrec;
 836
 837         public NSEC3Parameters(NSEC3Record r) {
 838             alg = r.getHashAlgorithm();
 839             salt = r.getSalt();
 840             iterations = r.getIterations();
 841
 842             nsec3paramrec = new NSEC3PARAMRecord(Name.root, DClass.IN, 0, alg,
 843                     0, iterations, salt);
 844         }
 845
 846         public boolean match(NSEC3Record r, ByteArrayComparator bac) {
 847             if (r.getHashAlgorithm() != alg) {
 848                 return false;
 849             }
 850
 851             if (r.getIterations() != iterations) {
 852                 return false;
 853             }
 854
 855             if ((salt == null) && (r.getSalt() != null)) {
 856                 return false;
 857             }
 858
 859             if (salt == null) {
 860                 return true;
 861             }
 862
 863             if (bac == null) {
 864                 bac = new ByteArrayComparator();
 865             }
 866
 867             return bac.compare(r.getSalt(), salt) == 0;
 868         }
 869
 870         public byte[] hash(Name name) throws NoSuchAlgorithmException {
 871             return nsec3paramrec.hashName(name);
 872         }
 873     }
 874
 875     /**
 876      * This is just a simple class to encapsulate the response to a closest
 877      * encloser proof.
 878      */
 879     private static class CEResponse {
 880         public Name closestEncloser;
 881         public NSEC3Record ce_nsec3;
 882         public NSEC3Record nc_nsec3;
 883
 884         public CEResponse(Name ce, NSEC3Record nsec3) {
 885             this.closestEncloser = ce;
 886             this.ce_nsec3 = nsec3;
 887         }
 888     }
 889 }