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