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