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.