Secure boot chain

Deep dive

How it works

In: per-stage image with a signed header (version, image hash, next-stage key), ROM-held root key hash, counters · Out: run the next stage or refuse; a PCR value and event log of what ran · State: write-once root hash, per-stage version counters (fuses or tamper-evident storage), PCRs cleared at reset · Cost: one signature check plus one hash pass over the image per stage

1. Root. ROM hashes the stored root public key and compares it with the fused hash; a 32-byte hash uses fewer fuses than a key.
2. Verify. For stage i: check the header signature with the current key, version >= counter[i], and the image hash.
3. Measure. Extend a register: PCR = H(PCR || H(image)). It can only be extended, never set, so a verifier replays the logged digests (TCG TPM 2.0).
4. Hand over. The header carries the next stage's key, so keys differ per stage and rotate without touching ROM.
5. Commit. Raise counters only after the slot fully verifies; earlier risks bricking on a failed update.
6. Fall back. On failure, reset (PCRs clear) and try the other A/B slot, then recovery.

Code

Rust: ed25519-dalek = "2" (direct verify_strict), sha2 = "0.10". Three stages, A/B slots, counters, PCR log.

use ed25519_dalek::{Signature, Signer, SigningKey, VerifyingKey};
use sha2::{Digest, Sha256};

type H = [u8; 32];
fn sha(b: &[u8]) -> H { Sha256::digest(b).into() }
fn extend(pcr: &H, d: &H) -> H { sha(&[&pcr[..], &d[..]].concat()) } // PCR' = H(PCR || H(code))

#[derive(Clone)]
pub struct Stage { pub version: u32, pub image_hash: H, pub next_key: [u8; 32], pub sig: [u8; 64], pub image: Vec<u8> }
impl Stage { fn header(&self) -> Vec<u8> { [&self.version.to_be_bytes()[..], &self.image_hash, &self.next_key].concat() } }
pub struct Slot { pub root_pub: [u8; 32], pub stages: [Stage; 3] }
pub struct Rom { pub root_hash: H, pub min_version: [u32; 3] } // fuses: write-once hash, counters only rise

#[derive(Debug, PartialEq)]
pub enum Fail { RootKey, Signature(usize), Rollback(usize), ImageHash(usize), NoBootableSlot }

fn try_slot(rom: &Rom, s: &Slot) -> Result<(H, Vec<H>), Fail> {
    if sha(&s.root_pub) != rom.root_hash { return Err(Fail::RootKey); }
    let mut key = VerifyingKey::from_bytes(&s.root_pub).map_err(|_| Fail::RootKey)?;
    let (mut pcr, mut log) = ([0u8; 32], vec![]); // PCRs are zero after every reset
    for (i, st) in s.stages.iter().enumerate() {
        key.verify_strict(&st.header(), &Signature::from_bytes(&st.sig)).map_err(|_| Fail::Signature(i))?;
        if st.version < rom.min_version[i] { return Err(Fail::Rollback(i)); }
        let h = sha(&st.image); // the only O(n) step
        if h != st.image_hash { return Err(Fail::ImageHash(i)); }
        pcr = extend(&pcr, &h);
        log.push(h);
        key = VerifyingKey::from_bytes(&st.next_key).map_err(|_| Fail::Signature(i))?;
    }
    Ok((pcr, log))
}

/// A/B: active slot first, then the other. Counters rise only after a full success.
pub fn boot(rom: &mut Rom, slots: &[Slot; 2]) -> Result<(usize, H, Vec<H>), Fail> {
    for (n, s) in slots.iter().enumerate() {
        if let Ok((pcr, log)) = try_slot(rom, s) {
            for i in 0..3 { rom.min_version[i] = rom.min_version[i].max(s.stages[i].version); }
            return Ok((n, pcr, log));
        }
    }
    Err(Fail::NoBootableSlot)
}
pub fn replay(log: &[H]) -> H { log.iter().fold([0u8; 32], |p, d| extend(&p, d)) } // verifier side

pub fn build_slot(keys: &[SigningKey; 3], versions: [u32; 3], images: [Vec<u8>; 3]) -> Slot {
    let mk = |i: usize| {
        let (image, version) = (images[i].clone(), versions[i]);
        let next_key = keys[(i + 1).min(2)].verifying_key().to_bytes();
        let mut st = Stage { version, image_hash: sha(&image), next_key, sig: [0; 64], image };
        st.sig = keys[i].sign(&st.header()).to_bytes(); // offline signing host
        st
    };
    Slot { root_pub: keys[0].verifying_key().to_bytes(), stages: [mk(0), mk(1), mk(2)] }
}

#[cfg(test)]
mod tests {
    use super::*;
    fn imgs(t: u8) -> [Vec<u8>; 3] { [vec![t; 4096], vec![t + 1; 65536], vec![t + 2; 1 << 20]] }
    #[test]
    fn chain() {
        let k = [1u8, 2, 3].map(|s| SigningKey::from_bytes(&[s; 32]));
        let mut rom = Rom { root_hash: sha(&k[0].verifying_key().to_bytes()), min_version: [0; 3] };
        let (a, b) = (build_slot(&k, [2, 2, 2], imgs(10)), build_slot(&k, [2, 2, 2], imgs(10)));
        let (n, pcr, log) = boot(&mut rom, &[a, b]).unwrap();
        assert_eq!((n, rom.min_version), (0, [2, 2, 2]));
        assert_eq!(pcr, replay(&log)); // PCR reproducible from the event log
        let mut bad = build_slot(&k, [3, 3, 3], imgs(20));
        bad.stages[2].image[100] ^= 1; // tampered kernel
        assert_eq!(try_slot(&rom, &bad).err(), Some(Fail::ImageHash(2)));
        let good = build_slot(&k, [3, 3, 3], imgs(20));
        assert_eq!(boot(&mut rom, &[bad, good]).unwrap().0, 1); // slot B fallback
        let old = build_slot(&k, [2, 3, 3], imgs(30)); // stage 0 below its counter
        assert_eq!(try_slot(&rom, &old).err(), Some(Fail::Rollback(0)));
        let also_old = build_slot(&k, [2, 2, 2], imgs(30));
        assert_eq!(boot(&mut rom, &[old, also_old]).err(), Some(Fail::NoBootableSlot));
    }
}

Complexity and constants

• Per stage: one Ed25519 verification, independent of image size, plus one SHA-256 pass over the image: O(n).
• Measured on an Apple M-series Mac, release build, sha2 0.10.9 defaults: verify_strict 22 µs (1 MB image) and 27 µs (16 MB); SHA-256 about 2.0 ms/MB (1.94 ms for 1 MB, 32.4 ms for 16 MB). Hashing dominates above roughly 12 KB.
• Cost drivers: bytes read from flash and fuse bits; checking happens once per boot.

Efficiency

• Cost: the 1.1 MB test chain (4 KB + 64 KB + 1 MB) is about 2 ms of hashing plus 3 signature checks (about 75 µs), measured on a Mac, not a boot ROM. Bound: flash read bandwidth, then SHA throughput.
• Levers:
  • Sign a hash, not the image — signature work stays about 25 µs (measured above) — always.
  • Verify lazily with a hash tree (dm-verity; AVB hashtree descriptors hold its root hash) — only blocks actually read are hashed (AVB README) — large read-only partitions.
  • Hardware SHA-256 instructions or a crypto block — several times portable code (order of) — MCUs and SoCs that have it.
  • Check the counter before hashing — a rolled-back image is rejected without reading it — any chain.
• Naive → standard → state of the art:
  • Naive · hash the whole rootfs every boot, seconds on a large partition
  • Standard · sign headers, hash the small boot stages, verify the root filesystem lazily
  • State of the art · hardware hash, lazy tree verification, generation-number revocation instead of a hash denylist

Implementation notes

• Copy the image into RAM first, verify that copy, run that copy; verifying flash then executing flash allows content to change in between.
• Sign the version inside the header so a stage cannot be relabelled to pass the counter.
• Keep signing keys in an HSM; the device holds only public keys.
• Seal disk keys to PCR values with key sealing so a modified chain gets no keys.

Pitfalls

• Unrevoked vulnerable bootloader: a flawed signed bootloader boots until denied. The 2020 GRUB2 flaw (CVE-2020-10713, "BootHole") showed that revoking by image hash does not scale, which led to SBAT generation numbers in shim.
• Downgrade: old signed images pass signature checks; only a counter stops them.
• Counter raised before the image proves good bricks on a failed update; never raised, rollback stays possible.
• Verified but not measured: a user-enrolled key or disabled check stays invisible to a remote party.

Variants and alternatives

In production

• PCs and servers: UEFI Secure Boot (PK, KEK, db, dbx); Microsoft requires a KEK entry so it can add allowed or known-bad images (Microsoft docs). Linux: shim with MOK and SBAT.
• Phones: Android Verified Boot (vbmeta, rollback indexes, chained partitions, A/B); Apple Boot ROM → iBoot → kernel.
• Microcontrollers: MCUboot, swap, overwrite or direct-xip upgrades, test and revert.

Implementations

Sources

• Android Open Source Project, Android Verified Boot 2.0 (libavb README). doc
• MCUboot, Design. doc · code
• Microsoft, Secure boot, Windows hardware design. doc
• rhboot, UEFI shim bootloader secure boot life-cycle improvements (SBAT). doc · code
• The Chromium Projects, Verified Boot. doc
• Apple, Apple Platform Security: Secure boot. doc
• Josefsson, Liusvaara, Edwards-Curve Digital Signature Algorithm (EdDSA), RFC 8032, 2017. rfc
• UEFI Forum, UEFI Specification 2.10, section 32 Secure Boot and Driver Signing; Trusted Computing Group, TPM 2.0 Library Specification (PCR extend). No link.