sequoia_git/

verify.rs

//! Commit-tree traversal and verification.

use std::{
    path::{Path, PathBuf},
    collections::{
        BTreeMap,
        BTreeSet,
    },
};

use anyhow::{anyhow, Context, Result};
use git2::{
    Repository,
    Oid,
};

use sequoia_openpgp::{
    self as openpgp,
    Cert,
    cert::{
        amalgamation::ValidAmalgamation,
        CertParser,
    },
    Fingerprint,
    packet::{Signature, UserID},
    parse::Parse,
    policy::StandardPolicy,
    types::{
        HashAlgorithm,
        RevocationStatus,
        RevocationType,
    },
};

use crate::{
    Policy,
    persistent_set,
};

/// Whether to trace execution by default (on stderr).
const TRACE: bool = false;

#[derive(Default, Debug)]
pub struct VerificationResult {
    pub signer_keys: BTreeSet<openpgp::Fingerprint>,
    pub primary_uids: BTreeSet<UserID>,
}

pub fn verify(git: &Repository,
              trust_root: Oid,
              shadow_policy: Option<&[u8]>,
              commit_range: (Oid, Oid),
              results: &mut VerificationResult,
              keep_going: bool,
              mut verify_cb: impl FnMut(&Oid, Option<&Oid>, &crate::Result<Vec<crate::Result<(String, Signature, Cert, Fingerprint)>>>) -> crate::Result<()>,
              cache: &mut VerificationCache)
              -> Result<()> {
    tracer!(TRACE, "verify");
    t!("verify(_, {}, {}..{})", trust_root, commit_range.0, commit_range.1);

    if shadow_policy.is_some() {
        t!("Using a shadow policy to verify commits.");
    } else {
        t!("Using in-band policies to verify commits.");
    }

    // XXX: These should be passed in as arguments.
    let p: &StandardPolicy = &StandardPolicy::new();
    let now = std::time::SystemTime::now();

    // STRATEGY
    //
    // We want to determine if we can authenticate the target commit
    // starting from the trust root.  A simple approach is to try each
    // possible path.  Unfortunately, this is exponential in the
    // number of merges.  Consider a project where development is done
    // on feature branches, and then merged using a merge commit.  The
    // commit graph will look like:
    //
    // ```
    //   o      <- Merge commit
    //   | \
    //   |  o   <- Feature branch
    //   | /
    //   o      <- Merge commit
    //   | \
    //   |  o   <- Feature branch
    //   | /
    //   o      <- Merge commit
    //   | \
    //   ...
    // ```
    //
    // After 100 such merges, there are 2**100 different paths.
    // That's intractable.
    //
    // Happily, we can do better.  We can determine if there is an
    // authenticated path as a byproduct of a topological walk.  This
    // approach limits both the work we have to do, and the space we
    // require to O(N), where N is the number of commits preceding the
    // target commit in the commit graph.  (If the trust root is a
    // dominator, which is usually the case, then N is the number of
    // commits that precede target, and follow the trust root, which
    // is often very small.)
    //
    // Recall the following facts:
    //
    //   - A commit is authenticated if it is the trust root, or at
    //     least one parent's policy authenticates the commit.
    //     - Unless the signer's certificate is hard revoked.
    //       - Unless there is an authenticated suffix that
    //         immediately follows the commit, and a commit on that
    //         authenticated suffix goodlists commit.
    //
    // In order to check the last condition, we need to know the
    // goodlists of all the following, authenticated commits when we
    // process the commit.  When we do a topological walk, we know
    // that when we visit a commit, we've already visited all of its
    // ancestors.  This means that we can easily collect the goodlists
    // of all of the commits on authenticated paths from the commit to
    // the target during the walk by propagating good lists from
    // authenticated commits to their parents.  Then, when we are
    // examining a commit, and we discover that it has been revoked,
    // we can immediately check if it is on a relevant goodlist.
    //
    // To do the topological walk, we first have to do a bit of
    // preparation.  Since we don't know a commit's children by
    // looking at the commit (and not all children lead to the
    // target), we have to extract that information from the graph.
    // We do this by visiting all commits on paths from the target to
    // the trust root, which we can do in O(N) space and time by doing
    // a breath first search.  When we visit a commit, we increment
    // the number of children each of its parents has.  We also use
    // this opportunity to discover any certificates that have been
    // hard revoked.
    //
    // Then we do the topological walk.  For each commit, we consider
    // the number of unprocessed children to be the number of recorded
    // children.  We then visit commits that have no unprocessed
    // children.
    //
    // When we visit a commit, and there is an authenticated path from
    // it to the target, we try to authenticate the commit.  That is,
    // for each parent, we check if the parent can authenticate the
    // commit.  If a parent authenticates the commit, but the signer's
    // certificate has been revoked, we can immediately check whether
    // the commit is on a goodlist.  For each parent that
    // authenticated the commit, we merge the commit's *aggregate*
    // goodlist into the parent's goodlist.  Finally, for each parent,
    // we decrement the number of unprocessed children.  If there are
    // no unprocessed children left, it is added to a pending queue,
    // so that it can be processed.

    // Return the policy associated with the commit.
    let read_policy = |commit: &Oid| -> Result<Vec<u8>> {
        if let Some(p) = &shadow_policy {
            Ok(p.to_vec())
        } else {
            Ok(Policy::read_bytes_from_commit(git, commit)?)
        }
    };

    // Whether we've seen the policy file before.  The key is the
    // SHA512 digest of the policy file.
    let mut policy_files: BTreeSet<Vec<u8>> = Default::default();
    // Any hard revoked certificates.
    let mut hard_revoked: BTreeSet<Fingerprint> = Default::default();

    // Scans the specified commit's policy for hard revocations, and
    // adds them to hard_revoked.
    let mut scan_policy = |commit_id| -> Result<()> {
        let policy_bytes = read_policy(&commit_id)?;
        let policy_hash = sha512sum(&policy_bytes)?;
        if policy_files.contains(&policy_hash) {
            t!("Already scanned an identical copy of {}'s policy, skipping.",
               commit_id);
            return Ok(());
        }
        t!("Scanning {}'s policy for hard revocations", commit_id);

        let policy = Policy::parse_bytes(&policy_bytes)?;
        policy_files.insert(policy_hash);

        // Scan for revoked certificates.
        for authorization in policy.authorization().values() {
            for cert in CertParser::from_bytes(&authorization.keyring)? {
                let cert = if let Ok(cert) = cert {
                    cert
                } else {
                    continue;
                };

                let vc = if let Ok(vc) = cert.with_policy(p, Some(now)) {
                    vc
                } else {
                    continue;
                };

                let is_hard_revoked = |rs| {
                    if let RevocationStatus::Revoked(revs) = rs {
                        revs.iter().any(|rev| {
                            if let Some((reason, _)) = rev.reason_for_revocation() {
                                reason.revocation_type() == RevocationType::Hard
                            } else {
                                true
                            }
                        })
                    } else {
                        false
                    }
                };

                // Check if the certificate is hard revoked.
                if is_hard_revoked(vc.revocation_status()) {
                    t!("Certificate {} is hard revoked, bad listing",
                       cert.fingerprint());
                    hard_revoked.insert(vc.fingerprint());
                    for k in vc.keys().subkeys().for_signing() {
                        hard_revoked.insert(k.key().fingerprint());
                        t!("  Badlisting signing key {}",
                           k.key().fingerprint());
                    }

                    continue;
                }

                // Check if any of the signing keys are hard revoked.
                for k in vc.keys().subkeys().for_signing() {
                    if is_hard_revoked(k.revocation_status()) {
                        hard_revoked.insert(k.key().fingerprint());
                        t!("  Signing key {} hard revoked, bad listing",
                           k.key().fingerprint());
                    }
                }
            }
        }

        Ok(())
    };

    let middle = if trust_root == commit_range.0 {
        None
    } else {
        Some(commit_range.0)
    };

    struct Commit {
        // Number of children (commits derived from this one).
        children: usize,

        // Whether there is an authenticated path from this node to
        // the target.
        authenticated_suffix: bool,

        // Whether we still need to go via MIDDLE.
        traversed_middle: bool,
    }

    impl Default for Commit {
        fn default() -> Self {
            Commit {
                children: 0,
                authenticated_suffix: false,
                traversed_middle: false,
            }
        }
    }

    let mut commits: BTreeMap<Oid, Commit> = Default::default();
    if trust_root != commit_range.1 {
        commits.insert(
            commit_range.1.clone(),
            Commit {
                children: 0,
                authenticated_suffix: true,
                traversed_middle: middle.is_none(),
            });
    }

    // We walk the tree from the target to the trust root (using a
    // breath first search, but it doesn't matter), and fill in
    // COMMITS.CHILDREN.
    {
        // Commits that we haven't processed yet.
        let mut pending: BTreeSet<Oid> = Default::default();
        pending.insert(commit_range.1.clone());

        // Commits that we've processed.
        let mut processed: BTreeSet<Oid> = Default::default();

        while let Some(commit_id) = pending.pop_first() {
            processed.insert(commit_id);

            let commit = git.find_commit(commit_id)?;

            // Don't fail if we can't parse the policy file.
            let _ = scan_policy(commit_id);

            if commit_id == trust_root {
                // This is the trust root.  There is no need to go
                // further.
                continue;
            }

            for parent in commit.parents() {
                let parent_id = parent.id();

                let info = commits.entry(parent_id).or_default();
                info.children += 1;

                if ! processed.contains(&parent_id)
                    && ! pending.contains(&parent_id)
                {
                    pending.insert(parent_id);
                }
            }
        }
    }

    // The union of the commit goodlists of commits on an
    // authenticated suffix (not including this commit).  We build
    // this up as we authenticate commits.  Since we do a topological
    // walk, this will be complete for a given commit when we process
    // that commit.
    let mut descendant_goodlist: BTreeMap<Oid, BTreeSet<String>>
        = Default::default();

    let mut errors = Vec::new();
    let mut unauthenticated_commits: BTreeSet<Oid> = Default::default();
    let mut authenticated_commits: BTreeSet<Oid> = Default::default();

    // Authenticate the commit using the specified parent.
    //
    // NOTE: This must only be called on a commit, if the commit is on
    // an authenticated suffix!!!
    let mut authenticate_commit = |commit_id, parent_id| -> Result<bool> {
        let parent_policy = read_policy(&parent_id)?;
        let parent_id = if commit_id == parent_id {
            // This is only the case when verifying the trust root
            // using the shadow policy.
            assert_eq!(commit_id, trust_root);
            assert!(shadow_policy.is_some());
            None
        } else {
            Some(&parent_id)
        };

        // The current commit's good list.
        let mut commit_goodlist = BTreeSet::new();

        // XXX: If we have some certificates that are hard revoked,
        // then we can't use the cache.  This is because the cache
        // doesn't tell us what certificate was used to sign the
        // commit, which means we can't figure out if the signer's
        // certificate was revoked when the result is cached.
        let (vresult, cache_hit) = if hard_revoked.is_empty()
            && cache.contains(&parent_policy, commit_id)?
        {
            (Ok(vec![]), true)
        } else {
            let parent_policy = Policy::parse_bytes(&parent_policy)?;
            let commit_policy = Policy::parse_bytes(read_policy(&commit_id)?)?;

            commit_goodlist = commit_policy.commit_goodlist().clone();

            (parent_policy.verify(git, &commit_id, &commit_policy,
                                  &mut results.signer_keys,
                                  &mut results.primary_uids),
             false)
        };

        if let Err(err) = verify_cb(&commit_id, parent_id, &vresult) {
            t!("verify_cb -> {}", err);
            return Err(err.into());
        }

        if cache_hit {
            // XXX: communicate this to the caller
            // instead of eprintln.
            let id = if let Some(parent_id) = parent_id {
                format!("{}..{}", parent_id, commit_id)
            } else {
                commit_id.to_string()
            };
            eprintln!("{}:\n  Cached positive verification", id);
        }

        match vresult {
            Ok(results) => {
                // Whether the parent authenticated the commit.
                let mut good = false;
                // Whether the commit was goodlisted by a later
                // commit.
                let mut goodlisted = false;

                // Whether the commit was goodlisted by the parent's
                // policy.  (Because commits form a Merkle tree, this
                // is only possible when we are using a shadow
                // policy.)
                if ! cache_hit && results.is_empty() {
                    // XXX: communicate this to the caller
                    // instead of eprintln.
                    eprintln!("{}: Explicitly goodlisted", commit_id);
                    good = true;
                }

                for r in results {
                    match r {
                        Ok((_, _sig, cert, signer_fpr)) => {
                            // It looks good, but make sure the
                            // certificate was not revoked.
                            if hard_revoked.contains(&signer_fpr) {
                                t!("Cert {}{} used to sign {} is revoked.",
                                   cert.fingerprint(),
                                   if cert.fingerprint() != signer_fpr {
                                       format!(", key {}", signer_fpr)
                                   } else {
                                       "".to_string()
                                   },
                                   commit_id);

                                // It was revoked, but perhaps the
                                // commit was goodlisted.
                                if descendant_goodlist.get(&commit_id)
                                    .map(|goodlist| {
                                        t!("  Goodlist contains: {}",
                                           goodlist
                                               .iter().cloned()
                                               .collect::<Vec<String>>()
                                               .join(", "));
                                        goodlist.contains(&commit_id.to_string())
                                    })
                                    .unwrap_or(false)
                                {
                                    t!("But the commit was goodlisted, \
                                        so all is good.");
                                    goodlisted = true;
                                }
                            } else {
                                t!("{} has a good signature from {}",
                                   commit_id, cert.fingerprint());
                                good = true;
                            }
                        }
                        Err(e) => errors.push(
                            anyhow::Error::from(e).context(
                                format!("While verifying commit {}",
                                        commit_id))),
                    }
                }

                // We do NOT insert into the cache if the commit was
                // goodlisted.  The cache is a function of the parent
                // policy and the children policy; goodlisting is a
                // function of commit range.
                if ! cache_hit && good && ! goodlisted {
                    cache.insert(&parent_policy, commit_id)?;
                }

                if cache_hit || good || goodlisted {
                    // Merge the commit's goodlist into the parent's
                    // goodlist.
                    if let Some(descendant_goodlist)
                        = descendant_goodlist.get(&commit_id)
                    {
                        commit_goodlist.extend(descendant_goodlist.iter().cloned());
                    };

                    if let Some(parent_id) = parent_id {
                        if let Some(p_goodlist)
                            = descendant_goodlist.get_mut(&parent_id)
                        {
                            p_goodlist.extend(commit_goodlist.into_iter());
                        } else if ! commit_goodlist.is_empty() {
                            descendant_goodlist.insert(
                                parent_id.clone(), commit_goodlist);
                        }
                    }
                }

                let authenticated = cache_hit || good || goodlisted;
                if authenticated {
                    authenticated_commits.insert(commit_id);
                } else {
                    unauthenticated_commits.insert(commit_id);
                }
                Ok(authenticated)
            },
            Err(e) => {
                unauthenticated_commits.insert(commit_id);
                errors.push(anyhow::Error::from(e).context(
                    format!("While verifying commit {}", commit_id)));
                Ok(false)
            },
        }
    };

    // We now do a topological walk from the target to the trust root.

    // Assume there is no path until we prove otherwise.  (A
    // zero-length path is already valid.)
    let mut valid_path = trust_root == commit_range.0
        && commit_range.0 == commit_range.1;

    // Commits that we haven't processed yet.
    let mut pending: BTreeSet<Oid> = Default::default();
    if trust_root != commit_range.1 {
        pending.insert(commit_range.1.clone());
    }

    'authentication: while let Some(commit_id) = pending.pop_first() {
        let commit = git.find_commit(commit_id)?;

        t!("Processing {}: {}", commit_id, commit.summary().unwrap_or(""));

        let commit_info = commits.get(&commit_id).expect("added");
        assert_eq!(commit_info.children, 0);
        let authenticated_suffix = commit_info.authenticated_suffix;
        let traversed_middle = commit_info.traversed_middle;

        for (parent_i, parent) in commit.parents().enumerate() {
            let parent_id = parent.id();
            t!("Considering {} -> {} (parent #{})",
               commit_id, parent_id, parent_i);

            let parent_info = commits.get_mut(&parent_id).expect("added");
            t!("  Parent has {} unprocessed children", parent_info.children);
            assert!(parent_info.children > 0);
            parent_info.children -= 1;

            if authenticated_suffix {
                t!("  Child IS on an authenticated suffix");
            } else {
                t!("  Child IS NOT on an authenticated suffix.");
            }

            let authenticated = if keep_going || authenticated_suffix {
                authenticate_commit(commit_id, parent_id)
                    .with_context(|| {
                        format!("Authenticating {} with {}",
                                commit_id, parent_id)
                    })?
            } else {
                false
            };

            if authenticated_suffix && authenticated {
                t!("  Parent authenticates child");
                parent_info.authenticated_suffix = true;

                if traversed_middle {
                    parent_info.traversed_middle = true;
                } else if middle == Some(commit_id) {
                    t!("  Traversed {} on way to trust root.", commit_id);
                    parent_info.traversed_middle = true;
                }

                if parent_id == trust_root {
                    t!("  Parent is the trust root.");

                    // This is the trust root.  There is no need to go
                    // further.
                    if ! parent_info.traversed_middle {
                        t!("  but path was not via {}", middle.unwrap());
                    } else {
                        valid_path = true;
                    }
                    if ! keep_going {
                        break 'authentication;
                    }
                }
            }

            if parent_info.children == 0 {
                t!("  No other unprocessed children.");
                if parent_id == trust_root {
                    t!("  Parent is the start of the commit range, \
                        so it doesn't need to be processed.");
                } else if ! keep_going && ! parent_info.authenticated_suffix {
                    t!("  Parent does not authenticate any child, \
                        so it doesn't need to be processed.");
                } else {
                    t!("  Adding parent to pending.");
                    pending.insert(parent_id);
                }
            }
        }
    }

    // When using a shadow policy, we also authenticate the trust
    // root with it.
    if (keep_going || valid_path) && shadow_policy.is_some() {
        t!("Verifying trust root ({}) using the shadow policy",
           trust_root);
        // We verify the trust root using itself?  Not quite.  We know
        // that authenticate_commit prefers the shadow policy, and we
        // know that a shadow policy is set.  So this will actually
        // check that the shadow policy verifies the trust root.
        if ! authenticate_commit(trust_root, trust_root)? {
            valid_path = false;

            if let Some(e) = errors.pop() {
                errors.push(
                    e.context(format!("Could not verify trust root {} \
                                       using the specified policy",
                                      trust_root)));
            }
        }
    }

    if valid_path {
        if trust_root == commit_range.0 {
            eprintln!(
                "Verified that there is an authenticated path from the trust root\n\
                 {} to {}.",
                trust_root, commit_range.1);
        } else {
            eprintln!(
                "Verified that there is an authenticated path from the trust root\n\
                 {} via {}\n\
                 to {}.",
                trust_root, commit_range.0, commit_range.1);
        }
        Ok(())
    } else {
        if errors.is_empty() {
            Err(anyhow!("Could not verify commits {}..{}{}",
                        trust_root,
                        if let Some(middle) = middle {
                            format!("{}..", middle)
                        } else {
                            "".to_string()
                        },
                        commit_range.1))
        } else {
            let mut e = errors.swap_remove(0)
                .context(format!("Could not verify commits {}..{}{}",
                                 commit_range.0,
                                 if let Some(middle) = middle {
                                     format!("{}..", middle)
                                 } else {
                                     "".to_string()
                                 },
                                 commit_range.1));
            if ! errors.is_empty() {
                e = e.context(
                    format!("{} errors occurred while verifying the commits.  \
                             {} commits couldn't be authenticated.  \
                             Note: not all errors are fatal.  \
                             The first error is shown:",
                            errors.len() + 1,
                            unauthenticated_commits.difference(
                                &authenticated_commits).count()));
            }
            Err(e)
        }
    }
}

// Returns the SHA512 digest of the provided bytes.
fn sha512sum(bytes: &[u8]) -> Result<Vec<u8>> {
    let mut digest = HashAlgorithm::SHA512.context()?.for_digest();
    digest.update(bytes);

    let mut key = Vec::with_capacity(32);
    digest.digest(&mut key)?;
    Ok(key)
}

pub struct VerificationCache {
    path: PathBuf,
    set: persistent_set::Set,
}

impl VerificationCache {
    const CONTEXT: &'static str = "SqGitVerify0";

    pub fn new() -> Result<Self> {
        let p = dirs::cache_dir().ok_or(anyhow::anyhow!("No cache dir"))?
            .join("sq-git.verification.cache");
        Self::open(p)
    }

    pub fn open<P: AsRef<Path>>(path: P) -> Result<Self> {
        let path = path.as_ref();

        Ok(VerificationCache {
            path: path.into(),
            set: persistent_set::Set::read(&path, Self::CONTEXT)?,
        })
    }

    fn key(&self, policy: &[u8], commit: Oid) -> Result<persistent_set::Value> {
        let mut digest = HashAlgorithm::SHA512.context()?.for_digest();
        digest.update(policy);
        digest.update(commit.as_bytes());

        let mut key = [0; 32];
        digest.digest(&mut key)?;

        Ok(key)
    }

    /// Returns whether (policy, commit id) is in the cache.
    ///
    /// If (policy, commit id) is in the cache, then it was previously
    /// determined that the policy authenticated the commit.
    pub fn contains(&mut self, policy: &[u8], commit: Oid) -> Result<bool> {
        Ok(self.set.contains(&self.key(policy, commit)?)?)
    }

    /// Add (policy, commit id) to the cache.
    ///
    /// If (policy, commit id) is in the cache, this means that the
    /// policy considers the commit to be authenticated.  Normally,
    /// the policy comes from the parent commit, but it may be a
    /// shadow policy.
    pub fn insert(&mut self, policy: &[u8], commit: Oid) -> Result<()> {
        self.set.insert(self.key(policy, commit)?);
        Ok(())
    }

    pub fn persist(&mut self) -> Result<()> {
        self.set.write(&self.path)?;
        Ok(())
    }
}