rhdl_dsig_scalable_core/verify/

mod.rs

//! The DSig verifier: checks signatures at the rate the signer makes them.
//!
#![doc = include_str!("../../docs/verifier.md")]
//!
//! # Record layout
//!
//! One record = [`RECORD_BYTES`] = 1,664 bytes = 26 beats of 64 bytes.
//!
//! | Bytes | Field | Beat |
//! |---|---|---|
//! | 0..64 | batch commitment ([`crate::certificate`]) | 0 |
//! | 64..128 | Ed25519 signature `R ‖ S` | 1 |
//! | 128..130 | key index, little endian | 2 |
//! | 130..162 | `pk_hash` | 2 |
//! | 162..178 | `pk_nonce` | 2 |
//! | 178..194 | message `nonce` | 2–3 |
//! | 194..418 | 7 Merkle siblings × 32 bytes, bottom up | 3–6 |
//! | 418..1642 | 68 chain nodes × 18 bytes | 6–25 |
//! | 1642..1658 | the 16-byte message | 25 |
//! | 1658..1664 | zero | 25 |
//!
//! The first 1,642 bytes are exactly [`DsigSignature::to_bytes`](crate::reference::DsigSignature::to_bytes).
//!
//! # Verdicts
//!
//! The verifier writes one byte per record, in record order. Bit 7
//! ([`VERDICT_WRITTEN`]) is always set, so a zero byte means "never
//! written". A record is valid exactly when its byte is [`VERDICT_VALID`].
//!
//! | Bit | Name | Set when |
//! |---|---|---|
//! | 0 | [`VERDICT_FORMAT`] | commitment header bytes 0..16 are not `DSIGFP01`, profile 1, batch 128, or the key index is 128 or more |
//! | 1 | [`VERDICT_MERKLE`] | the Merkle climb from `pk_hash` (with the index's low 7 bits) misses the commitment's root |
//! | 2 | [`VERDICT_CHAINS`] | the commitment of the 68 chain ends is not `pk_hash` |
//! | 3 | [`VERDICT_CERT`] | strict Ed25519 verification of the certificate fails |
//! | 7 | [`VERDICT_WRITTEN`] | always |
//!
//! [`expected_verdict`] computes the same byte in software. The card run
//! checks every byte against it, and [`expected_verdict`] itself is tested
//! against [`DsigSignature::verify`](crate::reference::DsigSignature::verify): valid ⇔ the reference
//! accepts.
//!
//! # Neighbours
//!
//! * [`crate::reference`] is the scheme; [`expected_verdict`] is built on it.
//! * [`crate::chain_lane`] and [`crate::blake3_core`] are the hash lanes the
//!   unit reuses.
//! * The planner's `DsigVerify` component (feature `planner`) prices this
//!   block for the chip planner and TUI.

pub mod certs;
pub mod chains;
pub mod datapath;
pub mod engine;
pub mod hasher;
pub mod unit;

use ed25519_dalek::VerifyingKey;

use crate::certificate::{DOMAIN, PROFILE_ID};
use crate::reference::{
    DsigSignature, SIGNATURE_WIRE_BYTES, WotsSignature, root_from_proof,
};
use crate::{BATCH_KEYS, MERKLE_HEIGHT};

/// Bytes of one verifier input record: the wire signature, the message and
/// zero bytes up to a whole beat (profile 1: 16-byte message, 1,664 bytes,
/// 26 beats; profile 2: 64-byte message, 1,728 bytes, 27 beats).
pub const RECORD_BYTES: usize = (SIGNATURE_WIRE_BYTES + MESSAGE_BYTES).div_ceil(64) * 64;
/// HBM beats per record (64 bytes each).
pub const RECORD_BEATS: usize = RECORD_BYTES / 64;
/// Offset of the message inside a record (right after the signature).
pub const MESSAGE_OFFSET: usize = SIGNATURE_WIRE_BYTES;
/// Bytes of the signed message (`DSIG_MESSAGE_BYTES`; see [`PROFILE_ID`]).
pub const MESSAGE_BYTES: usize = crate::MESSAGE_BYTES;

const _: () = assert!(RECORD_BEATS * 64 == RECORD_BYTES);
const _: () = assert!(MESSAGE_OFFSET + MESSAGE_BYTES <= RECORD_BYTES);

/// Verdict bit 0: malformed commitment header or key index ≥ 128.
pub const VERDICT_FORMAT: u8 = 1;
/// Verdict bit 1: the Merkle path does not lead to the commitment's root.
pub const VERDICT_MERKLE: u8 = 2;
/// Verdict bit 2: the chain ends do not commit to `pk_hash`.
pub const VERDICT_CHAINS: u8 = 4;
/// Verdict bit 3: the Ed25519 certificate does not verify.
pub const VERDICT_CERT: u8 = 8;
/// Verdict bit 7: set on every written verdict.
pub const VERDICT_WRITTEN: u8 = 0x80;
/// The byte of a valid signature.
pub const VERDICT_VALID: u8 = VERDICT_WRITTEN;

/// The 16 header bytes every well-formed commitment starts with:
/// `DSIGFP01`, profile 1 and batch size 128, little endian.
#[must_use]
pub fn commitment_header() -> [u8; 16] {
    let mut header = [0; 16];
    header[..8].copy_from_slice(&DOMAIN);
    header[8..12].copy_from_slice(&PROFILE_ID.to_le_bytes());
    header[12..16].copy_from_slice(&(BATCH_KEYS as u32).to_le_bytes());
    header
}

/// Builds one input record from a wire signature and its message.
#[must_use]
pub fn record(signature: &[u8; SIGNATURE_WIRE_BYTES], message: &[u8; MESSAGE_BYTES]) -> [u8; RECORD_BYTES] {
    let mut bytes = [0; RECORD_BYTES];
    bytes[..SIGNATURE_WIRE_BYTES].copy_from_slice(signature);
    bytes[MESSAGE_OFFSET..MESSAGE_OFFSET + MESSAGE_BYTES].copy_from_slice(message);
    bytes
}

/// The verdict byte the hardware must write for `record`, given the trusted
/// Ed25519 key.
///
/// Each check runs on the raw bytes, independently of the others, exactly
/// as the hardware does: a bad key index still gets its Merkle and chain
/// checks (with the index's low 7 bits), and a bad header still gets its
/// certificate checked. Only the combination matters for validity, but the
/// byte pins down every bit, so the card run is checked bit for bit.
#[must_use]
pub fn expected_verdict(record: &[u8; RECORD_BYTES], trusted: &VerifyingKey) -> u8 {
    let mut verdict = VERDICT_WRITTEN;
    // Format: the header and the key index.
    let index = u16::from_le_bytes([record[128], record[129]]);
    if record[..16] != commitment_header() || usize::from(index) >= BATCH_KEYS {
        verdict |= VERDICT_FORMAT;
    }
    // Merkle: climb from pk_hash with the index's low 7 bits.
    let pk_hash: [u8; 32] = record[130..162].try_into().expect("32 bytes");
    let mut proof = [[0; 32]; MERKLE_HEIGHT];
    for (i, sibling) in proof.iter_mut().enumerate() {
        sibling.copy_from_slice(&record[194 + 32 * i..226 + 32 * i]);
    }
    let root = root_from_proof(pk_hash, usize::from(index) & (BATCH_KEYS - 1), &proof).expect("index < 128");
    if root[..] != record[32..64] {
        verdict |= VERDICT_MERKLE;
    }
    // Chains: walk every node to its end and commit.
    let mut elements = [[0; crate::ELEMENT_BYTES]; crate::CHAINS];
    for (i, element) in elements.iter_mut().enumerate() {
        element.copy_from_slice(&record[418 + 18 * i..436 + 18 * i]);
    }
    let wots = WotsSignature {
        public: crate::reference::KeyPublic {
            pk_hash,
            pk_nonce: record[162..178].try_into().expect("16 bytes"),
        },
        nonce: record[178..194].try_into().expect("16 bytes"),
        elements,
    };
    if !wots.verify_hash_component(&record[MESSAGE_OFFSET..MESSAGE_OFFSET + MESSAGE_BYTES]) {
        verdict |= VERDICT_CHAINS;
    }
    // Certificate: strict Ed25519 over the 64 commitment bytes as they are.
    let signature = ed25519_dalek::Signature::from_bytes(record[64..128].try_into().expect("64 bytes"));
    if trusted.verify_strict(&record[..64], &signature).is_err() {
        verdict |= VERDICT_CERT;
    }
    verdict
}

/// Whether the reference verifier accepts the record's signature for its
/// message. Used to check that [`expected_verdict`] means the same thing.
#[must_use]
pub fn reference_accepts(record: &[u8; RECORD_BYTES], trusted: &VerifyingKey) -> bool {
    DsigSignature::from_bytes(&record[..SIGNATURE_WIRE_BYTES])
        .is_some_and(|signature| signature.verify(&record[MESSAGE_OFFSET..MESSAGE_OFFSET + MESSAGE_BYTES], trusted))
}

/// Checks the oracle against the reference on valid and tampered records.
#[cfg(test)]
mod tests {
    use super::*;
    use crate::reference::PreparedBatch;
    use ed25519_dalek::SigningKey;

    /// One batch of real signatures, each tampered in every field class.
    #[test]
    fn oracle_matches_reference_on_valid_and_tampered_records() {
        let signer = SigningKey::from_bytes(&[0x11; 32]);
        let trusted = signer.verifying_key();
        let mut batch = PreparedBatch::new([0x42; 32], 7, 9, &signer);
        let mut checked = 0;
        for index in 0..8_usize {
            let message = [index as u8; MESSAGE_BYTES];
            let signature = batch.sign(index, &message).expect("fresh key");
            let good = record(&signature.to_bytes(), &message);
            assert_eq!(expected_verdict(&good, &trusted), VERDICT_VALID);
            assert!(reference_accepts(&good, &trusted));
            // Flip one bit in each region: header, root, Ed25519, index,
            // pk_hash, pk_nonce, nonce, a sibling, a chain node, the message.
            for (offset, bit) in [
                (3, VERDICT_FORMAT | VERDICT_CERT),
                (40, VERDICT_MERKLE | VERDICT_CERT),
                (100, VERDICT_CERT),
                (129, VERDICT_FORMAT),
                (140, 0),
                (170, VERDICT_CHAINS),
                (180, VERDICT_CHAINS),
                (300, VERDICT_MERKLE),
                (1000, VERDICT_CHAINS),
                (1650, VERDICT_CHAINS),
            ] {
                let mut bad = good;
                bad[offset] ^= 0x40;
                let verdict = expected_verdict(&bad, &trusted);
                assert_ne!(verdict, VERDICT_VALID, "offset {offset}");
                assert!(!reference_accepts(&bad, &trusted), "offset {offset}");
                if bit != 0 {
                    assert_eq!(verdict & bit, bit, "offset {offset}: {verdict:#04x}");
                }
                checked += 1;
            }
        }
        assert_eq!(checked, 80);
    }
}