sequoia-wot 0.15.0

use std::borrow::Borrow;
use std::collections::BTreeMap;
use std::fmt;
use std::time::SystemTime;
use std::ops::Deref;

use sequoia_openpgp as openpgp;

use openpgp::Result;
use openpgp::cert::prelude::*;
use openpgp::cert::raw::RawCert;
use openpgp::Fingerprint;
use openpgp::packet::UserID;
use openpgp::policy::Policy;

use sequoia_cert_store as cert_store;

use crate::CertSynopsis;
use crate::Certification;
use crate::FULLY_TRUSTED;
use crate::Path;
use crate::Paths;
use crate::store::CertStore;
use crate::store::Store;
use crate::store::SynopsisSlice;

pub(crate) mod filter;
use filter::CapCertificateFilter;
use filter::CapDepthFilter;
use filter::ChainFilter;
use filter::SuppressIssuerFilter;
use filter::SuppressCertificationFilter;
use filter::TrustedIntroducerFilter;
mod root;
pub use root::Root;
mod roots;
pub use roots::Roots;
mod path;
pub use path::PathError;
pub use path::CertLints;
pub use path::CertificationLints;
pub use path::PathLints;
mod builder;
pub use builder::NetworkBuilder;

use super::TRACE;

/// A certification network.
pub struct Network<S>
    where S: Store
{
    store: S,

    // The trust roots.
    roots: Roots,

    // If this is a certification network (where all certificates are
    // considered tsigs with infinite depth and no regular
    // expression), or a normal authentication network.
    certification_network: bool,

    /// Whether to constrain the search to paths with a given depth.
    maximum_depth: Option<usize>,
}

impl<S> fmt::Debug for Network<S>
    where S: Store
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Network {{\n")?;
        write!(f, "  Reference time: {:?}\n", self.reference_time())?;
        write!(f, "  Nodes:\n")?;

        let mut certs: Vec<_> = self.synopses().map(|cert| {
            (
                cert.userids()
                    .map(|userid| {
                        String::from_utf8_lossy(userid.value())
                            .into_owned()
                    })
                    .collect::<Vec<String>>()
                    .join(", "),
                cert.fingerprint()
            )
        }).collect();
        certs.sort();

        for (userid, fpr) in certs {
            write!(f, "    {}: {}\n", fpr, userid)?;
        }

        write!(f, "  Edges:\n")?;

        let mut certifications: Vec<crate::CertificationSet> = self
            .iter_fingerprints()
            .filter_map(|fpr| {
                if let Ok(cs) = self.certifications_of(&fpr, 0.into()) {
                    if cs.is_empty() {
                        None
                    } else {
                        Some((*cs).clone())
                    }
                } else {
                    None
                }
            })
            .flatten()
            .collect::<Vec<_>>();
        certifications.sort_by_key(|cs| {
            (cs.issuer().primary_userid().map(|u| u.userid().clone()),
             cs.issuer().fingerprint(),
             cs.target().fingerprint())
        });

        let mut last_issuer_fpr = None;
        for cs in certifications.into_iter() {
            let issuer = &cs.issuer();
            let issuer_fpr = issuer.fingerprint();
            if Some(&issuer_fpr) != last_issuer_fpr.as_ref() {
                write!(f, "    {} certifies:\n", issuer)?;
                last_issuer_fpr = Some(issuer_fpr);
            }

            let target_fpr = cs.target().fingerprint();
            for c in cs.into_certifications() {
                write!(f, "      {}, {}: {}, {}, {}\n",
                       target_fpr,
                       c.userid().map(|userid| {
                           String::from_utf8_lossy(userid.value()).into_owned()
                       }).unwrap_or_else(|| "<No User ID>".into()),
                       c.depth(), c.amount(),
                       if let Some(re_set) = c.regular_expressions() {
                           if re_set.matches_everything() {
                               "*".into()
                           } else {
                               format!("{:?}", re_set)
                           }
                       } else {
                           "<invalid RE>".into()
                       })?;
            }
        }

        write!(f, "}}\n")?;

        Ok(())
    }
}

impl<S> Deref for Network<S>
    where S: Store
{
    type Target = S;

    fn deref(&self) -> &Self::Target {
        &self.store
    }
}

impl<S> Network<S>
    where S: Store
{
    /// Returns a rooted Network.
    ///
    /// By default, the `Network` is an authentication network.  In
    /// this mode of operation, plain certifications are only
    /// considered certifications, and the target is not considered to
    /// be a trusted introducer.  An alternative mode of operation is
    /// a certification network.  This can be configured using
    /// [`NetworkBuilder::certification_network`].
    pub fn new<R>(store: S, roots: R)
        -> Result<Self>
        where R: Into<Roots>,
    {
        tracer!(TRACE, "Network::new");

        let roots = roots.into();

        t!("Roots ({}): {}.",
           roots.iter().count(),
           roots.iter()
               .map(|r| format!("{} ({})", r.fingerprint(), r.amount()))
               .collect::<Vec<_>>()
               .join(", "));

        Ok(NetworkBuilder::rooted(store, roots).build())
    }

    /// Returns a reference to the underlying store.
    pub fn backend(&self) -> &S {
        &self.store
    }
}

impl<'a: 'policy, 'policy> Network<CertStore<'a, 'policy, cert_store::store::Certs<'a>>> {
    /// Builds a web of trust network from a set of certificates.
    ///
    /// If a certificate is invalid according to the policy, the
    /// certificate is silently ignored.
    pub fn from_certs<I, C, T, R>(certs: I,
                                  policy: &'policy dyn Policy, t: T,
                                  roots: R)
        -> Result<Self>
    where T: Into<Option<SystemTime>>,
          I: IntoIterator<Item=C>,
          C: Into<Cert>,
          R: Into<Roots>,
    {
        tracer!(TRACE, "Network::from_certs");

        let t = t.into().unwrap_or_else(|| SystemTime::now());
        Network::new(
            CertStore::from_certs(
                certs.into_iter().map(|c| c.into()),
                policy, t)?,
            roots)
    }

    /// Builds a web of trust network from a set of certificates.
    ///
    /// If a certificate is invalid according to the policy, the
    /// certificate is silently ignored.
    pub fn from_cert_refs<I, C, T, R>(certs: I,
                                      policy: &'policy dyn Policy, t: T,
                                      roots: R)
        -> Result<Self>
    where T: Into<Option<SystemTime>>,
          I: IntoIterator<Item=C>,
          C: Into<&'a Cert>,
          R: Into<Roots>,
    {
        tracer!(TRACE, "Network::from_certs");

        let t = t.into().unwrap_or_else(|| SystemTime::now());
        Network::new(
            CertStore::from_cert_refs(
                certs.into_iter().map(|c| c.into()),
                policy, t)?,
            roots)
    }

    /// Builds a web of trust network from a keyring.
    ///
    /// If a certificate is invalid according to the policy, the
    /// certificate is silently ignored.
    pub fn from_bytes<T, R>(certs: &'a [u8], policy: &'policy dyn Policy, t: T,
                            roots: R)
        -> Result<Self>
    where T: Into<Option<SystemTime>>,
          R: Into<Roots>,
    {
        tracer!(TRACE, "Network::from_bytes");

        let t = t.into().unwrap_or_else(|| SystemTime::now());
        Network::new(CertStore::from_bytes(certs, policy, t)?, roots)
    }

    /// Builds a web of trust network from a set of raw certificates.
    ///
    /// If a certificate is invalid according to the policy, the
    /// certificate is silently ignored.
    pub fn from_raw_certs<T, R>(certs: impl Iterator<Item=RawCert<'a>>,
                                policy: &'a dyn Policy, t: T,
                                roots: R)
        -> Result<Self>
    where T: Into<Option<SystemTime>>,
          R: Into<Roots>,
    {
        tracer!(TRACE, "Network::from_raw_certs");

        let t = t.into().unwrap_or_else(|| SystemTime::now());
        Network::new(
            CertStore::from_raw_certs(certs, policy, t)?,
            roots)
    }
}

impl<'a> Network<SynopsisSlice<'a>> {
    /// Builds a web of trust network from a set of certificates.
    ///
    /// If a certificate is invalid according to the policy, the
    /// certificate is silently ignored.
    pub fn from_synopses<R>(certs: &'a [CertSynopsis],
                            certifications: &'a [Certification],
                            t: SystemTime,
                            roots: R)
        -> Result<Self>
        where R: Into<Roots>
    {
        Network::new(
            SynopsisSlice::new(certs, certifications, t)?,
            roots)
    }
}

impl<S> Network<S>
    where S: Store
{
    /// Returns a reference to the roots.
    pub fn roots(&self) -> &Roots
    {
        &self.roots
    }

    /// Returns whether the specified certificate is a root.
    pub fn is_root<F>(&self, fpr: F) -> bool
        where F: Borrow<Fingerprint>
    {
        self.roots.is_root(fpr.borrow())
    }

    /// Returns the specified root.
    pub fn root<F>(&self, fpr: F) -> Option<&Root>
        where F: Borrow<Fingerprint>
    {
        self.roots.get(fpr.borrow())
    }

    /// Returns whether the `Network` is a certification network.
    ///
    /// See [`NetworkBuilder::certification_network`] for
    /// details.
    pub fn certification_network(&self) -> bool {
        self.certification_network
    }

    /// Returns whether the `Network` is an authentication network.
    ///
    /// See [`NetworkBuilder::certification_network`] for
    /// details.
    pub fn authentication_network(&self) -> bool {
        ! self.certification_network
    }

    /// Returns the maximum depth.
    ///
    /// With the depth limited to `0`, the maximum lengths of paths
    /// will be two, with the paths containing the certifier and the
    /// target).
    pub fn maximum_depth(&mut self) -> Option<usize> {
        self.maximum_depth
    }

    fn authenticate_internal<U, F>(&self, target_userid: U, target_fpr: F,
                                   target_trust_amount: usize,
                                   gossip: bool)
        -> Paths
    where U: Borrow<UserID>,
          F: Borrow<Fingerprint>,
    {
        tracer!(TRACE, "Network::authenticate_internal");

        let target_userid = target_userid.borrow();
        let target_fpr = target_fpr.borrow();

        t!("Authenticating <{}, {}>",
           target_fpr, String::from_utf8_lossy(target_userid.value()));
        t!("Roots ({}):", self.roots.iter().count());
        for (i, r) in self.roots.iter().enumerate() {
            t!("  {}: {} ({})", i, r.fingerprint(), r.amount());
        }

        let mut paths = Paths::new();

        let mut filter = ChainFilter::new();
        if self.certification_network {
            // We're building a certification network: treat all
            // certifications like tsigs with infinite depth and no
            // regular expressions.
            filter.push(TrustedIntroducerFilter::new());
        } else {
            if self.roots.iter().any(|r| r.amount() != FULLY_TRUSTED) {
                let mut caps = CapCertificateFilter::new();
                for r in self.roots.iter() {
                    let amount = r.amount();
                    if amount != FULLY_TRUSTED  {
                        caps.cap(r.fingerprint().clone(), amount);
                    }
                }
                filter.push(caps);
            };
        }

        // Limit the path length.  Note: It is important to push this
        // filter after the TrustedIntroducerFilter, which
        // unconditionally sets the depth to unconstrained.
        if let Some(limit) = self.maximum_depth {
            filter.push(CapDepthFilter::new(limit));
        }

        let mut progress = true;
        'next_path: while progress
            && (paths.amount() < target_trust_amount || gossip)
        {
            progress = false;

            let mut gossip_paths = Vec::new();

            for self_signed in [true, false] {
                let auth_paths: BTreeMap<Fingerprint, (Path, usize)>
                    = self.backward_propagate(
                        target_fpr.clone(), target_userid.clone(),
                        self_signed, &filter, gossip);

                // Note: the paths returned by backward_propagate may
                // overlap.  As such, we can only take one.  (Or we need
                // to subtract any overlap.  But that is fragile.)  Then
                // we subtract the path from the network and run
                // backward_propagate again, if necessary.
                if let Some((path, path_amount)) = self.roots.iter()
                    // Get the paths that start at the roots.
                    .filter_map(|r| {
                        auth_paths.get(r.fingerprint())
                    })
                    // Choose the one that: has the maximum amount of
                    // trust.  If there are multiple such paths, prefer
                    // the shorter one.
                    .max_by_key(|(path, path_amount)| {
                        (// We want the *most* amount of trust,
                            path_amount,
                            // but the *shortest* path.
                            -(path.len() as isize),
                            // Be predictable.  Break ties based on the
                            // fingerprint of the root.
                            path.root().fingerprint())
                    })
                {
                    let path = path.clone();

                    if path.len() == 1 {
                        // It's a root.
                        let mut suppress_filter
                            = SuppressIssuerFilter::new();
                        suppress_filter.suppress_issuer(
                            &path.root().fingerprint(), *path_amount);
                        filter.push(suppress_filter);
                    } else {
                        // Add the path to the filter to create a residual
                        // network without this path.
                        let mut suppress_filter
                            = SuppressCertificationFilter::new();
                        suppress_filter.suppress_path(&path, *path_amount);
                        filter.push(suppress_filter);
                    }

                    paths.push(path, *path_amount);
                    progress = true;
                    // Prefer paths where the target User ID is self
                    // signed as long as possible.
                    continue 'next_path;
                } else if gossip {
                    gossip_paths.extend(auth_paths.into_values());
                }
            }

            // No authenticated paths left.
            assert!(! progress);

            if gossip {
                // We're looking for gossip paths.  Add the remaining
                // paths.  But, don't add paths that are just suffixes
                // of other paths.  To make this easier, we add the
                // longest paths first so that shorter suffixes are
                // filtered out when we try to add them.
                t!("Adding the remaining paths ({}) as gossip paths",
                   gossip_paths.len());

                gossip_paths.sort_by_key(|(path, _amount)| {
                    -(path.len() as isize)
                });
                for (path, _amount) in gossip_paths.into_iter() {
                    if ! paths.has_suffix(&path) {
                        t!("Adding: {:?} (length: {})", path, path.len());
                        paths.push(path, 0);
                    } else {
                        t!("Skipping suffix: {:?}", path);
                    }
                }
            }
        }

        paths
    }

    /// Authenticates the specified binding.
    ///
    /// Enough independent paths are gotten to satisfy
    /// `target_trust_amount`.  A fully trusted authentication is 120.
    /// If you require that a binding be double authenticated, you can
    /// specify 240.
    pub fn authenticate<U, F>(&self, target_userid: U, target_fpr: F,
                              target_trust_amount: usize)
        -> Paths
    where U: Borrow<UserID>,
          F: Borrow<Fingerprint>,
    {
        self.authenticate_internal(target_userid, target_fpr,
                                   target_trust_amount, false)
    }

    /// Gets gossip about the specified binding.
    ///
    /// This is like [`Network::authenticate`], but it also includes
    /// all unauthenticated paths to the target binding.  The
    /// aggregate trust amount is accurate.
    ///
    /// Note: the paths are dedup based on whether they are a suffix
    /// of another path.  That is, if `A -> B -> C` is a valid gossip
    /// path, then so is `B -> C`.
    pub fn gossip<U, F>(&self, target_fpr: F, target_userid: U)
        -> Paths
    where U: Borrow<UserID>,
          F: Borrow<Fingerprint>,
    {
        self.authenticate_internal(target_userid, target_fpr,
                                   0, true)
    }
}

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

    use openpgp::Fingerprint;
    use openpgp::packet::UserID;
    use openpgp::parse::Parse;
    use openpgp::policy::StandardPolicy;

    #[allow(unused)]
    #[test]
    fn third_party_certifications_of() -> Result<()> {
        let p = &StandardPolicy::new();

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

        let bob_fpr: Fingerprint =
            "03182611B91B1E7E20B848E83DFC151ABFAD85D5"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@other.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA

        let carol_fpr: Fingerprint =
            "9CA36907B46FE7B6B9EE9601E78064C12B6D7902"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 03182611B91B1E7E20B848E83DFC151ABFAD85D5

        let dave_fpr: Fingerprint =
            "C1BC6794A6C6281B968A6A41ACE2055D610CEA03"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: 9CA36907B46FE7B6B9EE9601E78064C12B6D7902


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-userids-1.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(store).build();

        eprintln!("{:?}", n);

        // No one certified alice.
        assert!(
            n.third_party_certifications_of(&alice_fpr.clone())
                .is_empty());

        // Alice (and no one else) certified each of Bob's User IDs.
        let mut c = n.third_party_certifications_of(&bob_fpr);
        assert_eq!(c.len(), 2);
        c.sort_by_key(|c| (c.issuer().fingerprint(),
                           c.userid().map(Clone::clone)));
        assert_eq!(&c[0].issuer().fingerprint(), &alice_fpr);
        assert_eq!(c[0].userid(), Some(&bob_uid));
        assert_eq!(&c[1].issuer().fingerprint(), &alice_fpr);
        assert_eq!(c[1].userid(), Some(&bob_some_org_uid));

        Ok(())
    }

    #[allow(unused)]
    #[test]
    fn certified_userids_of() -> Result<()> {
        let p = &StandardPolicy::new();

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

        let bob_fpr: Fingerprint =
            "03182611B91B1E7E20B848E83DFC151ABFAD85D5"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@other.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA

        let carol_fpr: Fingerprint =
            "9CA36907B46FE7B6B9EE9601E78064C12B6D7902"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 03182611B91B1E7E20B848E83DFC151ABFAD85D5

        let dave_fpr: Fingerprint =
            "C1BC6794A6C6281B968A6A41ACE2055D610CEA03"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: 9CA36907B46FE7B6B9EE9601E78064C12B6D7902


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-userids-1.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(store).build();

        eprintln!("{:?}", n);

        // There is the self signature.
        let mut c = n.certified_userids_of(&alice_fpr);
        assert_eq!(c.len(), 1);

        // Alice (and no one else) certified each of Bob's User IDs
        // for the two self signed User ID.
        let mut c = n.certified_userids_of(&bob_fpr);
        assert_eq!(c.len(), 2);
        c.sort_unstable();
        assert_eq!(&c[0], &bob_uid);
        assert_eq!(&c[1], &bob_some_org_uid);

        Ok(())
    }

    #[allow(unused)]
    #[test]
    fn certified_userids() -> Result<()> {
        let p = &StandardPolicy::new();

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

        let bob_fpr: Fingerprint =
            "03182611B91B1E7E20B848E83DFC151ABFAD85D5"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@other.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA

        let carol_fpr: Fingerprint =
            "9CA36907B46FE7B6B9EE9601E78064C12B6D7902"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 03182611B91B1E7E20B848E83DFC151ABFAD85D5

        let dave_fpr: Fingerprint =
            "C1BC6794A6C6281B968A6A41ACE2055D610CEA03"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: 9CA36907B46FE7B6B9EE9601E78064C12B6D7902


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-userids-1.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(store).build();

        eprintln!("{:?}", n);

        // Alice is the root, but self signatures count, so there are
        // five certified User IDs in this network.
        let mut got = n.certified_userids();
        assert_eq!(got.len(), 5);

        got.sort_unstable();

        let mut expected = [
            (alice_fpr.clone(), alice_uid.clone()),
            (bob_fpr.clone(), bob_uid.clone()),
            (bob_fpr.clone(), bob_some_org_uid.clone()),
            (carol_fpr.clone(), carol_uid.clone()),
            (dave_fpr.clone(), dave_uid.clone()),
        ];
        expected.sort_unstable();

        assert_eq!(got, expected);

        Ok(())
    }
}