ic_cipher/
gf.rs

1//! Constant-time GF(2^8) arithmetic for AES.
2//!
3//! The AES S-box is computed *algebraically* rather than read from a lookup
4//! table:
5//!
6//! ```text
7//! S(x)    = A · x^-1  ⊕ 0x63       (inversion, then the affine map)
8//! S^-1(y) = (A^-1 · y ⊕ 0x05)^-1
9//! ```
10//!
11//! with `x^-1 = x^254` evaluated by square-and-multiply over the Rijndael
12//! field. Every operation is a branch-free bitwise sequence, so no secret ever
13//! reaches an address bus. That closes the cache-timing channel that table-based
14//! AES (the default in many portable C implementations) leaves open, at the cost
15//! of throughput — see the crate docs for the backend roadmap.
16
17/// The Rijndael reduction polynomial, x^8 + x^4 + x^3 + x + 1, low byte.
18const MODULUS: u8 = 0x1b;
19
20/// Constant-time multiplication in GF(2^8).
21#[inline(always)]
22pub const fn mul(mut a: u8, mut b: u8) -> u8 {
23    let mut p: u8 = 0;
24    let mut i = 0;
25    while i < 8 {
26        // Add `a` into the accumulator iff the low bit of `b` is set.
27        p ^= a & (b & 1).wrapping_neg();
28        // xtime(a): shift left, reduce iff the high bit was set.
29        let hi = (a >> 7) & 1;
30        a <<= 1;
31        a ^= MODULUS & hi.wrapping_neg();
32        b >>= 1;
33        i += 1;
34    }
35    p
36}
37
38/// `x * 2` in GF(2^8), the AES `xtime` operation.
39#[inline(always)]
40pub const fn xtime(a: u8) -> u8 {
41    let hi = (a >> 7) & 1;
42    (a << 1) ^ (MODULUS & hi.wrapping_neg())
43}
44
45/// Multiplicative inverse in GF(2^8), with `inv(0) == 0`.
46///
47/// Computed as `x^254` via the square-and-multiply chain for `0b1111_1110`,
48/// which is 7 squarings and 6 multiplications, all constant-time.
49#[inline(always)]
50pub const fn inv(x: u8) -> u8 {
51    let mut r = x;
52    let mut bit = 6i32;
53    // Exponent 254 = 0b11111110; the leading 1 is the initial `r = x`.
54    while bit >= 0 {
55        r = mul(r, r);
56        if bit > 0 {
57            r = mul(r, x);
58        }
59        bit -= 1;
60    }
61    r
62}
63
64/// The AES forward S-box, computed in constant time.
65#[inline(always)]
66pub const fn sbox(x: u8) -> u8 {
67    let y = inv(x);
68    y ^ y.rotate_left(1) ^ y.rotate_left(2) ^ y.rotate_left(3) ^ y.rotate_left(4) ^ 0x63
69}
70
71/// The AES inverse S-box, computed in constant time.
72#[inline(always)]
73pub const fn inv_sbox(y: u8) -> u8 {
74    let t = y.rotate_left(1) ^ y.rotate_left(3) ^ y.rotate_left(6) ^ 0x05;
75    inv(t)
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    /// The published FIPS 197 S-box, used only to validate the algebraic
83    /// construction. The library itself never indexes this table.
84    const SBOX_REFERENCE: [u8; 256] = [
85        0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab,
86        0x76, 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4,
87        0x72, 0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71,
88        0xd8, 0x31, 0x15, 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2,
89        0xeb, 0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6,
90        0xb3, 0x29, 0xe3, 0x2f, 0x84, 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb,
91        0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45,
92        0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
93        0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44,
94        0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a,
95        0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 0xe0, 0x32, 0x3a, 0x0a, 0x49,
96        0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d,
97        0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 0xba, 0x78, 0x25,
98        0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e,
99        0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 0xe1,
100        0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
101        0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb,
102        0x16,
103    ];
104
105    #[test]
106    fn algebraic_sbox_matches_fips197() {
107        for x in 0..=255u8 {
108            assert_eq!(sbox(x), SBOX_REFERENCE[x as usize], "S({x:#04x})");
109        }
110    }
111
112    #[test]
113    fn inverse_sbox_undoes_sbox() {
114        for x in 0..=255u8 {
115            assert_eq!(inv_sbox(sbox(x)), x, "S^-1(S({x:#04x}))");
116        }
117    }
118
119    #[test]
120    fn field_inversion_is_correct() {
121        assert_eq!(inv(0), 0);
122        for x in 1..=255u8 {
123            assert_eq!(mul(x, inv(x)), 1, "x * x^-1 for {x:#04x}");
124        }
125    }
126
127    #[test]
128    fn xtime_matches_multiplication_by_two() {
129        for x in 0..=255u8 {
130            assert_eq!(xtime(x), mul(x, 2));
131        }
132    }
133}
ic_cipher/gf.rs

ic_cipher/
gf.rs
