diff options
author | Justus Winter <justus@sequoia-pgp.org> | 2024-04-18 15:35:31 +0200 |
---|---|---|
committer | Justus Winter <justus@sequoia-pgp.org> | 2024-05-29 12:17:54 +0200 |
commit | d34e61a5b3a64f559f5635cfdd34423f968bb762 (patch) | |
tree | 357abd8a0188ac09a0712e8af3dcd38556555ac4 /openpgp | |
parent | 426ecd605cb52039ece5e2872086889489fc015c (diff) |
openpgp: Lazily verify self-signatures in certs.
- In the original implementation of `Cert::canonicalize`, all
self-signatures were verified. This has turned out to be very
expensive. Instead, we should only verify the signatures we are
actually interested in.
- To preserve the semantics, every self signature we hand out from
the `Cert` API must have been verified first. However, we can do
that lazily. And, when we reason over the cert (i.e. we are
looking for the right self-signature), we can search the
signatures without triggering the verification, and only verify
the one we are really interested in.
Diffstat (limited to 'openpgp')
-rw-r--r-- | openpgp/src/cert.rs | 121 | ||||
-rw-r--r-- | openpgp/src/cert/bundle.rs | 129 | ||||
-rw-r--r-- | openpgp/src/cert/lazysigs.rs | 356 | ||||
-rw-r--r-- | openpgp/src/cert/parser/low_level/bundle.rs | 112 | ||||
-rw-r--r-- | openpgp/src/cert/parser/low_level/grammar.lalrpop | 15 | ||||
-rw-r--r-- | openpgp/src/cert/parser/low_level/lexer.rs | 2 | ||||
-rw-r--r-- | openpgp/src/cert/parser/low_level/mod.rs | 1 |
7 files changed, 662 insertions, 74 deletions
diff --git a/openpgp/src/cert.rs b/openpgp/src/cert.rs index 0dbdd896..aeff17c0 100644 --- a/openpgp/src/cert.rs +++ b/openpgp/src/cert.rs @@ -189,6 +189,7 @@ use bundle::{ SubkeyBundles, UnknownBundles, }; +mod lazysigs; mod parser; pub mod raw; mod revoke; @@ -1174,7 +1175,12 @@ impl Cert { /// ``` pub fn bad_signatures(&self) -> impl Iterator<Item = &Signature> + Send + Sync { - self.bad.iter() + self.primary.bad_signatures() + .chain(self.userids.iter().flat_map(|u| u.bad_signatures())) + .chain(self.user_attributes.iter().flat_map(|u| u.bad_signatures())) + .chain(self.subkeys.iter().flat_map(|u| u.bad_signatures())) + .chain(self.unknowns.iter().flat_map(|u| u.bad_signatures())) + .chain(self.bad.iter()) } /// Returns a list of any designated revokers for this certificate. @@ -1518,33 +1524,57 @@ impl Cert { // desc: a description of the component // binding: the binding to check // sigs: a vector of sigs in $binding to check - // verify_method: the method to call on a signature to verify it - // verify_args: additional arguments to pass to verify_method macro_rules! check { ($desc:expr, $binding:expr, $sigs:ident, - $verify_method:ident, $($verify_args:expr),*) => ({ + $hash_method:ident, // method to hash the signature + $sig_type_pat:pat, // pattern to test signature types against + $($hash_args:expr),* // additional arguments to pass to hash_method + ) => ({ t!("check!({}, {}, {:?}, {}, ...)", $desc, stringify!($binding), $binding.$sigs, - stringify!($verify_method)); - for sig in mem::take(&mut $binding.$sigs).into_iter() { - match sig.$verify_method(self.primary.key(), - self.primary.key(), - $($verify_args),*) { - Ok(()) => $binding.$sigs.push(sig), - Err(err) => { - t!("Sig {:02X}{:02X}, type = {} \ - doesn't belong to {}: {:?}", - sig.digest_prefix()[0], sig.digest_prefix()[1], - sig.typ(), $desc, err); - - self.bad.push(sig); - } + stringify!($hash_method)); + for sig in $binding.$sigs.take().into_iter() { + // Use hash prefix as heuristic. + let key = self.primary.key(); + match sig.hash_algo().context().and_then(|mut ctx| { + if matches!(sig.typ(), $sig_type_pat) { + sig.$hash_method(&mut ctx, key, $($hash_args),*); + ctx.into_digest() + } else { + Err(Error::UnsupportedSignatureType(sig.typ()).into()) + } + }) { + Ok(hash) => { + if &sig.digest_prefix()[..] == &hash[..2] { + sig.set_computed_digest(Some(hash)); + $binding.$sigs.push(sig); + } else { + t!("Sig {:02X}{:02X}, type = {} \ + doesn't belong to {} (computed hash's prefix: {:02X}{:02X})", + sig.digest_prefix()[0], sig.digest_prefix()[1], + sig.typ(), $desc, + hash[0], hash[1]); + + self.bad.push(sig); + } + }, + Err(e) => { + // Hashing failed, we likely don't support the + // hash algorithm, or the signature type was + // bad. + t!("Sig {:02X}{:02X}, type = {}: \ + Hashing failed: {}", + sig.digest_prefix()[0], sig.digest_prefix()[1], + sig.typ(), e); + + self.bad.push(sig); + }, } } }); ($desc:expr, $binding:expr, $sigs:ident, - $verify_method:ident) => ({ - check!($desc, $binding, $sigs, $verify_method,) + $hash_method:ident, $sig_type_pat:pat) => ({ + check!($desc, $binding, $sigs, $hash_method, $sig_type_pat, ) }); } @@ -1610,8 +1640,9 @@ impl Cert { } }, Err(e) => { - // Hashing failed, we likely don't support - // the hash algorithm. + // Hashing failed, we likely don't support the + // hash algorithm, or the signature type was + // bad. t!("Sig {:02X}{:02X}, type = {}: \ Hashing failed: {}", sig.digest_prefix()[0], sig.digest_prefix()[1], @@ -1636,9 +1667,9 @@ impl Cert { } check!("primary key", - self.primary, self_signatures, verify_direct_key); + self.primary, self_signatures, hash_direct_key, DirectKey); check!("primary key", - self.primary, self_revocations, verify_primary_key_revocation); + self.primary, self_revocations, hash_direct_key, KeyRevocation); check_3rd_party!("primary key", self.primary, certifications, lookup_fn, verify_direct_key, hash_direct_key, DirectKey); @@ -1650,15 +1681,19 @@ impl Cert { for ua in self.userids.iter_mut() { check!(format!("userid \"{}\"", String::from_utf8_lossy(ua.userid().value())), - ua, self_signatures, verify_userid_binding, + ua, self_signatures, hash_userid_binding, + GenericCertification | PersonaCertification + | CasualCertification | PositiveCertification, ua.userid()); check!(format!("userid \"{}\"", String::from_utf8_lossy(ua.userid().value())), - ua, self_revocations, verify_userid_revocation, + ua, self_revocations, hash_userid_binding, + CertificationRevocation, ua.userid()); check!(format!("userid \"{}\"", String::from_utf8_lossy(ua.userid().value())), - ua, attestations, verify_userid_attestation, + ua, attestations, hash_userid_binding, + AttestationKey, ua.userid()); check_3rd_party!( format!("userid \"{}\"", @@ -1679,13 +1714,17 @@ impl Cert { for binding in self.user_attributes.iter_mut() { check!("user attribute", - binding, self_signatures, verify_user_attribute_binding, + binding, self_signatures, hash_user_attribute_binding, + GenericCertification | PersonaCertification + | CasualCertification | PositiveCertification, binding.user_attribute()); check!("user attribute", - binding, self_revocations, verify_user_attribute_revocation, + binding, self_revocations, hash_user_attribute_binding, + CertificationRevocation, binding.user_attribute()); check!("user attribute", - binding, attestations, verify_user_attribute_attestation, + binding, attestations, hash_user_attribute_binding, + AttestationKey, binding.user_attribute()); check_3rd_party!( "user attribute", @@ -1704,10 +1743,12 @@ impl Cert { for binding in self.subkeys.iter_mut() { check!(format!("subkey {}", binding.key().keyid()), - binding, self_signatures, verify_subkey_binding, + binding, self_signatures, hash_subkey_binding, + SubkeyBinding, binding.key()); check!(format!("subkey {}", binding.key().keyid()), - binding, self_revocations, verify_subkey_revocation, + binding, self_revocations, hash_subkey_binding, + SubkeyRevocation, binding.key()); check_3rd_party!( format!("subkey {}", binding.key().keyid()), @@ -1737,13 +1778,13 @@ impl Cert { // remember where we took them from. for (i, c) in self.unknowns.iter_mut().enumerate() { for sig in - std::mem::take(&mut c.self_signatures).into_iter() + c.self_signatures.take().into_iter() .chain( std::mem::take(&mut c.certifications).into_iter()) .chain( - std::mem::take(&mut c.attestations).into_iter()) + c.attestations.take().into_iter()) .chain( - std::mem::take(&mut c.self_revocations).into_iter()) + c.self_revocations.take().into_iter()) .chain( std::mem::take(&mut c.other_revocations).into_iter()) { @@ -7035,16 +7076,6 @@ Pu1xwz57O4zo1VYf6TqHJzVC3OMvMUM2hhdecMUe5x6GorNaj6g= let cert = Cert::try_from(pp)?; assert_eq!(cert.clone().merge_public_and_secret(cert.clone())?, cert); - // Specifically, the issuer information should have been added - // back by the canonicalization. - assert_eq!( - cert.userids().next().unwrap().self_signatures().next().unwrap() - .unhashed_area().subpackets(SubpacketTag::Issuer).count(), - 1); - assert_eq!( - cert.keys().subkeys().next().unwrap().self_signatures().next().unwrap() - .unhashed_area().subpackets(SubpacketTag::Issuer).count(), - 1); Ok(()) } diff --git a/openpgp/src/cert/bundle.rs b/openpgp/src/cert/bundle.rs index 580e60a6..cf843d9f 100644 --- a/openpgp/src/cert/bundle.rs +++ b/openpgp/src/cert/bundle.rs @@ -81,8 +81,10 @@ use std::time; use std::cmp::{self, Ordering}; use std::ops::{Deref, DerefMut}; +use std::sync::Arc; use crate::{ + cert::lazysigs::LazySignatures, Error, packet::Signature, packet::Key, @@ -116,17 +118,21 @@ pub struct ComponentBundle<C> { pub(super) hash_algo_security: HashAlgoSecurity, // Self signatures. - pub(super) self_signatures: Vec<Signature>, + pub(super) self_signatures: LazySignatures, + + /// If set, is equal to `component`, and provides context to + /// verify primary key binding signatures. + backsig_signer: Option<Key<key::PublicParts, key::SubordinateRole>>, // Third-party certifications. (In general, this will only be by // designated revokers.) pub(super) certifications: Vec<Signature>, // Attestation key signatures. - pub(super) attestations: Vec<Signature>, + pub(super) attestations: LazySignatures, // Self revocations. - pub(super) self_revocations: Vec<Signature>, + pub(super) self_revocations: LazySignatures, // Third-party revocations (e.g., designated revokers). pub(super) other_revocations: Vec<Signature>, @@ -185,17 +191,19 @@ impl<C> ComponentBundle<C> { /// use `pub(in ...)` because the cert parser isn't an ancestor of /// this module. pub(crate) fn new(component: C, - hash_algo_security: HashAlgoSecurity, - sigs: Vec<Signature>) + hash_algo_security: HashAlgoSecurity, + sigs: Vec<Signature>, + primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>) -> ComponentBundle<C> { ComponentBundle { component, hash_algo_security, - self_signatures: vec![], + self_signatures: LazySignatures::new(primary_key.clone()), + backsig_signer: None, certifications: sigs, - attestations: vec![], - self_revocations: vec![], + attestations: LazySignatures::new(primary_key.clone()), + self_revocations: LazySignatures::new(primary_key), other_revocations: vec![], } } @@ -278,6 +286,9 @@ impl<C> ComponentBundle<C> { // We want the newest signature that is older than `t`, or // that has been created at `t`. So, search for `t`. + // XXX: this should be done over all signatures, independent + // of their state: + let i = // Usually, the first signature is what we are looking for. // Short circuit the binary search. @@ -348,6 +359,10 @@ impl<C> ComponentBundle<C> { continue; } + + // XXX: and here we lazily verify the signature, skipping bad ones. + + // The signature is good, but we may still need to verify the // back sig. if s.typ() == crate::types::SignatureType::SubkeyBinding && @@ -411,8 +426,10 @@ impl<C> ComponentBundle<C> { } } - find_binding_signature(policy, &self.self_signatures, - self.hash_algo_security, t) + find_binding_signature( + policy, + self.self_signatures.slice_verified(self.backsig_signer.as_ref()), + self.hash_algo_security, t) } /// Returns the component's self-signatures. @@ -443,13 +460,13 @@ impl<C> ComponentBundle<C> { // XXXv2: Rename this function. pub fn self_signatures2(&self) -> impl Iterator<Item=&Signature> + Send + Sync { - self.self_signatures.iter() + self.self_signatures.iter_verified(self.backsig_signer.as_ref()) } /// Returns the component's self-signatures. #[deprecated(note = "Use self_signatures2 instead.")] pub fn self_signatures(&self) -> &[Signature] { - &self.self_signatures + &self.self_signatures.slice_verified(self.backsig_signer.as_ref()) } /// Returns the component's third-party certifications. @@ -518,14 +535,14 @@ impl<C> ComponentBundle<C> { // XXXv2: Rename this function. pub fn self_revocations2(&self) -> impl Iterator<Item=&Signature> + Send + Sync { - self.self_revocations.iter() + self.self_revocations.iter_verified(self.backsig_signer.as_ref()) } /// Returns the component's revocations that were issued by the /// certificate holder. #[deprecated(note = "Use self_revocations2 instead.")] pub fn self_revocations(&self) -> &[Signature] { - &self.self_revocations + &self.self_revocations.slice_verified(self.backsig_signer.as_ref()) } /// Returns the component's revocations that were issued by other @@ -603,7 +620,7 @@ impl<C> ComponentBundle<C> { pub fn attestations(&self) -> impl Iterator<Item = &Signature> + Send + Sync { - self.attestations.iter() + self.attestations.iter_verified(None) } /// Returns all of the component's signatures. @@ -742,7 +759,8 @@ impl<C> ComponentBundle<C> { }; if let Some(revs) - = check(&self.self_revocations, self.hash_algo_security) + = check(self.self_revocations.slice_verified(self.backsig_signer.as_ref()), + self.hash_algo_security) // XXX must use iterator for lazy verification { t!("-> RevocationStatus::Revoked({})", revs.len()); RevocationStatus::Revoked(revs) @@ -780,9 +798,9 @@ impl<C> ComponentBundle<C> { { let p : Packet = self.component.into(); std::iter::once(p) - .chain(self.self_revocations.into_iter().map(|s| s.into())) - .chain(self.self_signatures.into_iter().map(|s| s.into())) - .chain(self.attestations.into_iter().map(|s| s.into())) + .chain(self.self_revocations.into_unverified().map(|s| s.into())) + .chain(self.self_signatures.into_unverified().map(|s| s.into())) + .chain(self.attestations.into_unverified().map(|s| s.into())) .chain(self.certifications.into_iter().map(|s| s.into())) .chain(self.other_revocations.into_iter().map(|s| s.into())) } @@ -829,12 +847,12 @@ impl<C> ComponentBundle<C> { // Order self signatures so that the most recent one comes // first. self.self_signatures.sort_by(sig_cmp); - self.self_signatures.iter_mut().for_each(sig_fixup); + self.self_signatures.iter_mut_unverified().for_each(sig_fixup); self.attestations.sort_by(Signature::normalized_cmp); self.attestations.dedup_by(sig_merge); self.attestations.sort_by(sig_cmp); - self.attestations.iter_mut().for_each(sig_fixup); + self.attestations.iter_mut_unverified().for_each(sig_fixup); self.certifications.sort_by(Signature::normalized_cmp); self.certifications.dedup_by(sig_merge); @@ -849,7 +867,7 @@ impl<C> ComponentBundle<C> { self.self_revocations.sort_by(Signature::normalized_cmp); self.self_revocations.dedup_by(sig_merge); self.self_revocations.sort_by(sig_cmp); - self.self_revocations.iter_mut().for_each(sig_fixup); + self.self_revocations.iter_mut_unverified().for_each(sig_fixup); self.other_revocations.sort_by(Signature::normalized_cmp); self.other_revocations.dedup_by(sig_merge); @@ -892,7 +910,42 @@ impl<P: key::KeyParts, R: key::KeyRole> ComponentBundle<Key<P, R>> { } } +impl<P: key::KeyParts> ComponentBundle<Key<P, key::PrimaryRole>> { + /// Returns all of the bundles's bad signatures. + pub(crate) fn bad_signatures(&self) + -> impl Iterator<Item = &Signature> + Send + Sync + { + self.self_signatures.iter_bad(self.backsig_signer.as_ref()) + .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref())) + } +} + impl<P: key::KeyParts> ComponentBundle<Key<P, key::SubordinateRole>> { + /// Creates a new subkey component. + /// + /// Should only be used from the cert parser. However, we cannot + /// use `pub(in ...)` because the cert parser isn't an ancestor of + /// this module. + pub(crate) fn new_subkey(component: Key<P, key::SubordinateRole>, + hash_algo_security: HashAlgoSecurity, + sigs: Vec<Signature>, + primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>) + -> Self + { + let backsig_signer = component.pk_algo().for_signing() + .then(|| component.parts_as_public().clone()); + ComponentBundle { + component, + hash_algo_security, + self_signatures: LazySignatures::new(primary_key.clone()), + backsig_signer, + certifications: sigs, + attestations: LazySignatures::new(primary_key.clone()), + self_revocations: LazySignatures::new(primary_key), + other_revocations: vec![], + } + } + /// Returns the subkey's revocation status at time `t`. /// /// A subkey is revoked at time `t` if: @@ -937,6 +990,14 @@ impl<P: key::KeyParts> ComponentBundle<Key<P, key::SubordinateRole>> { self._revocation_status(policy, t, true, self.binding_signature(policy, t).ok()) } + + /// Returns all of the bundles's bad signatures. + pub(crate) fn bad_signatures(&self) + -> impl Iterator<Item = &Signature> + Send + Sync + { + self.self_signatures.iter_bad(self.backsig_signer.as_ref()) + .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref())) + } } impl ComponentBundle<UserID> { @@ -1012,6 +1073,14 @@ impl ComponentBundle<UserID> { let t = t.into(); self._revocation_status(policy, t, false, self.binding_signature(policy, t).ok()) } + + /// Returns all of the bundles's bad signatures. + pub(crate) fn bad_signatures(&self) + -> impl Iterator<Item = &Signature> + Send + Sync + { + self.self_signatures.iter_bad(self.backsig_signer.as_ref()) + .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref())) + } } impl ComponentBundle<UserAttribute> { @@ -1083,6 +1152,14 @@ impl ComponentBundle<UserAttribute> { self._revocation_status(policy, t, false, self.binding_signature(policy, t).ok()) } + + /// Returns all of the bundles's bad signatures. + pub(crate) fn bad_signatures(&self) + -> impl Iterator<Item = &Signature> + Send + Sync + { + self.self_signatures.iter_bad(self.backsig_signer.as_ref()) + .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref())) + } } impl ComponentBundle<Unknown> { @@ -1112,6 +1189,14 @@ impl ComponentBundle<Unknown> { pub fn unknown(&self) -> &Unknown { self.component() } + + /// Returns all of the bundles's bad signatures. + pub(crate) fn bad_signatures(&self) + -> impl Iterator<Item = &Signature> + Send + Sync + { + self.self_signatures.iter_bad(self.backsig_signer.as_ref()) + .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref())) + } } /// A collection of `ComponentBundles`. diff --git a/openpgp/src/cert/lazysigs.rs b/openpgp/src/cert/lazysigs.rs new file mode 100644 index 00000000..d54ca551 --- /dev/null +++ b/openpgp/src/cert/lazysigs.rs @@ -0,0 +1,356 @@ +//! Lazily verified signatures. +//! +//! In the original implementation of `Cert::canonicalize`, all +//! self-signatures were verified. This has turned out to be very +//! expensive. Instead, we should only verify the signatures we are +//! actually interested in. +//! +//! To preserve the semantics, every self signature we hand out from +//! the `Cert` API must have been verified first. However, we can do +//! that lazily. And, when we reason over the cert (i.e. we are +//! looking for the right self-signature), we can search the +//! signatures without triggering the verification, and only verify +//! the one we are really interested in. + +use std::{ + cmp::Ordering, + mem, + sync::{Arc, Mutex, OnceLock}, +}; + +use crate::{ + Error, + Result, + packet::{ + Key, + Signature, + key, + signature::subpacket::{SubpacketTag, SubpacketValue}, + }, +}; + +/// Lazily verified signatures, similar to a `Vec<Signature>`. +/// +/// We use two distinct vectors to store the signatures and their +/// state. The reason for that is that we need to modify the +/// signature states while the signatures are borrowed. +/// +/// We provide a subset of `Vec<Signature>`'s interface to make it +/// (mostly) a drop-in replacement. +/// +/// # Invariant +/// +/// - There are as many signatures as signature states. +/// +/// - If the field `verified_sigs` is used, then there must have been +/// a bad signature (i.e. len(verified_sigs) < len(sigs)). +#[derive(Debug)] +pub struct LazySignatures { + /// The primary key to verify the signatures with. + primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>, + + /// The signatures. + sigs: Vec<Signature>, + + /// The signature states. + states: Mutex<Vec<SigState>>, + + /// Verified signatures. + /// + /// Because of https://gitlab.com/sequoia-pgp/sequoia/-/issues/638 + /// we have to hand out contiguous slices of verified signatures. + /// If all signatures are good, we can serve that request from + /// `sigs`. Otherwise, we have to clone the verified signatures. + /// + /// XXXv2: Remove this field. + verified_sigs: OnceLock<Vec<Signature>>, +} + +impl PartialEq for LazySignatures { + fn eq(&self, other: &Self) -> bool { + self.assert_invariant(); + other.assert_invariant(); + self.primary_key == other.primary_key + && self.sigs == other.sigs + } +} + +impl Clone for LazySignatures { + fn clone(&self) -> Self { + self.assert_invariant(); + LazySignatures { + primary_key: self.primary_key.clone(), + sigs: self.sigs.clone(), + // Avoid blocking. If we fail to get the lock, reset the + // signature states to unverified in the clone. + states: if let Ok(states) = self.states.try_lock() { + states.clone() + } else { + vec![SigState::Unverified; self.sigs.len()] + }.into(), + verified_sigs: Default::default(), + } + } +} + +/// Verification state of a signature. +#[derive(Debug, Clone, PartialEq, Eq)] +pub enum SigState { + /// Not yet verified. + Unverified, + + /// Verification was successful. + Good, + + /// Verification failed. + Bad, +} + +impl LazySignatures { + /// Asserts the invariant. + fn assert_invariant(&self) { + debug_assert_eq!(self.sigs.len(), self.states.lock().unwrap().len()); + debug_assert!( + self.verified_sigs.get().map(|v| v.len() < self.sigs.len()) + .unwrap_or(true)); + } + + /// Creates a vector of lazily verified signatures. + /// + /// The provided `primary_key` is used to verify the signatures. + /// It should be shared across the certificate. + pub fn new(primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>) + -> Self + { + LazySignatures { + primary_key, + sigs: Default::default(), + states: Default::default(), + verified_sigs: Default::default(), + } + } + + /// Like [`Vec::is_empty`]. + pub fn is_empty(&self) -> bool { + self.assert_invariant(); + self.sigs.is_empty() + } + + /// Like [`std::mem::take`]. + pub fn take(&mut self) -> Vec<Sig |