sequoia_wot/

certification.rs

use std::borrow::Cow;
use std::cmp::Ordering;
use std::collections::HashMap;
use std::collections::hash_map::Entry;
use std::fmt;
use std::time::SystemTime;
use std::time::Duration;

use sequoia_openpgp as openpgp;
use openpgp::cert::prelude::*;
use openpgp::KeyHandle;
use openpgp::packet::UserID;
use openpgp::regex::RegexSet;
use openpgp::packet::Signature;
use openpgp::policy::HashAlgoSecurity;

use crate::CertSynopsis;
use crate::format_time;
use crate::Result;
use crate::RevocationStatus;

use crate::TRACE;

/// [`Certification`] specific error codes.
#[non_exhaustive]
#[derive(thiserror::Error, Debug)]
pub enum CertificationError {
    /// No creation time.
    ///
    /// The certification is invalid, because it does not include the
    /// required CreationTime subpacket.
    #[error("{0}: invalid, missing creation time")]
    MissingCreationTime(Certification),

    /// The certification violates the policy.
    #[error("{0}: policy violation")]
    InvalidCertification(Certification, #[source] anyhow::Error),

    #[error("{0}: issuer revoked the certification")]
    IssuerRevoked(Certification),

    #[error("{0}: certification created after reference time ({time})",
            time=format_time(.1))]
    BornLater(Certification, SystemTime),

    /// The certification is expired (1) as of the reference time (2).
    #[error("{0}: certification expired ({time1}) as of reference time ({time2})",
            time1=format_time(.1), time2=format_time(.2))]
    CertificationExpired(Certification, SystemTime, SystemTime),

    #[error("{0}: target is not live \
             as of the certification time ({time})",
            time=format_time(.1))]
    TargetNotLive(Certification, SystemTime, #[source] anyhow::Error),

    #[error("{0}: target certificate is not valid \
             as of the certification time ({time})",
            time=format_time(.1))]
    TargetNotValid(Certification, SystemTime, #[source] anyhow::Error),

    #[error("{0}: issuer certificate is hard revoked: {1} ({msg})",
            msg=String::from_utf8_lossy(.2))]
    IssuerHardRevoked(Certification,
                      openpgp::types::ReasonForRevocation, Vec<u8>),

    #[error("{0}: issuer certificate is soft revoked \
             as of the certification time ({time}): {2} ({msg})",
            time=format_time(.1),
            msg=String::from_utf8_lossy(.3))]
    IssuerSoftRevoked(Certification, SystemTime,
                      openpgp::types::ReasonForRevocation, Vec<u8>),

    #[error("{0}: target certificate is hard revoked: {1} ({msg})",
            msg=String::from_utf8_lossy(.2))]
    TargetHardRevoked(Certification,
                      openpgp::types::ReasonForRevocation, Vec<u8>),

    #[error("{0}: target certificate is soft revoked \
             as of the certification time ({time}): {2} ({msg})",
            time=format_time(.1),
            msg=String::from_utf8_lossy(.3))]
    TargetSoftRevoked(Certification, SystemTime,
                      openpgp::types::ReasonForRevocation, Vec<u8>),
}

/// Trust depth.
///
/// A certification may include a [trust signature subpacket], which
/// specifies that the issuer not only considers the target binding to
/// be correct, but that they are also willing to rely on certifications
/// that the target certificate makes.  That is, if Alice designates
/// Bob as a trusted introducer, than if Carol is willing to rely on
/// Alice's certifications, she should also be willing to rely on
/// Bob's.
///
/// The trust depth is one of two parameters stored in the trust
/// signature subpacket, and indicates how far that capability may be
/// delegated.  A value of zero means that the certification is
/// actually a normal certification, and the target is *not* a trusted
/// introducer.  A value of one means that the target certificate
/// should be considered a trusted introducer, but it may not further
/// delegate that capability.  A value of two means that the target
/// certificate should be considered a trusted introducer, and that it
/// may delegate that capability to another certificate, but they may
/// not further delegate it.  In short, a value of `n` means that
/// there may be up to `n` intervening trusted introducers between the
/// issuer and the target binding:
///
///   - 0: Normal certification.
///   - 1: Trusted introducer.
///   - 2: Meta-introducer.
///   - etc.
///
/// A value of 255, the maximum value that can be stored in the
/// OpenPGP data structure, has a special meaning: the issuer does not
/// impose a constraint on the number of delegations.
///
/// This data structure does not automatically convert a value of 255
/// to `Depth::Unconstrained`; the caller must specify
/// `Depth::Unconstrained` explicitly.
///
///   [trust signature subpacket]: https://datatracker.ietf.org/doc/html/rfc4880#section-5.2.3.13
#[derive(Debug, Clone, Copy, Eq)]
pub enum Depth {
    Unconstrained,
    Limit(usize),
}

impl Depth {
    pub fn new<I>(depth: I) -> Self
        where I: Into<Option<usize>>
    {
        if let Some(d) = depth.into() {
            Depth::Limit(d)
        } else {
            Depth::Unconstrained
        }
    }

    /// Returns an unconstrained `Depth`.
    pub fn unconstrained() -> Self {
        Depth::Unconstrained
    }

    /// Returns whether this `Depth` is unconstrained.
    pub fn is_unconstrained(&self) -> bool {
        matches!(self, Depth::Unconstrained)
    }

    /// Returns whether this `Depth` allows introducing.
    pub fn can_introduce(&self) -> bool {
        match self {
            Depth::Unconstrained => true,
            Depth::Limit(d) if *d > 0 => true,
            _ => false
        }
    }

    /// Converts the `Depth` to an `Option<usize>`.
    ///
    /// An unconstrained depth is converted to `None`.  A constrained
    /// depth of `d` is converted to `Some(d)`.
    pub fn limit(&self) -> Option<usize> {
        match self {
            Depth::Unconstrained => None,
            Depth::Limit(d) => Some(*d),
        }
    }

    /// Decreases the depth by `value`.
    ///
    /// The depth must be at least as large as `value`.  If the depth
    /// is unconstrained, decreasing the depth doesn't do anything.
    pub fn decrease(&self, value: usize) -> Depth {
        match self {
            Depth::Unconstrained => {
                // Still unconstrained.
                Depth::Unconstrained
            }
            Depth::Limit(d) => {
                assert!(*d >= value);
                Depth::Limit(d - value)
            }
        }
    }
}

impl fmt::Display for Depth {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Depth::Unconstrained => write!(f, "unconstrained"),
            Depth::Limit(d) => write!(f, "{}", d),
        }
    }
}

impl From<usize> for Depth {
    fn from(d: usize) -> Self {
        Depth::new(d)
    }
}

impl From<Option<usize>> for Depth {
    fn from(d: Option<usize>) -> Self {
        Depth::new(d)
    }
}

impl PartialOrd for Depth {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Depth {
    fn cmp(&self, other: &Self) -> Ordering {
        match (self, other) {
            (Depth::Unconstrained, Depth::Unconstrained) => Ordering::Equal,
            (Depth::Limit(_), Depth::Unconstrained) => Ordering::Less,
            (Depth::Unconstrained, Depth::Limit(_)) => Ordering::Greater,
            (Depth::Limit(x), Depth::Limit(y)) => x.cmp(&y),
        }
    }
}

impl PartialEq for Depth {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

/// Encapsulates a certification.
///
/// This data structure holds the information about a certification
/// that is relevant to web of trust calculations.  Note: this data
/// structure includes the certification's context (the issuer and the
/// certified binding), which is not included in an OpenPGP signature.
///
/// If the User ID is None, then this is a delegation.
#[derive(Clone)]
pub struct Certification {
    issuer: CertSynopsis,
    target: CertSynopsis,
    // If None, it's a delegation.
    userid: Option<UserID>,

    creation_time: SystemTime,
    expiration_time: Option<SystemTime>,

    exportable: bool,

    /// 60: partial trust.
    /// 120: complete trust.
    amount: usize,

    /// Trust depth.
    depth: Depth,

    /// Scope.  If None, then the Regexes are invalid and nothing
    /// should match.
    re_set: Option<RegexSet>,
    /// RegexSet doesn't implement PartialEq.  To allow Certification
    /// to implement PartialEq, we store the bytes.
    re_bytes: Vec<Vec<u8>>,

    /// The digest prefix.
    digest_prefix: Option<[u8; 2]>,
}

impl<'a> From<(&'a ValidCert<'a>, &'a ValidCert<'a>, &'a Signature)>
    for Certification
{
    fn from(x: (&ValidCert, &ValidCert, &Signature)) -> Self {
        Certification::from_signature(
            x.0,
            x.1.primary_userid().ok().map(|ua| ua.userid().clone()),
            x.1,
            x.2)
    }
}

impl PartialEq for Certification {
    fn eq(&self, other: &Self) -> bool {
        self.issuer.fingerprint() == other.issuer.fingerprint()
            && self.target.fingerprint() == other.target.fingerprint()
            && self.userid == other.userid
            && self.creation_time == other.creation_time
            && self.expiration_time == other.expiration_time
            && self.exportable == other.exportable
            && self.amount == other.amount
            && self.depth == other.depth
            // RegexSet doesn't implement eq.
            && self.re_bytes == other.re_bytes
            // We explicitly don't check digest_prefix as we may not
            // have it.  This isn't bad as if everything else the
            // same, they are the same!
    }
}

impl fmt::Display for Certification {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}by {} on {} at {}",
               if let Some(digest_prefix) = self.digest_prefix {
                   format!("{:02X}{:02X} ",
                           digest_prefix[0], digest_prefix[1])
               } else {
                   "".to_string()
               },
               self.issuer.keyid(),
               self.target.keyid(),
               format_time(&self.creation_time))
    }
}

impl fmt::Debug for Certification {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Certification")
            .field("issuer", &self.issuer.fingerprint())
            .field("target", &self.target)
            .field("userid",
                   &self.userid.as_ref().map(|uid| {
                       String::from_utf8_lossy(uid.value()).into_owned()
                   })
                   .unwrap_or_else(|| "<None>".into()))
            .field("creation time",
                   &self.creation_time
                       .duration_since(SystemTime::UNIX_EPOCH)
                       .unwrap_or_else(|_| Duration::new(0, 0)))
            .field("expiration time",
                   &if let Some(e) = self.expiration_time {
                       format!("{:?}",
                                e
                                .duration_since(SystemTime::UNIX_EPOCH)
                                .unwrap_or_else(|_| Duration::new(0, 0)))
                   } else {
                       "never".to_string()
                   })
            .field("amount", &self.amount)
            .field("depth", &self.depth)
            .field("regexes",
                   &if let Some(re_set) = self.re_set.as_ref() {
                       if re_set.matches_everything() {
                           String::from("*")
                       } else {
                           format!("{:?}", &re_set)
                       }
                   } else {
                       String::from("<invalid RE>")
                   })
            .finish()
    }
}

impl Certification {
    /// Returns a `Certification`.
    ///
    /// The returned certification's amount is set to 120 (fully
    /// trusted), its depth to 0 (it's not a trusted introducer), and
    /// no regular expression is set.
    ///
    /// # Examples
    ///
    /// `0xAA` (bob@example.org) certifies the binding `<0xBB,
    /// bob@example.org>`.
    ///
    /// ```
    /// use std::iter;
    /// use std::time::SystemTime;
    ///
    /// use sequoia_openpgp as openpgp;
    /// use openpgp::Fingerprint;
    /// use openpgp::parse::Parse;
    ///
    /// use sequoia_wot::CertSynopsis;
    /// use sequoia_wot::UserIDSynopsis;
    /// use sequoia_wot::Certification;
    /// use sequoia_wot::RevocationStatus;
    ///
    /// let alice_fpr: Fingerprint =
    ///     "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
    ///    .parse().expect("valid fingerprint");
    /// let alice_uid
    ///     = UserIDSynopsis::from("<alice@example.org>");
    ///
    /// let bob_fpr: Fingerprint =
    ///     "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
    ///    .parse().expect("valid fingerprint");
    /// let bob_uid
    ///     = UserIDSynopsis::from("<bob@example.org>");
    ///
    /// let alice = CertSynopsis::new(
    ///     alice_fpr, None, RevocationStatus::NotAsFarAsWeKnow,
    ///     iter::once(alice_uid));
    /// let bob = CertSynopsis::new(
    ///     bob_fpr, None, RevocationStatus::NotAsFarAsWeKnow,
    ///     iter::once(bob_uid.clone()));
    ///
    /// let c = Certification::new(
    ///     alice, Some(bob_uid.userid().clone()), bob,
    ///     SystemTime::now());
    /// ```
    pub fn new<C1, U, C2>(issuer: C1,
                          userid: Option<U>,
                          target: C2,
                          creation_time: SystemTime)
        -> Self
        where C1: Into<CertSynopsis>,
              U: Into<UserID>,
              C2: Into<CertSynopsis>,
    {
        let issuer = issuer.into();
        let target = target.into();

        Certification {
            issuer: issuer,
            userid: userid.map(Into::into),
            target: target,
            creation_time: creation_time,
            expiration_time: None,
            exportable: true,
            depth: Depth::new(0),
            amount: 120,
            re_set: Some(RegexSet::everything()),
            re_bytes: Vec::new(),
            digest_prefix: None,
        }
    }

    /// Creates a `Certification` from a `Signature`.
    ///
    /// `userid` and `target` are the certified binding.  If no User
    /// ID is supplied, this is interpreted as a delegation.
    ///
    /// The signature is assumed to be valid.
    ///
    /// If the signature does not have a signature creation time
    /// (which technically makes the signature [invalid]), it defaults
    /// to the [Unix epoch].
    ///
    ///   [invalid]: https://datatracker.ietf.org/doc/html/rfc4880#section-5.2.3.4
    ///   [Unix epoch]: https://en.wikipedia.org/wiki/Unix_time
    pub fn from_signature<C1, U, C2>(issuer: C1,
                                     userid: Option<U>,
                                     target: C2,
                                     sig: &Signature)
        -> Self
        where C1: Into<CertSynopsis>,
              U: Into<UserID>,
              C2: Into<CertSynopsis>,
    {
        let (d, a, r) = if let Some((d, a)) = sig.trust_signature()
        {
            (d as usize,
             a as usize,
             Some(sig.regular_expressions()))
        } else {
            (0, 120, None)
        };

        let mut c = Self::new(issuer, userid, target,
                              sig.signature_creation_time()
                                  .unwrap_or(std::time::UNIX_EPOCH))
            .set_amount(a)
            .set_depth(Depth::new(if d == 255 { None } else { Some(d) }));
        if let Some(r) = r {
            let r: Vec<&[u8]> = r.collect();
            c = c.set_regular_expressions(r.iter().cloned());
            c.re_bytes = r.into_iter().map(<[u8]>::to_vec).collect();
        }
        if let Some(e) = sig.signature_expiration_time() {
            c = c.set_expiration_time(Some(e));
        }
        c = c.set_exportable(sig.exportable_certification().unwrap_or(true));

        c.digest_prefix = Some(*sig.digest_prefix());

        c
    }

    /// Returns a certification, if the certification is valid.
    ///
    /// This function is different from
    /// `Certification::from_signature`, which works with Synopses,
    /// and assumes the certification is valid.  This function checks
    /// that the certification is valid, and only returns a
    /// `Certification` if that is the case.
    ///
    /// Note a signature may have multiple [Issuer] or Issuer
    /// Fingerprint packets.  This function ignores those and checks
    /// whether the provided certificate issued the certificate.
    /// Normally, you'll want to call this function in a loop, once
    /// for each of the alleged issuers.
    ///
    /// [Issuer]: https://www.rfc-editor.org/rfc/rfc4880#section-5.2.3.5
    pub fn try_from_signature(possible_issuer: &ValidCert,
                              ua: Option<&UserIDAmalgamation>,
                              target: &ValidCert,
                              certification: &Signature)
        -> Result<Self>
    {
        tracer!(TRACE, "Certification::try_from_signature");

        let reference_time = target.time();

        let certification_time =
            if let Some(t) = certification.signature_creation_time() {
                t
            } else {
                return Err(CertificationError::MissingCreationTime(
                    (possible_issuer, target, certification).into()).into());
            };

        let verify = |possible_issuer: &ValidCert| -> Result<Certification>
        {
            if let Err(err) = target.policy()
                .signature(
                    certification, HashAlgoSecurity::CollisionResistance)
            {
                return Err(CertificationError::InvalidCertification(
                    (possible_issuer, target, certification).into(),
                    err).into());
            }

            certification
                .clone()
                .verify_signature(possible_issuer.primary_key().key())?;

            // Ignore if the issuer is not alive at the
            // certification time (not the reference time!).
            let possible_issuer_then
                = possible_issuer.clone().with_policy(
                    possible_issuer.policy(), certification_time)?;

            if let Err(err) = possible_issuer_then.alive() {
                t!("Skipping certification {:02X}{:02X}: issuer \
                    was not alive at certification time.",
                   certification.digest_prefix()[0],
                   certification.digest_prefix()[1]);

                return Err(err.context(
                    "issuer not alive at certification time"));
            }

            // Ignore if the issuer was revoked at the
            // certification time (not the reference time!).
            let rs = possible_issuer_then.revocation_status();
            if let openpgp::types::RevocationStatus::Revoked(ref revs) = rs {
                // We know we have at least one revocation.
                let reason = revs.iter().next().expect("have one")
                    .reason_for_revocation();
                let msg = reason
                    .map(|r| r.1.to_vec())
                    .unwrap_or(Vec::new());
                let code = reason
                    .map(|r| r.0)
                    .unwrap_or(openpgp::types::ReasonForRevocation::Unspecified);

                match RevocationStatus::from(rs) {
                    RevocationStatus::Hard => {
                        t!("Skipping certification {:02X}{:02X}: issuer \
                            was hard revoked.",
                           certification.digest_prefix()[0],
                           certification.digest_prefix()[1]);
                        return Err(CertificationError::IssuerHardRevoked(
                            (possible_issuer, target, certification).into(),
                            code, msg).into());
                    }
                    RevocationStatus::Soft(rev_time) => {
                        if rev_time <= certification_time {
                            t!("Skipping certification {:02X}{:02X}: issuer \
                                was soft revoked at certification time.",
                               certification.digest_prefix()[0],
                               certification.digest_prefix()[1]);
                            return Err(CertificationError::IssuerSoftRevoked(
                                (possible_issuer, target, certification).into(),
                                certification_time, code, msg).into());
                        }
                    }
                    RevocationStatus::NotAsFarAsWeKnow => unreachable!(),
                }
            }

            let issuer: KeyHandle
                = possible_issuer.fingerprint().into();

            // Ignore if the issuer later revoked the
            // certification.
            if let Some(ua) = ua {
                for rev in ua.other_revocations() {
                    // We have a UserIDAmalgamation, not a
                    // ValidUserIDAmalgamation, so we need to check
                    // that the revocation is valid under the current
                    // policy ourselves.
                    if target.policy()
                        .signature(
                            // XXX: Is this right for revocations?
                            rev, HashAlgoSecurity::CollisionResistance)
                        .is_err()
                    {
                        continue;
                    }

                    // All User ID revocations are soft
                    // revocations.  So if the User ID was later
                    // recertified, that's okay.
                    if let Some(rev_time) = rev.signature_creation_time() {
                        if rev_time > reference_time {
                            // Revocation is not yet live.  Ignore it.
                            continue;
                        }
                        if rev_time <= certification_time {
                            // Certification is newer than the
                            // revocation.  Ignore the revocation.
                            continue;
                        }
                    } else {
                        // Invalid signature.
                        continue;
                    };

                    // We explicitly ignore any expiration on
                    // revocations.

                    // Check that the issuer actually issued this
                    // revocation.
                    if rev.get_issuers().iter().any(|kh| {
                        kh.aliases(&issuer)
                    }) {
                        if let Ok(()) = rev
                            .clone()
                            .verify_signature(possible_issuer.primary_key().key())
                        {
                            t!("issuer revoked certification, ignoring");
                            return Err(
                                CertificationError::IssuerRevoked((
                                    possible_issuer, target, certification).into())
                                    .into());
                        }
                    }
                }
            }


            let (depth, amount, re_set) = if let Some((d, a))
                = certification.trust_signature()
            {
                (d, a, RegexSet::from_signature(certification)
                 .expect("internal error"))
            } else {
                (0, 120, RegexSet::everything())
            };

            t!("<{}, {}> {} <{}, {}> \
                (depth: {}, amount: {}, scope: {:?})",
               possible_issuer.cert().keyid(),
               possible_issuer
               .primary_userid()
               .map(|ua| {
                   String::from_utf8_lossy(ua.userid().value()).into_owned()
               })
               .unwrap_or("[no User ID]".into()),
               if depth > 0 {
                   "tsigned"
               } else {
                   "certified"
               },
               target.keyid(),
               ua.map(|ua| String::from_utf8_lossy(ua.userid().value()))
                   .unwrap_or(Cow::Borrowed("(delegation)")),
               depth,
               amount,
               if re_set.matches_everything() {
                   "*".into()
               } else {
                   format!("{:?}", re_set)
               });

            Ok(Certification::from_signature(
                possible_issuer, ua.map(|ua| ua.userid().clone()), target,
                certification))
        };

        // Ignore if the certification is not alive at the
        // reference time.
        if reference_time < certification_time {
            t!("Skipping certification {:02X}{:02X}: \
                created ({:?}) after reference time ({:?}).",
               certification.digest_prefix()[0],
               certification.digest_prefix()[1],
               certification_time, reference_time);
            return Err(CertificationError::BornLater(
                (possible_issuer, target, certification).into(),
                reference_time).into());
        }
        if let Some(e) = certification.signature_expiration_time() {
            if e <= reference_time {
                t!("Skipping certification {:02X}{:02X}: \
                    expired ({:?}) as of reference time ({:?}).",
                   certification.digest_prefix()[0],
                   certification.digest_prefix()[1],
                   e, reference_time);
                return Err(CertificationError::CertificationExpired(
                    (possible_issuer, target, certification).into(),
                    e, reference_time).into());
            }
        }

        let target_then =
            match target.clone()
            .with_policy(target.policy(), certification_time)
        {
            Ok(vc) => vc,
            Err(err) => {
                t!("Skipping certification {:02X}{:02X}: target \
                    was not valid at certification time: {}.",
                   certification.digest_prefix()[0],
                   certification.digest_prefix()[1],
                   err);
                return Err(CertificationError::TargetNotValid(
                    (possible_issuer, target, certification).into(),
                    certification_time, err).into());
            }
        };

        // Ignore if the target is not alive at the
        // certification time (not the reference time!).
        if let Err(err) = target_then.alive() {
            t!("Skipping certification {:02X}{:02X}: target \
                not alive at certification time: {}.",
               certification.digest_prefix()[0],
               certification.digest_prefix()[1],
               err);
            return Err(CertificationError::TargetNotLive(
                (possible_issuer, target, certification).into(),
                certification_time, err).into());
        }

        // Ignore if the target was revoked at the
        // certification time (not the reference time!).
        let rs = target_then.revocation_status();
        if let openpgp::types::RevocationStatus::Revoked(ref revs) = rs {
            // We know we have at least one revocation.
            let reason = revs.iter().next().expect("have one")
                .reason_for_revocation();
            let msg = reason
                .map(|r| r.1.to_vec())
                .unwrap_or(Vec::new());
            let code = reason
                .map(|r| r.0)
                .unwrap_or(openpgp::types::ReasonForRevocation::Unspecified);

            match RevocationStatus::from(rs) {
                RevocationStatus::Hard => {
                    t!("Skipping certification {:02X}{:02X}: target \
                        was hard revoked at certification time.",
                       certification.digest_prefix()[0],
                       certification.digest_prefix()[1]);
                    return Err(CertificationError::TargetHardRevoked(
                        (possible_issuer, target, certification).into(),
                        code, msg).into());
                }
                RevocationStatus::Soft(rev_time) => {
                    if rev_time <= certification_time {
                        t!("Skipping certification {:02X}{:02X}: target \
                            was soft revoked at certification time.",
                           certification.digest_prefix()[0],
                           certification.digest_prefix()[1]);
                        return Err(CertificationError::TargetSoftRevoked(
                            (possible_issuer, target, certification).into(),
                            certification_time, code, msg).into());
                    }
                }
                RevocationStatus::NotAsFarAsWeKnow => unreachable!(),
            }
        }

        match verify(&possible_issuer) {
            Ok(certification) => {
                t!("Using certification \
                    by {} for <{:?}, {}> at {:?}: \
                    {}/{}.",
                   possible_issuer,
                   ua.map(|ua| String::from_utf8_lossy(ua.userid().value()))
                       .unwrap_or(Cow::Borrowed("(delegation)")),
                   target.keyid(),
                   certification.creation_time(),
                   certification.depth(),
                   certification.amount());

                Ok(certification)
            }
            Err(err) => {
                t!("Invalid certification {:02X}{:02X} \
                    by {} for <{:?}, {}>: {}",
                   certification.digest_prefix()[0],
                   certification.digest_prefix()[1],
                   possible_issuer,
                   ua.map(|ua| String::from_utf8_lossy(ua.userid().value()))
                       .unwrap_or(Cow::Borrowed("(delegation)")),
                   target.keyid(),
                   err);
                Err(err)
            }
        }
    }

    /// Returns the certification's issuer.
    pub fn issuer(&self) -> &CertSynopsis {
        &self.issuer
    }

    /// Returns the certification's target certificate.
    pub fn target(&self) -> &CertSynopsis {
        &self.target
    }

    /// Returns the certification's target UserID, if any.
    pub fn userid(&self) -> Option<&UserID> {
        self.userid.as_ref()
    }

    /// Returns the certification's creation time.
    pub fn creation_time(&self) -> SystemTime {
        self.creation_time
    }

    /// Returns the certification's expiration time, if any.
    pub fn expiration_time(&self) -> Option<SystemTime> {
        self.expiration_time
    }

    /// Sets the certification's expiration time.
    pub fn set_expiration_time<I>(mut self, expiration_time: I) -> Self
        where I: Into<Option<SystemTime>>
    {
        self.expiration_time = expiration_time.into();
        self
    }

    /// Returns whether the certification is marked as exportable (i.e.,
    /// not a so-called local signature).
    pub fn exportable(&self) -> bool {
        self.exportable
    }

    /// Sets whether the certification is marked as exportable (i.e.,
    /// not a so-called local signature).
    pub fn set_exportable(mut self, exportable: bool) -> Self {
        self.exportable = exportable;
        self
    }

    /// Returns the certification's trust amount.
    pub fn amount(&self) -> usize {
        self.amount
    }

    /// Sets the certification's trust amount.
    pub fn set_amount(mut self, amount: usize) -> Self {
        self.amount = amount;
        self
    }

    /// Returns the certification's trust depth.
    pub fn depth(&self) -> Depth {
        self.depth
    }

    /// Sets the certification's trust depth.
    ///
    /// Note: this function does not automatically convert the value
    /// `255` to `Depth::Unconstrained`.
    pub fn set_depth<I>(mut self, depth: I) -> Self
    where I: Into<Depth>
    {
        self.depth = depth.into();
        self
    }

    /// Returns the certification's regular expressions.
    ///
    /// If the signature has none, this returns a regular expression
    /// that matches everything.
    ///
    /// If any of the regular expressions were invalid, this returns
    /// `None`.
    pub fn regular_expressions(&self) -> Option<&RegexSet> {
        self.re_set.as_ref()
    }

    /// Returns the certification's regular expressions as a slice of
    /// byte strings.
    pub fn regular_expressions_bytes(&self) -> &[Vec<u8>] {
        &self.re_bytes[..]
    }

    /// Sets the certification's regular expressions.
    pub fn set_regular_expressions<'a>(mut self,
                                       re_set: impl Iterator<Item=&'a [u8]>)
        -> Self
    {
        let regexes: Vec<&[u8]> = re_set.collect();
        self.re_set = RegexSet::from_bytes(&regexes).ok();
        self.re_bytes = regexes.into_iter().map(Into::into).collect();
        self
    }

    /// Returns the certification's digest prefix, if it is known.
    pub fn digest_prefix(&self) -> Option<&[u8; 2]> {
        self.digest_prefix.as_ref()
    }
}

/// All active certifications that one certificate made on another.
///
/// Encapsulates the *active* certifications with respect to a
/// reference time that a certificate made on another certificate.
/// For instance, if the certificate 0xB has two User IDs: B and B'
/// and 0xA signed both, then this contains the latest certification
/// for <0xA, B:0xB> and the latest certification for <0xA, B':0xB>.
#[derive(Clone)]
pub struct CertificationSet {
    // The certificate that issued the certifications.
    issuer: CertSynopsis,
    // The certificate that was signed.
    target: CertSynopsis,

    reference_time: SystemTime,

    // The certifications, keyed by the certified (target) User ID.
    // It is reasonable to have multiple certifications over the same
    // User ID if they all have the same timestamp.
    certifications: HashMap<Option<UserID>, Vec<Certification>>,
}

impl CertificationSet {
    /// Returns an empty CertificationSet.
    pub(crate) fn empty<I, T>(issuer: I, target: T,
                              reference_time: SystemTime)
        -> Self
    where I: Into<CertSynopsis>,
          T: Into<CertSynopsis>,
    {
        Self {
            issuer: issuer.into(),
            target: target.into(),
            reference_time: reference_time,
            certifications: HashMap::new(),
        }
    }

    /// Returns a new CertificationSet with the supplied
    /// certification.
    pub fn from_certification(certification: Certification,
                              reference_time: SystemTime) -> Self
    {
        let mut cs = CertificationSet::empty(
            certification.issuer.clone(),
            certification.target.clone(),
            reference_time);
        cs.add(certification);
        cs
    }

    /// Splits the supplied certifications into CertificationSets.
    ///
    /// This function splits the supplied [`Certification`]s into
    /// `CertificationSet`s.  The certifications may come from
    /// different issuers, be for different targets, and over
    /// different User IDs (or just be delegations), and they will be
    /// added to an appropriate `CertificationSet`.
    ///
    /// Any invalid or unneeded certifications are silently pruned.
    /// For instance, this function discards certifications that were
    /// created after the reference time, or are expired as of the
    /// reference time.  It also only keeps the most recent
    /// certifications for a given `<issuer, target, userid>` tuple.
    /// (Sometimes there are multiple certifications with the same
    /// timestamp.  In this case, all of those certificates are kept.)
    pub fn from_certifications(mut certifications: Vec<Certification>,
                               reference_time: SystemTime) -> Vec<Self>
    {
        if certifications.is_empty() {
            return Vec::new();
        }

        certifications.retain(|c| {
            // Keep it if it is born at or before the reference time
            c.creation_time <= reference_time
                // and it expires after the reference time.
                && c.expiration_time.map(|e| e > reference_time).unwrap_or(true)
        });

        // Sort them so that they are grouped by <issuer, target, User
        // ID>, and with each group sorted so that the most recent
        // certification comes first.
        certifications.sort_unstable_by(|a, b| {
            a.issuer().fingerprint().cmp(&b.issuer().fingerprint())
                .then(a.target().fingerprint().cmp(&b.target().fingerprint()))
                .then(a.userid().cmp(&b.userid()))
                .then(a.creation_time().cmp(&b.creation_time()).reverse())
        });

        // Create the CertificationSets.

        // The finished CertificationSets.
        let mut cs = Vec::new();
        // The CertificationSet under construction.
        let mut acc: Vec<(Option<UserID>, Vec<Certification>)>
            = Vec::with_capacity(certifications.len().min(4));

        for certification in certifications.into_iter() {
            let group = if let Some(last) = acc.last() {
                last
            } else {
                // First time through.
                acc.push((certification.userid().map(Clone::clone),
                          vec![ certification ]));
                continue;
            };

            let group_issuer = group.1[0].issuer();
            let group_target = group.1[0].target();
            let group_userid = group.0.as_ref();
            let group_certification_time = group.1[0].creation_time();

            if group_issuer.fingerprint()
                == certification.issuer().fingerprint()
                && group_target.fingerprint()
                   == certification.target().fingerprint()
            {
                // Same CertificationSet.

                if group_userid == certification.userid() {
                    // Same User ID.

                    if group_certification_time
                        == certification.creation_time()
                    {
                        // Same creation time, keep it.
                        acc.last_mut().unwrap().1.push(certification);
                    } else {
                        // The certification is older than what we
                        // have; ignore it.
                        assert!(certification.creation_time()
                                < group_certification_time);
                    }
                } else {
                    // Different User ID.  Start a new group.
                    acc.push((certification.userid().map(Clone::clone),
                              vec![ certification ]));
                }
            } else {
                // New CertificationSet.
                let issuer = acc[0].1[0].issuer().clone();
                let target = acc[0].1[0].target().clone();

                cs.push(
                    CertificationSet {
                        issuer,
                        target,
                        reference_time,
                        certifications: HashMap::from_iter(acc),
                    });

                // Reset the accumulator and start a new group.
                acc = vec![(certification.userid().map(Clone::clone),
                    vec![ certification ])];
            }
        }

        // Don't forget to add the pending CertificationSet.
        let issuer = acc[0].1[0].issuer().clone();
        let target = acc[0].1[0].target().clone();

        cs.push(
            CertificationSet {
                issuer,
                target,
                reference_time,
                certifications: HashMap::from_iter(acc),
            });

        for cs in cs.iter() {
            for (userid, certifications) in cs.certifications.iter() {
                for certification in certifications.iter() {
                    assert_eq!(userid, &certification.userid,
                               "Certification with user ID {:?} \
                                added to wrong group (user ID: {:?}",
                               certification.userid, userid);
                }
            }
        }

        cs
    }

    /// Returns the issuer's certificate.
    pub fn issuer(&self) -> &CertSynopsis {
        &self.issuer
    }

    /// Returns the target's certificate.
    pub fn target(&self) -> &CertSynopsis {
        &self.target
    }

    /// Returns the reference time.
    pub fn reference_time(&self) -> SystemTime {
        self.reference_time
    }

    /// Adds a certification to the CertificationSet.
    ///
    /// All certifications in a `CertificationSet` must be issued by
    /// the same certificate, and have the same reference time.
    ///
    /// Note: if there are multiple certifications for the same User
    /// ID, all are considered.  Normally only the newest
    /// certification should be considered.  But, there may be
    /// multiple such certifications.
    pub(crate) fn add(&mut self, certification: Certification) {
        // certification must be over the same certificate.
        if let Some((_, cs)) = self.certifications.iter().next() {
            for c in cs {
                assert_eq!(certification.issuer.fingerprint(),
                           c.issuer.fingerprint());
                assert_eq!(certification.target.fingerprint(),
                           c.target.fingerprint());
            }
        }

        match self.certifications.entry(certification.userid.clone()) {
            e @ Entry::Occupied(_) => {
                e.and_modify(|e| e.push(certification));
            }
            e @ Entry::Vacant(_) => {
                e.or_insert([ certification ].into());
            }
        }
    }

    /// Merges other into self.
    ///
    /// This function asserts that `self` and `other` are for the same
    /// issuer and target certificates.
    ///
    /// Note: if there are multiple certifications for the same User
    /// ID, all are considered.  Normally only the newest
    /// certification should be considered.  But, there may be
    /// multiple such certifications.
    pub(crate) fn merge(&mut self, other: Self) {
        assert_eq!(self.issuer.fingerprint(), other.issuer.fingerprint());
        assert_eq!(self.target.fingerprint(), other.target.fingerprint());
        assert_eq!(self.reference_time, other.reference_time);

        for (_, cs) in other.certifications.into_iter() {
            for c in cs {
                self.add(c);
            }
        }
    }

    /// Returns an iterator over all of the user ids, and their
    /// certifications.
    pub fn certifications(&self)
        -> impl Iterator<Item=(Option<&UserID>, &[Certification])>
    {
        self.certifications.iter().map(|(userid, c)| (userid.as_ref(), &c[..]))
    }

    /// Returns an iterator over the certifications.
    pub fn into_certifications(self)
        -> impl Iterator<Item=Certification>
    {
        self.certifications.into_iter()
            .flat_map(|(_userid, c)| c.into_iter())
    }
}

#[cfg(test)]
mod test {
    use super::*;

    use std::iter;
    use std::time::Duration;

    use sequoia_openpgp as openpgp;
    use openpgp::Fingerprint;
    use openpgp::Result;

    use crate::CertSynopsis;

    use crate::Depth;

    #[test]
    fn depth() -> Result<()> {
        assert_eq!(Depth::new(0), Depth::new(0));
        assert_eq!(Depth::new(10), Depth::new(10));
        assert_eq!(Depth::new(None), Depth::new(None));

        assert!(Depth::new(0) < Depth::new(1));
        assert!(Depth::new(1) < Depth::new(10));
        assert!(Depth::new(10) < Depth::new(None));
        assert!(Depth::new(255) < Depth::new(None));
        assert!(Depth::new(1000) < Depth::new(None));

        assert!(Depth::new(1) > Depth::new(0));
        assert!(Depth::new(10) > Depth::new(1));
        assert!(Depth::new(None) > Depth::new(10));
        assert!(Depth::new(None) > Depth::new(255));
        assert!(Depth::new(None) > Depth::new(1000));

        assert_eq!(std::cmp::min(Depth::new(0), Depth::new(10)),
                   Depth::new(0));
        assert_eq!(std::cmp::min(Depth::new(0), Depth::new(None)),
                   Depth::new(0));
        assert_eq!(std::cmp::min(Depth::new(1000), Depth::new(None)),
                   Depth::new(1000));

        assert_eq!(std::cmp::min(Depth::new(10), Depth::new(0)),
                   Depth::new(0));
        assert_eq!(std::cmp::min(Depth::new(None), Depth::new(0)),
                   Depth::new(0));
        assert_eq!(std::cmp::min(Depth::new(None), Depth::new(1000)),
                   Depth::new(1000));

        assert_eq!(std::cmp::min(Depth::new(None), Depth::new(None)),
                   Depth::new(None));

        Ok(())
    }

    #[test]
    fn certification_set_from_certifications() -> Result<()> {
        use openpgp::types::RevocationStatus;

        let alice_fpr: Fingerprint =
            "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
            .parse().expect("valid fingerprint");
        let alice_uid = UserID::from("<alice@example.org>");

        let alice = CertSynopsis::new(
            alice_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            iter::once((alice_uid.clone(), crate::now())));

        let bob_fpr: Fingerprint =
            "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
            .parse().expect("valid fingerprint");
        let bob_uid = UserID::from("<bob@example.org>");

        let bob = CertSynopsis::new(
            bob_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            iter::once((bob_uid.clone(), crate::now())));

        let carol_fpr: Fingerprint =
            "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"
            .parse().expect("valid fingerprint");
        let carol_uid = UserID::from("<carol@example.org>");

        let carol = CertSynopsis::new(
            carol_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            iter::once((carol_uid.clone(), crate::now())));

        let t = crate::now();

        let certifications = vec![
            // Alice certifies Bob.
            Certification::new(alice.clone(),
                               Some(bob_uid.clone()),
                               bob.clone(),
                               t),
            // Alice certifies Bob a second time at the same time.
            Certification::new(alice.clone(),
                               Some(bob_uid.clone()),
                               bob.clone(),
                               t),
            // Alice certifies Bob a third time at an earlier time
            // (this should be ignore because the other two signatures
            // are valid).
            Certification::new(alice.clone(),
                               Some(bob_uid.clone()),
                               bob.clone(),
                               t - Duration::new(1, 0)),
            // Alice certifies Bob a fourth time, but in the future
            // (this should be ignore, because it is after the
            // reference time).
            Certification::new(alice.clone(),
                               Some(bob_uid.clone()),
                               bob.clone(),
                               t + Duration::new(1, 0)),

            // Alice certifies Carol.
            Certification::new(alice.clone(),
                               Some(carol_uid.clone()),
                               carol.clone(),
                               t),

            // Bob certifies Carol.
            Certification::new(bob.clone(),
                               Some(carol_uid.clone()),
                               carol.clone(),
                               t),

            // Bob certifies Carol for "alice", which Carol did not
            // self sign.
            Certification::new(bob.clone(),
                               Some(alice_uid.clone()),
                               carol.clone(),
                               t),
        ];

        let mut cs = CertificationSet::from_certifications(certifications, t);
        // We should have 3 CertificationSets:
        //
        //   - Alice -> Bob
        //   - Alice -> Carol
        //   - Bob -> Carol
        assert_eq!(cs.len(), 3);

        cs.sort_by_key(|c| {
            (c.issuer().fingerprint(), c.target().fingerprint())
        });

        //   - Alice -> Bob
        assert_eq!(cs[0].issuer().fingerprint(), alice_fpr);
        assert_eq!(cs[0].target().fingerprint(), bob_fpr);
        // Two active certifications on one User ID.
        assert_eq!(cs[0].certifications().count(), 1);
        assert_eq!(cs[0].certifications().next().unwrap().1.len(), 2);

        //   - Alice -> Carol
        assert_eq!(cs[1].issuer().fingerprint(), alice_fpr);
        assert_eq!(cs[1].target().fingerprint(), carol_fpr);
        // One active certifications on one User ID.
        assert_eq!(cs[1].certifications().count(), 1);
        assert_eq!(cs[1].certifications().next().unwrap().1.len(), 1);

        //   - Bob -> Carol
        assert_eq!(cs[2].issuer().fingerprint(), bob_fpr);
        assert_eq!(cs[2].target().fingerprint(), carol_fpr);
        // One active certifications on each of two User IDs.
        assert_eq!(cs[2].certifications().count(), 2);
        assert_eq!(cs[2].certifications().next().unwrap().1.len(), 1);
        assert_eq!(cs[2].certifications().nth(1).unwrap().1.len(), 1);

        Ok(())
    }

    #[test]
    fn certification_set_group() -> Result<()> {
        // CertificationSet::from_certifications would add a
        // certification to the first group if a certification's user
        // ID and creation time matched another group's
        // certification's user ID and creation time instead of that
        // group.
        //
        // See YesWeHack report #176.

        let ct = crate::now();

        let alice_fpr: Fingerprint =
            "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
            .parse().expect("valid fingerprint");
        let alice_uid = UserID::from("<alice@example.org>");

        let alice = CertSynopsis::new(
            alice_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            iter::once((alice_uid.clone(), ct)));

        let bob_fpr: Fingerprint =
            "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
            .parse().expect("valid fingerprint");
        let bob1_uid = UserID::from("<bob1@example.org>");
        let bob2_uid = UserID::from("<bob2@example.org>");

        let bob = CertSynopsis::new(
            bob_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            [(bob1_uid.clone(), ct), (bob2_uid.clone(), ct)].into_iter());

        let ct = std::time::UNIX_EPOCH + std::time::Duration::from_secs(1);

        let certification = Certification {
            issuer: alice.clone(),
            target: bob.clone(),
            userid: Some(bob1_uid.clone()),
            creation_time: ct,
            expiration_time: None,
            exportable: true,
            amount: 120,
            depth: 0.into(),
            re_set: None,
            re_bytes: Vec::new(),
            digest_prefix: None,
        };

        let certifications = vec![
            certification.clone(),
            {
                let mut c = certification.clone();
                c.userid = Some(bob2_uid.clone());
                c
            },
            {
                let mut c = certification.clone();
                c.userid = Some(bob2_uid.clone());
                c
            },
        ];

        let cs = CertificationSet::from_certifications(
            certifications,
            crate::now());

        for cs in cs.into_iter() {
            for (userid, certifications) in cs.certifications.iter() {
                for certification in certifications.iter() {
                    assert_eq!(userid, &certification.userid,
                               "Certification with user ID {:?} \
                                added to wrong group (user ID: {:?}",
                               certification.userid, userid);
                }
            }
        }

        Ok(())
    }
}