Add support for building proofs using a local recursive resolver
[dnssec-prover] / src / lib.rs
index 740879d62c78869682bbbb3b8c97b922f8397a53..14104e50d6b534e34383d7fbe224013fc9db2d8f 100644 (file)
 //! It is no-std (but requires `alloc`) and seeks to have minimal dependencies and a reasonably
 //! conservative MSRV policy, allowing it to be used in as many places as possible.
 
-#![allow(deprecated)] // XXX
 #![deny(missing_docs)]
 
-#![no_std]
+#![cfg_attr(not(feature = "std"), no_std)]
 extern crate alloc;
 
 use alloc::vec::Vec;
 use alloc::vec;
-use alloc::string::String;
-use alloc::borrow::ToOwned;
 
 use ring::signature;
 
+pub mod rr;
+use rr::*;
+
+mod ser;
+use ser::{bytes_to_rsa_pk, parse_rr, write_name};
+
+#[cfg(feature = "std")]
+pub mod query;
+
 /// Gets the trusted root anchors
 ///
 /// These are available at <https://data.iana.org/root-anchors/root-anchors.xml>
@@ -48,239 +54,6 @@ pub fn root_hints() -> Vec<DS> {
        res
 }
 
-/// A valid domain name.
-///
-/// It must end with a ".", be no longer than 255 bytes, consist of only printable ASCII
-/// characters and each label may be no longer than 63 bytes.
-#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
-pub struct Name(String);
-impl core::ops::Deref for Name {
-       type Target = str;
-       fn deref(&self) -> &str { &self.0 }
-}
-impl TryFrom<String> for Name {
-       type Error = ();
-       fn try_from(s: String) -> Result<Name, ()> {
-               if s.is_empty() { return Err(()); }
-               if *s.as_bytes().last().unwrap_or(&0) != b"."[0] { return Err(()); }
-               if s.len() > 255 { return Err(()); }
-               if s.chars().any(|c| !c.is_ascii_graphic() && c != '.' && c != '-') { return Err(()); }
-               for label in s.split(".") {
-                       if label.len() > 63 { return Err(()); }
-               }
-
-               Ok(Name(s))
-       }
-}
-impl TryFrom<&str> for Name {
-       type Error = ();
-       fn try_from(s: &str) -> Result<Name, ()> {
-               Self::try_from(s.to_owned())
-       }
-}
-
-#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
-/// A supported Resource Record
-///
-/// Note that we only currently support a handful of RR types as needed to generate and validate
-/// TXT or TLSA record proofs.
-pub enum RR {
-       /// A text resource record
-       Txt(Txt),
-       /// A TLS Certificate Association resource record
-       TLSA(TLSA),
-       /// A DNS (Public) Key resource record
-       DnsKey(DnsKey),
-       /// A Delegated Signer resource record
-       DS(DS),
-       /// A Resource Record Signature record
-       RRSig(RRSig),
-}
-impl RR {
-       /// Gets the name this record refers to.
-       pub fn name(&self) -> &Name {
-               match self {
-                       RR::Txt(rr) => &rr.name,
-                       RR::TLSA(rr) => &rr.name,
-                       RR::DnsKey(rr) => &rr.name,
-                       RR::DS(rr) => &rr.name,
-                       RR::RRSig(rr) => &rr.name,
-               }
-       }
-       fn ty(&self) -> u16 {
-               match self {
-                       RR::Txt(_) => Txt::TYPE,
-                       RR::TLSA(_) => TLSA::TYPE,
-                       RR::DnsKey(_) => DnsKey::TYPE,
-                       RR::DS(_) => DS::TYPE,
-                       RR::RRSig(_) => RRSig::TYPE,
-               }
-       }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               match self {
-                       RR::Txt(rr) => StaticRecord::write_u16_len_prefixed_data(rr, out),
-                       RR::TLSA(rr) => StaticRecord::write_u16_len_prefixed_data(rr, out),
-                       RR::DnsKey(rr) => StaticRecord::write_u16_len_prefixed_data(rr, out),
-                       RR::DS(rr) => StaticRecord::write_u16_len_prefixed_data(rr, out),
-                       RR::RRSig(rr) => StaticRecord::write_u16_len_prefixed_data(rr, out),
-               }
-       }
-}
-impl From<Txt> for RR { fn from(txt: Txt) -> RR { RR::Txt(txt) } }
-impl From<TLSA> for RR { fn from(tlsa: TLSA) -> RR { RR::TLSA(tlsa) } }
-impl From<DnsKey> for RR { fn from(dnskey: DnsKey) -> RR { RR::DnsKey(dnskey) } }
-impl From<DS> for RR { fn from(ds: DS) -> RR { RR::DS(ds) } }
-impl From<RRSig> for RR { fn from(rrsig: RRSig) -> RR { RR::RRSig(rrsig) } }
-
-trait StaticRecord : Ord {
-       // http://www.iana.org/assignments/dns-parameters/dns-parameters.xhtml#dns-parameters-4
-       const TYPE: u16;
-       fn name(&self) -> &Name;
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>);
-}
-/// A trait describing a resource record (including the [`RR`] enum).
-pub trait Record : Ord + {
-       /// The resource record type, as maintained by IANA.
-       ///
-       /// Current assignments can be found at
-       /// <http://www.iana.org/assignments/dns-parameters/dns-parameters.xhtml#dns-parameters-4>
-       fn ty(&self) -> u16;
-       /// The name this record is at.
-       fn name(&self) -> &Name;
-       /// Writes the data of this record, prefixed by a u16 length, to the given `Vec`.
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>);
-}
-impl<RR: StaticRecord> Record for RR {
-       fn ty(&self) -> u16 { RR::TYPE }
-       fn name(&self) -> &Name { RR::name(self) }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               RR::write_u16_len_prefixed_data(self, out)
-       }
-}
-impl Record for RR {
-       fn ty(&self) -> u16 { self.ty() }
-       fn name(&self) -> &Name { self.name() }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               self.write_u16_len_prefixed_data(out)
-       }
-}
-
-fn read_u8(inp: &mut &[u8]) -> Result<u8, ()> {
-       let res = *inp.get(0).ok_or(())?;
-       *inp = &inp[1..];
-       Ok(res)
-}
-fn read_u16(inp: &mut &[u8]) -> Result<u16, ()> {
-       if inp.len() < 2 { return Err(()); }
-       let mut bytes = [0; 2];
-       bytes.copy_from_slice(&inp[..2]);
-       *inp = &inp[2..];
-       Ok(u16::from_be_bytes(bytes))
-}
-fn read_u32(inp: &mut &[u8]) -> Result<u32, ()> {
-       if inp.len() < 4 { return Err(()); }
-       let mut bytes = [0; 4];
-       bytes.copy_from_slice(&inp[..4]);
-       *inp = &inp[4..];
-       Ok(u32::from_be_bytes(bytes))
-}
-
-fn read_name(inp: &mut &[u8]) -> Result<Name, ()> {
-       let mut name = String::with_capacity(1024);
-       loop {
-               let len = read_u8(inp)? as usize;
-               if len == 0 {
-                       if name.is_empty() { name += "."; }
-                       break;
-               }
-               if inp.len() <= len { return Err(()); }
-               name += core::str::from_utf8(&inp[..len]).map_err(|_| ())?;
-               name += ".";
-               *inp = &inp[len..];
-               if name.len() > 1024 { return Err(()); }
-       }
-       Ok(name.try_into()?)
-}
-
-trait Writer { fn write(&mut self, buf: &[u8]); }
-impl Writer for Vec<u8> { fn write(&mut self, buf: &[u8]) { self.extend_from_slice(buf); } }
-impl Writer for ring::digest::Context { fn write(&mut self, buf: &[u8]) { self.update(buf); } }
-fn write_name<W: Writer>(out: &mut W, name: &str) {
-       let canonical_name = name.to_ascii_lowercase();
-       if canonical_name == "." {
-               out.write(&[0]);
-       } else {
-               for label in canonical_name.split(".") {
-                       out.write(&(label.len() as u8).to_be_bytes());
-                       out.write(label.as_bytes());
-               }
-       }
-}
-fn name_len(name: &Name) -> u16 {
-       if name.0 == "." {
-               1
-       } else {
-               let mut res = 0;
-               for label in name.split(".") {
-                       res += 1 + label.len();
-               }
-               res as u16
-       }
-}
-
-fn parse_rr(inp: &mut &[u8]) -> Result<RR, ()> {
-       let name = read_name(inp)?;
-       let ty = read_u16(inp)?;
-       let class = read_u16(inp)?;
-       if class != 1 { return Err(()); } // We only support the INternet
-       let _ttl = read_u32(inp)?;
-       let data_len = read_u16(inp)? as usize;
-       if inp.len() < data_len { return Err(()); }
-       let mut data = &inp[..data_len];
-       *inp = &inp[data_len..];
-
-       match ty {
-               Txt::TYPE => {
-                       let mut parsed_data = Vec::with_capacity(data_len - 1);
-                       while !data.is_empty() {
-                               let len = read_u8(&mut data)? as usize;
-                               if data.len() < len { return Err(()); }
-                               parsed_data.extend_from_slice(&data[..len]);
-                               data = &data[len..];
-                       }
-                       Ok(RR::Txt(Txt { name, data: parsed_data }))
-               }
-               TLSA::TYPE => {
-                       if data_len <= 3 { return Err(()); }
-                       Ok(RR::TLSA(TLSA {
-                               name, cert_usage: read_u8(&mut data)?, selector: read_u8(&mut data)?,
-                               data_ty: read_u8(&mut data)?, data: data.to_vec(),
-                       }))
-               },
-               DnsKey::TYPE => {
-                       Ok(RR::DnsKey(DnsKey {
-                               name, flags: read_u16(&mut data)?, protocol: read_u8(&mut data)?,
-                               alg: read_u8(&mut data)?, pubkey: data.to_vec(),
-                       }))
-               },
-               DS::TYPE => {
-                       Ok(RR::DS(DS {
-                               name, key_tag: read_u16(&mut data)?, alg: read_u8(&mut data)?,
-                               digest_type: read_u8(&mut data)?, digest: data.to_vec(),
-                       }))
-               },
-               RRSig::TYPE => {
-                       Ok(RR::RRSig(RRSig {
-                               name, ty: read_u16(&mut data)?, alg: read_u8(&mut data)?,
-                               labels: read_u8(&mut data)?, orig_ttl: read_u32(&mut data)?,
-                               expiration: read_u32(&mut data)?, inception: read_u32(&mut data)?,
-                               key_tag: read_u16(&mut data)?, key_name: read_name(&mut data)?,
-                               signature: data.to_vec(),
-                       }))
-               },
-               _ => Err(()),
-       }
-}
 /// Parse a stream of [`RR`]s from the format described in [RFC 9102](https://www.rfc-editor.org/rfc/rfc9102.html).
 ///
 /// Note that this is only the series of `AuthenticationChain` records, and does not read the
@@ -305,201 +78,6 @@ pub fn write_rr<RR: Record>(rr: &RR, ttl: u32, out: &mut Vec<u8>) {
        rr.write_u16_len_prefixed_data(out);
 }
 
-#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] // TODO: ord is wrong cause need to consider len first, maybe
-/// A text resource record, containing arbitrary text data
-pub struct Txt {
-       /// The name this record is at.
-       pub name: Name,
-       /// The text record itself.
-       ///
-       /// While this is generally UTF-8-valid, there is no specific requirement that it be, and thus
-       /// is an arbitrary series of bytes here.
-       data: Vec<u8>,
-}
-impl StaticRecord for Txt {
-       const TYPE: u16 = 16;
-       fn name(&self) -> &Name { &self.name }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               let len = (self.data.len() + self.data.len() / 255 + 1) as u16;
-               out.extend_from_slice(&len.to_be_bytes());
-
-               let mut data_write = &self.data[..];
-               out.extend_from_slice(&[data_write.len().try_into().unwrap_or(255)]);
-               while !data_write.is_empty() {
-                       let split_pos = core::cmp::min(255, data_write.len());
-                       out.extend_from_slice(&data_write[..split_pos]);
-                       data_write = &data_write[split_pos..];
-                       if !data_write.is_empty() {
-                               out.extend_from_slice(&[data_write.len().try_into().unwrap_or(255)]);
-                       }
-               }
-       }
-}
-
-#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
-/// A TLS Certificate Association resource record containing information about the TLS certificate
-/// which should be expected when communicating with the host at the given name.
-///
-/// See <https://en.wikipedia.org/wiki/DNS-based_Authentication_of_Named_Entities#TLSA_RR> for more
-/// info.
-pub struct TLSA {
-       /// The name this record is at.
-       pub name: Name,
-       /// The type of constraint on the TLS certificate(s) used which should be enforced by this
-       /// record.
-       pub cert_usage: u8,
-       /// Whether to match on the full certificate, or only the public key.
-       pub selector: u8,
-       /// The type of data included which is used to match the TLS certificate(s).
-       pub data_ty: u8,
-       /// The certificate data or hash of the certificate data itself.
-       pub data: Vec<u8>,
-}
-impl StaticRecord for TLSA {
-       const TYPE: u16 = 52;
-       fn name(&self) -> &Name { &self.name }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               let len = 3 + self.data.len();
-               out.extend_from_slice(&(len as u16).to_be_bytes());
-               out.extend_from_slice(&[self.cert_usage, self.selector, self.data_ty]);
-               out.extend_from_slice(&self.data);
-       }
-}
-
-#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
-/// A public key resource record which can be used to validate [`RRSig`]s.
-pub struct DnsKey {
-       /// The name this record is at.
-       pub name: Name,
-       /// Flags which constrain the usage of this public key.
-       pub flags: u16,
-       /// The protocol this key is used for (protocol `3` is DNSSEC). 
-       pub protocol: u8,
-       /// The algorithm which this public key uses to sign data.
-       pub alg: u8,
-       /// The public key itself.
-       pub pubkey: Vec<u8>,
-}
-impl StaticRecord for DnsKey {
-       const TYPE: u16 = 48;
-       fn name(&self) -> &Name { &self.name }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               let len = 2 + 1 + 1 + self.pubkey.len();
-               out.extend_from_slice(&(len as u16).to_be_bytes());
-               out.extend_from_slice(&self.flags.to_be_bytes());
-               out.extend_from_slice(&self.protocol.to_be_bytes());
-               out.extend_from_slice(&self.alg.to_be_bytes());
-               out.extend_from_slice(&self.pubkey);
-       }
-}
-impl DnsKey {
-       /// A short (non-cryptographic) digest which can be used to refer to this [`DnsKey`].
-       pub fn key_tag(&self) -> u16 {
-               let mut res = u32::from(self.flags);
-               res += u32::from(self.protocol) << 8;
-               res += u32::from(self.alg);
-               for (idx, b) in self.pubkey.iter().enumerate() {
-                       if idx % 2 == 0 {
-                               res += u32::from(*b) << 8;
-                       } else {
-                               res += u32::from(*b);
-                       }
-               }
-               res += (res >> 16) & 0xffff;
-               (res & 0xffff) as u16
-       }
-}
-
-#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
-/// A Delegation Signer resource record which indicates that some alternative [`DnsKey`] can sign
-/// for records in the zone which matches [`DS::name`].
-pub struct DS {
-       /// The name this record is at.
-       ///
-       /// This is also the zone that a [`DnsKey`] which matches the [`Self::digest`] can sign for.
-       pub name: Name,
-       /// A short tag which describes the matching [`DnsKey`].
-       ///
-       /// This matches the [`DnsKey::key_tag`] for the [`DnsKey`] which is referred to by this
-       /// [`DS`].
-       pub key_tag: u16,
-       /// The algorithm which the [`DnsKey`] referred to by this [`DS`] uses.
-       ///
-       /// This matches the [`DnsKey::alg`] field in the referred-to [`DnsKey`].
-       pub alg: u8,
-       /// The type of digest used to hash the referred-to [`DnsKey`].
-       pub digest_type: u8,
-       /// The digest itself.
-       pub digest: Vec<u8>,
-}
-impl StaticRecord for DS {
-       const TYPE: u16 = 43;
-       fn name(&self) -> &Name { &self.name }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               let len = 2 + 1 + 1 + self.digest.len();
-               out.extend_from_slice(&(len as u16).to_be_bytes());
-               out.extend_from_slice(&self.key_tag.to_be_bytes());
-               out.extend_from_slice(&self.alg.to_be_bytes());
-               out.extend_from_slice(&self.digest_type.to_be_bytes());
-               out.extend_from_slice(&self.digest);
-       }
-}
-
-#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
-/// A Resource Record (set) Signature resource record. This contains a signature over all the
-/// resources records of the given type at the given name.
-pub struct RRSig {
-       /// The name this record is at.
-       ///
-       /// This is also the name of any records which this signature is covering (ignoring wildcards).
-       pub name: Name,
-       /// The resource record type which this [`RRSig`] is signing.
-       ///
-       /// All resources records of this type at the same name as [`Self::name`] must be signed by
-       /// this [`RRSig`].
-       pub ty: u16,
-       /// The algorithm which is being used to sign.
-       ///
-       /// This must match the [`DnsKey::alg`] field in the [`DnsKey`] being used to sign.
-       pub alg: u8,
-       /// The number of labels in the name of the records that this signature is signing.
-       // TODO: Describe this better in terms of wildcards
-       pub labels: u8,
-       /// The TTL of the records which this [`RRSig`] is signing.
-       pub orig_ttl: u32,
-       /// The expiration (as a UNIX timestamp) of this signature.
-       pub expiration: u32,
-       /// The time (as a UNIX timestamp) at which this signature becomes valid.
-       pub inception: u32,
-       /// A short tag which describes the matching [`DnsKey`].
-       ///
-       /// This matches the [`DnsKey::key_tag`] for the [`DnsKey`] which created this signature.
-       pub key_tag: u16,
-       /// The [`DnsKey::name`] in the [`DnsKey`] which created this signature.
-       ///
-       /// This must be a parent of the [`Self::name`].
-       pub key_name: Name,
-       /// The signature itself.
-       pub signature: Vec<u8>,
-}
-impl StaticRecord for RRSig {
-       const TYPE: u16 = 46;
-       fn name(&self) -> &Name { &self.name }
-       fn write_u16_len_prefixed_data(&self, out: &mut Vec<u8>) {
-               let len = 2 + 1 + 1 + 4*3 + 2 + name_len(&self.key_name) + self.signature.len() as u16;
-               out.extend_from_slice(&len.to_be_bytes());
-               out.extend_from_slice(&self.ty.to_be_bytes());
-               out.extend_from_slice(&self.alg.to_be_bytes());
-               out.extend_from_slice(&self.labels.to_be_bytes());
-               out.extend_from_slice(&self.orig_ttl.to_be_bytes());
-               out.extend_from_slice(&self.expiration.to_be_bytes());
-               out.extend_from_slice(&self.inception.to_be_bytes());
-               out.extend_from_slice(&self.key_tag.to_be_bytes());
-               write_name(out, &self.key_name);
-               out.extend_from_slice(&self.signature);
-       }
-}
-
 #[derive(Debug, PartialEq)]
 /// An error when validating DNSSEC signatures or other data
 pub enum ValidationError {
@@ -514,27 +92,6 @@ pub enum ValidationError {
        Invalid,
 }
 
-fn bytes_to_rsa_pk<'a>(pubkey: &'a [u8])
--> Result<signature::RsaPublicKeyComponents<&'a [u8]>, ValidationError> {
-       if pubkey.len() <= 3 { return Err(ValidationError::Invalid); }
-
-       let mut pos = 0;
-       let exponent_length;
-       if pubkey[0] == 0 {
-               exponent_length = ((pubkey[1] as usize) << 8) | (pubkey[2] as usize);
-               pos += 3;
-       } else {
-               exponent_length = pubkey[0] as usize;
-               pos += 1;
-       }
-
-       if pubkey.len() <= pos + exponent_length { return Err(ValidationError::Invalid); }
-       Ok(signature::RsaPublicKeyComponents {
-               n: &pubkey[pos + exponent_length..],
-               e: &pubkey[pos..pos + exponent_length]
-       })
-}
-
 // TODO: return the validity period
 fn verify_rrsig<'a, RR: Record, Keys>(sig: &RRSig, dnskeys: Keys, mut records: Vec<&RR>)
 -> Result<(), ValidationError>
@@ -565,8 +122,19 @@ where Keys: IntoIterator<Item = &'a DnsKey> {
                        records.sort();
 
                        for record in records.iter() {
-                               // TODO: Handle wildcards
-                               write_name(&mut signed_data, record.name());
+                               let periods = record.name().as_str().chars().filter(|c| *c == '.').count();
+                               let labels = sig.labels.into();
+                               if periods != 1 && periods != labels {
+                                       if periods < labels { return Err(ValidationError::Invalid); }
+                                       let signed_name = record.name().as_str().splitn(periods - labels + 1, ".").last();
+                                       debug_assert!(signed_name.is_some());
+                                       if let Some(name) = signed_name {
+                                               signed_data.extend_from_slice(b"\x01*");
+                                               write_name(&mut signed_data, name);
+                                       } else { return Err(ValidationError::Invalid); }
+                               } else {
+                                       write_name(&mut signed_data, record.name());
+                               }
                                signed_data.extend_from_slice(&record.ty().to_be_bytes());
                                signed_data.extend_from_slice(&1u16.to_be_bytes()); // The INternet class
                                signed_data.extend_from_slice(&sig.orig_ttl.to_be_bytes());
@@ -580,7 +148,7 @@ where Keys: IntoIterator<Item = &'a DnsKey> {
                                        } else {
                                                &signature::RSA_PKCS1_1024_8192_SHA512_FOR_LEGACY_USE_ONLY
                                        };
-                                       bytes_to_rsa_pk(&dnskey.pubkey)?
+                                       bytes_to_rsa_pk(&dnskey.pubkey).map_err(|_| ValidationError::Invalid)?
                                                .verify(alg, &signed_data, &sig.signature)
                                                .map_err(|_| ValidationError::Invalid)?;
                                },
@@ -664,20 +232,30 @@ where T: IntoIterator<IntoIter = I>, I: Iterator<Item = &'a DS> + Clone {
 /// Given a set of arbitrary records, this attempts to validate DNSSEC data from the [`root_hints`]
 /// through to any supported non-DNSSEC record types.
 ///
-/// All records which could be validated are returned.
+/// All records which could be validated are returned, though if an error is found validating any
+/// contained record, only `Err` will be returned.
 pub fn verify_rr_stream<'a>(inp: &'a [RR]) -> Result<Vec<&'a RR>, ValidationError> {
        let mut zone = ".";
        let mut res = Vec::new();
-       let mut next_ds_set = None;
-       'next_zone: while zone == "." || next_ds_set.is_some() {
+       let mut pending_ds_sets = Vec::with_capacity(1);
+       'next_zone: while zone == "." || !pending_ds_sets.is_empty() {
                let mut found_unsupported_alg = false;
+               let next_ds_set;
+               if let Some((next_zone, ds_set)) = pending_ds_sets.pop() {
+                       next_ds_set = Some(ds_set);
+                       zone = next_zone;
+               } else {
+                       debug_assert_eq!(zone, ".");
+                       next_ds_set = None;
+               }
+
                for rrsig in inp.iter()
                        .filter_map(|rr| if let RR::RRSig(sig) = rr { Some(sig) } else { None })
-                       .filter(|rrsig| rrsig.name.0 == zone && rrsig.ty == DnsKey::TYPE)
+                       .filter(|rrsig| rrsig.name.as_str() == zone && rrsig.ty == DnsKey::TYPE)
                {
                        let dnskeys = inp.iter()
                                .filter_map(|rr| if let RR::DnsKey(dnskey) = rr { Some(dnskey) } else { None })
-                               .filter(move |dnskey| dnskey.name.0 == zone);
+                               .filter(move |dnskey| dnskey.name.as_str() == zone);
                        let dnskeys_verified = if zone == "." {
                                verify_dnskey_rrsig(rrsig, &root_hints(), dnskeys.clone().collect())
                        } else {
@@ -686,19 +264,11 @@ pub fn verify_rr_stream<'a>(inp: &'a [RR]) -> Result<Vec<&'a RR>, ValidationErro
                                verify_dnskey_rrsig(rrsig, next_ds_set.clone().unwrap(), dnskeys.clone().collect())
                        };
                        if dnskeys_verified.is_ok() {
-                               let mut last_validated_type = None;
-                               next_ds_set = None;
                                for rrsig in inp.iter()
                                        .filter_map(|rr| if let RR::RRSig(sig) = rr { Some(sig) } else { None })
-                                       .filter(move |rrsig| rrsig.key_name.0 == zone && rrsig.name.0 != zone)
+                                       .filter(move |rrsig| rrsig.key_name.as_str() == zone && rrsig.name.as_str() != zone)
                                {
                                        if !rrsig.name.ends_with(zone) { return Err(ValidationError::Invalid); }
-                                       if last_validated_type == Some(rrsig.ty) {
-                                               // If we just validated all the RRs for this type, go ahead and skip it. We
-                                               // may end up double-validating some RR Sets if there's multiple RRSigs for
-                                               // the same sets interwoven with other RRSets, but that's okay.
-                                               continue;
-                                       }
                                        let signed_records = inp.iter()
                                                .filter(|rr| rr.name() == &rrsig.name && rr.ty() == rrsig.ty);
                                        verify_rrsig(rrsig, dnskeys.clone(), signed_records.clone().collect())?;
@@ -706,19 +276,23 @@ pub fn verify_rr_stream<'a>(inp: &'a [RR]) -> Result<Vec<&'a RR>, ValidationErro
                                                // RRSigs shouldn't cover child `DnsKey`s or other `RRSig`s
                                                RRSig::TYPE|DnsKey::TYPE => return Err(ValidationError::Invalid),
                                                DS::TYPE => {
-                                                       next_ds_set = Some(signed_records.filter_map(|rr|
-                                                               if let RR::DS(ds) = rr { Some(ds) }
-                                                               else { debug_assert!(false, "We already filtered by type"); None }));
-                                                       zone = &rrsig.name;
+                                                       if !pending_ds_sets.iter().any(|(pending_zone, _)| pending_zone == &rrsig.name.as_str()) {
+                                                               pending_ds_sets.push((
+                                                                       &rrsig.name,
+                                                                       signed_records.filter_map(|rr|
+                                                                               if let RR::DS(ds) = rr { Some(ds) }
+                                                                               else { debug_assert!(false, "We already filtered by type"); None })
+                                                               ));
+                                                       }
                                                },
                                                _ => {
-                                                       for record in signed_records { res.push(record); }
-                                                       last_validated_type = Some(rrsig.ty);
+                                                       for record in signed_records {
+                                                               if !res.contains(&record) { res.push(record); }
+                                                       }
                                                },
                                        }
                                }
-                               if next_ds_set.is_none() { break 'next_zone; }
-                               else { continue 'next_zone; }
+                               continue 'next_zone;
                        } else if dnskeys_verified == Err(ValidationError::UnsupportedAlgorithm) {
                                // There may be redundant signatures by different keys, where one we don't supprt
                                // and another we do. Ignore ones we don't support, but if there are no more,
@@ -742,8 +316,12 @@ pub fn verify_rr_stream<'a>(inp: &'a [RR]) -> Result<Vec<&'a RR>, ValidationErro
 
 #[cfg(test)]
 mod tests {
+       #![allow(deprecated)]
+
        use super::*;
 
+       use alloc::borrow::ToOwned;
+
        use hex_conservative::FromHex;
        use rand::seq::SliceRandom;
 
@@ -840,8 +418,104 @@ mod tests {
                (txt_resp, txt_rrsig)
        }
 
+       fn matcorallo_dnskey() -> (Vec<DnsKey>, Vec<RR>) {
+               let com_dnskeys = com_dnskey().0;
+               let mut matcorallo_ds = vec![DS {
+                       name: "matcorallo.com.".try_into().unwrap(), key_tag: 24930, alg: 13, digest_type: 2,
+                       digest: Vec::from_hex("693E990CBB1CE1095E387092D3C04BCE907C008891F32A88D41D3ECB129E5E23").unwrap(),
+               }];
+               let ds_rrsig = RRSig {
+                       name: "matcorallo.com.".try_into().unwrap(), ty: DS::TYPE, alg: 13, labels: 2, orig_ttl: 86400,
+                       expiration: 1707628636, inception: 1707019636, key_tag: 4534, key_name: "com.".try_into().unwrap(),
+                       signature: base64::decode("l9b+DhtnJSIzR6y4Bwx+0L9kep77UNCBoTg74RTSL6oMrQd8w4OobHxzwDyXqnLfyxVP18V+AnQp4DdJ2nUW1g==").unwrap(),
+               };
+               verify_rrsig(&ds_rrsig, &com_dnskeys, matcorallo_ds.iter().collect()).unwrap();
+               let dnskeys = vec![DnsKey {
+                       name: "matcorallo.com.".try_into().unwrap(), flags: 257, protocol: 3, alg: 13,
+                       pubkey: base64::decode("pfO3ow3SrKhLS7AMEi3b5W9P28nCOB9vryxfSXhqMcXFP1x9V4xAt0/JLr0zNodsqRD/8d9Yhu4Wf3hnSlaavw==").unwrap(),
+               }, DnsKey {
+                       name: "matcorallo.com.".try_into().unwrap(), flags: 256, protocol: 3, alg: 13,
+                       pubkey: base64::decode("OO6LQTV1mnRsFgn6YQoyeo/SDqS3eajfVv8WGQVnuSYO/bTS9St1tJiox2fgU6wRWDU3chhjz1Pj0unKUAQKig==").unwrap(),
+               }];
+               let dnskey_rrsig = RRSig {
+                       name: "matcorallo.com.".try_into().unwrap(), ty: DnsKey::TYPE, alg: 13, labels: 2, orig_ttl: 604800,
+                       expiration: 1708309135, inception: 1707094135, key_tag: 24930, key_name: "matcorallo.com.".try_into().unwrap(),
+                       signature: base64::decode("2MKg3bTn9zf4ThwCoKRFadqD6l1D6SuLksRieKxFC0QQnzUOCRgZSK2/IlT0DMEoM0+mGrJZo7UG79UILMGUyg==").unwrap(),
+               };
+               verify_dnskey_rrsig(&dnskey_rrsig, &matcorallo_ds, dnskeys.iter().collect()).unwrap();
+               let rrs = vec![matcorallo_ds.pop().unwrap().into(), ds_rrsig.into(),
+                       dnskeys[0].clone().into(), dnskeys[1].clone().into(), dnskey_rrsig.into()];
+               (dnskeys, rrs)
+       }
+
+       fn matcorallo_txt_record() -> (Txt, RRSig) {
+               let txt_resp = Txt {
+                       name: "txt_test.matcorallo.com.".try_into().unwrap(),
+                       data: "dnssec_prover_test".to_owned().into_bytes(),
+               };
+               let txt_rrsig = RRSig {
+                       name: "txt_test.matcorallo.com.".try_into().unwrap(),
+                       ty: Txt::TYPE, alg: 13, labels: 3, orig_ttl: 30, expiration: 1708319203,
+                       inception: 1707104203, key_tag: 34530, key_name: "matcorallo.com.".try_into().unwrap(),
+                       signature: base64::decode("4vaE5Jex2VvIT39JpuMNT7Ds7O0OfzTik5f8WcRRxO0IJnGAO16syAsNUkNkNqsMYknnjHDF0lI4agszgzdpsw==").unwrap(),
+               };
+               (txt_resp, txt_rrsig)
+       }
+
+       fn matcorallo_cname_record() -> (CName, RRSig) {
+               let cname_resp = CName {
+                       name: "cname_test.matcorallo.com.".try_into().unwrap(),
+                       canonical_name: "txt_test.matcorallo.com.".try_into().unwrap(),
+               };
+               let cname_rrsig = RRSig {
+                       name: "cname_test.matcorallo.com.".try_into().unwrap(),
+                       ty: CName::TYPE, alg: 13, labels: 3, orig_ttl: 30, expiration: 1708319203,
+                       inception: 1707104203, key_tag: 34530, key_name: "matcorallo.com.".try_into().unwrap(),
+                       signature: base64::decode("5HIrmEotbVb95umE6SX3NrPboKsthdcY8b7DdaYQZzm0Nj5m2VgcfOmEPJYS8o1xE4GvGGF4sdfSy3Uw7TibBg==").unwrap(),
+               };
+               (cname_resp, cname_rrsig)
+       }
+
+       fn matcorallo_wildcard_record() -> (Txt, RRSig) {
+               let txt_resp = Txt {
+                       name: "test.wildcard_test.matcorallo.com.".try_into().unwrap(),
+                       data: "wildcard_test".to_owned().into_bytes(),
+               };
+               let txt_rrsig = RRSig {
+                       name: "test.wildcard_test.matcorallo.com.".try_into().unwrap(),
+                       ty: Txt::TYPE, alg: 13, labels: 3, orig_ttl: 30, expiration: 1708321778,
+                       inception: 1707106778, key_tag: 34530, key_name: "matcorallo.com.".try_into().unwrap(),
+                       signature: base64::decode("vdnXunPY4CnbW/BL8VOOR9o33+dqyKA/4h+u5VM7NjB30Shp8L8gL5UwE0k7TKRNgHC8j3TqEPEmNMIHz87Z4Q==").unwrap(),
+               };
+               (txt_resp, txt_rrsig)
+       }
+
+       fn matcorallo_cname_wildcard_record() -> (CName, RRSig, Txt, RRSig) {
+               let cname_resp = CName {
+                       name: "test.cname_wildcard_test.matcorallo.com.".try_into().unwrap(),
+                       canonical_name: "cname.wildcard_test.matcorallo.com.".try_into().unwrap(),
+               };
+               let txt_resp = Txt {
+                       name: "cname.wildcard_test.matcorallo.com.".try_into().unwrap(),
+                       data: "wildcard_test".to_owned().into_bytes(),
+               };
+               let cname_rrsig = RRSig {
+                       name: "test.cname_wildcard_test.matcorallo.com.".try_into().unwrap(),
+                       ty: CName::TYPE, alg: 13, labels: 3, orig_ttl: 30, expiration: 1708322050,
+                       inception: 1707107050, key_tag: 34530, key_name: "matcorallo.com.".try_into().unwrap(),
+                       signature: base64::decode("JfJuSemF5dtQYxEw6eKL4IRP8BaDt6FtbtdpZ6HjODTDflhKQRhBEbwT7kwceKPAq18q5sWHFV1bMTqE/F3WLw==").unwrap(),
+               };
+               let txt_rrsig = RRSig {
+                       name: "cname.wildcard_test.matcorallo.com.".try_into().unwrap(),
+                       ty: Txt::TYPE, alg: 13, labels: 3, orig_ttl: 30, expiration: 1708321778,
+                       inception: 1707106778, key_tag: 34530, key_name: "matcorallo.com.".try_into().unwrap(),
+                       signature: base64::decode("vdnXunPY4CnbW/BL8VOOR9o33+dqyKA/4h+u5VM7NjB30Shp8L8gL5UwE0k7TKRNgHC8j3TqEPEmNMIHz87Z4Q==").unwrap(),
+               };
+               (cname_resp, cname_rrsig, txt_resp, txt_rrsig)
+       }
+
        #[test]
-       fn check_txt_record() {
+       fn check_txt_record_a() {
                let dnskeys = mattcorallo_dnskey().0;
                let (txt, txt_rrsig) = mattcorallo_txt_record();
                let txt_resp = [txt];
@@ -849,7 +523,7 @@ mod tests {
        }
 
        #[test]
-       fn check_txt_proof() {
+       fn check_single_txt_proof() {
                let mut rr_stream = Vec::new();
                for rr in root_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
                for rr in com_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
@@ -862,11 +536,93 @@ mod tests {
                let verified_rrs = verify_rr_stream(&rrs).unwrap();
                assert_eq!(verified_rrs.len(), 1);
                if let RR::Txt(txt) = &verified_rrs[0] {
-                       assert_eq!(txt.name.0, "matt.user._bitcoin-payment.mattcorallo.com.");
+                       assert_eq!(txt.name.as_str(), "matt.user._bitcoin-payment.mattcorallo.com.");
                        assert_eq!(txt.data, b"bitcoin:?b12=lno1qsgqmqvgm96frzdg8m0gc6nzeqffvzsqzrxqy32afmr3jn9ggkwg3egfwch2hy0l6jut6vfd8vpsc3h89l6u3dm4q2d6nuamav3w27xvdmv3lpgklhg7l5teypqz9l53hj7zvuaenh34xqsz2sa967yzqkylfu9xtcd5ymcmfp32h083e805y7jfd236w9afhavqqvl8uyma7x77yun4ehe9pnhu2gekjguexmxpqjcr2j822xr7q34p078gzslf9wpwz5y57alxu99s0z2ql0kfqvwhzycqq45ehh58xnfpuek80hw6spvwrvttjrrq9pphh0dpydh06qqspp5uq4gpyt6n9mwexde44qv7lstzzq60nr40ff38u27un6y53aypmx0p4qruk2tf9mjwqlhxak4znvna5y");
                } else { panic!(); }
        }
 
+       #[test]
+       fn check_txt_record_b() {
+               let dnskeys = matcorallo_dnskey().0;
+               let (txt, txt_rrsig) = matcorallo_txt_record();
+               let txt_resp = [txt];
+               verify_rrsig(&txt_rrsig, &dnskeys, txt_resp.iter().collect()).unwrap();
+       }
+
+       #[test]
+       fn check_cname_record() {
+               let dnskeys = matcorallo_dnskey().0;
+               let (cname, cname_rrsig) = matcorallo_cname_record();
+               let cname_resp = [cname];
+               verify_rrsig(&cname_rrsig, &dnskeys, cname_resp.iter().collect()).unwrap();
+       }
+
+       #[test]
+       fn check_multi_zone_proof() {
+               let mut rr_stream = Vec::new();
+               for rr in root_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+               for rr in com_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+               for rr in mattcorallo_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+               let (txt, txt_rrsig) = mattcorallo_txt_record();
+               for rr in [RR::Txt(txt), RR::RRSig(txt_rrsig)] { write_rr(&rr, 1, &mut rr_stream); }
+               for rr in matcorallo_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+               let (txt, txt_rrsig) = matcorallo_txt_record();
+               for rr in [RR::Txt(txt), RR::RRSig(txt_rrsig)] { write_rr(&rr, 1, &mut rr_stream); }
+               let (cname, cname_rrsig) = matcorallo_cname_record();
+               for rr in [RR::CName(cname), RR::RRSig(cname_rrsig)] { write_rr(&rr, 1, &mut rr_stream); }
+
+               let mut rrs = parse_rr_stream(&rr_stream).unwrap();
+               rrs.shuffle(&mut rand::rngs::OsRng);
+               let mut verified_rrs = verify_rr_stream(&rrs).unwrap();
+               verified_rrs.sort();
+               assert_eq!(verified_rrs.len(), 3);
+               if let RR::Txt(txt) = &verified_rrs[0] {
+                       assert_eq!(txt.name.as_str(), "matt.user._bitcoin-payment.mattcorallo.com.");
+                       assert_eq!(txt.data, b"bitcoin:?b12=lno1qsgqmqvgm96frzdg8m0gc6nzeqffvzsqzrxqy32afmr3jn9ggkwg3egfwch2hy0l6jut6vfd8vpsc3h89l6u3dm4q2d6nuamav3w27xvdmv3lpgklhg7l5teypqz9l53hj7zvuaenh34xqsz2sa967yzqkylfu9xtcd5ymcmfp32h083e805y7jfd236w9afhavqqvl8uyma7x77yun4ehe9pnhu2gekjguexmxpqjcr2j822xr7q34p078gzslf9wpwz5y57alxu99s0z2ql0kfqvwhzycqq45ehh58xnfpuek80hw6spvwrvttjrrq9pphh0dpydh06qqspp5uq4gpyt6n9mwexde44qv7lstzzq60nr40ff38u27un6y53aypmx0p4qruk2tf9mjwqlhxak4znvna5y");
+               } else { panic!(); }
+               if let RR::Txt(txt) = &verified_rrs[1] {
+                       assert_eq!(txt.name.as_str(), "txt_test.matcorallo.com.");
+                       assert_eq!(txt.data, b"dnssec_prover_test");
+               } else { panic!(); }
+               if let RR::CName(cname) = &verified_rrs[2] {
+                       assert_eq!(cname.name.as_str(), "cname_test.matcorallo.com.");
+                       assert_eq!(cname.canonical_name.as_str(), "txt_test.matcorallo.com.");
+               } else { panic!(); }
+       }
+
+       #[test]
+       fn check_wildcard_record() {
+               let dnskeys = matcorallo_dnskey().0;
+               let (txt, txt_rrsig) = matcorallo_wildcard_record();
+               let txt_resp = [txt];
+               verify_rrsig(&txt_rrsig, &dnskeys, txt_resp.iter().collect()).unwrap();
+       }
+
+       #[test]
+       fn check_wildcard_proof() {
+               let mut rr_stream = Vec::new();
+               for rr in root_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+               for rr in com_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+               for rr in matcorallo_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+               let (cname, cname_rrsig, txt, txt_rrsig) = matcorallo_cname_wildcard_record();
+               for rr in [RR::CName(cname), RR::RRSig(cname_rrsig)] { write_rr(&rr, 1, &mut rr_stream); }
+               for rr in [RR::Txt(txt), RR::RRSig(txt_rrsig)] { write_rr(&rr, 1, &mut rr_stream); }
+
+               let mut rrs = parse_rr_stream(&rr_stream).unwrap();
+               rrs.shuffle(&mut rand::rngs::OsRng);
+               let mut verified_rrs = verify_rr_stream(&rrs).unwrap();
+               verified_rrs.sort();
+               assert_eq!(verified_rrs.len(), 2);
+               if let RR::Txt(txt) = &verified_rrs[0] {
+                       assert_eq!(txt.name.as_str(), "cname.wildcard_test.matcorallo.com.");
+                       assert_eq!(txt.data, b"wildcard_test");
+               } else { panic!(); }
+               if let RR::CName(cname) = &verified_rrs[1] {
+                       assert_eq!(cname.name.as_str(), "test.cname_wildcard_test.matcorallo.com.");
+                       assert_eq!(cname.canonical_name.as_str(), "cname.wildcard_test.matcorallo.com.");
+               } else { panic!(); }
+       }
+
        #[test]
        fn rfc9102_parse_test() {
                // Note that this is the `AuthenticationChain` field only, and ignores the