vitaminc_permutation/
bitwise.rs

1use crate::{elementwise::permute_array, PermutationKey};
2use std::num::{NonZeroU128, NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8};
3use zeroize::{Zeroize, Zeroizing};
4
5// TODO: Make this a private trait
6// FIXME: This trait is backwards - self should be T and the argument should be a key
7pub trait BitwisePermute<const N: usize, T> {
8    fn bitwise_permute(&self, input: T) -> T;
9}
10
11macro_rules! impl_bitwise_permutable {
12    ($N:literal, $int_type:ty, $array_size:expr) => {
13        impl BitwisePermute<$N, $int_type> for PermutationKey<$N> {
14            fn bitwise_permute(&self, mut input: $int_type) -> $int_type {
15                // Unpack the input into one byte per bit (MSB-first), permute
16                // the bit-vector through the constant-time `permute_array`
17                // primitive, then re-pack. The previous implementation used
18                // `bitvec::get_unchecked(secret_index)` which performs a
19                // secret-dependent bit load; even though the bit array fits in
20                // a single cache line, this defends against intra-cache-line
21                // microarchitectural leaks (port pressure, etc.).
22                let bytes = Zeroizing::new(input.to_be_bytes());
23                let mut bits: Zeroizing<[u8; $N]> = Zeroizing::new([0u8; $N]);
24                for j in 0..$N {
25                    bits[j] = (bytes[j / 8] >> (7 - (j % 8))) & 1;
26                }
27                let permuted = Zeroizing::new(permute_array(self, *bits));
28                let mut out = [0u8; $array_size];
29                for j in 0..$N {
30                    out[j / 8] |= (permuted[j] & 1) << (7 - (j % 8));
31                }
32                input.zeroize();
33                <$int_type>::from_be_bytes(out)
34            }
35        }
36    };
37}
38
39impl_bitwise_permutable!(8, u8, 1);
40impl_bitwise_permutable!(16, u16, 2);
41impl_bitwise_permutable!(32, u32, 4);
42impl_bitwise_permutable!(64, u64, 8);
43impl_bitwise_permutable!(128, u128, 16);
44
45macro_rules! impl_nonzeroint_bitwise_permutable {
46    ($N:literal, $nonzero_type:ty) => {
47        impl BitwisePermute<$N, $nonzero_type> for PermutationKey<$N> {
48            fn bitwise_permute(&self, mut input: $nonzero_type) -> $nonzero_type {
49                let out = self.bitwise_permute(input.get());
50                input.zeroize();
51                // If the input is NonZero, the output will be NonZero
52                unsafe { <$nonzero_type>::new_unchecked(out) }
53            }
54        }
55    };
56}
57
58impl_nonzeroint_bitwise_permutable!(8, NonZeroU8);
59impl_nonzeroint_bitwise_permutable!(16, NonZeroU16);
60impl_nonzeroint_bitwise_permutable!(32, NonZeroU32);
61impl_nonzeroint_bitwise_permutable!(64, NonZeroU64);
62impl_nonzeroint_bitwise_permutable!(128, NonZeroU128);
63
64#[cfg(test)]
65mod tests {
66    use std::fmt::Debug;
67    use std::num::{NonZeroU128, NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8};
68
69    use crate::private::IsPermutable;
70    use crate::tests;
71    use crate::{BitwisePermute, PermutationKey};
72    use zeroize::Zeroize;
73
74    fn test_permute<const N: usize, T>(input: T)
75    where
76        // FIXME: These trait bounds are pretty clunky
77        T: Zeroize + Debug + PartialEq + Copy,
78        PermutationKey<N>: BitwisePermute<N, T>,
79        [u8; N]: IsPermutable,
80    {
81        let key = tests::gen_key([0; 32]);
82        let output = key.bitwise_permute(input);
83        assert_ne!(output, input);
84    }
85
86    #[test]
87    fn bitwise_permute_case() {
88        test_permute::<8, u8>(117);
89        test_permute::<16, u16>(46321);
90        test_permute::<32, u32>(87483343);
91        test_permute::<64, u64>(2813387843809117391);
92        test_permute::<128, u128>(28133878438091173912256);
93
94        test_permute::<8, _>(NonZeroU8::new(77).unwrap());
95        test_permute::<16, _>(NonZeroU16::new(13267).unwrap());
96        test_permute::<32, _>(NonZeroU32::new(12345678).unwrap());
97        test_permute::<64, _>(NonZeroU64::new(7178231783183).unwrap());
98        test_permute::<128, _>(NonZeroU128::new(29472929298731313).unwrap());
99    }
100
101    // Zero in -> zero out, for every supported width.
102    // Catches sign/endian bugs in the unpack/repack glue: any path that
103    // accidentally introduces a stray bit would fail here.
104    #[test]
105    fn bitwise_permute_zero_in_zero_out() {
106        assert_eq!(tests::gen_key::<8>([0; 32]).bitwise_permute(0u8), 0);
107        assert_eq!(tests::gen_key::<16>([0; 32]).bitwise_permute(0u16), 0);
108        assert_eq!(tests::gen_key::<32>([0; 32]).bitwise_permute(0u32), 0);
109        assert_eq!(tests::gen_key::<64>([0; 32]).bitwise_permute(0u64), 0);
110        assert_eq!(tests::gen_key::<128>([0; 32]).bitwise_permute(0u128), 0);
111    }
112
113    // All-ones is a fixed point of every bit permutation (every bit position
114    // already holds a 1, so permuting positions can't change anything).
115    // Catches missing-bit bugs at the high or low boundary of each width.
116    #[test]
117    fn bitwise_permute_all_ones_invariant() {
118        assert_eq!(
119            tests::gen_key::<8>([0; 32]).bitwise_permute(u8::MAX),
120            u8::MAX
121        );
122        assert_eq!(
123            tests::gen_key::<16>([0; 32]).bitwise_permute(u16::MAX),
124            u16::MAX
125        );
126        assert_eq!(
127            tests::gen_key::<32>([0; 32]).bitwise_permute(u32::MAX),
128            u32::MAX
129        );
130        assert_eq!(
131            tests::gen_key::<64>([0; 32]).bitwise_permute(u64::MAX),
132            u64::MAX
133        );
134        assert_eq!(
135            tests::gen_key::<128>([0; 32]).bitwise_permute(u128::MAX),
136            u128::MAX
137        );
138    }
139
140    // Hamming weight (popcount) must be preserved — a permutation moves bits
141    // but neither creates nor destroys them. This is the strongest single
142    // property check available for the bit-shuffle glue: any bug that drops,
143    // duplicates, or mis-positions a bit will change the count. As a
144    // corollary, this is also what justifies the `unsafe new_unchecked` in
145    // the NonZero impls: popcount > 0 in -> popcount > 0 out.
146    #[test]
147    fn bitwise_permute_preserves_hamming_weight() {
148        let key8 = tests::gen_key::<8>([0; 32]);
149        for n in [0u8, 1, 0x80, 0x55, 0xaa, 0xff] {
150            assert_eq!(key8.bitwise_permute(n).count_ones(), n.count_ones());
151        }
152
153        let key32 = tests::gen_key::<32>([0; 32]);
154        for n in [0u32, 1, 0x8000_0000, 0xcafe_babe, 0x1234_5678, u32::MAX] {
155            assert_eq!(key32.bitwise_permute(n).count_ones(), n.count_ones());
156        }
157
158        let key128 = tests::gen_key::<128>([0; 32]);
159        for n in [
160            0u128,
161            1,
162            1 << 127,
163            0x0123_4567_89ab_cdef_fedc_ba98_7654_3210,
164            u128::MAX,
165        ] {
166            assert_eq!(key128.bitwise_permute(n).count_ones(), n.count_ones());
167        }
168    }
169
170    // Same key + same input must produce the same output. Cheap guard against
171    // any future change that accidentally introduces nondeterminism (e.g. a
172    // hash-seed in the permute path, or branching on uninitialised memory
173    // that happens to read consistent values in test but not in production).
174    #[test]
175    fn bitwise_permute_is_deterministic() {
176        let key_a = tests::gen_key::<64>([7; 32]);
177        let key_b = tests::gen_key::<64>([7; 32]);
178        let input = 0xcafe_babe_dead_beefu64;
179        assert_eq!(key_a.bitwise_permute(input), key_b.bitwise_permute(input));
180    }
181}
vitaminc_permutation/bitwise.rs

vitaminc_permutation/
bitwise.rs
