hashsigs_reference/

lib.rs

//! Auditable software oracle for the two `HashSigs` RHDL cryptographic profiles.
//!
//! The implementation follows pinned `HashSigsRS` commit
//! `2d315dd4168804b7cbc51c51a1bf7ca27bf74140`. It intentionally models only
//! the non-Solana WOTS+ primitive. It is suitable for test-vector generation,
//! differential tests, and checking hardware behavior; it has not been audited
//! as a production cryptographic library.
//!
//! # Security boundary
//!
//! - A private WOTS key may sign **one message only**. Key reuse can enable
//!   forgeries. Signing APIs consume private-key values, but durable one-time
//!   use remains the caller's responsibility.
//! - Inputs are already-hashed 32-byte messages. Applications must define their
//!   own collision-resistant, domain-separated prehash.
//! - `HashSigsRS` uses shared masks and a simplified address construction. It is
//!   not RFC 8391 XMSS, FIPS 205 SLH-DSA, or a many-time signature scheme.
//! - [`LegacyKeccak`] uses legacy Keccak-256 padding and is byte-compatible with
//!   upstream. [`HashSigsSha256GenericV1`] is a distinct, incompatible profile.
#![forbid(unsafe_code)]

use core::marker::PhantomData;

pub use hashsigs_types::{
    CHAIN_COUNT, CHAIN_STEPS, CHECKSUM_DIGITS, FUSED_OUTPUT_BYTES, HASH_BYTES,
    HashSigsSha256GenericV1, LegacyKeccak, LengthError, MASK_COUNT, MESSAGE_BYTES, MESSAGE_DIGITS,
    MessageDigest, PRF_INPUT_BYTES, ParseProfileIdError, PrivateKey, PrivateSeed, Profile,
    ProfileId, PublicKey, SIGNATURE_BYTES, Signature, WINTERNITZ_W,
};
use sha2::Digest as _;

/// A 32-byte hash value used internally by the WOTS construction.
pub type HashValue = [u8; HASH_BYTES];

/// Hash behavior associated with one supported reference profile.
///
/// This trait extends the sealed [`Profile`] trait, so only profiles defined by
/// `hashsigs-types` can implement it.
pub trait ReferenceProfile: Profile {
    /// Hashes one complete software-oracle input according to this profile.
    ///
    /// Hardware designs may split this operation into compression or
    /// permutation jobs, but their final digest must match this function.
    #[doc(hidden)]
    fn hash(input: &[u8]) -> HashValue;
}

impl ReferenceProfile for LegacyKeccak {
    fn hash(input: &[u8]) -> HashValue {
        let mut hasher = sha3::Keccak256::new();
        hasher.update(input);
        hasher.finalize().into()
    }
}

impl ReferenceProfile for HashSigsSha256GenericV1 {
    fn hash(input: &[u8]) -> HashValue {
        let mut hasher = sha2::Sha256::new();
        hasher.update(input);
        hasher.finalize().into()
    }
}

/// A generated public/private key pair for one WOTS signing operation.
///
/// The private key is non-cloneable and consumed by [`Wots::sign`] or a fused
/// operation. Persisting or reconstructing its raw bytes requires explicit
/// action and moves one-time-use enforcement outside this API.
#[derive(Debug)]
pub struct KeyPair<P: ReferenceProfile> {
    /// Public verification key.
    pub public_key: PublicKey<P>,
    /// One-time private signing key.
    pub private_key: PrivateKey<P>,
}

/// Output produced by a constant-work fused sign-and-public-key operation.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct FusedOutput<P: ReferenceProfile> {
    /// Public key derived from the same private key used for this signature.
    pub public_key: PublicKey<P>,
    /// Signature captured while every chain is advanced to its endpoint.
    pub signature: Signature<P>,
}

/// Stateless `HashSigsRS` WOTS+ reference implementation for profile `P`.
///
/// `Wots<LegacyKeccak>` and `Wots<HashSigsSha256GenericV1>` have different key
/// and signature types. The following accidental cross-profile verification is
/// rejected at compile time:
///
/// ```compile_fail
/// use hashsigs_reference::{
///     HashSigsSha256GenericV1, LegacyKeccak, MessageDigest, PublicKey, Signature,
///     Wots, CHAIN_COUNT,
/// };
///
/// let key = PublicKey::<LegacyKeccak>::new([0; 32], [0; 32]);
/// let signature = Signature::<HashSigsSha256GenericV1>::new([[0; 32]; CHAIN_COUNT]);
/// let message = MessageDigest::new([0; 32]);
/// Wots::<LegacyKeccak>::new().verify(&key, &message, &signature);
/// ```
///
/// Serialized keys and signatures have no in-band profile tag. A protocol that
/// handles bytes must authenticate [`Profile::ID`] separately.
#[derive(Clone, Copy, Debug)]
pub struct Wots<P: ReferenceProfile> {
    profile: PhantomData<fn() -> P>,
}

/// Byte-compatible oracle for the pinned `HashSigsRS` Keccak construction.
pub type LegacyKeccakWots = Wots<LegacyKeccak>;

/// Oracle for the incompatible SHA-256 generic performance profile.
pub type Sha256GenericWots = Wots<HashSigsSha256GenericV1>;

impl<P: ReferenceProfile> Default for Wots<P> {
    fn default() -> Self {
        Self::new()
    }
}

impl<P: ReferenceProfile> Wots<P> {
    /// Constructs a stateless software oracle.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            profile: PhantomData,
        }
    }

    /// Returns the cryptographic profile implemented by this oracle.
    #[must_use]
    pub const fn profile_id(&self) -> ProfileId {
        P::ID
    }

    /// Applies the `HashSigsRS` domain-separated PRF.
    ///
    /// The exact preimage is `0x03 || seed || u16_be(index)`, totaling 35
    /// bytes. The two-byte index is big-endian, matching pinned upstream code.
    #[must_use]
    pub fn prf(&self, seed: &HashValue, index: u16) -> HashValue {
        let mut input = [0_u8; PRF_INPUT_BYTES];
        input[0] = 0x03;
        input[1..=HASH_BYTES].copy_from_slice(seed);
        input[1 + HASH_BYTES..].copy_from_slice(&index.to_be_bytes());
        hash::<P>(&input)
    }

    /// Derives all randomization masks that can affect a result.
    ///
    /// Pinned upstream allocates 67 PRF results. Its function key is mask zero;
    /// signing and key generation start every chain at index zero and perform at
    /// most 15 transitions; verification starts at a message digit and ends at
    /// index 15. Consequently every observable access is in `0..=15`, and
    /// upstream masks 16 through 66 are provably unreachable. Computing exactly
    /// these 16 entries preserves every key, signature, and verification result.
    #[must_use]
    pub fn randomization_masks(&self, public_seed: &HashValue) -> [HashValue; MASK_COUNT] {
        #[allow(clippy::cast_possible_truncation)]
        core::array::from_fn(|index| self.prf(public_seed, index as u16))
    }

    /// Converts a 32-byte message digest to 64 base-16 digits plus checksum.
    ///
    /// Each byte contributes its high nibble followed by its low nibble. The
    /// checksum is `sum(15 - digit)` and is appended as three big-endian base-16
    /// digits, including leading zeroes.
    #[must_use]
    pub fn message_chain_indexes(&self, message: &MessageDigest) -> [u8; CHAIN_COUNT] {
        let mut indexes = [0_u8; CHAIN_COUNT];

        for (index, byte) in message.as_bytes().iter().copied().enumerate() {
            indexes[index * 2] = byte >> 4;
            indexes[index * 2 + 1] = byte & 0x0F;
        }

        let checksum: u16 = indexes[..MESSAGE_DIGITS]
            .iter()
            .map(|digit| u16::from(15 - digit))
            .sum();
        for (output, shift) in indexes[MESSAGE_DIGITS..].iter_mut().zip([8_u32, 4, 0]) {
            #[allow(clippy::cast_possible_truncation)]
            let digit = ((checksum >> shift) & 0x0F) as u8;
            *output = digit;
        }

        indexes
    }

    /// Derives a one-time private key by hashing a caller-supplied seed once.
    ///
    /// The seed is consumed to discourage accidental derivation of the same key
    /// for multiple signing calls.
    #[must_use]
    pub fn private_key_from_seed(&self, private_seed: PrivateSeed<P>) -> PrivateKey<P> {
        PrivateKey::new(hash::<P>(&private_seed.into_secret()))
    }

    /// Derives a public key from a one-time private key.
    ///
    /// This computes all 67 complete, 15-transition chains and hashes their
    /// concatenated endpoints. The private key is borrowed so callers can derive
    /// the public key before consuming it in exactly one signing operation.
    #[must_use]
    pub fn public_key_from_private_key(&self, private_key: &PrivateKey<P>) -> PublicKey<P> {
        let public_seed = self.prf(private_key.expose_secret(), 0);
        self.public_key_from_private_key_and_seed(private_key.expose_secret(), public_seed)
    }

    /// Generates a public/private WOTS key pair from a one-time seed.
    #[must_use]
    pub fn generate_key_pair(&self, private_seed: PrivateSeed<P>) -> KeyPair<P> {
        let private_key = self.private_key_from_seed(private_seed);
        let public_key = self.public_key_from_private_key(&private_key);
        KeyPair {
            public_key,
            private_key,
        }
    }

    /// Signs one 32-byte message digest and consumes the one-time private key.
    ///
    /// This compatibility-oriented path stops each chain at its message digit,
    /// so its amount of hash work depends on the public message. Use
    /// [`Self::sign_and_public_key_from_private_key`] for the fixed-work fused
    /// hardware oracle.
    #[must_use]
    pub fn sign(&self, private_key: PrivateKey<P>, message: &MessageDigest) -> Signature<P> {
        self.sign_from_private_key_bytes(&private_key.into_secret(), message)
    }

    /// Verifies a typed signature against a typed public key and message digest.
    ///
    /// Profile mismatches are compile-time type errors. The final public-key hash
    /// comparison examines every byte before returning.
    #[must_use]
    pub fn verify(
        &self,
        public_key: &PublicKey<P>,
        message: &MessageDigest,
        signature: &Signature<P>,
    ) -> bool {
        let masks = self.randomization_masks(public_key.public_seed());
        let indexes = self.message_chain_indexes(message);
        let mut endpoints = [0_u8; SIGNATURE_BYTES];

        for (chain_index, ((signature_segment, digit), endpoint)) in signature
            .segments()
            .iter()
            .zip(indexes.iter().copied())
            .zip(endpoints.chunks_exact_mut(HASH_BYTES))
            .enumerate()
        {
            debug_assert!(chain_index < CHAIN_COUNT);
            let value = advance_chain::<P>(signature_segment, &masks, digit, 15 - digit);
            endpoint.copy_from_slice(&value);
        }

        let computed = hash::<P>(&endpoints);
        constant_time_eq(&computed, public_key.public_key_hash())
    }

    /// Parses and verifies untrusted serialized inputs.
    ///
    /// Wrong-length message, public-key, or signature values return a
    /// [`LengthError`]. Correctly sized but corrupted values return `Ok(false)`.
    ///
    /// # Errors
    ///
    /// Returns [`LengthError`] when any input does not have its protocol-defined
    /// fixed length.
    pub fn verify_bytes(
        &self,
        public_key: &[u8],
        message: &[u8],
        signature: &[u8],
    ) -> Result<bool, LengthError> {
        let message = MessageDigest::from_slice(message)?;
        let public_key = PublicKey::<P>::from_slice(public_key)?;
        let signature = Signature::<P>::from_slice(signature)?;
        Ok(self.verify(&public_key, &message, &signature))
    }

    /// Signs and derives the public key in one fixed-work traversal.
    ///
    /// Every one of the 67 chains is advanced through all 15 transitions. The
    /// signature segment is copied when the public message digit is reached,
    /// and the final value becomes the public-key endpoint. No message digit can
    /// skip a hash operation. The private key is consumed to discourage reuse.
    #[must_use]
    pub fn sign_and_public_key_from_private_key(
        &self,
        private_key: PrivateKey<P>,
        message: &MessageDigest,
    ) -> FusedOutput<P> {
        self.fused_from_private_key_bytes(&private_key.into_secret(), message)
    }

    /// Derives a private key, signs, and derives its public key at fixed work.
    ///
    /// The seed is hashed once and then every chain performs all 15 transitions.
    /// For `LEGACY_KECCAK` this costs exactly 1,173 Keccak-f permutations. For
    /// `HASHSIGS_SHA256_GENERIC_V1` it costs exactly 1,258 SHA-256 compression
    /// blocks. See the corresponding constants in `hashsigs-types` for the full
    /// derivations.
    #[must_use]
    pub fn sign_and_public_key_from_private_seed(
        &self,
        private_seed: PrivateSeed<P>,
        message: &MessageDigest,
    ) -> FusedOutput<P> {
        let private_key = hash::<P>(&private_seed.into_secret());
        self.fused_from_private_key_bytes(&private_key, message)
    }

    fn sign_from_private_key_bytes(
        &self,
        private_key: &HashValue,
        message: &MessageDigest,
    ) -> Signature<P> {
        let public_seed = self.prf(private_key, 0);
        let masks = self.randomization_masks(&public_seed);
        let indexes = self.message_chain_indexes(message);
        let mut signature = [[0_u8; HASH_BYTES]; CHAIN_COUNT];

        for (index, (output, digit)) in signature
            .iter_mut()
            .zip(indexes.iter().copied())
            .enumerate()
        {
            let secret = self.secret_segment(private_key, &masks[0], index);
            *output = advance_chain::<P>(&secret, &masks, 0, digit);
        }

        Signature::new(signature)
    }

    fn public_key_from_private_key_and_seed(
        &self,
        private_key: &HashValue,
        public_seed: HashValue,
    ) -> PublicKey<P> {
        let masks = self.randomization_masks(&public_seed);
        let mut endpoints = [0_u8; SIGNATURE_BYTES];

        for (index, endpoint) in endpoints.chunks_exact_mut(HASH_BYTES).enumerate() {
            let secret = self.secret_segment(private_key, &masks[0], index);
            let value = advance_chain::<P>(&secret, &masks, 0, 15);
            endpoint.copy_from_slice(&value);
        }

        PublicKey::new(public_seed, hash::<P>(&endpoints))
    }

    fn fused_from_private_key_bytes(
        &self,
        private_key: &HashValue,
        message: &MessageDigest,
    ) -> FusedOutput<P> {
        let public_seed = self.prf(private_key, 0);
        let masks = self.randomization_masks(&public_seed);
        let indexes = self.message_chain_indexes(message);
        let mut signature = [[0_u8; HASH_BYTES]; CHAIN_COUNT];
        let mut endpoints = [0_u8; SIGNATURE_BYTES];

        for (index, ((signature_segment, digit), endpoint)) in signature
            .iter_mut()
            .zip(indexes.iter().copied())
            .zip(endpoints.chunks_exact_mut(HASH_BYTES))
            .enumerate()
        {
            let mut state = self.secret_segment(private_key, &masks[0], index);
            if digit == 0 {
                *signature_segment = state;
            }

            // Fixed work: the loop always executes all 15 chain transitions.
            for step in 1_u8..=15 {
                state = hash::<P>(&xor(&state, &masks[usize::from(step)]));
                if step == digit {
                    *signature_segment = state;
                }
            }

            endpoint.copy_from_slice(&state);
        }

        FusedOutput {
            public_key: PublicKey::new(public_seed, hash::<P>(&endpoints)),
            signature: Signature::new(signature),
        }
    }

    fn secret_segment(
        &self,
        private_key: &HashValue,
        function_key: &HashValue,
        chain_index: usize,
    ) -> HashValue {
        let secret_prf = self.prf(
            private_key,
            u16::try_from(chain_index + 1).expect("chain index fits u16"),
        );
        let mut input = [0_u8; HASH_BYTES * 2];
        input[..HASH_BYTES].copy_from_slice(function_key);
        input[HASH_BYTES..].copy_from_slice(&secret_prf);
        hash::<P>(&input)
    }
}

fn hash<P: ReferenceProfile>(input: &[u8]) -> HashValue {
    #[cfg(test)]
    work_audit::record(input.len());
    P::hash(input)
}

fn advance_chain<P: ReferenceProfile>(
    initial: &HashValue,
    masks: &[HashValue; MASK_COUNT],
    start: u8,
    steps: u8,
) -> HashValue {
    debug_assert!(usize::from(start) + usize::from(steps) <= CHAIN_STEPS);
    let mut value = *initial;
    for offset in 1..=steps {
        let mask_index = usize::from(start + offset);
        value = hash::<P>(&xor(&value, &masks[mask_index]));
    }
    value
}

fn xor(left: &HashValue, right: &HashValue) -> HashValue {
    let mut output = [0_u8; HASH_BYTES];
    for ((byte, left), right) in output.iter_mut().zip(left).zip(right) {
        *byte = left ^ right;
    }
    output
}

fn constant_time_eq(left: &HashValue, right: &HashValue) -> bool {
    left.iter()
        .zip(right)
        .fold(0_u8, |difference, (left, right)| {
            difference | (left ^ right)
        })
        == 0
}

#[cfg(test)]
mod work_audit {
    use std::cell::RefCell;

    thread_local! {
        static INPUT_LENGTHS: RefCell<Option<Vec<usize>>> = const { RefCell::new(None) };
    }

    pub fn record(length: usize) {
        INPUT_LENGTHS.with(|lengths| {
            if let Some(lengths) = lengths.borrow_mut().as_mut() {
                lengths.push(length);
            }
        });
    }

    pub fn capture<T>(operation: impl FnOnce() -> T) -> (T, Vec<usize>) {
        INPUT_LENGTHS.with(|lengths| {
            assert!(lengths.borrow().is_none(), "work audit cannot be nested");
            *lengths.borrow_mut() = Some(Vec::new());
        });
        let output = operation();
        let lengths = INPUT_LENGTHS.with(|lengths| {
            lengths
                .borrow_mut()
                .take()
                .expect("work audit must be active")
        });
        (output, lengths)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use hashsigs_types::{
        LEGACY_FUSED_PRIVATE_KEY_KECCAK_PERMUTATIONS,
        LEGACY_FUSED_PRIVATE_SEED_KECCAK_PERMUTATIONS, SHA256_FUSED_PRIVATE_KEY_COMPRESSION_BLOCKS,
        SHA256_FUSED_PRIVATE_SEED_COMPRESSION_BLOCKS,
    };

    #[test]
    fn message_digits_match_upstream_order_and_checksum() {
        let oracle = LegacyKeccakWots::new();
        let zeros = oracle.message_chain_indexes(&MessageDigest::new([0; MESSAGE_BYTES]));
        assert_eq!(&zeros[..MESSAGE_DIGITS], &[0; MESSAGE_DIGITS]);
        assert_eq!(&zeros[MESSAGE_DIGITS..], &[3, 12, 0]);

        let ones = oracle.message_chain_indexes(&MessageDigest::new([0xFF; MESSAGE_BYTES]));
        assert_eq!(&ones[..MESSAGE_DIGITS], &[15; MESSAGE_DIGITS]);
        assert_eq!(&ones[MESSAGE_DIGITS..], &[0, 0, 0]);

        let mut ordered = [0_u8; MESSAGE_BYTES];
        for (index, byte) in ordered.iter_mut().enumerate() {
            *byte = u8::try_from(index).expect("index fits u8");
        }
        let digits = oracle.message_chain_indexes(&MessageDigest::new(ordered));
        assert_eq!(&digits[..8], &[0, 0, 0, 1, 0, 2, 0, 3]);
    }

    #[test]
    fn fused_and_independent_paths_match_for_both_profiles() {
        assert_fused_matches::<LegacyKeccak>();
        assert_fused_matches::<HashSigsSha256GenericV1>();
    }

    fn assert_fused_matches<P: ReferenceProfile>() {
        let oracle = Wots::<P>::new();
        let key_bytes = [0xA7; HASH_BYTES];
        let message = MessageDigest::new(core::array::from_fn(|index| {
            u8::try_from(index * 7).expect("test value fits u8")
        }));
        let public_key = oracle.public_key_from_private_key(&PrivateKey::new(key_bytes));
        let signature = oracle.sign(PrivateKey::new(key_bytes), &message);
        let fused =
            oracle.sign_and_public_key_from_private_key(PrivateKey::new(key_bytes), &message);
        assert_eq!(fused.public_key.to_bytes(), public_key.to_bytes());
        assert_eq!(fused.signature.to_bytes(), signature.to_bytes());
        assert!(oracle.verify(&fused.public_key, &message, &fused.signature));
    }

    #[test]
    fn fused_work_counts_match_architecture_contract() {
        let message = MessageDigest::new([0x39; MESSAGE_BYTES]);

        let keccak = LegacyKeccakWots::new();
        let (_, lengths) = work_audit::capture(|| {
            keccak
                .sign_and_public_key_from_private_key(PrivateKey::new([0x11; HASH_BYTES]), &message)
        });
        let permutations: usize = lengths.iter().map(|length| length / 136 + 1).sum();
        assert_eq!(permutations, LEGACY_FUSED_PRIVATE_KEY_KECCAK_PERMUTATIONS);

        let (_, lengths) = work_audit::capture(|| {
            keccak.sign_and_public_key_from_private_seed(
                PrivateSeed::new([0x11; HASH_BYTES]),
                &message,
            )
        });
        let permutations: usize = lengths.iter().map(|length| length / 136 + 1).sum();
        assert_eq!(permutations, LEGACY_FUSED_PRIVATE_SEED_KECCAK_PERMUTATIONS);

        let sha = Sha256GenericWots::new();
        let (_, lengths) = work_audit::capture(|| {
            sha.sign_and_public_key_from_private_key(PrivateKey::new([0x11; HASH_BYTES]), &message)
        });
        let compression_blocks: usize =
            lengths.iter().map(|length| (length + 9).div_ceil(64)).sum();
        assert_eq!(
            compression_blocks,
            SHA256_FUSED_PRIVATE_KEY_COMPRESSION_BLOCKS
        );

        let (_, lengths) = work_audit::capture(|| {
            sha.sign_and_public_key_from_private_seed(
                PrivateSeed::new([0x11; HASH_BYTES]),
                &message,
            )
        });
        let compression_blocks: usize =
            lengths.iter().map(|length| (length + 9).div_ceil(64)).sum();
        assert_eq!(
            compression_blocks,
            SHA256_FUSED_PRIVATE_SEED_COMPRESSION_BLOCKS
        );
    }

    #[test]
    fn malformed_and_corrupted_serialized_inputs_are_distinct() {
        let oracle = LegacyKeccakWots::new();
        let message = MessageDigest::new([0x42; MESSAGE_BYTES]);
        let fused = oracle
            .sign_and_public_key_from_private_key(PrivateKey::new([0x17; HASH_BYTES]), &message);
        let public_key = fused.public_key.to_bytes();
        let signature = fused.signature.to_bytes();

        assert!(matches!(
            oracle.verify_bytes(&public_key[..63], message.as_bytes(), &signature),
            Err(error) if error.expected() == hashsigs_types::PUBLIC_KEY_BYTES
        ));
        assert!(
            oracle
                .verify_bytes(&public_key, &message.as_bytes()[..31], &signature)
                .is_err()
        );
        assert!(
            oracle
                .verify_bytes(&public_key, message.as_bytes(), &signature[..2_143])
                .is_err()
        );

        let mut corrupted_signature = signature;
        corrupted_signature[777] ^= 0x80;
        assert_eq!(
            oracle.verify_bytes(&public_key, message.as_bytes(), &corrupted_signature),
            Ok(false)
        );

        let mut corrupted_key = public_key;
        corrupted_key[63] ^= 1;
        assert_eq!(
            oracle.verify_bytes(&corrupted_key, message.as_bytes(), &signature),
            Ok(false)
        );

        let mut corrupted_message = message.into_bytes();
        corrupted_message[0] ^= 1;
        assert_eq!(
            oracle.verify_bytes(&public_key, &corrupted_message, &signature),
            Ok(false)
        );
    }

    #[test]
    fn profiles_are_cryptographically_distinct() {
        let message = MessageDigest::new([0xCC; MESSAGE_BYTES]);
        let legacy = LegacyKeccakWots::new()
            .sign_and_public_key_from_private_key(PrivateKey::new([0x55; HASH_BYTES]), &message);
        let sha = Sha256GenericWots::new()
            .sign_and_public_key_from_private_key(PrivateKey::new([0x55; HASH_BYTES]), &message);
        assert_ne!(legacy.public_key.to_bytes(), sha.public_key.to_bytes());
        assert_ne!(legacy.signature.to_bytes(), sha.signature.to_bytes());
    }
}