src/com/verisign/tat/dnssec/CaptiveValidator.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 org.apache.log4j.Logger;
  27
  28 import org.xbill.DNS.*;
  29 import org.xbill.DNS.utils.base64;
  30
  31 import java.io.IOException;
  32
  33 import java.util.*;
  34
  35 /**
  36  * This resolver module implements a "captive" DNSSEC validator. The
  37  * captive validator does not have direct access to the Internet and
  38  * DNS system -- instead it attempts to validate DNS messages using
  39  * only configured context.  This is useful for determining if
  40  * responses coming from a given authoritative server will validate
  41  * independent of the normal chain of trust.
  42  */
  43 public class CaptiveValidator {
  44     // A data structure holding all all of our trusted keys.
  45     private TrustAnchorStore mTrustedKeys;
  46
  47     // The local validation utilities.
  48     private ValUtils mValUtils;
  49
  50     // The local verification utility.
  51     private DnsSecVerifier mVerifier;
  52     private Logger log = Logger.getLogger(this.getClass());
  53
  54     // The list of validation errors found.
  55     private List<String> mErrorList;
  56
  57     public CaptiveValidator() {
  58         mVerifier    = new DnsSecVerifier();
  59         mValUtils    = new ValUtils(mVerifier);
  60         mTrustedKeys = new TrustAnchorStore();
  61         mErrorList   = new ArrayList<String>();
  62     }
  63
  64     // ---------------- Module Initialization -------------------
  65
  66     /**
  67      * Add a set of trusted keys from a file. The file should be in
  68      * DNS master zone file format. Only DNSKEY records will be added.
  69      *
  70      * @param filename
  71      *            The file contains the trusted keys.
  72      * @throws IOException
  73      */
  74     @SuppressWarnings("unchecked")
  75     public void addTrustedKeysFromFile(String filename) throws IOException {
  76         // First read in the whole trust anchor file.
  77         Master            master  = new Master(filename, Name.root, 0);
  78         ArrayList<Record> records = new ArrayList<Record>();
  79         Record            r       = null;
  80
  81         while ((r = master.nextRecord()) != null) {
  82             records.add(r);
  83         }
  84
  85         // Record.compareTo() should sort them into DNSSEC canonical
  86         // order.  Don't care about canonical order per se, but do
  87         // want them to be formable into RRsets.
  88         Collections.sort(records);
  89
  90         SRRset cur_rrset = new SRRset();
  91
  92         for (Record rec : records) {
  93             // Skip RR types that cannot be used as trusted
  94             // keys. I.e., everything not a key :)
  95             if (rec.getType() != Type.DNSKEY) {
  96                 continue;
  97             }
  98
  99             // If our cur_rrset is empty, we can just add it.
 100             if (cur_rrset.size() == 0) {
 101                 cur_rrset.addRR(rec);
 102
 103                 continue;
 104             }
 105
 106             // If this record matches our current RRset, we can just
 107             // add it.
 108             if (cur_rrset.getName().equals(rec.getName()) &&
 109                 (cur_rrset.getType() == rec.getType()) && (cur_rrset.getDClass() == rec.getDClass())) {
 110
 111                 cur_rrset.addRR(rec);
 112                 continue;
 113             }
 114
 115             // Otherwise, we add the rrset to our set of trust anchors.
 116             mTrustedKeys.store(cur_rrset);
 117             cur_rrset = new SRRset();
 118             cur_rrset.addRR(rec);
 119         }
 120
 121         // add the last rrset (if it was not empty)
 122         if (cur_rrset.size() > 0) {
 123             mTrustedKeys.store(cur_rrset);
 124         }
 125     }
 126
 127     public void addTrustedKeysFromResponse(Message m) {
 128         RRset[] rrsets = m.getSectionRRsets(Section.ANSWER);
 129
 130         for (int i = 0; i < rrsets.length; ++i) {
 131             if (rrsets[i].getType() == Type.DNSKEY) {
 132                 SRRset srrset = new SRRset(rrsets[i]);
 133                 mTrustedKeys.store(srrset);
 134             }
 135         }
 136     }
 137
 138     // ----------------- Validation Support ----------------------
 139
 140     /**
 141      * This routine normalizes a response. This includes removing
 142      * "irrelevant" records from the answer and additional sections
 143      * and (re)synthesizing CNAMEs from DNAMEs, if present.
 144      *
 145      * @param response
 146      */
 147     private SMessage normalize(SMessage m) {
 148         if (m == null) {
 149             return m;
 150         }
 151
 152         if ((m.getRcode() != Rcode.NOERROR) && (m.getRcode() != Rcode.NXDOMAIN)) {
 153             return m;
 154         }
 155
 156         Name qname = m.getQuestion().getName();
 157         int  qtype = m.getQuestion().getType();
 158
 159         Name sname = qname;
 160
 161         // For the ANSWER section, remove all "irrelevant" records and add
 162         // synthesized CNAMEs from DNAMEs
 163         // This will strip out-of-order CNAMEs as well.
 164         List<SRRset> rrset_list = m.getSectionList(Section.ANSWER);
 165         Set<Name> additional_names = new HashSet<Name>();
 166
 167         for (ListIterator<SRRset> i = rrset_list.listIterator(); i.hasNext();) {
 168             SRRset rrset = i.next();
 169             int    type  = rrset.getType();
 170             Name   n     = rrset.getName();
 171
 172             // Handle DNAME synthesis; DNAME synthesis does not occur
 173             // at the DNAME name itself.
 174             if ((type == Type.DNAME) && ValUtils.strictSubdomain(sname, n)) {
 175                 if (rrset.size() > 1) {
 176                     log.debug("Found DNAME rrset with size > 1: " + rrset);
 177                     m.setStatus(SecurityStatus.INVALID);
 178
 179                     return m;
 180                 }
 181
 182                 DNAMERecord dname = (DNAMERecord) rrset.first();
 183
 184                 try {
 185                     Name cname_alias = sname.fromDNAME(dname);
 186
 187                     // Note that synthesized CNAMEs should have a TTL of zero.
 188                     CNAMERecord cname = new CNAMERecord(sname, dname.getDClass(), 0, cname_alias);
 189                     SRRset cname_rrset = new SRRset();
 190                     cname_rrset.addRR(cname);
 191                     i.add(cname_rrset);
 192
 193                     sname = cname_alias;
 194                 } catch (NameTooLongException e) {
 195                     log.debug("not adding synthesized CNAME -- " +
 196                               "generated name is too long", e);
 197                 }
 198
 199                 continue;
 200             }
 201
 202             // The only records in the ANSWER section not allowed to
 203             if (!n.equals(sname)) {
 204                 log.debug("normalize: removing irrelevant rrset: " + rrset);
 205                 i.remove();
 206
 207                 continue;
 208             }
 209
 210             // Follow the CNAME chain.
 211             if (type == Type.CNAME) {
 212                 if (rrset.size() > 1) {
 213                     mErrorList.add("Found CNAME rrset with size > 1: " + rrset);
 214                     m.setStatus(SecurityStatus.INVALID);
 215
 216                     return m;
 217                 }
 218
 219                 CNAMERecord cname = (CNAMERecord) rrset.first();
 220                 sname = cname.getAlias();
 221
 222                 continue;
 223             }
 224
 225             // Otherwise, make sure that the RRset matches the qtype.
 226             if ((qtype != Type.ANY) && (qtype != type)) {
 227                 log.debug("normalize: removing irrelevant rrset: " + rrset);
 228                 i.remove();
 229             }
 230
 231             // Otherwise, fetch the additional names from the relevant rrset.
 232             rrsetAdditionalNames(additional_names, rrset);
 233         }
 234
 235         // Get additional names from AUTHORITY
 236         rrset_list = m.getSectionList(Section.AUTHORITY);
 237
 238         for (SRRset rrset : rrset_list) {
 239             rrsetAdditionalNames(additional_names, rrset);
 240         }
 241
 242         // For each record in the additional section, remove it if it is an
 243         // address record and not in the collection of additional names found in
 244         // ANSWER and AUTHORITY.
 245         rrset_list = m.getSectionList(Section.ADDITIONAL);
 246
 247         for (Iterator<SRRset> i = rrset_list.iterator(); i.hasNext();) {
 248             SRRset rrset = i.next();
 249             int    type  = rrset.getType();
 250
 251             if (((type == Type.A) || (type == Type.AAAA)) &&
 252                 !additional_names.contains(rrset.getName())) {
 253
 254                 i.remove();
 255             }
 256         }
 257
 258         return m;
 259     }
 260
 261     /**
 262      * Extract additional names from the records in an rrset.
 263      *
 264      * @param additional_names
 265      *            The set to add the additional names to, if any.
 266      * @param rrset
 267      *            The rrset to extract from.
 268      */
 269     private void rrsetAdditionalNames(Set<Name> additional_names, SRRset rrset) {
 270         if (rrset == null) {
 271             return;
 272         }
 273
 274         for (Iterator<Record> i = rrset.rrs(); i.hasNext();) {
 275             Record r        = i.next();
 276             Name   add_name = r.getAdditionalName();
 277
 278             if (add_name != null) {
 279                 additional_names.add(add_name);
 280             }
 281         }
 282     }
 283
 284     private SRRset findKeys(SMessage message) {
 285         Name qname = message.getQName();
 286         int qclass = message.getQClass();
 287
 288         return mTrustedKeys.find(qname, qclass);
 289     }
 290
 291     /**
 292      * Check to see if a given response needs to go through the
 293      * validation process. Typical reasons for this routine to return
 294      * false are: CD bit was on in the original request, the response
 295      * was already validated, or the response is a kind of message
 296      * that is unvalidatable (i.e., SERVFAIL, REFUSED, etc.)
 297      *
 298      * @param message
 299      *            The message to check.
 300      * @param origRequest
 301      *            The original request received from the client.
 302      *
 303      * @return true if the response could use validation (although this does not
 304      *         mean we can actually validate this response).
 305      */
 306     private boolean needsValidation(SMessage message) {
 307         int rcode = message.getRcode();
 308
 309         if ((rcode != Rcode.NOERROR) && (rcode != Rcode.NXDOMAIN)) {
 310             log.debug("cannot validate non-answer.");
 311             log.trace("non-answer: " + message);
 312
 313             return false;
 314         }
 315
 316         if (!mTrustedKeys.isBelowTrustAnchor(message.getQName(), message.getQClass())) {
 317             return false;
 318         }
 319
 320         return true;
 321     }
 322
 323     /**
 324      * Given a "positive" response -- a response that contains an
 325      * answer to the question, and no CNAME chain, validate this
 326      * response. This generally consists of verifying the answer RRset
 327      * and the authority RRsets.
 328      *
 329      * Note that by the time this method is called, the process of
 330      * finding the trusted DNSKEY rrset that signs this response must
 331      * already have been completed.
 332      *
 333      * @param response
 334      *            The response to validate.
 335      * @param request
 336      *            The request that generated this response.
 337      * @param key_rrset
 338      *            The trusted DNSKEY rrset that matches the signer of the
 339      *            answer.
 340      */
 341     private void validatePositiveResponse(SMessage message, SRRset key_rrset) {
 342         Name qname = message.getQName();
 343         int  qtype = message.getQType();
 344
 345         SMessage m = message;
 346
 347         // validate the ANSWER section - this will be the answer itself
 348         SRRset[] rrsets = m.getSectionRRsets(Section.ANSWER);
 349
 350         Name              wc        = null;
 351         boolean           wcNSEC_ok = false;
 352         boolean           dname     = false;
 353         List<NSEC3Record> nsec3s    = null;
 354
 355         for (int i = 0; i < rrsets.length; i++) {
 356             // Skip the CNAME following a (validated) DNAME.
 357             // Because of the normalization routines in NameserverClient, there
 358             // will always be an unsigned CNAME following a DNAME (unless
 359             // qtype=DNAME).
 360             if (dname && (rrsets[i].getType() == Type.CNAME)) {
 361                 dname = false;
 362                 continue;
 363             }
 364
 365             // Verify the answer rrset.
 366             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
 367
 368             // If the (answer) rrset failed to validate, then this
 369             // message is bogus.
 370             if (status != SecurityStatus.SECURE) {
 371                 mErrorList.add("Positive response has failed ANSWER rrset: " +
 372                                rrsets[i]);
 373                 m.setStatus(SecurityStatus.BOGUS);
 374
 375                 return;
 376             }
 377
 378             // Check to see if the rrset is the result of a wildcard expansion.
 379             // If so, an additional check will need to be made in the authority
 380             // section.
 381             wc = ValUtils.rrsetWildcard(rrsets[i]);
 382
 383             // Notice a DNAME that should be followed by an unsigned CNAME.
 384             if ((qtype != Type.DNAME) && (rrsets[i].getType() == Type.DNAME)) {
 385                 dname = true;
 386             }
 387         }
 388
 389         // validate the AUTHORITY section as well - this will
 390         // generally be the NS rrset (which could be missing, no
 391         // problem)
 392         rrsets = m.getSectionRRsets(Section.AUTHORITY);
 393
 394         for (int i = 0; i < rrsets.length; i++) {
 395             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
 396
 397             // If anything in the authority section fails to be
 398             // secure, we have a bad message.
 399             if (status != SecurityStatus.SECURE) {
 400                 mErrorList.add("Positive response has failed AUTHORITY rrset: " +
 401                                rrsets[i]);
 402                 m.setStatus(SecurityStatus.BOGUS);
 403
 404                 return;
 405             }
 406
 407             // If this is a positive wildcard response, and we have a
 408             // (just verified) NSEC record, try to use it to 1) prove
 409             // that qname doesn't exist and 2) that the correct
 410             // wildcard was used.
 411             if ((wc != null) && (rrsets[i].getType() == Type.NSEC)) {
 412                 NSECRecord nsec = (NSECRecord) rrsets[i].first();
 413
 414                 if (ValUtils.nsecProvesNameError(nsec, qname, key_rrset.getName())) {
 415                     Name nsec_wc = ValUtils.nsecWildcard(qname, nsec);
 416
 417                     if (!wc.equals(nsec_wc)) {
 418                         mErrorList.add("Positive wildcard response wasn't generated by the correct wildcard");
 419                         m.setStatus(SecurityStatus.BOGUS);
 420
 421                         return;
 422                     }
 423
 424                     wcNSEC_ok = true;
 425                 }
 426             }
 427
 428             // Otherwise, if this is a positive wildcard response and we have
 429             // NSEC3 records, collect them.
 430             if ((wc != null) && (rrsets[i].getType() == Type.NSEC3)) {
 431                 if (nsec3s == null) {
 432                     nsec3s = new ArrayList<NSEC3Record>();
 433                 }
 434
 435                 nsec3s.add((NSEC3Record) rrsets[i].first());
 436             }
 437         }
 438
 439         // If this was a positive wildcard response that we haven't
 440         // already proven, and we have NSEC3 records, try to prove it
 441         // using the NSEC3 records.
 442         if ((wc != null) && !wcNSEC_ok && (nsec3s != null)) {
 443             if (NSEC3ValUtils.proveWildcard(nsec3s, qname, key_rrset.getName(),
 444                                             wc, mErrorList)) {
 445                 wcNSEC_ok = true;
 446             }
 447         }
 448
 449         // If after all this, we still haven't proven the positive
 450         // wildcard response, fail.
 451         if ((wc != null) && !wcNSEC_ok) {
 452             // log.debug("positive response was wildcard expansion and " +
 453             //           "did not prove original data did not exist");
 454             m.setStatus(SecurityStatus.BOGUS);
 455
 456             return;
 457         }
 458
 459         log.trace("Successfully validated positive response");
 460         m.setStatus(SecurityStatus.SECURE);
 461     }
 462
 463     /** Given a "referral" type response (RCODE=NOERROR, ANSWER=0,
 464      * AUTH=NS records under the zone we thought we were talking to,
 465      * etc.), validate it.  This consists of validating the DS or
 466      * NSEC/NSEC3 RRsets and noting that the response does indeed look
 467      * like a referral.
 468      *
 469      *
 470      */
 471     private void validateReferral(SMessage message, SRRset key_rrset) {
 472         SMessage m = message;
 473
 474         if (m.getCount(Section.ANSWER) > 0) {
 475             m.setStatus(SecurityStatus.INVALID);
 476
 477             return;
 478         }
 479
 480         // validate the AUTHORITY section.
 481         SRRset[] rrsets = m.getSectionRRsets(Section.AUTHORITY);
 482
 483         boolean           secure_delegation = false;
 484         Name              delegation        = null;
 485         Name              nsec3zone         = null;
 486         NSECRecord        nsec              = null;
 487         List<NSEC3Record> nsec3s            = null;
 488
 489         // validate the AUTHORITY section as well - this will generally be the
 490         // NS rrset, plus proof of a secure delegation or not
 491         rrsets = m.getSectionRRsets(Section.AUTHORITY);
 492
 493         for (int i = 0; i < rrsets.length; i++) {
 494             int type = rrsets[i].getType();
 495
 496             // The NS RRset won't be signed, but everything else
 497             // should be.  If we have an unexpected type here
 498             // with a bad signature, we will fail when we otherwise
 499             // might just have warned about the odd record.  Consider
 500             // checking the types first, then validating.
 501             if (type != Type.NS) {
 502                 int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
 503
 504                 // If anything in the authority section fails to be
 505                 // secure, we have a bad message.
 506                 if (status != SecurityStatus.SECURE) {
 507                     mErrorList.add("Referral response has failed AUTHORITY rrset: " +
 508                              rrsets[i]);
 509                     m.setStatus(SecurityStatus.BOGUS);
 510
 511                     return;
 512                 }
 513             }
 514
 515             switch (type) {
 516             case Type.DS:
 517                 secure_delegation = true;
 518                 break;
 519
 520             case Type.NS:
 521                 delegation = rrsets[i].getName();
 522                 break;
 523
 524             case Type.NSEC:
 525                 nsec = (NSECRecord) rrsets[i].first();
 526                 break;
 527
 528             case Type.NSEC3:
 529                 if (nsec3s == null) {
 530                     nsec3s = new ArrayList<NSEC3Record>();
 531                 }
 532
 533                 NSEC3Record nsec3 = (NSEC3Record) rrsets[i].first();
 534                 nsec3s.add(nsec3);
 535                 // this is a hack, really.
 536                 nsec3zone = rrsets[i].getSignerName();
 537
 538                 break;
 539
 540             default:
 541                 log.warn("Encountered unexpected type in a REFERRAL response: "
 542                         + Type.string(type));
 543
 544                 break;
 545             }
 546         }
 547
 548         // At this point, all validatable RRsets have been validated.
 549         // Now to check to see if we have a valid combination of
 550         // things.
 551         if (delegation == null) {
 552             // somehow we have a referral without an NS rrset.
 553             mErrorList.add("Apparent referral does not contain NS RRset");
 554             m.setStatus(SecurityStatus.BOGUS);
 555
 556             return;
 557         }
 558
 559         if (secure_delegation) {
 560             if ((nsec != null) || ((nsec3s != null) && (nsec3s.size() > 0))) {
 561                 // we found both a DS rrset *and* NSEC/NSEC3 rrsets!
 562                 mErrorList.add("Referral contains both DS and NSEC/NSEC3 RRsets");
 563                 m.setStatus(SecurityStatus.BOGUS);
 564
 565                 return;
 566             }
 567
 568             // otherwise, we are done.
 569             m.setStatus(SecurityStatus.SECURE);
 570
 571             return;
 572         }
 573
 574         // Note: not going to care if both NSEC and NSEC3 rrsets were present.
 575         if (nsec != null) {
 576             byte status = ValUtils.nsecProvesNoDS(nsec, delegation);
 577
 578             if (status != SecurityStatus.SECURE) {
 579                 // The NSEC *must* prove that there was no DS
 580                 // record. The INSECURE state here is still bogus.
 581                 mErrorList.add("Referral does not contain a NSEC record proving no DS");
 582                 m.setStatus(SecurityStatus.BOGUS);
 583
 584                 return;
 585             }
 586
 587             m.setStatus(SecurityStatus.SECURE);
 588
 589             return;
 590         }
 591
 592         if (nsec3s != null && nsec3s.size() > 0) {
 593             byte status = NSEC3ValUtils.proveNoDS(nsec3s, delegation, nsec3zone, mErrorList);
 594
 595             if (status != SecurityStatus.SECURE) {
 596                 // the NSEC3 RRs MUST prove no DS, so the INDETERMINATE state is
 597                 // actually bogus
 598                 mErrorList.add("Referral does not contain NSEC3 record(s) proving no DS");
 599                 m.setStatus(SecurityStatus.BOGUS);
 600
 601                 return;
 602             }
 603
 604             m.setStatus(SecurityStatus.SECURE);
 605
 606             return;
 607         }
 608
 609         // failed to find proof either way.
 610         mErrorList.add("Referral does not contain proof of no DS");
 611         m.setStatus(SecurityStatus.BOGUS);
 612     }
 613
 614     // When processing CNAME responses, if we have wildcard-generated CNAMEs we
 615     // have to keep track of several bits of information per-cname.  This small
 616     // inner class is for that.
 617     class CNAMEWildcardEntry {
 618         public Name owner;
 619         public Name wildcard;
 620         public Name signer;
 621
 622         public CNAMEWildcardEntry(Name owner, Name wildcard, Name signer) {
 623             this.owner    = owner;
 624             this.wildcard = wildcard;
 625             this.signer   = signer;
 626         }
 627     }
 628
 629     // When processing CNAME responses, our final step is check the end of the
 630     // chain if we ended up in zone. To that end, we generate a temporary
 631     // message that removes the CNAME/DNAME chain.
 632     private SMessage messageFromCNAME(SMessage source, Name sname, Name zone) {
 633
 634         SMessage m = new SMessage();
 635         m.setHeader(source.getHeader());
 636         Record oldQuestion = source.getQuestion();
 637         Record newQuestion = Record.newRecord(sname, oldQuestion.getType(), oldQuestion.getDClass());
 638         m.setQuestion(newQuestion);
 639         m.setOPT(source.getOPT());
 640
 641         // Add the rrsets from the source message, stripping answers that don't
 642         // belong to the end of the chain
 643         RRset[] rrsets = source.getSectionRRsets(Section.ANSWER);
 644         for (int i = 0; i < rrsets.length; i++) {
 645             Name rname = rrsets[i].getName();
 646
 647             if (rname.equals(sname)) {
 648                 m.addRRset(rrsets[i], Section.ANSWER);
 649             }
 650         }
 651
 652         // The authority and additional sections should be about the end of the
 653         // chain, plus some additional NSEC or NSEC3 records.
 654         for (int i = Section.AUTHORITY; i <= Section.ADDITIONAL; i++) {
 655             rrsets = source.getSectionRRsets(i);
 656
 657             for (int j = 0; j < rrsets.length; j++) {
 658                 m.addRRset(rrsets[j], i);
 659             }
 660         }
 661         return m;
 662     }
 663
 664     /**
 665      * Given a "CNAME" response (i.e., a response that contains at least one
 666      * CNAME, and qtype != CNAME).  This largely consists of validating each
 667      * CNAME RRset until the CNAME chain goes "out of zone".  Note that
 668      * out-of-order CNAME chains will have been cleaned up via normalize(). When
 669      * traversing the CNAME chain, we detect if the CNAMEs were generated from a
 670      * wildcard, and we detect when the chain goes "out-of-zone".  For each
 671      * in-zone wildcard generated CNAME, we check for a proof that the alias
 672      * (the owner of each cname) doesn't exist.
 673      *
 674      * If the end of the chain is still in zone, we then strip the CNAME/DNAME
 675      * chain, reclassify the response, then validate the "tail message".
 676      *
 677      * Note that once the CNAME chain goes out of zone, any further CNAMEs are
 678      * not DNSSEC validated (we would need more trusted keysets for that), so
 679      * this isn't useful in all cases (i.e., for testing a nameserver, like
 680      * BIND, which generates CNAME chains across zones.)
 681      *
 682      * Note that by the time this method is called, the process of finding the
 683      * trusted DNSKEY rrset that signs this response must already have been
 684      * completed.
 685      */
 686     private void validateCNAMEResponse(SMessage message, SRRset key_rrset)
 687     {
 688         Name qname = message.getQName();
 689
 690         Name                     sname     = qname;  // this is the "current" name in the chain
 691         boolean                  dname     = false;  // a flag indicating that prev iteration was a dname
 692         boolean                  inZone    = true;   // a flag telling us if we ended up in zone.
 693         List<CNAMEWildcardEntry> wildcards =
 694             new ArrayList<CNAMEWildcardEntry>();     // The CNAMEs that were generated with wildcards.
 695         Name zone = key_rrset.getName();
 696
 697         SRRset[] rrsets = message.getSectionRRsets(Section.ANSWER);
 698
 699         // Validate the ANSWER section RRsets.
 700         for (int i = 0; i < rrsets.length; i++) {
 701
 702             int  rtype = rrsets[i].getType();
 703             Name rname = rrsets[i].getName();
 704
 705             // Follow the CNAME chain
 706             if (rtype == Type.CNAME) {
 707                 // If we've gotten off track...  Note: this should be
 708                 // impossible with normalization in effect.
 709
 710                 if (!sname.equals(rname)) {
 711                     mErrorList.add("CNAME chain is broken: expected owner name of " +
 712                                    sname + " got: " + rname);
 713                     message.setStatus(SecurityStatus.BOGUS);
 714                     return;
 715                 }
 716
 717                 sname = ((CNAMERecord) rrsets[i].first()).getAlias();
 718
 719                 // Check to see if the CNAME was generated by a wildcard.  We
 720                 // store the generated name instead of the wildcard value, as we
 721                 // need to prove that the wildcard wasn't blocked.  For now, we
 722                 // only want to do that for "in zone" wildcard CNAMEs
 723                 Name wc = ValUtils.rrsetWildcard(rrsets[i]);
 724                 if (wc != null && inZone) {
 725                     RRSIGRecord rrsig = rrsets[i].firstSig();
 726                     wildcards.add(new CNAMEWildcardEntry(sname, wc, rrsig.getSigner()));
 727                 }
 728             }
 729
 730             // Note when we see a DNAME.
 731             if (rtype == Type.DNAME) {
 732                 dname = true;
 733                 Name wc = ValUtils.rrsetWildcard(rrsets[i]);
 734                 if (wc != null) {
 735                     mErrorList.add("Illegal wildcard DNAME found: " + rrsets[i]);
 736                 }
 737             }
 738
 739             // Skip validation of CNAMEs following DNAMEs.  The
 740             // normalization step will have synthesized an unsigned
 741             // CNAME RRset.
 742             if (dname && rtype == Type.CNAME) {
 743                 dname = false;
 744                 continue;
 745             }
 746
 747             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
 748
 749             if (status != SecurityStatus.SECURE) {
 750                 mErrorList.add("CNAME response has a failed ANSWER rrset: " +
 751                                rrsets[i]);
 752                 message.setStatus(SecurityStatus.BOGUS);
 753
 754                 return;
 755             }
 756
 757             // Once we've gone off the reservation, avoid further
 758             // validation.
 759             if (! sname.subdomain(zone)) {
 760                 inZone = false;
 761                 break;
 762             }
 763         }
 764
 765         log.trace("processed CNAME chain and ended with: " +
 766                 sname + "; inZone = " + inZone);
 767
 768         // Keep track of NSEC and NSEC3 records we find in the auth section
 769         // Only add verified records, though.
 770         List<NSECRecord>  nsecs  = new ArrayList<NSECRecord>();
 771         List<NSEC3Record> nsec3s = new ArrayList<NSEC3Record>();
 772
 773         // Validate the AUTHORITY section.
 774         rrsets = message.getSectionRRsets(Section.ANSWER);
 775         for (int i = 0; i < rrsets.length; i++) {
 776             Name rname = rrsets[i].getName();
 777             int  rtype = rrsets[i].getType();
 778
 779             if (! rname.subdomain(zone)) {
 780                 // Skip auth records that are not in our zone
 781                 // This is a current limitation of this method
 782                 continue;
 783             }
 784
 785             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
 786
 787             // If anything in the authority section fails to be
 788             // secure, we have a bad message.
 789             if (status != SecurityStatus.SECURE) {
 790                 mErrorList.add("Positive response has failed AUTHORITY rrset: " +
 791                                rrsets[i]);
 792                 message.setStatus(SecurityStatus.BOGUS);
 793
 794                 return;
 795             }
 796
 797             // otherwise, collect the validated NSEC and NSEC3 RRs, if any
 798             if (rtype == Type.NSEC) {
 799                 nsecs.add((NSECRecord) rrsets[i].first());
 800             }
 801             else if (rtype == Type.NSEC3) {
 802                 nsec3s.add((NSEC3Record) rrsets[i].first());
 803             }
 804         }
 805
 806         // Regardless if whether or not we left the reservation, if some of our
 807         // CNAMEs were generated from wildcards we need to prove that.
 808         if (wildcards.size() > 0) {
 809
 810             for (CNAMEWildcardEntry wcEntry : wildcards) {
 811                 boolean result = false;
 812                 if (nsecs.size() > 0) {
 813                     for (NSECRecord nsec : nsecs) {
 814                         result = ValUtils.nsecProvesNameError(nsec, wcEntry.owner, wcEntry.signer);
 815                         if (result) break;
 816                     }
 817                 }
 818                 else if (nsec3s.size() > 0) {
 819                     result = NSEC3ValUtils.proveWildcard(nsec3s, wcEntry.owner, zone, wcEntry.wildcard, mErrorList);
 820                 }
 821
 822                 if (!result) {
 823                     mErrorList.add("CNAME response has a wildcard-generated CNAME '" +
 824                                    wcEntry.owner + "' but does not prove that the wildcard '" +
 825                                    wcEntry.wildcard + "' was valid via a covering NSEC or NSEC3 RR");
 826                     message.setStatus(SecurityStatus.BOGUS);
 827                     return;
 828                 }
 829             }
 830         }
 831
 832         // If our CNAME chain took us out of zone, we are done.
 833         if (! inZone) {
 834             log.trace("Successfully validated CNAME response up to the point where it left our zone.");
 835             message.setStatus(SecurityStatus.SECURE);
 836             return;
 837         }
 838
 839         // Otherwise, we need to do some additional proofs
 840         SMessage tailMessage = messageFromCNAME(message, sname, zone);
 841         ValUtils.ResponseType tailType = ValUtils.classifyResponse(tailMessage, zone);
 842         switch (tailType) {
 843             case POSITIVE:
 844             log.trace("Validating the rest of the CNAME response as a positive response");
 845             validatePositiveResponse(tailMessage, key_rrset);
 846             message.setSecurityStatus(tailMessage.getSecurityStatus());
 847             break;
 848
 849         case REFERRAL:
 850             log.trace("Validating the rest of the CNAME response as a referral");
 851             validateReferral(tailMessage, key_rrset);
 852             message.setSecurityStatus(tailMessage.getSecurityStatus());
 853             break;
 854
 855         case NODATA:
 856             log.trace("Validating the rest of the CNAME responses as a NODATA response");
 857             validateNodataResponse(tailMessage, key_rrset, mErrorList);
 858             message.setSecurityStatus(tailMessage.getSecurityStatus());
 859             break;
 860
 861         case NAMEERROR:
 862             log.trace("Validating a the rest of the CNAME responses as NXDOMAIN response");
 863             validateNameErrorResponse(tailMessage, key_rrset);
 864             message.setSecurityStatus(tailMessage.getSecurityStatus());
 865             break;
 866
 867         case CNAME:
 868             log.error("Reclassified the tail of a CNAME response as a CNAME");
 869             log.error(tailMessage);
 870             message.setStatus(SecurityStatus.BOGUS);
 871             break;
 872
 873         case ANY:
 874             log.error("Reclassified the tail of a CNAME response as an ANY response");
 875             log.error(tailMessage);
 876             message.setStatus(SecurityStatus.BOGUS);
 877             break;
 878
 879         default:
 880             log.error("unhandled response subtype: " + tailType);
 881             message.setStatus(SecurityStatus.BOGUS);
 882             break;
 883         }
 884     }
 885
 886     /**
 887      * Given an "ANY" response -- a response that contains an answer
 888      * to a qtype==ANY question, with answers. This consists of simply
 889      * verifying all present answer/auth RRsets, with no checking that
 890      * all types are present.
 891      *
 892      * NOTE: it may be possible to get parent-side delegation point
 893      * records here, which won't all be signed. Right now, this
 894      * routine relies on the upstream iterative resolver to not return
 895      * these responses -- instead treating them as referrals.
 896      *
 897      * NOTE: RFC 4035 is silent on this issue, so this may change upon
 898      * clarification.
 899      *
 900      * Note that by the time this method is called, the process of
 901      * finding the trusted DNSKEY rrset that signs this response must
 902      * already have been completed.
 903      *
 904      * @param message
 905      *            The response to validate.
 906      * @param key_rrset
 907      *            The trusted DNSKEY rrset that matches the signer of the
 908      *            answer.
 909      */
 910     private void validateAnyResponse(SMessage message, SRRset key_rrset) {
 911         int qtype = message.getQType();
 912
 913         if (qtype != Type.ANY) {
 914             throw new IllegalArgumentException("ANY validation called on non-ANY response.");
 915         }
 916
 917         SMessage m = message;
 918
 919         // validate the ANSWER section.
 920         SRRset[] rrsets = m.getSectionRRsets(Section.ANSWER);
 921
 922         for (int i = 0; i < rrsets.length; i++) {
 923             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
 924
 925             // If the (answer) rrset failed to validate, then this message is
 926             // BAD.
 927             if (status != SecurityStatus.SECURE) {
 928                 mErrorList.add("Positive response has failed ANSWER rrset: " +
 929                                rrsets[i]);
 930                 m.setStatus(SecurityStatus.BOGUS);
 931
 932                 return;
 933             }
 934         }
 935
 936         // validate the AUTHORITY section as well - this will be the NS rrset
 937         // (which could be missing, no problem)
 938         rrsets = m.getSectionRRsets(Section.AUTHORITY);
 939
 940         for (int i = 0; i < rrsets.length; i++) {
 941             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
 942
 943             // If anything in the authority section fails to be secure, we have
 944             // a bad message.
 945             if (status != SecurityStatus.SECURE) {
 946                 mErrorList.add("Positive response has failed AUTHORITY rrset: " +
 947                                rrsets[i]);
 948                 m.setStatus(SecurityStatus.BOGUS);
 949
 950                 return;
 951             }
 952         }
 953
 954         log.trace("Successfully validated positive ANY response");
 955         m.setStatus(SecurityStatus.SECURE);
 956     }
 957
 958     /**
 959      * Validate a NOERROR/NODATA signed response -- a response that
 960      * has a NOERROR Rcode but no ANSWER section RRsets. This consists
 961      * of verifying the authority section rrsets and making certain
 962      * that the authority section NSEC/NSEC3s proves that the qname
 963      * does exist and the qtype doesn't.
 964      *
 965      * Note that by the time this method is called, the process of
 966      * finding the trusted DNSKEY rrset that signs this response must
 967      * already have been completed.
 968      *
 969      * @param response
 970      *            The response to validate.
 971      * @param request
 972      *            The request that generated this response.
 973      * @param key_rrset
 974      *            The trusted DNSKEY rrset that signs this response.
 975      */
 976     private void validateNodataResponse(SMessage     message,
 977                                         SRRset       key_rrset,
 978                                         List<String> errorList) {
 979         Name qname = message.getQName();
 980         int  qtype = message.getQType();
 981
 982         SMessage m = message;
 983
 984         // Since we are here, there must be nothing in the ANSWER
 985         // section to validate.
 986
 987         // validate the AUTHORITY section
 988         SRRset[] rrsets = m.getSectionRRsets(Section.AUTHORITY);
 989
 990         // If true, then the NODATA has been proven.
 991         boolean hasValidNSEC = false;
 992
 993         // for wildcard NODATA responses. This is the proven closest
 994         // encloser.
 995         Name ce = null;
 996
 997         // for wildcard NODATA responses. This is the wildcard NSEC.
 998         NSECRecord wc = null;
 999
1000         // A collection of NSEC3 RRs found in the authority section.
1001         List<NSEC3Record> nsec3s = null;
1002
1003         // The RRSIG signer field for the NSEC3 RRs.
1004         Name nsec3Signer = null;
1005
1006         for (int i = 0; i < rrsets.length; i++) {
1007             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
1008
1009             if (status != SecurityStatus.SECURE) {
1010                 mErrorList.add("NODATA response has failed AUTHORITY rrset: " +
1011                                rrsets[i]);
1012                 m.setStatus(SecurityStatus.BOGUS);
1013
1014                 return;
1015             }
1016
1017             // If we encounter an NSEC record, try to use it to prove NODATA.
1018             // This needs to handle the ENT NODATA case.
1019             if (rrsets[i].getType() == Type.NSEC) {
1020                 NSECRecord nsec = (NSECRecord) rrsets[i].first();
1021
1022                 if (ValUtils.nsecProvesNodata(nsec, qname, qtype)) {
1023                     hasValidNSEC = true;
1024
1025                     if (nsec.getName().isWild()) {
1026                         wc = nsec;
1027                     }
1028                 } else if (ValUtils.nsecProvesNameError(nsec, qname, rrsets[i].getSignerName())) {
1029                     ce = ValUtils.closestEncloser(qname, nsec);
1030                 }
1031             }
1032
1033             // Collect any NSEC3 records present.
1034             if (rrsets[i].getType() == Type.NSEC3) {
1035                 if (nsec3s == null) {
1036                     nsec3s = new ArrayList<NSEC3Record>();
1037                 }
1038
1039                 nsec3s.add((NSEC3Record) rrsets[i].first());
1040                 nsec3Signer = rrsets[i].getSignerName();
1041             }
1042         }
1043
1044         // check to see if we have a wildcard NODATA proof.
1045
1046         // The wildcard NODATA is 1 NSEC proving that qname does not
1047         // exists (and also proving what the closest encloser is), and
1048         // 1 NSEC showing the matching wildcard, which must be
1049         // *.closest_encloser.
1050         if ((ce != null) || (wc != null)) {
1051             try {
1052                 Name wc_name = new Name("*", ce);
1053
1054                 if (!wc_name.equals(wc.getName())) {
1055                     hasValidNSEC = false;
1056                 }
1057             } catch (TextParseException e) {
1058                 log.error(e);
1059             }
1060         }
1061
1062         NSEC3ValUtils.stripUnknownAlgNSEC3s(nsec3s);
1063
1064         if (!hasValidNSEC && (nsec3s != null) && (nsec3s.size() > 0)) {
1065             // try to prove NODATA with our NSEC3 record(s)
1066             hasValidNSEC = NSEC3ValUtils.proveNodata(nsec3s, qname, qtype,
1067                                                      nsec3Signer, errorList);
1068         }
1069
1070         if (!hasValidNSEC) {
1071             log.debug("NODATA response failed to prove NODATA " +
1072                       "status with NSEC/NSEC3");
1073             log.trace("Failed NODATA:\n" + m);
1074             mErrorList.add("NODATA response failed to prove NODATA status with NSEC/NSEC3");
1075             m.setStatus(SecurityStatus.BOGUS);
1076
1077             return;
1078         }
1079
1080         log.trace("successfully validated NODATA response.");
1081         m.setStatus(SecurityStatus.SECURE);
1082     }
1083
1084     /**
1085      * Validate a NAMEERROR signed response -- a response that has a
1086      * NXDOMAIN Rcode. This consists of verifying the authority
1087      * section rrsets and making certain that the authority section
1088      * NSEC proves that the qname doesn't exist and the covering
1089      * wildcard also doesn't exist..
1090      *
1091      * Note that by the time this method is called, the process of
1092      * finding the trusted DNSKEY rrset that signs this response must
1093      * already have been completed.
1094      *
1095      * @param response
1096      *            The response to validate.
1097      * @param request
1098      *            The request that generated this response.
1099      * @param key_rrset
1100      *            The trusted DNSKEY rrset that signs this response.
1101      */
1102     private void validateNameErrorResponse(SMessage message, SRRset key_rrset) {
1103         Name qname = message.getQName();
1104
1105         SMessage m = message;
1106
1107         if (message.getCount(Section.ANSWER) > 0) {
1108             log.warn("NameError response contained records in the ANSWER SECTION");
1109             mErrorList.add("NameError response contained records in the ANSWER SECTION");
1110             message.setStatus(SecurityStatus.INVALID);
1111
1112             return;
1113         }
1114
1115         // Validate the authority section -- all RRsets in the authority section
1116         // must be signed and valid.
1117         // In addition, the NSEC record(s) must prove the NXDOMAIN condition.
1118         boolean           hasValidNSEC   = false;
1119         boolean           hasValidWCNSEC = false;
1120         SRRset[]          rrsets         = m.getSectionRRsets(Section.AUTHORITY);
1121         List<NSEC3Record> nsec3s         = null;
1122         Name              nsec3Signer    = null;
1123
1124         for (int i = 0; i < rrsets.length; i++) {
1125             int status = mValUtils.verifySRRset(rrsets[i], key_rrset);
1126
1127             if (status != SecurityStatus.SECURE) {
1128                 mErrorList.add("NameError response has failed AUTHORITY rrset: " +
1129                                rrsets[i]);
1130                 m.setStatus(SecurityStatus.BOGUS);
1131
1132                 return;
1133             }
1134
1135             if (rrsets[i].getType() == Type.NSEC) {
1136                 NSECRecord nsec = (NSECRecord) rrsets[i].first();
1137
1138                 if (ValUtils.nsecProvesNameError(nsec, qname, rrsets[i].getSignerName())) {
1139                     hasValidNSEC = true;
1140                 }
1141
1142                 if (ValUtils.nsecProvesNoWC(nsec, qname, rrsets[i].getSignerName())) {
1143                     hasValidWCNSEC = true;
1144                 }
1145             }
1146
1147             if (rrsets[i].getType() == Type.NSEC3) {
1148                 if (nsec3s == null) {
1149                     nsec3s = new ArrayList<NSEC3Record>();
1150                 }
1151
1152                 nsec3s.add((NSEC3Record) rrsets[i].first());
1153                 nsec3Signer = rrsets[i].getSignerName();
1154             }
1155         }
1156
1157         NSEC3ValUtils.stripUnknownAlgNSEC3s(nsec3s);
1158
1159         if ((nsec3s != null) && (nsec3s.size() > 0)) {
1160             log.debug("Validating nxdomain: using NSEC3 records");
1161
1162             // Attempt to prove name error with nsec3 records.
1163             if (NSEC3ValUtils.allNSEC3sIgnoreable(nsec3s, key_rrset, mVerifier)) {
1164                 // log.debug("all NSEC3s were validated but ignored.");
1165                 m.setStatus(SecurityStatus.INSECURE);
1166
1167                 return;
1168             }
1169
1170             hasValidNSEC = NSEC3ValUtils.proveNameError(nsec3s, qname, nsec3Signer, mErrorList);
1171
1172             // Note that we assume that the NSEC3ValUtils proofs
1173             // encompass the wildcard part of the proof.
1174             hasValidWCNSEC = hasValidNSEC;
1175         }
1176
1177         // If the message fails to prove either condition, it is bogus.
1178         if (!hasValidNSEC) {
1179             mErrorList.add("NameError response has failed to prove qname does not exist");
1180             m.setStatus(SecurityStatus.BOGUS);
1181
1182             return;
1183         }
1184
1185         if (!hasValidWCNSEC) {
1186             mErrorList.add("NameError response has failed to prove covering wildcard does not exist");
1187             m.setStatus(SecurityStatus.BOGUS);
1188
1189             return;
1190         }
1191
1192         // Otherwise, we consider the message secure.
1193         log.trace("successfully validated NAME ERROR response.");
1194         m.setStatus(SecurityStatus.SECURE);
1195     }
1196
1197     public byte validateMessage(SMessage message, Name zone) {
1198         mErrorList.clear();
1199         if (!zone.isAbsolute()) {
1200             try {
1201                 zone = Name.concatenate(zone, Name.root);
1202             } catch (NameTooLongException e) {
1203                 log.error(e);
1204
1205                 return SecurityStatus.UNCHECKED;
1206             }
1207         }
1208
1209         // It is unclear if we should actually normalize our
1210         // responses Instead, maybe we should just fail if they are
1211         // not normal?
1212         message = normalize(message);
1213
1214         if (!needsValidation(message)) {
1215             return SecurityStatus.UNCHECKED;
1216         }
1217
1218         SRRset key_rrset = findKeys(message);
1219
1220         if (key_rrset == null) {
1221             mErrorList.add("Failed to find matching DNSKEYs for the response");
1222             return SecurityStatus.BOGUS;
1223         }
1224
1225         ValUtils.ResponseType subtype = ValUtils.classifyResponse(message, zone);
1226
1227         switch (subtype) {
1228         case POSITIVE:
1229             log.trace("Validating a positive response");
1230             validatePositiveResponse(message, key_rrset);
1231             break;
1232
1233         case REFERRAL:
1234             validateReferral(message, key_rrset);
1235             break;
1236
1237         case NODATA:
1238             log.trace("Validating a NODATA response");
1239             validateNodataResponse(message, key_rrset, mErrorList);
1240             break;
1241
1242         case NAMEERROR:
1243             log.trace("Validating a NXDOMAIN response");
1244             validateNameErrorResponse(message, key_rrset);
1245             break;
1246
1247         case CNAME:
1248             log.trace("Validating a CNAME response");
1249             validateCNAMEResponse(message, key_rrset);
1250             break;
1251
1252         case ANY:
1253             log.trace("Validating a positive ANY response");
1254             validateAnyResponse(message, key_rrset);
1255             break;
1256
1257         default:
1258             log.error("unhandled response subtype: " + subtype);
1259         }
1260
1261         return message.getSecurityStatus().getStatus();
1262     }
1263
1264     public byte validateMessage(Message message, String zone)
1265         throws TextParseException {
1266         SMessage sm = new SMessage(message);
1267         Name     z  = Name.fromString(zone);
1268
1269         return validateMessage(sm, z);
1270     }
1271
1272     public byte validateMessage(byte[] messagebytes, String zone)
1273         throws IOException {
1274         Message message = new Message(messagebytes);
1275         return validateMessage(message, zone);
1276     }
1277
1278     public byte validateMessage(String b64messagebytes, String zone)
1279         throws IOException {
1280         byte[] messagebytes = base64.fromString(b64messagebytes);
1281         return validateMessage(messagebytes, zone);
1282     }
1283
1284     public List<String> listTrustedKeys() {
1285         return mTrustedKeys.listTrustAnchors();
1286     }
1287
1288     public List<String> getErrorList() {
1289         return mErrorList;
1290     }
1291  }