Signed update metadata (TUF)

Deep dive

How it works

Parts:

• Root — keys and thresholds of every top-level role, itself included; offline; kept as N.root.json.
• Targets — file name to hash and length; may delegate path patterns to other roles.
• Snapshot — current version of every targets file; blocks mix-and-match.
• Timestamp — online, re-signed often: snapshot version and hash; blocks freeze and replay.
• Client — shipped root, last accepted version of each file, a fixed start time.

Client update (spec §5):

1. Fix the start time once; load the trusted root (its expiry matters only after step 2).
2. Fetch N+1.root.json until none exists: signed by a threshold of old and of new keys, version exactly N+1; the last root must be unexpired.
3. Timestamp: threshold from root, version not lower (equal: nothing changed), snapshot version not lower, unexpired.
4. Snapshot: hash and version as named by the timestamp, threshold, no targets version lower or entry dropped, unexpired.
5. Targets: hash and version from the snapshot, threshold, unexpired; walk delegations depth first with a visit limit.
6. Fetch the file up to its listed length; compare the hash.
7. Persist each file only after its checks pass; any failure aborts, the next run starts again.

root(offline) --keys--> timestamp --snapshot ver+hash--> snapshot --targets vers--> targets --> file hash+len
root N --old AND new threshold--> root N+1 --> ... --> latest root

Rotation needs both sets: stolen new keys alone cannot take over, old keys alone cannot install keys the new set rejects. After a timestamp or snapshot key rotation the client deletes its stored timestamp and snapshot, forgetting inflated version numbers (fast-forward).

Code

Client-side checker with a pluggable verify. The test stub is a keyed checksum and the digest is FNV: not crypto; use Ed25519 and SHA-256. Omitted: download byte limits, parent-hash checks, delegations, persistence.

use std::collections::{BTreeMap, HashSet};
pub type Verify = fn(&str, &[u8], &[u8]) -> bool; // (key_id, message, signature)
#[derive(Clone, Debug)] pub struct Role { pub keys: Vec<String>, pub threshold: usize }
#[derive(Clone, Debug)] pub struct Root { pub version: u64, pub expires: u64, pub roles: BTreeMap<String, Role> }
#[derive(Debug)] pub struct Ts { pub version: u64, pub expires: u64, pub snap_version: u64 }
#[derive(Debug)] pub struct Snap { pub version: u64, pub expires: u64, pub targets_version: u64 }
#[derive(Debug)] pub struct Targets { pub version: u64, pub expires: u64, pub hash: u64, pub length: usize }
pub struct Signed<T> { pub meta: T, pub sigs: Vec<(String, Vec<u8>)> }
#[derive(Debug, PartialEq)] pub enum E { Sig, Rollback, Expired, MixMatch, Length, Hash }
// Stand-in for canonical JSON: any deterministic encoding of the signed part.
pub fn enc<T: std::fmt::Debug>(m: &T) -> Vec<u8> { format!("{m:?}").into_bytes() }
pub fn digest(d: &[u8]) -> u64 { d.iter().fold(0xcbf29ce484222325, |h, &b| (h ^ b as u64).wrapping_mul(0x100000001b3)) } // FNV-1a: NOT a secure hash
/// Count each key at most once, whatever the signature list says (spec §5.3.2).
fn met<T: std::fmt::Debug>(r: &Role, s: &Signed<T>, v: Verify) -> bool {
    let msg = enc(&s.meta);
    let ok = s.sigs.iter().filter(|(k, sig)| r.keys.contains(k) && v(k, &msg, sig)).map(|(k, _)| k.as_str());
    ok.collect::<HashSet<_>>().len() >= r.threshold
}
pub struct Client { pub root: Root, pub ts: u64, pub snap: u64, pub tgt: u64, pub v: Verify }
impl Client {
    /// Root N -> N+1: signed by a threshold of the OLD and of the NEW root keys, version exactly +1.
    pub fn update_root(&mut self, n: Signed<Root>) -> Result<(), E> {
        if !met(&self.root.roles["root"], &n, self.v) || !met(&n.meta.roles["root"], &n, self.v) { return Err(E::Sig); }
        if n.meta.version != self.root.version + 1 { return Err(E::Rollback); }
        Ok(self.root = n.meta)
    }
    /// timestamp -> snapshot -> targets -> file; state moves only if every check passes.
    pub fn update(&mut self, now: u64, ts: &Signed<Ts>, sn: &Signed<Snap>, t: &Signed<Targets>, file: &[u8]) -> Result<(), E> {
        let r = &self.root.roles;
        if self.root.expires <= now { return Err(E::Expired); }
        if !met(&r["timestamp"], ts, self.v) { return Err(E::Sig); }
        if ts.meta.version < self.ts || ts.meta.snap_version < self.snap { return Err(E::Rollback); }
        if ts.meta.expires <= now { return Err(E::Expired); }
        if !met(&r["snapshot"], sn, self.v) { return Err(E::Sig); }
        if sn.meta.version != ts.meta.snap_version { return Err(E::MixMatch); }
        if sn.meta.targets_version < self.tgt { return Err(E::Rollback); }
        if sn.meta.expires <= now { return Err(E::Expired); }
        if !met(&r["targets"], t, self.v) { return Err(E::Sig); }
        if t.meta.version != sn.meta.targets_version { return Err(E::MixMatch); }
        if t.meta.expires <= now { return Err(E::Expired); }
        if file.len() != t.meta.length { return Err(E::Length); } // a real client stops reading at `length` bytes
        if digest(file) != t.meta.hash { return Err(E::Hash); }
        Ok((self.ts, self.snap, self.tgt) = (ts.meta.version, sn.meta.version, t.meta.version))
    }
}
#[cfg(test)]
mod t {
    use super::*;
    fn sig(k: &str, m: &[u8]) -> Vec<u8> { digest(&[k.as_bytes(), m].concat()).to_le_bytes().to_vec() }
    fn stub(k: &str, m: &[u8], s: &[u8]) -> bool { s == sig(k, m) } // stub
    fn sign<T: std::fmt::Debug>(meta: T, ks: &[&str]) -> Signed<T> {
        Signed { sigs: ks.iter().map(|k| (k.to_string(), sig(k, &enc(&meta)))).collect(), meta }
    }
    fn role(ks: &[&str], threshold: usize) -> Role { Role { keys: ks.iter().map(|k| k.to_string()).collect(), threshold } }
    fn root(version: u64, rk: &[&str]) -> Root {
        let r = [("root", role(rk, 2)), ("timestamp", role(&["t1"], 1)), ("snapshot", role(&["s1"], 1)), ("targets", role(&["g1", "g2", "g3"], 2))];
        Root { version, expires: 1000, roles: r.into_iter().map(|(n, r)| (n.to_string(), r)).collect() }
    }
    const FILE: &[u8] = b"firmware-v7";
    /// (ts ver, snapshot it names), (snapshot ver, targets it names), (targets ver, signers)
    fn mk(t: (u64, u64), s: (u64, u64), g: (u64, &[&str])) -> (Signed<Ts>, Signed<Snap>, Signed<Targets>) {
        (sign(Ts { version: t.0, expires: 500, snap_version: t.1 }, &["t1"]),
         sign(Snap { version: s.0, expires: 500, targets_version: s.1 }, &["s1"]),
         sign(Targets { version: g.0, expires: 500, hash: digest(FILE), length: FILE.len() }, g.1))
    }
    fn up(c: &mut Client, now: u64, t: (u64, u64), s: (u64, u64), g: (u64, &[&str]), f: &[u8]) -> Result<(), E> { let (a, b, x) = mk(t, s, g); c.update(now, &a, &b, &x, f) }
    #[test]
    fn paths() {
        let mut c = Client { root: root(1, &["r1", "r2"]), ts: 0, snap: 0, tgt: 0, v: stub };
        // rotation: 2 of {r1,r2} AND 2 of {r2,r3}, version N+1
        assert_eq!(c.update_root(sign(root(2, &["r2", "r3"]), &["r1", "r2"])), Err(E::Sig));
        assert_eq!(c.update_root(sign(root(2, &["r2", "r3"]), &["r2", "r3"])), Err(E::Sig));
        assert_eq!(c.update_root(sign(root(3, &["r2", "r3"]), &["r1", "r2", "r3"])), Err(E::Rollback));
        assert_eq!(c.update_root(sign(root(2, &["r2", "r3"]), &["r1", "r2", "r3"])), Ok(()));
        let (ok, f) = (&["g1", "g2"][..], FILE);
        assert_eq!(up(&mut c, 100, (5, 5), (5, 5), (5, ok), f), Ok(()));
        assert_eq!(up(&mut c, 100, (5, 5), (5, 5), (5, &["g1"]), f), Err(E::Sig)); // below threshold
        assert_eq!(up(&mut c, 100, (5, 5), (5, 5), (5, &["g1", "g1"]), f), Err(E::Sig)); // one key twice counts once
        assert_eq!(up(&mut c, 100, (4, 4), (4, 4), (4, ok), f), Err(E::Rollback));
        assert_eq!(up(&mut c, 500, (5, 5), (5, 5), (5, ok), f), Err(E::Expired)); // freeze
        assert_eq!(up(&mut c, 100, (5, 5), (6, 5), (5, ok), f), Err(E::MixMatch)); // snapshot is not the one named
        assert_eq!(up(&mut c, 100, (5, 5), (5, 6), (5, ok), f), Err(E::MixMatch)); // targets is not the one named
        assert_eq!(up(&mut c, 100, (5, 5), (5, 5), (5, ok), b"firmware-v7+junk"), Err(E::Length));
        assert_eq!(up(&mut c, 100, (5, 5), (5, 5), (5, ok), b"firmware-v8"), Err(E::Hash));
        let (a, b, x) = mk((5, 5), (5, 5), (5, ok));
        let t0 = std::time::Instant::now();
        for _ in 0..200_000 { assert!(c.update(100, &a, &b, &x, f).is_ok()); }
        println!("{} ns per full check", t0.elapsed().as_nanos() / 200_000);
    }
}

Run-checked with cargo test --release: all rejection paths, rotation, happy path.

Complexity and constants

• Per update: a verify per counted signer (sum of thresholds, 4 here), per root hop a verify against old and new sets, one hash over the file.
• Measured (M-series Mac, release, stub verify): 1.3-1.5 µs per full check over five runs, mostly format! encoding: overhead, not crypto.
• With Ed25519 at 40.1 µs per verify (ed25519-dalek README, Intel 10700K, via Ed25519), four verifies are of the order of 160 µs; not measured by me.

Efficiency

Cost: a no-change poll is one small timestamp fetch and one verification; a full update adds the verifications above and the file. Bound: round trips (one per metadata file), not compute.

Levers:

• Poll the timestamp first — equal version ends the run (spec §5.4) — frequent polling.
• Snapshot lists targets versions — fetch only changed targets files (spec §2.1.3) — many delegated roles.
• Parent hash before signature — cheap rejection of bad metadata (spec §5.5) — hostile mirrors.
• Length caps on every download — endless-data defence, bounded memory (spec §5) — always.
• Versioned/hash-named files — no half-written reads (spec §6.2); immutable names also cache on a CDN (my inference) — volatile repositories.

Naive → standard → state of the art:

• Naive: one key signs files, any server trusted · one stolen key owns every client.
• Standard: four roles, thresholds, timestamp polling (python-tuf, go-tuf, tough) · few verifications, small metadata.
• State of the art: static CDN repository, signing events through CI (tuf-on-ci, Sigstore root) · no always-on signing server.

Implementation notes

• Count signatures per key id; test with one signature repeated.
• Sign a canonical encoding; the spec leaves the format to implementations, Debug here is a stand-in.
• Keep every released root on the repository (spec §6.2.1) so old clients can walk forward.
• Root and targets keys offline, ideally in a hardware security module; only timestamp (and mirrors) online (spec §6.1). Timestamp expiry short, root long; the operator picks.
• Write client state atomically, after the whole chain verified; read the clock once (spec §5.1).

Pitfalls

• A valid signature on an old file: only version and expiry checks catch it.
• Counting duplicate signatures toward a threshold.
• Withholding new root files freezes clients until the last root expires, no key needed (spec §6.1).
• It covers the delivery path, not the build: pair with reproducible builds and attestations.

Variants and alternatives

In production

• PEP 458 (PyPI): status Accepted; implementation was deferred in 2019 until funding was found; not claimed as deployed.
• Notary v1 implements TUF; best known use Docker Content Trust (README).
• Sigstore's root-signing repository delivers trusted_root.json as a TUF repository, signed by keyholders.
• Uptane: ground-vehicle updates; the standard defines the two repositories and ECU verification levels.

Implementations

Sources

• The Update Framework specification, version 1.0.37. spec
• Samuel, Mathewson, Cappos, Dingledine, Survivable key compromise in software update systems, ACM CCS 2010, pp. 61-72. paper
• Uptane Standard 2.1.0. standard
• PEP 458, Secure PyPI downloads with signed repository metadata. PEP
• Notary README. code
• Sigstore root-signing. code