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