From 607731e70845f770b73a6658efc07f156ce7d9a4 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Tue, 21 May 2024 16:17:37 +0000 Subject: [PATCH] Limit the number of validation steps we'll take While proofs should be rather computation-time-limited through limits on their size, its still nice to limit proof validation time more directly through the same constant we already do to limit proof construction complexity. --- src/http.rs | 5 +++++ src/lib.rs | 5 +++++ src/query.rs | 10 +++++----- src/validation.rs | 24 ++++++++++++++++++++++++ 4 files changed, 39 insertions(+), 5 deletions(-) diff --git a/src/http.rs b/src/http.rs index 6107502..00383b6 100644 --- a/src/http.rs +++ b/src/http.rs @@ -17,6 +17,11 @@ extern crate alloc; +/// The maximum number of requests we will make when building a proof or the maximum number of +/// [`rr::RRSig`] sets we'll validate records from when validating proofs. +// Note that this is duplicated exactly in src/lib.rs +pub const MAX_PROOF_STEPS: usize = 20; + pub mod rr; pub mod ser; pub mod query; diff --git a/src/lib.rs b/src/lib.rs index 91a3156..4cf920d 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -49,6 +49,11 @@ #![cfg_attr(not(feature = "std"), no_std)] extern crate alloc; +/// The maximum number of requests we will make when building a proof or the maximum number of +/// [`rr::RRSig`] sets we'll validate records from when validating proofs. +// Note that this is duplicated exactly in src/http.rs +pub const MAX_PROOF_STEPS: usize = 20; + #[cfg(feature = "validation")] mod base32; diff --git a/src/query.rs b/src/query.rs index 388b961..fd99827 100644 --- a/src/query.rs +++ b/src/query.rs @@ -17,6 +17,7 @@ use tokio_crate::io::{AsyncReadExt, AsyncWriteExt}; use crate::rr::*; use crate::ser::*; +use crate::MAX_PROOF_STEPS; // In testing use a rather small buffer to ensure we hit the allocation paths sometimes. In // production, we should generally never actually need to go to heap as DNS messages are rarely @@ -192,7 +193,6 @@ pub fn fuzz_proof_builder(mut response_stream: &[u8]) { let _ = builder.finish_proof(); } -const MAX_REQUESTS: usize = 10; /// A simple state machine which will generate a series of queries and process the responses until /// it has built a DNSSEC proof. /// @@ -230,7 +230,7 @@ impl ProofBuilder { (ProofBuilder { proof: Vec::new(), min_ttl: u32::MAX, - dnskeys_requested: Vec::with_capacity(MAX_REQUESTS), + dnskeys_requested: Vec::with_capacity(MAX_PROOF_STEPS), pending_queries: 1, queries_made: 1, }, initial_query) @@ -242,7 +242,7 @@ impl ProofBuilder { /// [`Self::process_response`]. Once this returns false, [`Self::finish_proof`] should be used /// to (possibly) get the final proof. pub fn awaiting_responses(&self) -> bool { - self.pending_queries > 0 && self.queries_made <= MAX_REQUESTS + self.pending_queries > 0 && self.queries_made <= MAX_PROOF_STEPS } /// Processes a query response from the recursive resolver, returning a list of new queries to @@ -273,7 +273,7 @@ impl ProofBuilder { } } } - if self.queries_made <= MAX_REQUESTS { + if self.queries_made <= MAX_PROOF_STEPS { Ok(new_queries) } else { Ok(Vec::new()) @@ -284,7 +284,7 @@ impl ProofBuilder { /// used to cache the proof (i.e. the lowest TTL of all records which were used to build the /// proof). pub fn finish_proof(self) -> Result<(Vec, u32), ()> { - if self.pending_queries > 0 || self.queries_made > MAX_REQUESTS { + if self.pending_queries > 0 || self.queries_made > MAX_PROOF_STEPS { Err(()) } else { Ok((self.proof, self.min_ttl)) diff --git a/src/validation.rs b/src/validation.rs index ecca8f8..fc188a4 100644 --- a/src/validation.rs +++ b/src/validation.rs @@ -9,6 +9,7 @@ use crate::base32; use crate::crypto; use crate::rr::*; use crate::ser::write_name; +use crate::MAX_PROOF_STEPS; /// Gets the trusted root anchors /// @@ -43,6 +44,9 @@ pub enum ValidationError { UnsupportedAlgorithm, /// The provided data was invalid or signatures did not validate. Invalid, + /// We would need to validate more than [`MAX_PROOF_STEPS`] sets of [`RRSig`]s to validate the + /// proof we were given. + ValidationCountLimited, } fn verify_rrsig<'a, RR: WriteableRecord, Keys>(sig: &RRSig, dnskeys: Keys, mut records: Vec<&RR>) @@ -191,6 +195,10 @@ where RI: IntoIterator, R: Iterator, // no more, return UnsupportedAlgorithm found_unsupported_alg = true; }, + Err(ValidationError::ValidationCountLimited) => { + debug_assert!(false, "verify_rrsig doesn't internally limit"); + return Err(ValidationError::ValidationCountLimited); + }, Err(ValidationError::Invalid) => { // If a signature is invalid, just immediately fail, avoiding KeyTrap issues. return Err(ValidationError::Invalid); @@ -317,6 +325,7 @@ pub fn verify_rr_stream<'a>(inp: &'a [RR]) -> Result, Valid let mut latest_inception = 0; let mut earliest_expiry = u64::MAX; let mut min_ttl = u32::MAX; + let mut rrsig_sets_validated = 0; 'next_zone: while zone == "." || !pending_ds_sets.is_empty() { let next_ds_set; if let Some((next_zone, ds_set)) = pending_ds_sets.pop() { @@ -327,6 +336,11 @@ pub fn verify_rr_stream<'a>(inp: &'a [RR]) -> Result, Valid next_ds_set = None; } + rrsig_sets_validated += 1; + if rrsig_sets_validated > MAX_PROOF_STEPS { + return Err(ValidationError::ValidationCountLimited); + } + let dnskey_rrsigs = inp.iter() .filter_map(|rr| if let RR::RRSig(sig) = rr { Some(sig) } else { None }) .filter(|rrsig| rrsig.name.as_str() == zone && rrsig.ty == DnsKey::TYPE); @@ -344,16 +358,26 @@ pub fn verify_rr_stream<'a>(inp: &'a [RR]) -> Result, Valid latest_inception = cmp::max(latest_inception, resolve_time(verified_dnskey_rrsig.inception)); earliest_expiry = cmp::min(earliest_expiry, resolve_time(verified_dnskey_rrsig.expiration)); min_ttl = cmp::min(min_ttl, verified_dnskey_rrsig.orig_ttl); + for rrsig in inp.iter() .filter_map(|rr| if let RR::RRSig(sig) = rr { Some(sig) } else { None }) .filter(move |rrsig| rrsig.key_name.as_str() == zone && rrsig.ty != DnsKey::TYPE) { + rrsig_sets_validated += 1; + if rrsig_sets_validated > MAX_PROOF_STEPS { + return Err(ValidationError::ValidationCountLimited); + } + if !rrsig.name.ends_with(zone) { return Err(ValidationError::Invalid); } let signed_records = inp.iter() .filter(|rr| rr.name() == &rrsig.name && rr.ty() == rrsig.ty); match verify_rrsig(rrsig, dnskeys.clone(), signed_records.clone().collect()) { Ok(()) => {}, Err(ValidationError::UnsupportedAlgorithm) => continue, + Err(ValidationError::ValidationCountLimited) => { + debug_assert!(false, "verify_rrsig doesn't internally limit"); + return Err(ValidationError::ValidationCountLimited); + }, Err(ValidationError::Invalid) => { // If a signature is invalid, just immediately fail, avoiding KeyTrap issues. return Err(ValidationError::Invalid); -- 2.39.5