src/se/rfc/unbound/NSEC3ValUtils.java

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