SnarkVM ECDSA and Serialization Instructions

Description. Unlike Pedersen/Bowe-Hopwood-Pedersen hashes, which are well-defined for sequences of bits, the new hash functions like, Keccak, are only defined on byte sequences*. This leaves the question: what are the desired semantics when hashing a sequence of bits, which is not a multiple of 8? The proposed implementation does this by padding with zero bits up to the next byte boundary. The result is that the hash of a bit sequence is the same as the hash of the same bit sequence padded with zero bits up to the next byte boundary, e.g.

hash([]) = hash([0])

The result is that these hash functions are not collision-resistant (over bit sequences) and as a result, different values of different types with different sizes can produce the same digest when using the raw encoding. This is unexpected behavior: users expect that for raw encoding, types of the same size may produce the same sequence of serialized bits, however, it is unexpected that different types of different sizes, serializing to different bit sequences under raw encoding, can produce the same digest. A concrete example demonstrates the severity: a 33-bit Vote struct can collide with a 34-bit Send struct:

struct Vote {
    choice: u32,    // who to vote for
    is_final: bool  // can this vote be updated?
}

struct Send {
    approval: bool, // approval required from controller?
    fast: bool,     // fast transfer?
    dst: u32,       // index of dst account
}

Signing Vote { vote: 4, is_final: true } produces the bit sequence:

0100000000000000000000000000000 | 1 | 0000000

This is identical to Send { approval: false, fast: true, dst: 2 }:

0 | 1 | 0000000000000000000000000000010 | 000000

A signature on one type can be replayed as a valid signature for a completely different message type.

Impact. Developers may assume that different-sized types are automatically domain-separated, leading to signature replay attacks and hash collisions across different message types. This is especially dangerous when structs contain boolean flags or when protocol versions introduce new message formats. This affects the following instructions:

• hash.keccak256.raw
• hash.keccak384.raw
• hash.keccak512.raw
• hash.keccak256.native.raw
• hash.keccak384.native.raw
• hash.keccak512.native.raw
• hash.sha3_256.raw
• hash.sha3_384.raw
• hash.sha3_512.raw
• hash.sha3_256.native.raw
• hash.sha3_384.native.raw
• hash.sha3_512.native.raw

Recommendation. Implement a check that rejects inputs whose bit length is not a multiple of 8 (i.e., not byte-aligned). We believe this is the most reasonable behavior: Keccak hashes of bit sequences not a multiple of 8 bits are not well-defined. By rejecting these inputs as “not in the domain of Keccak”, developers are forced to explicitly handle padding, making the collision risk explicit and requiring them to make a deliberate choice about how to handle padding.

Description. The sign.verify.raw instruction for the native signature scheme suffers a similar zero-bit padding issue as the hash functions, except here the padding is applied to the last field element (instead of the last byte).

The serialization path leads to ToFieldsRaw implementation:

impl<N: Network> ToFieldsRaw for Plaintext<N> {
    /// Returns this plaintext as a list of field elements using the raw bits.
    fn to_fields_raw(&self) -> Result<Vec<Self::Field>> {
        // Encode the data as little-endian bits without variant or identifier bits.
        let bits_le = self.to_bits_raw_le();
        // Pack the bits into field elements.
        let fields = bits_le
            .chunks(Field::<N>::size_in_data_bits())
            .map(Field::<N>::from_bits_le)
            .collect::<Result<Vec<_>>>()?;
        // Ensure the number of field elements does not exceed the maximum allowed size.
        match fields.len() <= N::MAX_DATA_SIZE_IN_FIELDS as usize {
            true => Ok(fields),
            false => bail!("Plaintext exceeds maximum allowed size"),
        }
    }
}

The last field element is padded with zero bits when the bit length is not a multiple of the field element size. This allows signatures created for one message to verify against a different message that differs only in trailing zero bits within the padding region.

Impact. Similar to the hash collision issue, this enables signature replay attacks across different message types that align to the same field element boundaries after padding. An attacker can reuse a signature from one context in a different context with a structurally different but padding-equivalent message.

Recommendation. Consider whether a .raw version of the native signature scheme is necessary in the first place, as it introduces significant potential for security issues. If retained, implement domain separation for the raw version or apply a similar multiple-of-field-size validation as recommended for hash functions to make padding explicit.

Description. The sign function creates signatures that are not unforgeable in the general case due to potential hash collisions for variable-length messages:

/// Returns a signature on a `message` using the given `signing_key` and hash function.
pub fn sign<H: Hash<Output = Vec<bool>>>(
    signing_key: &SigningKey,
    hasher: &H,
    message: &[H::Input],
) -> Result<Self> {
    // Hash the message.
    let hash_bits = hasher.hash(message)?;
    // Convert the hash output to bytes.
    let hash_bytes = bytes_from_bits_le(&hash_bits);

    // Sign the prehashed message.
    signing_key
        .sign_prehash(&hash_bytes)
        .map(|(signature, recovery_id)| {
            let recovery_id = RecoveryID { recovery_id, chain_id: None };
            Self { signature, recovery_id }
        })
        .map_err(|e| anyhow!("Failed to sign message: {e:?}"))
}

The issue occurs because hash functions like the Bool hasher Keccak256 may have collisions for different-length messages. For example:

sigma = sign(sk, Keccak256, [0, 0, 1, 1])

This signature can be verified against a different message:

verify(vk, Keccak256, sigma, [0, 0, 1, 1, 0, 0, 0, 0])

Impact. An attacker could exploit the hash collisions across structs of different sizes to produce valid signatures on structures without possessing the signing key. This allows signature replay attacks where a signature on one message is reused to validate a different message that hashes to the same value.

Recommendation. Ensure the hash function includes message length in its domain separation or use a collision-resistant encoding that prevents different-length messages from hashing to the same value. Consider encoding the message length as part of the hash input.

Description. The execute_deserialize_internal function resizes the input bit array to match the destination type size without checking whether truncation occurs:

fn execute_deserialize_internal<A: circuit::Aleo<Network = N>, N: Network, F>(
    variant: u8,
    bits: &[circuit::Boolean<A>],
    destination_type: &PlaintextType<N>,
    get_struct: &F,
    depth: usize,
) -> Result<circuit::Plaintext<A>>
where
    F: Fn(&Identifier<N>) -> Result<StructType<N>>,
{
    use snarkvm_circuit::{Inject, traits::FromBits};

    // Ensure that the depth is within the maximum limit.
    if depth > A::Network::MAX_DATA_DEPTH {
        bail!("Plaintext depth exceeds maximum limit: {}", N::MAX_DATA_DEPTH)
    }

    // A helper to get the number of bits needed.
    let get_size_in_bits = |plaintext_type: &PlaintextType<N>| -> Result<usize> {
        match DeserializeVariant::from_u8(variant) {
            DeserializeVariant::FromBits => plaintext_type.plaintext_size_in_bits(get_struct),
            DeserializeVariant::FromBitsRaw => plaintext_type.plaintext_size_in_raw_bits(get_struct),
        }
    };

    // Get the number of bits needed.
    let num_bits = get_size_in_bits(destination_type)?;

    // Resize the bits to the appropriate length.
    let mut bits = bits.to_vec();
    bits.resize(num_bits, circuit::Boolean::<A>::constant(false));

The code does not check whether bits.len() <= num_bits before resizing, meaning excess bits are silently discarded when the input is longer than the destination type. This behavior deviates from the intended design, which is to allow padding but not truncation: for instance, promoting 32 bits to a 64-bit integer, should set the top-most bits to zero, but deserializing 64 bits into a 32-bit integer should return an error.

Impact. If the end user is not careful, the current implementation can allow a signature/hash on a longer bit message to be used as a signature on a shorter struct: by first verifying the validity / authenticity of a message of bits, which is then implicitly truncated during deserialization.

Recommendation. Add a length check: allow padding when bits.len() <= num_bits, but return an error when bits.len() > num_bits to match the intended behavior.

Description. The native signature scheme lacks domain separation between messages signed using native Aleo serialization (for instance, the signed requests used to authorize function calls) and messages signed using raw encoding. This can allow confusion between different message formats when the same signing key is used for both native and raw signatures. When signing a message that has been serialized using Aleo’s native serialization format, the resulting signature could potentially be valid for a different message that encodes to the same sequence of field elements when using raw encoding. This occurs because there is no cryptographic distinction in the signing process to indicate whether the message was intended to be interpreted as native-serialized data or raw bytes.

This issue only applies to the native (Schnorr) signature scheme, since the others are not otherwise used within Aleo itself.

Impact. The scope of the impact depends heavily on the applications that a user might use, but it could include:

• A user is tricked into signing a request authorizing the transfer of Aleo credits: a user is presented with a message representing a struct, the UI parses this struct in one way, however, the field serialized struct can also be parsed as a valid request.

• Conversely, a signed request, obtained by, e.g. a SNARK outsourcing service, can be used as a message which is raw encoded assuming the sizes (approximately) match; such that the message results in the same number of field elements being signed.

Recommendation. We recommend avoiding any potential for unexpected interaction / footguns between applications built on Aleo and Aleo itself. This can be achieved by adding domain separation between the native signatures used as part of Aleo and any messages signed as part of other applications. For instance, this can be implemented by using another initial state of the Poseidon sponge when sampling the challenge in the Schnorr signature.

Description. Multiple FromStr/FromBytes implementations do not validate that the entire input string is consumed during parsing. This means that adding junk to the encodings also deserializes successfully. For instance ECDSASignature and CircuitVerifyingKey:

impl FromStr for ECDSASignature {
    type Err = Error;

    /// Parses a hex-encoded string into an ECDSASignature.
    fn from_str(signature: &str) -> Result<Self, Self::Err> {
        let mut s = signature.trim();

        // Accept optional 0x prefix
        if let Some(rest) = s.strip_prefix("0x").or_else(|| s.strip_prefix("0X")) {
            s = rest;
        }

        // Decode the hex string into bytes.
        let bytes = hex::decode(s)?;

        // Construct the signature from the bytes.
        Self::from_bytes_le(&bytes)
     }
}

This occurs because the default from_bytes_le implementation treats the byte slice as a reader without checking for EOF:

pub trait FromBytes {
    /// Reads `Self` from `reader` as little-endian bytes.
    fn read_le<R: Read>(reader: R) -> IoResult<Self>
    where
        Self: Sized;

    /// Returns `Self` from a byte array in little-endian order.
    fn from_bytes_le(bytes: &[u8]) -> anyhow::Result<Self>
    where
        Self: Sized,
    {
        Ok(Self::read_le(bytes)?)
    }
}

As a result, any additional bytes appended to a valid signature hex string are silently ignored during parsing. This is expected behavior for read_le as it can be used to parse a sequence of objects from a reader, one after another, however from_bytes_le is given a slice and does not indicate the number of bytes consumed.

This issue is also present for verification keys:

impl<E: PairingEngine> FromStr for CircuitVerifyingKey<E> {
    type Err = anyhow::Error;

    #[inline]
    fn from_str(vk_hex: &str) -> Result<Self, Self::Err> {
        Self::from_bytes_le(&hex::decode(vk_hex)?)
    }
}

Which means that any verification key followed by junk will still be parsed successfully.

A similar issue is present in the deserializing of, for instance, native signatures from bech32:

impl<N: Network> FromStr for Signature<N> {
    type Err = Error;

    /// Reads in the signature string.
    fn from_str(signature: &str) -> Result<Self, Self::Err> {
        // Decode the signature string from bech32m.
        let (hrp, data, variant) = bech32::decode(signature)?;
        if hrp != SIGNATURE_PREFIX {
            bail!("Failed to decode signature: '{hrp}' is an invalid prefix")
        } else if data.is_empty() {
            bail!("Failed to decode signature: data field is empty")
        } else if variant != bech32::Variant::Bech32m {
            bail!("Found an signature that is not bech32m encoded: {signature}");
        }
        // Decode the signature data from u5 to u8, and into the signature.
        Ok(Self::read_le(&Vec::from_base32(&data)?[..])?)
    }
}

Meaning that any verification key followed by junk will still be parsed successfully.

Recommendation. Add a length check to ensure the input contains exactly the expected number of bytes, for instance, by replacing the existing default implementation of from_bytes_le with a version that checks that all the bytes of the slice have been consumed, e.g.

pub trait FromBytes {
    /// Reads `Self` from `reader` as little-endian bytes.
    fn read_le<R: Read>(reader: R) -> IoResult<Self>
    where
        Self: Sized;

    /// Returns `Self` from a byte array in little-endian order.
    fn from_bytes_le(bytes: &[u8]) -> anyhow::Result<Self>
    where
        Self: Sized,
    {
        use std::io::Cursor;
        let mut buf = Cursor::new(bytes);
        let value = Self::read_le(&mut buf)?;
        if buf.position() != bytes.len() as u64 {
            Err(anyhow::anyhow!("Unexpected trailing bytes"))
        } else {
            Ok(value)
        }
    }
}

And then use from_bytes_le consistently throughout the codebase, in place of read_le(Vec::from(..)) as done in e.g.

impl<N: Network> FromStr for Ciphertext<N> {
    type Err = Error;

    /// Reads in the ciphertext string.
    fn from_str(ciphertext: &str) -> Result<Self, Self::Err> {
        // Decode the ciphertext string from bech32m.
        let (hrp, data, variant) = bech32::decode(ciphertext)?;
        if hrp != CIPHERTEXT_PREFIX {
            bail!("Failed to decode ciphertext: '{hrp}' is an invalid prefix")
        } else if data.is_empty() {
            bail!("Failed to decode ciphertext: data field is empty")
        } else if variant != bech32::Variant::Bech32m {
            bail!("Found an ciphertext that is not bech32m encoded: {ciphertext}");
        }
        // Decode the ciphertext data from u5 to u8, and into the ciphertext.
        Ok(Self::read_le(&Vec::from_base32(&data)?[..])?)
    }
}