openpgp: Fix signature deduplication.

  - In order to deduplicate signatures, we need to sort them first.
    Previously, we used sig_cmp for that, which sorts by signature
    creation time and uses the actual signature data as a tie breaker.
    This, however, is not a suitable relation for deduplication with
    Signature::normalized_eq: Here, we need an order that is consistent
    with the equality operation, which sig_cmp is not.

  - Fix this by providing and using Signature::normalized_cmp.

  - Fixes #573.

3 files changed, 81 insertions, 14 deletions

diff --git a/openpgp/src/cert/bundle.rs b/openpgp/src/cert/bundle.rs
index 5dd56662..98c865cb 100644
--- a/openpgp/src/cert/bundle.rs
+++ b/openpgp/src/cert/bundle.rs
@@ -611,19 +611,28 @@ impl<C> ComponentBundle<C> {
     // that is kept is undefined.
     pub(crate) fn sort_and_dedup(&mut self)
     {
-        self.self_signatures.sort_by(sig_cmp);
+        self.self_signatures.sort_by(Signature::normalized_cmp);
         self.self_signatures.dedup_by(|a, b| a.normalized_eq(b));
+        // Order self signatures so that the most recent one comes
+        // first.
+        self.self_signatures.sort_by(sig_cmp);
 
-        // There is no need to sort the certifications, but we do
-        // want to remove dups and sorting is a prerequisite.
-        self.certifications.sort_by(sig_cmp);
+        self.certifications.sort_by(Signature::normalized_cmp);
         self.certifications.dedup_by(|a, b| a.normalized_eq(b));
+        // There is no need to sort the certifications, but doing so
+        // has the advantage that the most recent ones (and therefore
+        // presumably the more relevant ones) come first.  Also,
+        // cert::test::signature_order checks that the signatures are
+        // sorted.
+        self.certifications.sort_by(sig_cmp);
 
-        self.self_revocations.sort_by(sig_cmp);
+        self.self_revocations.sort_by(Signature::normalized_cmp);
         self.self_revocations.dedup_by(|a, b| a.normalized_eq(b));
+        self.self_revocations.sort_by(sig_cmp);
 
-        self.other_revocations.sort_by(sig_cmp);
+        self.other_revocations.sort_by(Signature::normalized_cmp);
         self.other_revocations.dedup_by(|a, b| a.normalized_eq(b));
+        self.other_revocations.sort_by(sig_cmp);
     }
 }
 
diff --git a/openpgp/src/cert/mod.rs b/openpgp/src/cert/mod.rs
index 1ce2ff00..81f8740b 100644
--- a/openpgp/src/cert/mod.rs
+++ b/openpgp/src/cert/mod.rs
@@ -1805,8 +1805,11 @@ impl Cert {
 
         self.primary.sort_and_dedup();
 
-        self.bad.sort_by(sig_cmp);
+        self.bad.sort_by(Signature::normalized_cmp);
         self.bad.dedup_by(|a, b| a.normalized_eq(b));
+        // Order bad signatures so that the most recent one comes
+        // first.
+        self.bad.sort_by(sig_cmp);
 
         self.userids.sort_and_dedup(UserID::cmp, |_, _| {});
         self.user_attributes.sort_and_dedup(UserAttribute::cmp, |_, _| {});
diff --git a/openpgp/src/packet/signature/mod.rs b/openpgp/src/packet/signature/mod.rs
index edbab5f2..35a3c33c 100644
--- a/openpgp/src/packet/signature/mod.rs
+++ b/openpgp/src/packet/signature/mod.rs
@@ -1928,13 +1928,68 @@ impl crate::packet::Signature {
     /// # }
     /// ```
     pub fn normalized_eq(&self, other: &Signature) -> bool {
-        self.mpis() == other.mpis()
-            && self.version() == other.version()
-            && self.typ() == other.typ()
-            && self.pk_algo() == other.pk_algo()
-            && self.hash_algo() == other.hash_algo()
-            && self.hashed_area() == other.hashed_area()
-            && self.digest_prefix() == other.digest_prefix()
+        self.normalized_cmp(other) == Ordering::Equal
+    }
+
+    /// Compares Signatures ignoring the unhashed subpacket area.
+    ///
+    /// This is useful to deduplicate signatures by first sorting them
+    /// using this function, and then deduplicating using the
+    /// [`Signature::normalized_eq`] predicate.
+    ///
+    ///   [`Signature::normalized_eq`]: #method.normalized_eq
+    ///
+    /// This comparison function ignores the unhashed subpacket area
+    /// when comparing two signatures.  This prevents a malicious
+    /// party from taking valid signatures, adding subpackets to the
+    /// unhashed area, and deriving valid but distinct signatures,
+    /// which could be used to perform a denial of service attack.
+    /// For instance, an attacker could create a lot of signatures,
+    /// which need to be validated.  Ignoring the unhashed subpackets
+    /// means that we can deduplicate signatures using this predicate.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::cmp::Ordering;
+    /// use sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// use openpgp::packet::prelude::*;
+    /// use openpgp::packet::signature::subpacket::{Subpacket, SubpacketValue};
+    /// use openpgp::policy::StandardPolicy;
+    /// use openpgp::types::SignatureType;
+    /// use openpgp::types::Features;
+    ///
+    /// # fn main() -> openpgp::Result<()> {
+    /// let p = &StandardPolicy::new();
+    ///
+    /// let (cert, _) = CertBuilder::new().generate()?;
+    ///
+    /// let orig = cert.with_policy(p, None)?.direct_key_signature()?;
+    ///
+    /// // Add an inconspicuous subpacket to the unhashed area.
+    /// let sb = Subpacket::new(SubpacketValue::Features(Features::empty()), false)?;
+    /// let mut modified = orig.clone();
+    /// modified.unhashed_area_mut().add(sb);
+    ///
+    /// // We modified the signature, but the signature is still valid.
+    /// modified.verify_direct_key(cert.primary_key().key(), cert.primary_key().key());
+    ///
+    /// // PartialEq considers the packets to not be equal...
+    /// assert!(orig != &modified);
+    /// // ... but normalized_partial_cmp does.
+    /// assert!(orig.normalized_cmp(&modified) == Ordering::Equal);
+    /// # Ok(()) }
+    /// ```
+    pub fn normalized_cmp(&self, other: &Signature)
+                          -> Ordering {
+        self.mpis().cmp(other.mpis())
+            .then_with(|| self.version().cmp(&other.version()))
+            .then_with(|| self.typ().cmp(&other.typ()))
+            .then_with(|| self.pk_algo().cmp(&other.pk_algo()))
+            .then_with(|| self.hash_algo().cmp(&other.hash_algo()))
+            .then_with(|| self.hashed_area().cmp(other.hashed_area()))
+            .then_with(|| self.digest_prefix().cmp(other.digest_prefix()))
     }
 
     /// Normalizes the signature.