small_order.rs

//! Known small-order Ed25519 public-key encodings.
//!
//! ZIP-215 verification accepts these encodings. A signature under one of
//! them can verify for every message. The table matches libsodium's
//! `ge25519_has_small_order` list: compare the first 31 bytes exactly and
//! the last byte with the sign bit cleared.

/// Canonical encodings of the Ed25519 8-torsion (sign bit already clear).
///
/// Source: libsodium `ge25519_has_small_order` (ref10).
const SMALL_ORDER_ENCODINGS: [[u8; 32]; 7] = [
    [0x00; 32],
    [
        0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00,
    ],
    [
        0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98,
        0xf0, 0xd5, 0xdf, 0xac, 0x05, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x02, 0x88, 0x6d, 0x53,
        0xfc, 0x05,
    ],
    [
        0xc7, 0x17, 0x6a, 0x70, 0x3d, 0x4d, 0xd8, 0x4f, 0xba, 0x3c, 0x0b, 0x76, 0x0d, 0x10, 0x67,
        0x0f, 0x2a, 0x20, 0x53, 0xfa, 0x2c, 0x39, 0xcc, 0xc6, 0x4e, 0xc7, 0xfd, 0x77, 0x92, 0xac,
        0x03, 0x7a,
    ],
    [
        0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0x7f,
    ],
    [
        0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0x7f,
    ],
    [
        0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0x7f,
    ],
];

/// True when `bytes` is a 32-byte small-order Ed25519 encoding, including the
/// sign-bit twin of each table row.
pub fn is_small_order_ed25519_encoding(bytes: &[u8]) -> bool {
    let Some((last, prefix)) = bytes.split_last() else {
        return false;
    };
    if prefix.len() != 31 {
        return false;
    }
    SMALL_ORDER_ENCODINGS.iter().any(|banned| {
        let Some((banned_last, banned_prefix)) = banned.split_last() else {
            return false;
        };
        banned_prefix == prefix && *banned_last == (last & 0x7f)
    })
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn rejects_identity_and_sign_bit_twin() {
        assert!(is_small_order_ed25519_encoding(&[0u8; 32]));
        let mut sign_bit_identity = [0u8; 32];
        sign_bit_identity[31] = 0x80;
        assert!(is_small_order_ed25519_encoding(&sign_bit_identity));
    }

    #[test]
    fn rejects_every_canonical_row_and_its_sign_bit() {
        for row in SMALL_ORDER_ENCODINGS {
            assert!(is_small_order_ed25519_encoding(&row));
            let mut twin = row;
            twin[31] |= 0x80;
            assert!(is_small_order_ed25519_encoding(&twin));
        }
    }

    #[test]
    fn accepts_an_ordinary_32_byte_key() {
        assert!(!is_small_order_ed25519_encoding(&[1u8; 32]));
    }

    #[test]
    fn ignores_non_32_byte_encodings() {
        assert!(!is_small_order_ed25519_encoding(&[0u8; 31]));
        assert!(!is_small_order_ed25519_encoding(&[0u8; 33]));
    }
}