access: values signed by their users

access::envelope: cv1.<payload>.<signature>, the payload naming the
path, value, user, time and the envelope it replaces (prev), signed
with one of the user's SSH keys from the registry (keys). Checked
against the registry as the writer saw it.

Auth plan M7.

5 files changed, 289 insertions, 2 deletions

diff --git a/src/access/envelope.rs b/src/access/envelope.rs
new file mode 100644
index 0000000..a875dca
--- /dev/null
+++ b/src/access/envelope.rs
@@ -0,0 +1,254 @@
+//! Values signed by their user: at a path the swarm lists as user-signed
+//! (`_continuum/access/userSigned`, `listed`), the value is a signed envelope, one
+//! string, `cv1.<payload>.<signature>` (each base64url, unpadded). The payload is JSON:
+//! the `path` it is for (segments), the `value` (`null`: deleted), the `user` who
+//! signed it, when (`at`, Unix ms, by the signer's clock), and `prev`: the SHA-256 (hex)
+//! of the envelope it replaces, empty if none. The signature is the user's, with one
+//! of its keys (`registry::User::keys`), over the payload's bytes, as
+//! `ssh-keygen -Y sign -n continuum-value` makes it (`access::sshsig`), its SSHSIG blob.
+//!
+//! It travels with the value, through replays and snapshots alike, and anyone can check
+//! it (`check`): a node before it writes or applies one, a client reading it. `prev`
+//! keeps a member from putting an older signed value back: an envelope only replaces
+//! the one it names. A node never writes there but as its user signed it.
+
+use base64::{Engine, engine::general_purpose::URL_SAFE_NO_PAD as B64URL};
+use serde::{Deserialize, Serialize};
+use serde_json::Value as JsonValue;
+use sha2::{Digest, Sha256};
+
+use super::{Right, registry, sshsig};
+use crate::document::{ReadDoc, meta, store};
+
+/// What a signature over a payload is for (`sshsig`).
+pub(crate) const NAMESPACE: &str = "continuum-value";
+/// What every envelope starts with.
+const PREFIX: &str = "cv1";
+
+/// Where the swarm lists the user-signed paths: a list of paths, each a list of
+/// segments.
+pub(crate) fn listed_at() -> Vec<String> {
+    meta::path(&[meta::ACCESS, "userSigned"])
+}
+
+/// The paths `doc` lists as user-signed; an entry that isn't a list of strings is left
+/// out.
+pub(crate) fn listed(doc: &impl ReadDoc) -> Vec<Vec<String>> {
+    let Ok(Some(JsonValue::Array(entries))) = store::read_path(doc, &listed_at()) else {
+        return Vec::new();
+    };
+    entries
+        .iter()
+        .filter_map(|entry| {
+            entry
+                .as_array()?
+                .iter()
+                .map(|segment| segment.as_str().map(str::to_owned))
+                .collect()
+        })
+        .collect()
+}
+
+/// The user-signed path `path` is at or within, if any (`listed`).
+pub(crate) fn signed_path<'a>(listed: &'a [Vec<String>], path: &[String]) -> Option<&'a [String]> {
+    listed
+        .iter()
+        .find(|signed| path.starts_with(signed))
+        .map(Vec::as_slice)
+}
+
+/// A signed value's payload.
+#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
+pub(crate) struct Payload {
+    pub(crate) path: Vec<String>,
+    pub(crate) value: JsonValue,
+    pub(crate) user: String,
+    pub(crate) at: u64,
+    pub(crate) prev: String,
+}
+
+/// An envelope checked (`check`): what it says, and the key that signed it.
+#[derive(Debug, Clone, PartialEq)]
+pub(crate) struct Signed {
+    pub(crate) payload: Payload,
+    pub(crate) key: sshsig::PublicKey,
+}
+
+/// What `prev` names for `envelope`, the one replaced (none: empty).
+pub(crate) fn digest(envelope: Option<&str>) -> String {
+    envelope.map_or_else(String::new, |envelope| {
+        Sha256::digest(envelope.as_bytes())
+            .iter()
+            .map(|byte| format!("{byte:02x}"))
+            .collect()
+    })
+}
+
+/// The envelope of `payload` (its exact bytes) signed by `signature` (armored, as
+/// `ssh-keygen -Y sign` writes it).
+pub(crate) fn seal(payload: &[u8], armored: &str) -> Result<String, String> {
+    let blob = sshsig::dearmor(armored)?;
+    Ok(format!(
+        "{PREFIX}.{}.{}",
+        B64URL.encode(payload),
+        B64URL.encode(blob)
+    ))
+}
+
+/// What `envelope` holds, unchecked: its payload's bytes, the payload, the signature's
+/// blob.
+fn open(envelope: &str) -> Result<(Vec<u8>, Payload, Vec<u8>), String> {
+    let mut parts = envelope.split('.');
+    let (Some(PREFIX), Some(payload), Some(signature), None) =
+        (parts.next(), parts.next(), parts.next(), parts.next())
+    else {
+        return Err("not a signed value (cv1.<payload>.<signature>)".to_owned());
+    };
+    let bytes = B64URL
+        .decode(payload)
+        .map_err(|error| format!("its payload doesn't decode: {error}"))?;
+    let parsed: Payload = serde_json::from_slice(&bytes)
+        .map_err(|error| format!("its payload isn't one: {error}"))?;
+    let signature = B64URL
+        .decode(signature)
+        .map_err(|error| format!("its signature doesn't decode: {error}"))?;
+    Ok((bytes, parsed, signature))
+}
+
+/// What `envelope` says, unchecked: for showing a value (`check` before taking it).
+pub(crate) fn read(envelope: &str) -> Result<Payload, String> {
+    open(envelope).map(|(_, payload, _)| payload)
+}
+
+/// Checks `envelope` as the value at `path`, replacing `previous` (the envelope there
+/// before, if any), against the user registry `doc` holds (as the writer saw it): for
+/// that path, naming what it replaces, signed by one of its user's keys, a user who may
+/// write there.
+pub(crate) fn check(
+    doc: &impl ReadDoc,
+    envelope: &str,
+    path: &[String],
+    previous: Option<&str>,
+) -> Result<Signed, String> {
+    let (bytes, payload, signature) = open(envelope)?;
+    if payload.path != path {
+        return Err(format!(
+            "signed for /{}, not /{}",
+            payload.path.join("/"),
+            path.join("/")
+        ));
+    }
+    if payload.prev != digest(previous) {
+        return Err("it doesn't replace the value there (prev)".to_owned());
+    }
+    let key = sshsig::verify_blob(&signature, NAMESPACE, &bytes)?;
+    let user =
+        registry::user(doc, &payload.user).ok_or_else(|| format!("no user {}", payload.user))?;
+    if !user.keys.values().any(|known| *known == key) {
+        return Err(format!("{} has no key {}", payload.user, key.fingerprint()));
+    }
+    if !user.caps().allows(Right::Write, path) {
+        return Err(format!(
+            "{} may not write /{}",
+            payload.user,
+            path.join("/")
+        ));
+    }
+    Ok(Signed { payload, key })
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::document::Document;
+    use crate::document::testing::change;
+    use ed25519_dalek::SigningKey;
+    use serde_json::json;
+
+    fn path(text: &str) -> Vec<String> {
+        text.split('/').map(str::to_owned).collect()
+    }
+
+    /// A registry with alice, who may write `config` and holds `key`'s public key, and
+    /// bob, who holds it too but may write nothing.
+    fn registry_with(key: &SigningKey) -> Document {
+        let line = sshsig::PublicKey(key.verifying_key().to_bytes()).line();
+        let mut doc = Document::new();
+        change(&mut doc, |doc| {
+            let mut alice = registry::entry("root", 1, &[(path("config"), &[Right::Write][..])]);
+            alice["keys"] = json!({ "laptop": line });
+            store::write_path(doc, &registry::user_path("alice"), &alice).unwrap();
+            let mut bob = registry::entry("root", 1, &[]);
+            bob["keys"] = json!({ "laptop": line });
+            store::write_path(doc, &registry::user_path("bob"), &bob).unwrap();
+        });
+        doc
+    }
+
+    fn signed(key: &SigningKey, payload: &Payload) -> String {
+        let bytes = serde_json::to_vec(payload).unwrap();
+        seal(&bytes, &sshsig::sign(key, NAMESPACE, &bytes)).unwrap()
+    }
+
+    fn payload(user: &str, at: &str, value: JsonValue, prev: &str) -> Payload {
+        Payload {
+            path: path(at),
+            value,
+            user: user.to_owned(),
+            at: 1,
+            prev: prev.to_owned(),
+        }
+    }
+
+    /// Signed for its path, replacing what is there, by one of its user's keys, a user
+    /// who may write there: taken; anything else refused.
+    #[test]
+    fn what_an_envelope_must_be() {
+        let key = SigningKey::from_bytes(&[5; 32]);
+        let other = SigningKey::from_bytes(&[6; 32]);
+        let doc = registry_with(&key);
+        let first = signed(
+            &key,
+            &payload("alice", "config", json!({"mode": "fast"}), ""),
+        );
+        let checked = check(&doc, &first, &path("config"), None).unwrap();
+        assert_eq!(checked.payload.value, json!({"mode": "fast"}));
+        assert_eq!(read(&first).unwrap().user, "alice");
+        // Another path, another key, a user who may not, an unknown one.
+        assert!(check(&doc, &first, &path("other"), None).is_err());
+        let foreign = signed(&other, &payload("alice", "config", json!(1), ""));
+        assert!(check(&doc, &foreign, &path("config"), None).is_err());
+        let bobs = signed(&key, &payload("bob", "config", json!(1), ""));
+        assert!(check(&doc, &bobs, &path("config"), None).is_err());
+        let nobodys = signed(&key, &payload("carol", "config", json!(1), ""));
+        assert!(check(&doc, &nobodys, &path("config"), None).is_err());
+        // Replacing: only what it names.
+        let second = signed(
+            &key,
+            &payload("alice", "config", json!(null), &digest(Some(&first))),
+        );
+        assert!(check(&doc, &second, &path("config"), Some(&first)).is_ok());
+        assert!(check(&doc, &second, &path("config"), None).is_err());
+        assert!(check(&doc, &first, &path("config"), Some(&second)).is_err());
+        // Tampered with.
+        let tampered = first.replacen("cv1.", "cv1.e30", 1);
+        assert!(check(&doc, &tampered, &path("config"), None).is_err());
+        assert!(check(&doc, "plain", &path("config"), None).is_err());
+    }
+
+    #[test]
+    fn listed_paths() {
+        let mut doc = Document::new();
+        change(&mut doc, |doc| {
+            store::write_path(doc, &listed_at(), &json!([["config"], ["a", "b"], "junk"])).unwrap();
+        });
+        let listed = listed(&doc);
+        assert_eq!(listed, vec![path("config"), path("a/b")]);
+        assert_eq!(
+            signed_path(&listed, &path("config")),
+            Some(&path("config")[..])
+        );
+        assert_eq!(signed_path(&listed, &path("a/b/c")), Some(&path("a/b")[..]));
+        assert_eq!(signed_path(&listed, &path("a")), None);
+    }
+}
diff --git a/src/access/mod.rs b/src/access/mod.rs
index 2ed19a5..b58355e 100644
--- a/src/access/mod.rs
+++ b/src/access/mod.rs
@@ -14,6 +14,9 @@ use serde::{Deserialize, Serialize};
 use crate::document::meta;
 
 pub(crate) mod bans;
+// Values signed by their users: what the store and the rules use; until then, the tests.
+#[cfg_attr(not(test), allow(dead_code))]
+pub(crate) mod envelope;
 pub(crate) mod policy;
 pub(crate) mod registry;
 pub(crate) mod rules;
diff --git a/src/access/registry.rs b/src/access/registry.rs
index 5899bdd..eb7919c 100644
--- a/src/access/registry.rs
+++ b/src/access/registry.rs
@@ -69,6 +69,10 @@ pub(crate) struct User {
     /// Tokens issued before (Unix ms) are no longer taken (`token::verify`): how all
     /// of a user's tokens are revoked at once.
     pub(crate) tokens_not_before: u64,
+    /// Its keys (`keys/<id>`, `authorized_keys` lines, `access::sshsig`): what it signs
+    /// values with (`access::envelope`) and logs in with. One that doesn't read is left
+    /// out.
+    pub(crate) keys: BTreeMap<String, super::sshsig::PublicKey>,
 }
 
 impl User {
@@ -101,6 +105,18 @@ impl User {
                 None => 0,
                 Some(at) => at.as_u64().unwrap_or(u64::MAX),
             },
+            keys: value
+                .get("keys")
+                .and_then(JsonValue::as_object)
+                .map(|keys| {
+                    keys.iter()
+                        .filter_map(|(id, line)| {
+                            let key = super::sshsig::PublicKey::parse(line.as_str()?).ok()?;
+                            Some((id.clone(), key))
+                        })
+                        .collect()
+                })
+                .unwrap_or_default(),
         }
     }
 
diff --git a/src/access/sshsig.rs b/src/access/sshsig.rs
index 1f01d21..b40da0d 100644
--- a/src/access/sshsig.rs
+++ b/src/access/sshsig.rs
@@ -79,6 +79,11 @@ impl PublicKey {
 /// The key that made `armored`, a signature of `message` for `namespace`, if it is
 /// one: valid, of an Ed25519 key, for that namespace.
 pub(crate) fn verify(armored: &str, namespace: &str, message: &[u8]) -> Result<PublicKey, String> {
+    verify_blob(&dearmor(armored)?, namespace, message)
+}
+
+/// The SSHSIG blob an armored signature holds.
+pub(crate) fn dearmor(armored: &str) -> Result<Vec<u8>, String> {
     let body: String = armored
         .trim()
         .strip_prefix(BEGIN)
@@ -86,9 +91,17 @@ pub(crate) fn verify(armored: &str, namespace: &str, message: &[u8]) -> Result<P
         .ok_or("not an armored SSH signature")?
         .split_whitespace()
         .collect();
-    let blob = BASE64
+    BASE64
         .decode(body)
-        .map_err(|error| format!("its base64 doesn't decode: {error}"))?;
+        .map_err(|error| format!("its base64 doesn't decode: {error}"))
+}
+
+/// [`verify`] of a signature's SSHSIG blob (`dearmor`).
+pub(crate) fn verify_blob(
+    blob: &[u8],
+    namespace: &str,
+    message: &[u8],
+) -> Result<PublicKey, String> {
     let mut reader = Reader(
         blob.strip_prefix(MAGIC)
             .ok_or("not an SSH signature (no SSHSIG)")?,
diff --git a/src/document/meta.rs b/src/document/meta.rs
index 8fd2138..df7741a 100644
--- a/src/document/meta.rs
+++ b/src/document/meta.rs
@@ -18,6 +18,7 @@
 //!   (`access::registry`).
 //! * `access/signed`: the paths whose writes are signed (`document::signatures`).
 //! * `access/policy`: whether every node judges received changes (`access::policy`).
+//! * `access/userSigned`: the paths whose values their users sign (`access::envelope`).
 //! * `banned/<pk>`: banned nodes (`access::bans`).
 
 /// The key every protocol path starts with.