binary_ff1/ff1.rs
1use cipher::{
2 generic_array::{typenum::U16, ArrayLength, GenericArray},
3 BlockEncrypt,
4};
5
6use crate::{Error, Limbs, Prf};
7
8/// A struct for performing FF1 encryption in radix 2.
9///
10/// The block cipher must have a 16 byte block size and should be AES-128,
11/// AES-192, or AES-256.
12pub struct BinaryFF1<'a, C: BlockEncrypt> {
13 limbs: Limbs<'a>,
14 prf: Prf<'a, C>,
15 s_len: usize,
16}
17
18impl<'a, C> BinaryFF1<'a, C>
19where
20 C: BlockEncrypt<BlockSize = U16>,
21 C::ParBlocks: ArrayLength<GenericArray<u8, U16>>,
22{
23 /// Creates an [`BinaryFF1`] instance for a given block cipher, input
24 /// length, and tweak. The scratch buffer must be at least `len + 1`
25 /// bytes.
26 ///
27 /// # Errors
28 ///
29 /// Returns [`Error::ScratchTooSmall`] if the scratch buffer is too small.
30 ///
31 /// # Examples
32 ///
33 /// ```rust
34 /// # use aes::{
35 /// # cipher::{generic_array::GenericArray, NewBlockCipher},
36 /// # Aes256,
37 /// # };
38 /// # use binary_ff1::{BinaryFF1, Error};
39 /// #
40 /// # let cipher = Aes256::new(GenericArray::from_slice(&[0; 32]));
41 /// # let tweak = [];
42 /// let mut scratch = vec![0; 128];
43 ///
44 /// assert!(BinaryFF1::new(&cipher, 126, &tweak, &mut scratch).is_ok());
45 /// assert!(BinaryFF1::new(&cipher, 127, &tweak, &mut scratch).is_ok());
46 ///
47 /// // Scratch buffer must be at least len + 1 bytes
48 /// assert_eq!(
49 /// BinaryFF1::new(&cipher, 128, &tweak, &mut scratch).err(),
50 /// Some(Error::ScratchTooSmall)
51 /// );
52 /// ```
53 pub fn new(
54 cipher: &'a C,
55 len: usize,
56 tweak: &[u8],
57 scratch: &'a mut [u8],
58 ) -> Result<Self, Error> {
59 // For an odd-numbered input length, the integers are not on byte boundaries.
60 // For example, an 11 byte input contains two 44-bit integers. We work
61 // around this by loading them into a scratch buffer, performing the
62 // encryption algorithm, and storing them back into the output buffer.
63 let limbs = Limbs::new(len, scratch)?;
64
65 let num_bits = (len * 8) as u32;
66 let tweak_len = tweak.len() as u32;
67
68 // 4. Let d = 4 * ceil(b / 4) + 4
69 let s_len = ((limbs.limb_len + 3) & !3) + 4;
70
71 // This can be precomputed so we only do one AES block encryption, rather than
72 // computing and encrypting it every time the user calls encrypt.
73 let mut block = [0; 16];
74 // 5. Let P =
75 block[0] = 1; // [1]^1
76 block[1] = 2; // [2]^1
77 block[2] = 1; // [1]^1
78 block[5] = 2; // [radix]^3
79 block[6] = 10; // [10]^1
80 block[7] = (num_bits / 2) as u8; // [u mod 256]^1
81 block[8..12].copy_from_slice(&num_bits.to_be_bytes()); // [n]^4
82 block[12..].copy_from_slice(&tweak_len.to_be_bytes()); // [t]^4
83
84 let mut prf = Prf::new(cipher);
85 prf.write(&block);
86 // The specification recomputes the entirety of Q in each Feistel round, but the
87 // beginning of Q can be precomputed here. If the tweak spans multiple
88 // blocks, this will also save us a few AES block encryptions.
89 prf.write(tweak);
90 // The specification defines this as [0]^((-t-b-1) mod 16). It is used to pad
91 // the input to the PRF function to a multiple of the block size (16
92 // bytes).
93 prf.seek(!(tweak.len() + limbs.limb_len) & 15);
94
95 Ok(Self { limbs, prf, s_len })
96 }
97
98 /// Encrypts the given plaintext.
99 ///
100 /// # Errors
101 ///
102 /// Returns [`Error::InvalidInputLength`] if the length of `x` is not the
103 /// same as the input length defined in this [`BinaryFF1`] structure.
104 pub fn encrypt(&mut self, x: &mut [u8]) -> Result<(), Error> {
105 self.limbs.load(x)?;
106
107 for i in 0..10 {
108 // This is equivalent to Step 6viii and 6ix in the specification, where A and B
109 // are swapped at the end of each Feistel round.
110 let (x_a, x_b) = if i % 2 == 0 {
111 (&mut self.limbs.upper, &self.limbs.lower)
112 } else {
113 (&mut self.limbs.lower, &self.limbs.upper)
114 };
115
116 // This is the remainder of Q. It is specific to a given Feistel round of a
117 // given plaintext, so we cannot precompute it.
118 let mut prf = self.prf;
119 prf.write(&[i]);
120 prf.write(x_b.buf);
121
122 // generate_s will panic if an incomplete block has been written to the PRF,
123 // i.e. the input was not a multiple of the block size. This cannot
124 // happen here because the PRF input was padded in the constructor.
125 x_a.add_s(prf.generate_s(self.s_len));
126 }
127
128 self.limbs.store(x).unwrap();
129 Ok(())
130 }
131
132 /// Decrypts the given ciphertext.
133 ///
134 /// # Errors
135 ///
136 /// Returns [`Error::InvalidInputLength`] if the length of `x` is not the
137 /// same as the input length defined in this [`BinaryFF1`] structure.
138 pub fn decrypt(&mut self, x: &mut [u8]) -> Result<(), Error> {
139 self.limbs.load(x)?;
140
141 // This is the inverse of our encryption routine: we iterate backwards, and
142 // subtract instead of adding.
143 for i in (0..10).rev() {
144 let (x_a, x_b) = if i % 2 == 0 {
145 (&mut self.limbs.upper, &self.limbs.lower)
146 } else {
147 (&mut self.limbs.lower, &self.limbs.upper)
148 };
149
150 let mut prf = self.prf;
151 prf.write(&[i]);
152 prf.write(x_b.buf);
153
154 x_a.sub_s(prf.generate_s(self.s_len));
155 }
156
157 self.limbs.store(x).unwrap();
158 Ok(())
159 }
160}
161
162#[cfg(test)]
163mod tests {
164 use super::BinaryFF1;
165
166 use aes::{
167 cipher::{generic_array::GenericArray, NewBlockCipher},
168 Aes256,
169 };
170
171 use lazy_static::lazy_static;
172 use quickcheck::TestResult;
173 use quickcheck_macros::quickcheck;
174
175 lazy_static! {
176 static ref CIPHER: Aes256 = {
177 const KEY: [u8; 32] = [
178 0xF9, 0xE8, 0x38, 0x9F, 0x5B, 0x80, 0x71, 0x2E, 0x38, 0x86, 0xCC, 0x1F, 0xA2, 0xD2,
179 0x8A, 0x3B, 0x8C, 0x9C, 0xD8, 0x8A, 0x2D, 0x4A, 0x54, 0xC6, 0xAA, 0x86, 0xCE, 0x0F,
180 0xEF, 0x94, 0x4B, 0xE0,
181 ];
182 Aes256::new(GenericArray::from_slice(&KEY))
183 };
184 }
185
186 macro_rules! a_then_b {
187 ($tweak:ident, $x:ident, $a:ident, $b:ident) => {{
188 let mut scratch = vec![0; $x.len() + 1];
189 let mut ff1 = BinaryFF1::new(&*CIPHER, $x.len(), &$tweak, &mut scratch).unwrap();
190
191 let mut output = $x.clone();
192 ff1.$a(&mut output).unwrap();
193 ff1.$b(&mut output).unwrap();
194
195 TestResult::from_bool(output == $x)
196 }};
197 }
198
199 /// Test that a [`BinaryFF1`] instance can encrypt and decrypt a plaintext.
200 #[quickcheck]
201 fn encrypt_then_decrypt(tweak: Vec<u8>, x: Vec<u8>) -> TestResult {
202 a_then_b!(tweak, x, encrypt, decrypt)
203 }
204
205 /// Test that a [`BinaryFF1`] instance can decrypt and encrypt a ciphertext.
206 #[quickcheck]
207 fn decrypt_then_encrypt(tweak: Vec<u8>, x: Vec<u8>) -> TestResult {
208 a_then_b!(tweak, x, decrypt, encrypt)
209 }
210
211 /// Test that a [`BinaryFF1`] instance can be used to encrypt multiple
212 /// plaintexts of the same length.
213 ///
214 /// This ensures that we do not mutate the instance in a way that affects
215 /// future encryption operations.
216 #[quickcheck]
217 fn encrypt_reuse_multiple_plaintexts(tweak: Vec<u8>, x1: Vec<u8>, x2: Vec<u8>) -> TestResult {
218 if x1.len() != x2.len() || x1 == x2 {
219 return TestResult::discard();
220 }
221
222 let len = x1.len();
223 let mut scratch = vec![0; len + 1];
224 let mut ff1 = BinaryFF1::new(&*CIPHER, len, &tweak, &mut scratch).unwrap();
225
226 let mut encrypt = |x: &[u8]| {
227 let mut output = x.to_vec();
228 ff1.encrypt(&mut output).unwrap();
229 output
230 };
231
232 // Test two different plaintexts to ensure that the instance does not become
233 // plaintext-specific.
234 let expected_1 = encrypt(&x1);
235 let expected_2 = encrypt(&x2);
236
237 if expected_1 == expected_2 {
238 return TestResult::failed();
239 }
240
241 TestResult::from_bool(
242 (0..10).all(|_| encrypt(&x1) == expected_1 && encrypt(&x2) == expected_2),
243 )
244 }
245}