gunnar-core 3.0.0

//! **The transparency log's arithmetic**: a Merkle tree over records, and a
//! signed tree head over the tree.
//!
//! Push attestation already appends one JSON line per push to an append-only file. Append-only
//! is a *discipline*, not a proof: nothing stops a file being rewritten, and
//! nothing in the file says it has not been. This module is what turns the
//! discipline into evidence.
//!
//! # The shape, and why it is RFC 6962's
//!
//! Certificate Transparency solved this problem, in public, against adversaries,
//! and its hashing rules are three lines:
//!
//! ```text
//!   leaf(record)     = SHA-256(0x00 ‖ record)
//!   node(left,right) = SHA-256(0x01 ‖ left ‖ right)
//!   root([])         = SHA-256("")
//! ```
//!
//! The domain-separating prefixes are the load-bearing part. Without them a leaf
//! whose bytes happen to be two concatenated hashes could be presented as an
//! interior node, and an attacker could show a "proof" for a record the log
//! never held (the second-preimage attack every naive Merkle implementation
//! has). Reimplementing this without the prefixes would be a Merkle tree with a
//! hole in it, so the prefixes are here and are tested.
//!
//! An odd node is **promoted, not duplicated**: a level with an odd count
//! carries the last hash up unchanged. Duplicating it instead is the flaw that
//! let two different trees share a root in early Bitcoin.
//!
//! # What signs a tree head, and why it is `sshsig`
//!
//! The same format everything else in this repository signs with: commits
//! (`gunnar-policy`), gRPC challenges (`gunnar-grpc`), and now tree heads. One
//! signature format means one verifier to trust and one that has already been
//! looked at — and it means a client can check a tree head with `ssh-keygen -Y
//! verify` and no gunnar at all.
//!
//! The namespace is [`STH_NAMESPACE`], and it is not the namespace anything else
//! signs under: a signature made for one namespace does not verify in another,
//! so a commit signature can never be replayed as a tree head and vice versa.

use sha2::Digest as _;

/// The `sshsig` namespace a signed tree head is signed under.
///
/// Distinct from `git` (commits) and `gunnar-grpc` (control-plane challenges) on
/// purpose: `sshsig` binds the namespace into what is signed, so a signature
/// made under one cannot be presented as another.
pub const STH_NAMESPACE: &str = "gunnar-transparency";

/// RFC 6962's leaf prefix. Domain separation; see the module docs.
const LEAF_PREFIX: u8 = 0x00;
/// RFC 6962's interior-node prefix.
const NODE_PREFIX: u8 = 0x01;

/// A 32-byte SHA-256 digest.
pub type Hash = [u8; 32];

/// Render a hash the way every field in this repository renders one: lowercase
/// hex.
pub fn hex(hash: &Hash) -> String {
    let mut out = String::with_capacity(64);
    for byte in hash {
        out.push_str(&format!("{byte:02x}"));
    }
    out
}

/// Parse a 64-character lowercase hex digest.
pub fn unhex(text: &str) -> Option<Hash> {
    if text.len() != 64 {
        return None;
    }
    let mut out = [0u8; 32];
    for (index, slot) in out.iter_mut().enumerate() {
        *slot = u8::from_str_radix(text.get(index * 2..index * 2 + 2)?, 16).ok()?;
    }
    Some(out)
}

/// `SHA-256(0x00 ‖ record)` — one record's leaf hash.
pub fn leaf_hash(record: &[u8]) -> Hash {
    let mut hasher = sha2::Sha256::new();
    hasher.update([LEAF_PREFIX]);
    hasher.update(record);
    hasher.finalize().into()
}

/// `SHA-256(0x01 ‖ left ‖ right)` — one interior node.
pub fn node_hash(left: &Hash, right: &Hash) -> Hash {
    let mut hasher = sha2::Sha256::new();
    hasher.update([NODE_PREFIX]);
    hasher.update(left);
    hasher.update(right);
    hasher.finalize().into()
}

/// The Merkle root over `leaves`, in order.
///
/// An empty log hashes to `SHA-256("")`, which is RFC 6962's rule and is a
/// *value* rather than an absence — an empty log can be signed, and a signed
/// empty head is how a verifier learns the log exists and holds nothing.
pub fn root(leaves: &[Hash]) -> Hash {
    if leaves.is_empty() {
        return sha2::Sha256::digest([]).into();
    }
    let mut level: Vec<Hash> = leaves.to_vec();
    while level.len() > 1 {
        let mut next = Vec::with_capacity(level.len().div_ceil(2));
        let mut pairs = level.chunks_exact(2);
        for pair in &mut pairs {
            next.push(node_hash(&pair[0], &pair[1]));
        }
        // Promoted, not duplicated. See the module docs.
        if let [odd] = pairs.remainder() {
            next.push(*odd);
        }
        level = next;
    }
    level[0]
}

/// The sibling hashes that carry `index` up to the root of a tree of `leaves`.
///
/// `None` when `index` is out of range — a proof for a record the log does not
/// hold is not an empty proof, and returning one would make "verified" the
/// answer for a leaf that was never there.
pub fn inclusion_proof(leaves: &[Hash], index: usize) -> Option<Vec<Hash>> {
    if index >= leaves.len() {
        return None;
    }
    let mut proof = Vec::new();
    let mut level: Vec<Hash> = leaves.to_vec();
    let mut at = index;
    while level.len() > 1 {
        // The promoted-odd rule again, and it has to be mirrored exactly: a
        // node with no sibling contributes nothing to the path.
        let sibling = if at % 2 == 0 { at + 1 } else { at - 1 };
        if sibling < level.len() {
            proof.push(level[sibling]);
        }
        let mut next = Vec::with_capacity(level.len().div_ceil(2));
        let mut pairs = level.chunks_exact(2);
        for pair in &mut pairs {
            next.push(node_hash(&pair[0], &pair[1]));
        }
        if let [odd] = pairs.remainder() {
            next.push(*odd);
        }
        level = next;
        at /= 2;
    }
    Some(proof)
}

/// Recompute a root from one leaf and its proof, and compare.
///
/// This is the whole point of the module: a client with a record, its position,
/// the tree size and a signed root can check membership **without the log**.
pub fn verify_inclusion(
    leaf: &Hash,
    index: usize,
    size: usize,
    proof: &[Hash],
    expected_root: &Hash,
) -> bool {
    if index >= size {
        return false;
    }
    let mut computed = *leaf;
    let mut at = index;
    let mut width = size;
    let mut steps = proof.iter();
    while width > 1 {
        let sibling = if at % 2 == 0 { at + 1 } else { at - 1 };
        if sibling < width {
            let Some(step) = steps.next() else {
                // The proof ran out before the tree did. A short proof must be
                // a refusal and never a pass: padding it with anything at all
                // would let a truncated proof verify.
                return false;
            };
            computed = if at % 2 == 0 {
                node_hash(&computed, step)
            } else {
                node_hash(step, &computed)
            };
        }
        at /= 2;
        width = width.div_ceil(2);
    }
    // A proof with steps left over describes a different tree.
    steps.next().is_none() && computed == *expected_root
}

/// **What a log signs**: how many records it holds and what they hash to.
///
/// The pair is the claim. A root alone says nothing about *when* — the same
/// root can be reissued for ever — and a size alone is not a commitment to
/// content. Together they say: *at this moment I held exactly these N records,
/// in this order.*
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
#[serde(deny_unknown_fields)]
pub struct TreeHead {
    /// How many records the log held.
    pub size: u64,
    /// [`root`] over those records, hex.
    pub root: String,
    /// When the head was issued.
    pub at_unix_ms: i64,
}

impl TreeHead {
    /// The exact bytes that are signed.
    ///
    /// A fixed, line-oriented rendering rather than the JSON: JSON has no
    /// canonical form, so signing the serialisation would make the signature
    /// depend on a serialiser's field order. Three lines and a label cannot
    /// drift.
    pub fn signing_bytes(&self) -> Vec<u8> {
        format!(
            "gunnar-transparency-v1\nsize {}\nroot {}\nat {}\n",
            self.size, self.root, self.at_unix_ms
        )
        .into_bytes()
    }
}

/// A [`TreeHead`] with the signature that makes it evidence.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
#[serde(deny_unknown_fields)]
pub struct SignedTreeHead {
    /// The head the signature is over.
    #[serde(flatten)]
    pub head: TreeHead,
    /// `SHA256:…` of the key that signed it, so a verifier knows which key to
    /// look up before it does any crypto.
    pub key_fingerprint: String,
    /// The `sshsig`, PEM-armoured, newlines and all.
    pub signature: String,
}

/// What went wrong verifying a tree head.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TreeHeadProblem {
    /// The signature is not a well-formed `sshsig`.
    Malformed(String),
    /// The head names a key that is not the one offered.
    WrongKey {
        /// The fingerprint the head claims.
        signed_by: String,
        /// The fingerprint of the key given to check it.
        offered: String,
    },
    /// The signature does not verify against the key.
    NotVerified,
}

impl std::fmt::Display for TreeHeadProblem {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            TreeHeadProblem::Malformed(why) => write!(
                f,
                "the tree head's signature is not a \
                 well-formed sshsig: {why}"
            ),
            TreeHeadProblem::WrongKey { signed_by, offered } => write!(
                f,
                "the tree head says it was signed by {signed_by} and was checked against {offered}"
            ),
            TreeHeadProblem::NotVerified => {
                write!(f, "the tree head's signature does not verify")
            }
        }
    }
}

/// Sign a tree head with `key`, under [`STH_NAMESPACE`].
pub fn sign_tree_head(
    key: &ssh_key::PrivateKey,
    head: TreeHead,
) -> Result<SignedTreeHead, ssh_key::Error> {
    let signature = key.sign(
        STH_NAMESPACE,
        ssh_key::HashAlg::Sha512,
        &head.signing_bytes(),
    )?;
    Ok(SignedTreeHead {
        key_fingerprint: key
            .public_key()
            .fingerprint(ssh_key::HashAlg::Sha256)
            .to_string(),
        signature: signature.to_pem(ssh_key::LineEnding::LF)?,
        head,
    })
}

/// Verify a signed tree head against a public key.
///
/// The fingerprint in the record is checked against the key **before** the
/// signature, so a head signed by key A can never be reported as verified by
/// key B even if the caller looked up the wrong row.
pub fn verify_tree_head(
    sth: &SignedTreeHead,
    key: &ssh_key::PublicKey,
) -> Result<(), TreeHeadProblem> {
    let offered = key.fingerprint(ssh_key::HashAlg::Sha256).to_string();
    if offered != sth.key_fingerprint {
        return Err(TreeHeadProblem::WrongKey {
            signed_by: sth.key_fingerprint.clone(),
            offered,
        });
    }
    let signature = ssh_key::SshSig::from_pem(sth.signature.as_bytes())
        .map_err(|err| TreeHeadProblem::Malformed(err.to_string()))?;
    if signature.namespace() != STH_NAMESPACE {
        return Err(TreeHeadProblem::Malformed(format!(
            "namespace is {:?}, not {STH_NAMESPACE:?}",
            signature.namespace()
        )));
    }
    key.verify(STH_NAMESPACE, &sth.head.signing_bytes(), &signature)
        .map_err(|_| TreeHeadProblem::NotVerified)
}

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

    fn leaves(n: usize) -> Vec<Hash> {
        (0..n)
            .map(|i| leaf_hash(format!("record {i}").as_bytes()))
            .collect()
    }

    /// **The prefixes are what stop a second-preimage attack**, so they are
    /// asserted rather than assumed: a leaf and a node over the same bytes must
    /// not collide.
    #[test]
    fn a_leaf_and_a_node_over_the_same_bytes_are_different_hashes() {
        let a = leaf_hash(b"x");
        let b = leaf_hash(b"y");
        let mut concatenated = Vec::new();
        concatenated.extend_from_slice(&a);
        concatenated.extend_from_slice(&b);
        assert_ne!(
            leaf_hash(&concatenated),
            node_hash(&a, &b),
            "a leaf whose bytes are two hashes hashes like an interior node, so a proof can be \
             forged for a record the log never held"
        );
    }

    /// An odd leaf is **promoted**, not duplicated — and the two rules give
    /// different roots, which is why it has to be said.
    #[test]
    fn an_odd_leaf_is_promoted_and_not_duplicated() {
        let three = leaves(3);
        let promoted = root(&three);
        let duplicated = {
            let pair = node_hash(&three[0], &three[1]);
            let doubled = node_hash(&three[2], &three[2]);
            node_hash(&pair, &doubled)
        };
        assert_ne!(
            promoted, duplicated,
            "promotion and duplication produced the same root, so this test cannot tell them \
             apart and the rule below is unasserted"
        );
    }

    /// Every leaf in every size up to 33 proves, and every proof is checked
    /// against the size it was made for.
    #[test]
    fn every_leaf_of_every_size_proves_against_its_own_root() {
        for size in 1..=33 {
            let set = leaves(size);
            let expected = root(&set);
            for index in 0..size {
                let proof = inclusion_proof(&set, index).expect("a leaf that is in the tree");
                assert!(
                    verify_inclusion(&set[index], index, size, &proof, &expected),
                    "leaf {index} of {size} did not verify"
                );
            }
        }
    }

    /// The refusals. Each one is a way a verifier could be talked into saying
    /// yes, and each must say no.
    #[test]
    fn a_forged_or_truncated_or_misplaced_proof_is_refused() {
        let set = leaves(8);
        let expected = root(&set);
        let proof = inclusion_proof(&set, 3).expect("in the tree");

        assert!(
            !verify_inclusion(&set[3], 4, 8, &proof, &expected),
            "a proof for leaf 3 verified at position 4"
        );
        assert!(
            !verify_inclusion(&set[4], 3, 8, &proof, &expected),
            "a different leaf verified with leaf 3's proof"
        );
        assert!(
            !verify_inclusion(&set[3], 3, 8, &proof[..proof.len() - 1], &expected),
            "a TRUNCATED proof verified; a short proof must be a refusal"
        );
        let mut too_long = proof.clone();
        too_long.push([0u8; 32]);
        assert!(
            !verify_inclusion(&set[3], 3, 8, &too_long, &expected),
            "a proof with a step left over verified; it describes a different tree"
        );
        assert!(
            !verify_inclusion(&set[3], 3, 8, &proof, &[0u8; 32]),
            "a proof verified against a root nobody signed"
        );
        assert!(
            inclusion_proof(&set, 8).is_none(),
            "a proof was produced for a leaf past the end of the log"
        );
    }

    /// **Rewriting one record changes the root**, which is the property the
    /// whole log exists for.
    #[test]
    fn changing_one_record_changes_the_root() {
        let mut set = leaves(9);
        let before = root(&set);
        set[4] = leaf_hash(b"record 4, tampered with");
        assert_ne!(
            before,
            root(&set),
            "a record was rewritten and the root did not move, so a signed head over the old \
             root still covers the new file"
        );
    }

    #[test]
    fn hex_round_trips_and_refuses_what_is_not_a_digest() {
        let h = leaf_hash(b"x");
        assert_eq!(unhex(&hex(&h)), Some(h));
        assert_eq!(unhex("short"), None);
        assert_eq!(unhex(&"z".repeat(64)), None);
    }

    /// A tree head signs and verifies, and every way of getting it wrong is
    /// refused: a different key, a moved size, a moved root, another namespace.
    #[test]
    fn a_tree_head_verifies_and_a_tampered_one_does_not() {
        let pem = crate::mint_ed25519().expect("mint a key");
        let key = ssh_key::PrivateKey::from_openssh(&pem).expect("parse");
        let other = ssh_key::PrivateKey::from_openssh(crate::mint_ed25519().expect("a second key"))
            .expect("parse");

        let head = TreeHead {
            size: 7,
            root: hex(&root(&leaves(7))),
            at_unix_ms: 1_700_000_000_000,
        };
        let sth = sign_tree_head(&key, head.clone()).expect("sign");
        assert_eq!(verify_tree_head(&sth, key.public_key()), Ok(()));

        assert!(matches!(
            verify_tree_head(&sth, other.public_key()),
            Err(TreeHeadProblem::WrongKey { .. })
        ));

        let mut moved = sth.clone();
        moved.head.size = 8;
        assert_eq!(
            verify_tree_head(&moved, key.public_key()),
            Err(TreeHeadProblem::NotVerified),
            "a head whose size was changed still verified"
        );

        let mut rerooted = sth.clone();
        rerooted.head.root = hex(&[0u8; 32]);
        assert_eq!(
            verify_tree_head(&rerooted, key.public_key()),
            Err(TreeHeadProblem::NotVerified),
            "a head whose root was changed still verified"
        );

        // A signature made under another namespace must not be accepted here,
        // which is what stops a commit signature being presented as a head.
        let elsewhere = key
            .sign("git", ssh_key::HashAlg::Sha512, &head.signing_bytes())
            .expect("sign under another namespace");
        let smuggled = SignedTreeHead {
            head,
            key_fingerprint: sth.key_fingerprint.clone(),
            signature: elsewhere.to_pem(ssh_key::LineEnding::LF).expect("armour"),
        };
        assert!(matches!(
            verify_tree_head(&smuggled, key.public_key()),
            Err(TreeHeadProblem::Malformed(_))
        ));
    }
}