1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "net/base/dnssec_chain_verifier.h"
6
7#include "base/logging.h"
8#include "base/memory/scoped_ptr.h"
9#include "base/sha1.h"
10#include "base/string_util.h"
11#include "crypto/sha2.h"
12#include "net/base/dns_util.h"
13#include "net/base/dnssec_keyset.h"
14
15// We don't have a location for the spec yet, so we'll include it here until it
16// finds a better home.
17
18/*
19When connecting to a host www.example.com, www.example.com may present a certificate which includes a DNSSEC chain embedded in it. The aim of the embedded chain is to prove that the fingerprint of the public key is valid DNSSEC data. This is achieved by proving a CERT record for the target domain.
20
21Initially, the target domain is constructed by prepending _ssl. For example, the initial target domain for www.example.com is _ssl.www.example.com.
22
23A DNSSEC chain verifier can be in one of two states: entering a zone, or within a zone. Initially, the verifier is entering the root zone.
24
25When entering a zone, the verifier reads the following structure:
26
27uint8 entryKey
28uint16 signature length:
29  // See RRSIG RDATA in RFC 4043 for details
30  uint8 algorithm
31  uint8 labels
32  uint32 ttl
33  uint32 expires
34  uint32 begins
35  uint16 keyid
36  []byte signature
37uint8 numKeys
38// for each key:
39uint16 key length:
40  []byte DNSKEY RDATA
41
42|entryKey| indexes the array of DNSKEYs and MUST be less than |numKeys|. The indexed DNSKEY MUST be a key that the verifier trusts, either because it's the long-term root key, or because of a previously presented DS signature.
43
44If only a trusted key is needed within this zone, then the signature length MAY be zero. In which case, |entryKey| MUST be 0 and |numKeys| MUST be 1.
45
46After processing this data, the verifier trusts one or more keys for this zone.
47
48When within a zone, the verifier reads the following structure:
49
50dnsName name
51uint16 RRtype
52
53|name| is in DNS format (a series of 8-bit, length prefixed strings). No DNS name compression is permitted.
54
55|name| must be closer to the current target domain than the current zone. Here, 'closer' is defined as a greater number of matching labels when comparing right to left.
56
57|RRtype| may be either DS, CERT or CNAME:
58
59DS: this indicates a zone transition to a new zone named |name|. The verifier reads the following structure:
60  uint16 signature length:
61    ... (see above for the signature structure)
62  uint8 num_ds
63  // for each DS:
64    uint8 digest_type
65    uint16 length
66    []byte DS DATA
67
68The verifier is now entering the named zone. It reads ahead and extracts the entry key from the zone entry data and synthisises a DS record for the given digest type and verifies the signature. It then enters the next zone.
69
70
71CERT: |name| MUST match the target domain. The verifier reads the following structure:
72  uint16 signature length:
73    ... (see above for the signature structure)
74  []byte CERT RDATA
75
76(The format of the CERT RDATA isn't specified here, but the verifier must be able to extract a public key fingerprint in order to validate the original certificate.)
77
78This terminates the verification. There MUST NOT be any more data in the chain.
79
80
81CNAME: |name| MUST match the target domain. The verifier reads the following structure:
82  uint16 signature length:
83    ... (see above for the signature structure)
84  []byte CNAME RDATA
85
86This replaces the target domain with a new domain. The new domain is the target of the CNAME with _ssl prepended. The verifier is now in the zone that is the greatest common ancestor of the old and new target domains. (For example, when switching from _ssl.www.example.com to _ssl.www.example2.com, the verifier is now in com.)
87
88
89Example for www.google.com:
90
91The target domain is www.google.com.
92
93The verifier enters ., it already trusts the long-term root key and both root keys are presented in order to extend the trust to the smaller root key.
94
95A DS signature is presented for .com. The verifier is now entering .com.
96
97All four .com keys are presented. The verifier is now in .com.
98
99A DS signature is presented for google.com. The verifier is now entering google.com
100
101As google.com contains only a single DNSKEY, it is included without a signature. The verifier is now in google.com.
102
103A CNAME is presented for www.google.com pointing to www.l.google.com. The target domain is now www.l.google.com. The verifier is now in google.com.
104
105A DS signature is presented for l.google.com. The verifier is now entering l.google.com.
106
107As l.google.com contains only a single DNSKEY, it is included without a signature. The verifier is now in l.google.com.
108
109A CERT record is presented for www.l.google.com. The verification is complete.
110*/
111
112namespace {
113
114// This is the 2048-bit DNS root key: http://www.iana.org/dnssec
115// 19036 8 2 49AAC11D7B6F6446702E54A1607371607A1A41855200FD2CE1CDDE32F24E8FB5
116const unsigned char kRootKey[] = {
117 0x01, 0x01, 0x03, 0x08, 0x03, 0x01, 0x00, 0x01, 0xa8, 0x00, 0x20, 0xa9, 0x55,
118 0x66, 0xba, 0x42, 0xe8, 0x86, 0xbb, 0x80, 0x4c, 0xda, 0x84, 0xe4, 0x7e, 0xf5,
119 0x6d, 0xbd, 0x7a, 0xec, 0x61, 0x26, 0x15, 0x55, 0x2c, 0xec, 0x90, 0x6d, 0x21,
120 0x16, 0xd0, 0xef, 0x20, 0x70, 0x28, 0xc5, 0x15, 0x54, 0x14, 0x4d, 0xfe, 0xaf,
121 0xe7, 0xc7, 0xcb, 0x8f, 0x00, 0x5d, 0xd1, 0x82, 0x34, 0x13, 0x3a, 0xc0, 0x71,
122 0x0a, 0x81, 0x18, 0x2c, 0xe1, 0xfd, 0x14, 0xad, 0x22, 0x83, 0xbc, 0x83, 0x43,
123 0x5f, 0x9d, 0xf2, 0xf6, 0x31, 0x32, 0x51, 0x93, 0x1a, 0x17, 0x6d, 0xf0, 0xda,
124 0x51, 0xe5, 0x4f, 0x42, 0xe6, 0x04, 0x86, 0x0d, 0xfb, 0x35, 0x95, 0x80, 0x25,
125 0x0f, 0x55, 0x9c, 0xc5, 0x43, 0xc4, 0xff, 0xd5, 0x1c, 0xbe, 0x3d, 0xe8, 0xcf,
126 0xd0, 0x67, 0x19, 0x23, 0x7f, 0x9f, 0xc4, 0x7e, 0xe7, 0x29, 0xda, 0x06, 0x83,
127 0x5f, 0xa4, 0x52, 0xe8, 0x25, 0xe9, 0xa1, 0x8e, 0xbc, 0x2e, 0xcb, 0xcf, 0x56,
128 0x34, 0x74, 0x65, 0x2c, 0x33, 0xcf, 0x56, 0xa9, 0x03, 0x3b, 0xcd, 0xf5, 0xd9,
129 0x73, 0x12, 0x17, 0x97, 0xec, 0x80, 0x89, 0x04, 0x1b, 0x6e, 0x03, 0xa1, 0xb7,
130 0x2d, 0x0a, 0x73, 0x5b, 0x98, 0x4e, 0x03, 0x68, 0x73, 0x09, 0x33, 0x23, 0x24,
131 0xf2, 0x7c, 0x2d, 0xba, 0x85, 0xe9, 0xdb, 0x15, 0xe8, 0x3a, 0x01, 0x43, 0x38,
132 0x2e, 0x97, 0x4b, 0x06, 0x21, 0xc1, 0x8e, 0x62, 0x5e, 0xce, 0xc9, 0x07, 0x57,
133 0x7d, 0x9e, 0x7b, 0xad, 0xe9, 0x52, 0x41, 0xa8, 0x1e, 0xbb, 0xe8, 0xa9, 0x01,
134 0xd4, 0xd3, 0x27, 0x6e, 0x40, 0xb1, 0x14, 0xc0, 0xa2, 0xe6, 0xfc, 0x38, 0xd1,
135 0x9c, 0x2e, 0x6a, 0xab, 0x02, 0x64, 0x4b, 0x28, 0x13, 0xf5, 0x75, 0xfc, 0x21,
136 0x60, 0x1e, 0x0d, 0xee, 0x49, 0xcd, 0x9e, 0xe9, 0x6a, 0x43, 0x10, 0x3e, 0x52,
137 0x4d, 0x62, 0x87, 0x3d,
138};
139
140// kRootKeyID is the key id for kRootKey
141const uint16 kRootKeyID = 19036;
142
143// CountLabels returns the number of DNS labels in |a|, which must be in DNS,
144// length-prefixed form.
145unsigned CountLabels(base::StringPiece a) {
146  for (unsigned c = 0;; c++) {
147    if (!a.size())
148      return c;
149    uint8 label_len = a.data()[0];
150    a.remove_prefix(1);
151    DCHECK_GE(a.size(), label_len);
152    a.remove_prefix(label_len);
153  }
154}
155
156// RemoveLeadingLabel removes the first label from |a|, which must be in DNS,
157// length-prefixed form.
158void RemoveLeadingLabel(base::StringPiece* a) {
159  if (!a->size())
160    return;
161  uint8 label_len = a->data()[0];
162  a->remove_prefix(1);
163  a->remove_prefix(label_len);
164}
165
166}  // namespace
167
168namespace net {
169
170struct DNSSECChainVerifier::Zone {
171  base::StringPiece name;
172  // The number of consecutive labels which |name| shares with |target_|,
173  // counting right-to-left from the root.
174  unsigned matching_labels;
175  DNSSECKeySet trusted_keys;
176  Zone* prev;
177};
178
179DNSSECChainVerifier::DNSSECChainVerifier(const std::string& target,
180                                         const base::StringPiece& chain)
181    : current_zone_(NULL),
182      target_(target),
183      chain_(chain),
184      ignore_timestamps_(false),
185      valid_(false),
186      already_entered_zone_(false),
187      rrtype_(0) {
188}
189
190DNSSECChainVerifier::~DNSSECChainVerifier() {
191  for (std::vector<void*>::iterator
192       i = scratch_pool_.begin(); i != scratch_pool_.end(); i++) {
193    free(*i);
194  }
195
196  Zone* next;
197  for (Zone* cur = current_zone_; cur; cur = next) {
198    next = cur->prev;
199    delete cur;
200  }
201}
202
203void DNSSECChainVerifier::IgnoreTimestamps() {
204  ignore_timestamps_ = true;
205}
206
207DNSSECChainVerifier::Error DNSSECChainVerifier::Verify() {
208  Error err;
209
210  err = EnterRoot();
211  if (err != OK)
212    return err;
213
214  for (;;) {
215    base::StringPiece next_name;
216    err = LeaveZone(&next_name);
217    if (err != OK)
218      return err;
219    if (valid_) {
220      if (!chain_.empty())
221        return BAD_DATA;  // no trailing data allowed.
222      break;
223    }
224
225    if (already_entered_zone_) {
226      already_entered_zone_ = false;
227    } else {
228      err = EnterZone(next_name);
229      if (err != OK)
230        return err;
231    }
232  }
233
234  return OK;
235}
236
237uint16 DNSSECChainVerifier::rrtype() const {
238  DCHECK(valid_);
239  return rrtype_;
240}
241
242const std::vector<base::StringPiece>& DNSSECChainVerifier::rrdatas() const {
243  DCHECK(valid_);
244  return rrdatas_;
245}
246
247// static
248std::map<std::string, std::string>
249DNSSECChainVerifier::ParseTLSTXTRecord(base::StringPiece rrdata) {
250  std::map<std::string, std::string> ret;
251
252  if (rrdata.empty())
253    return ret;
254
255  std::string txt;
256  txt.reserve(rrdata.size());
257
258  // TXT records are a series of 8-bit length prefixed substrings that we
259  // concatenate into |txt|
260  while (!rrdata.empty()) {
261    unsigned len = rrdata[0];
262    if (len == 0 || len + 1 > rrdata.size())
263      return ret;
264    txt.append(rrdata.data() + 1, len);
265    rrdata.remove_prefix(len + 1);
266  }
267
268  // We append a space to |txt| to make the parsing code, below, cleaner.
269  txt.append(" ");
270
271  // RECORD = KV (' '+ KV)*
272  // KV = KEY '=' VALUE
273  // KEY = [a-zA-Z0-9]+
274  // VALUE = [^ \0]*
275
276  enum State {
277    STATE_KEY,
278    STATE_VALUE,
279    STATE_SPACE,
280  };
281
282  State state = STATE_KEY;
283
284  std::map<std::string, std::string> m;
285
286  unsigned start = 0;
287  std::string key;
288
289  for (unsigned i = 0; i < txt.size(); i++) {
290    char c = txt[i];
291    if (c == 0)
292      return ret;  // NUL values are never allowed.
293
294    switch (state) {
295      case STATE_KEY:
296        if (c == '=') {
297          if (i == start)
298            return ret;  // zero length keys are not allowed.
299          key = txt.substr(start, i - start);
300          start = i + 1;
301          state = STATE_VALUE;
302          continue;
303        }
304        if (!IsAsciiAlpha(c) && !IsAsciiDigit(c))
305          return ret;  // invalid key value
306        break;
307      case STATE_VALUE:
308        if (c == ' ') {
309          if (m.find(key) == m.end())
310            m.insert(make_pair(key, txt.substr(start, i - start)));
311          state = STATE_SPACE;
312          continue;
313        }
314        break;
315      case STATE_SPACE:
316        if (c != ' ') {
317          start = i;
318          i--;
319          state = STATE_KEY;
320          continue;
321        }
322        break;
323      default:
324        NOTREACHED();
325        return ret;
326    }
327  }
328
329  if (state != STATE_SPACE)
330    return ret;
331
332  ret.swap(m);
333  return ret;
334}
335
336// MatchingLabels returns the number of labels which |a| and |b| share,
337// counting right-to-left from the root. |a| and |b| must be DNS,
338// length-prefixed names. All names match at the root label, so this always
339// returns a value >= 1.
340
341// static
342unsigned DNSSECChainVerifier::MatchingLabels(base::StringPiece a,
343                                             base::StringPiece b) {
344  unsigned c = 0;
345  unsigned a_labels = CountLabels(a);
346  unsigned b_labels = CountLabels(b);
347
348  while (a_labels > b_labels) {
349    RemoveLeadingLabel(&a);
350    a_labels--;
351  }
352  while (b_labels > a_labels) {
353    RemoveLeadingLabel(&b);
354    b_labels--;
355  }
356
357  for (;;) {
358    if (!a.size()) {
359      if (!b.size())
360        return c;
361      return 0;
362    }
363    if (!b.size())
364      return 0;
365    uint8 a_length = a.data()[0];
366    a.remove_prefix(1);
367    uint8 b_length = b.data()[0];
368    b.remove_prefix(1);
369    DCHECK_GE(a.size(), a_length);
370    DCHECK_GE(b.size(), b_length);
371
372    if (a_length == b_length && memcmp(a.data(), b.data(), a_length) == 0) {
373      c++;
374    } else {
375      c = 0;
376    }
377
378    a.remove_prefix(a_length);
379    b.remove_prefix(b_length);
380  }
381}
382
383// U8 reads, and removes, a single byte from |chain_|
384bool DNSSECChainVerifier::U8(uint8* v) {
385  if (chain_.size() < 1)
386    return false;
387  *v = chain_[0];
388  chain_.remove_prefix(1);
389  return true;
390}
391
392// U16 reads, and removes, a big-endian uint16 from |chain_|
393bool DNSSECChainVerifier::U16(uint16* v) {
394  if (chain_.size() < 2)
395    return false;
396  const uint8* data = reinterpret_cast<const uint8*>(chain_.data());
397  *v = static_cast<uint16>(data[0]) << 8 |
398       static_cast<uint16>(data[1]);
399  chain_.remove_prefix(2);
400  return true;
401}
402
403// VariableLength16 reads, and removes, a big-endian, uint16, length-prefixed
404// chunk from |chain_|
405bool DNSSECChainVerifier::VariableLength16(base::StringPiece* v) {
406  uint16 length;
407  if (!U16(&length))
408    return false;
409  if (chain_.size() < length)
410    return false;
411  *v = chain_.substr(0, length);
412  chain_.remove_prefix(length);
413  return true;
414}
415
416// ReadName reads, and removes, an 8-bit length prefixed DNS name from |chain_|
417bool DNSSECChainVerifier::ReadName(base::StringPiece* v) {
418  base::StringPiece saved = chain_;
419  unsigned length = 0;
420  static const uint8 kMaxDNSLabelLen = 63;
421
422  for (;;) {
423    if (chain_.size() < 1)
424      return false;
425    uint8 label_len = chain_.data()[0];
426    chain_.remove_prefix(1);
427    if (label_len > kMaxDNSLabelLen)
428      return false;
429    length += 1 + label_len;
430
431    if (label_len == 0)
432      break;
433
434    if (chain_.size() < label_len)
435      return false;
436    chain_.remove_prefix(label_len);
437  }
438
439  *v = base::StringPiece(saved.data(), length);
440  return true;
441}
442
443// ReadAheadEntryKey returns the entry key when |chain_| is positioned at the
444// start of a zone.
445bool DNSSECChainVerifier::ReadAheadEntryKey(base::StringPiece* v) {
446  base::StringPiece saved = chain_;
447
448  uint8 entry_key;
449  base::StringPiece sig;
450  if (!U8(&entry_key) ||
451      !VariableLength16(&sig)) {
452    return false;
453  }
454
455  if (!ReadAheadKey(v, entry_key))
456    return false;
457  chain_ = saved;
458  return true;
459}
460
461// ReadAheadKey returns the entry key when |chain_| is positioned at the start
462// of a list of keys.
463bool DNSSECChainVerifier::ReadAheadKey(base::StringPiece* v, uint8 entry_key) {
464  base::StringPiece saved = chain_;
465
466  uint8 num_keys;
467  if (!U8(&num_keys))
468    return false;
469
470  for (unsigned i = 0; i < num_keys; i++) {
471    if (!VariableLength16(v))
472      return false;
473    if (i == entry_key) {
474      chain_ = saved;
475      return true;
476    }
477  }
478
479  return false;
480}
481
482bool DNSSECChainVerifier::ReadDNSKEYs(std::vector<base::StringPiece>* out,
483                                      bool is_root) {
484  uint8 num_keys;
485  if (!U8(&num_keys))
486    return false;
487
488  for (unsigned i = 0; i < num_keys; i++) {
489    base::StringPiece key;
490    if (!VariableLength16(&key))
491      return false;
492    if (key.empty()) {
493      if (!is_root)
494        return false;
495      key = base::StringPiece(reinterpret_cast<const char*>(kRootKey),
496                              sizeof(kRootKey));
497    }
498
499    out->push_back(key);
500  }
501
502  return true;
503}
504
505// DigestKey calculates a DS digest as specified in
506// http://tools.ietf.org/html/rfc4034#section-5.1.4
507//   name: the DNS form name of the key
508//   dnskey: the DNSKEY's RRDATA
509//   digest_type: see http://tools.ietf.org/html/rfc4034#appendix-A.2
510//   keyid: the key's id
511//   algorithm: see http://tools.ietf.org/html/rfc4034#appendix-A.1
512bool DNSSECChainVerifier::DigestKey(base::StringPiece* out,
513                                    const base::StringPiece& name,
514                                    const base::StringPiece& dnskey,
515                                    uint8 digest_type,
516                                    uint16 keyid,
517                                    uint8 algorithm) {
518  std::string temp;
519  uint8 temp2[crypto::SHA256_LENGTH];
520  const uint8* digest;
521  unsigned digest_len;
522
523  std::string input = name.as_string() + dnskey.as_string();
524
525  if (digest_type == kDNSSEC_SHA1) {
526    temp = base::SHA1HashString(input);
527    digest = reinterpret_cast<const uint8*>(temp.data());
528    digest_len = base::SHA1_LENGTH;
529  } else if (digest_type == kDNSSEC_SHA256) {
530    crypto::SHA256HashString(input, temp2, sizeof(temp2));
531    digest = temp2;
532    digest_len = sizeof(temp2);
533  } else {
534    return false;
535  }
536
537  uint8* output = static_cast<uint8*>(malloc(4 + digest_len));
538  scratch_pool_.push_back(output);
539  output[0] = static_cast<uint8>(keyid >> 8);
540  output[1] = static_cast<uint8>(keyid);
541  output[2] = algorithm;
542  output[3] = digest_type;
543  memcpy(output + 4, digest, digest_len);
544  *out = base::StringPiece(reinterpret_cast<char*>(output), 4 + digest_len);
545  return true;
546}
547
548// EnterRoot enters the root zone at the beginning of the chain. This is
549// special because no DS record lead us here: we have to validate that the
550// entry key is the DNS root key that we already know and trust. Additionally,
551// for the root zone only, the keyid of the entry key is prepended to the data.
552DNSSECChainVerifier::Error DNSSECChainVerifier::EnterRoot() {
553  uint16 root_keyid;
554
555  if (!U16(&root_keyid))
556    return BAD_DATA;
557
558  if (root_keyid != kRootKeyID)
559    return UNKNOWN_ROOT_KEY;
560
561  base::StringPiece root_key;
562  if (!ReadAheadEntryKey(&root_key))
563    return BAD_DATA;
564
565  // If the root key is given then it must match the expected root key exactly.
566  if (root_key.size()) {
567    if (root_key.size() != sizeof(kRootKey) ||
568        memcmp(root_key.data(), kRootKey, sizeof(kRootKey))) {
569      return UNKNOWN_ROOT_KEY;
570    }
571  }
572
573  base::StringPiece root("", 1);
574  return EnterZone(root);
575}
576
577// EnterZone enters a new DNS zone. On entry it's assumed that the entry key
578// has been validated.
579DNSSECChainVerifier::Error DNSSECChainVerifier::EnterZone(
580    const base::StringPiece& zone) {
581  Zone* prev = current_zone_;
582  current_zone_ = new Zone;
583  current_zone_->prev = prev;
584  current_zone_->name = zone;
585  current_zone_->matching_labels = MatchingLabels(target_, zone);
586  if (ignore_timestamps_)
587    current_zone_->trusted_keys.IgnoreTimestamps();
588
589  uint8 entry_key;
590  base::StringPiece sig;
591  if (!U8(&entry_key) ||
592      !VariableLength16(&sig)) {
593    return BAD_DATA;
594  }
595
596  base::StringPiece key;
597  if (!ReadAheadKey(&key, entry_key))
598    return BAD_DATA;
599
600  if (zone.size() == 1 && key.empty()) {
601    // If a key is omitted in the root zone then it's the root key.
602    key = base::StringPiece(reinterpret_cast<const char*>(kRootKey),
603                            sizeof(kRootKey));
604  }
605  if (!current_zone_->trusted_keys.AddKey(key))
606    return BAD_DATA;
607
608  std::vector<base::StringPiece> dnskeys;
609  if (!ReadDNSKEYs(&dnskeys, zone.size() == 1))
610    return BAD_DATA;
611
612  if (sig.empty()) {
613    // An omitted signature on the keys means that only the entry key is used.
614    if (dnskeys.size() > 1 || entry_key != 0)
615      return BAD_DATA;
616    return OK;
617  }
618
619  if (!current_zone_->trusted_keys.CheckSignature(
620          zone, zone, sig, kDNS_DNSKEY, dnskeys)) {
621    return BAD_SIGNATURE;
622  }
623
624  // Add all the keys as trusted.
625  for (unsigned i = 0; i < dnskeys.size(); i++) {
626    if (i == entry_key)
627      continue;
628    current_zone_->trusted_keys.AddKey(dnskeys[i]);
629  }
630
631  return OK;
632}
633
634// LeaveZone transitions out of the current zone, either by following DS
635// records to validate the entry key of the next zone, or because the final
636// resource records are given.
637DNSSECChainVerifier::Error DNSSECChainVerifier::LeaveZone(
638    base::StringPiece* next_name) {
639  base::StringPiece sig;
640  uint16 rrtype;
641  Error err;
642
643  if (!ReadName(next_name) ||
644      !U16(&rrtype) ||
645      !VariableLength16(&sig)) {
646    return BAD_DATA;
647  }
648
649  std::vector<base::StringPiece> rrdatas;
650
651  if (rrtype == kDNS_DS) {
652    err = ReadDSSet(&rrdatas, *next_name);
653  } else if (rrtype == kDNS_CERT || rrtype == kDNS_TXT) {
654    err = ReadGenericRRs(&rrdatas);
655  } else if (rrtype == kDNS_CNAME) {
656    err = ReadCNAME(&rrdatas);
657  } else {
658    return UNKNOWN_TERMINAL_RRTYPE;
659  }
660  if (err != OK)
661    return err;
662
663  if (!current_zone_->trusted_keys.CheckSignature(
664      *next_name, current_zone_->name, sig, rrtype, rrdatas)) {
665    return BAD_SIGNATURE;
666  }
667
668  if (rrtype == kDNS_DS) {
669    // If we are transitioning to another zone then the next zone must be
670    // 'closer' to the target than the current zone.
671    if (MatchingLabels(target_, *next_name) <= current_zone_->matching_labels)
672      return OFF_COURSE;
673  } else if (rrtype == kDNS_CERT || rrtype == kDNS_TXT) {
674    // If this is the final entry in the chain then the name must match target_
675    if (next_name->size() != target_.size() ||
676        memcmp(next_name->data(), target_.data(), target_.size())) {
677      return BAD_TARGET;
678    }
679    rrdatas_ = rrdatas;
680    valid_ = true;
681    rrtype_ = rrtype;
682  } else if (rrtype == kDNS_CNAME) {
683    // A CNAME must match the current target. Then we update the current target
684    // and unwind the chain to the closest common ancestor.
685    if (next_name->size() != target_.size() ||
686        memcmp(next_name->data(), target_.data(), target_.size())) {
687      return BAD_TARGET;
688    }
689    DCHECK_EQ(1u, rrdatas.size());
690    target_ = rrdatas[0].as_string();
691    // We unwind the zones until the current zone is a (non-strict) subset of
692    // the new target.
693    while (MatchingLabels(target_, current_zone_->name) <
694           CountLabels(current_zone_->name)) {
695      Zone* prev = current_zone_->prev;
696      delete current_zone_;
697      current_zone_ = prev;
698      if (!current_zone_) {
699        NOTREACHED();
700        return BAD_DATA;
701      }
702    }
703    already_entered_zone_ = true;
704  } else {
705    NOTREACHED();
706    return UNKNOWN_TERMINAL_RRTYPE;
707  }
708
709  return OK;
710}
711
712// ReadDSSet reads a set of DS records from the chain. DS records which are
713// omitted are calculated from the entry key of the next zone.
714DNSSECChainVerifier::Error DNSSECChainVerifier::ReadDSSet(
715    std::vector<base::StringPiece>* rrdatas,
716    const base::StringPiece& next_name) {
717  uint8 num_ds;
718  if (!U8(&num_ds))
719    return BAD_DATA;
720  scoped_array<uint8> digest_types(new uint8[num_ds]);
721  // lookahead[i] is true iff the i'th DS record was empty and needs to be
722  // computed by hashing the next entry key.
723  scoped_array<bool> lookahead(new bool[num_ds]);
724  rrdatas->resize(num_ds);
725
726  for (unsigned i = 0; i < num_ds; i++) {
727    uint8 digest_type;
728    base::StringPiece digest;
729    if (!U8(&digest_type) ||
730        !VariableLength16(&digest)) {
731      return BAD_DATA;
732    }
733
734    digest_types[i] = digest_type;
735    lookahead[i] = digest.empty();
736    if (!digest.empty())
737      (*rrdatas)[i] = digest;
738  }
739
740  base::StringPiece next_entry_key;
741  if (!ReadAheadEntryKey(&next_entry_key))
742    return BAD_DATA;
743  if (next_entry_key.size() < 4)
744    return BAD_DATA;
745  uint16 keyid = DNSSECKeySet::DNSKEYToKeyID(next_entry_key);
746  uint8 algorithm = next_entry_key[3];
747
748  bool good = false;
749  for (unsigned i = 0; i < num_ds; i++) {
750    base::StringPiece digest;
751    bool have_digest = false;
752    if (DigestKey(&digest, next_name, next_entry_key, digest_types[i],
753                  keyid, algorithm)) {
754      have_digest = true;
755    }
756
757    if (lookahead[i]) {
758      // If we needed to fill in one of the DS entries, but we can't calculate
759      // that type of digest, then we can't continue.
760      if (!have_digest)
761        return UNKNOWN_DIGEST;
762      (*rrdatas)[i] = digest;
763      good = true;
764    } else {
765      const base::StringPiece& given_digest = (*rrdatas)[i];
766      if (have_digest &&
767          given_digest.size() == digest.size() &&
768          memcmp(given_digest.data(), digest.data(), digest.size()) == 0) {
769        good = true;
770      }
771    }
772  }
773
774  if (!good) {
775    // We didn't calculate or match any of the digests.
776    return NO_DS_LINK;
777  }
778
779  return OK;
780}
781
782DNSSECChainVerifier::Error DNSSECChainVerifier::ReadGenericRRs(
783    std::vector<base::StringPiece>* rrdatas) {
784  uint8 num_rrs;
785  if (!U8(&num_rrs))
786    return BAD_DATA;
787  rrdatas->resize(num_rrs);
788
789  for (unsigned i = 0; i < num_rrs; i++) {
790    base::StringPiece rrdata;
791    if (!VariableLength16(&rrdata))
792      return BAD_DATA;
793    (*rrdatas)[i] = rrdata;
794  }
795
796  return OK;
797}
798
799DNSSECChainVerifier::Error DNSSECChainVerifier::ReadCNAME(
800    std::vector<base::StringPiece>* rrdatas) {
801  base::StringPiece name;
802  if (!ReadName(&name))
803    return BAD_DATA;
804
805  rrdatas->resize(1);
806  (*rrdatas)[0] = name;
807  return OK;
808}
809
810}  // namespace net
811