plonky2-crypto-gadgets/src/native_gcm.rs
src/native_gcm.rsRaw
1//! For LICENSE check out https://github.com/0xPARC/plonky2-aes/blob/main/LICENSE
2//!
3//! Rust native implementation of [AES-GCM (Galois Counter
4//! Mode)](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf)
5//! having in mind the approach that will be done in-circuit; this means that it
6//! is not written in the most rust idiomatic way, nor memory-efficient, but
7//! simulating the behavior that we will do later inside the circuit.
8//!
9
10use crate::native_aes::{encrypt_block, flatten_state, key_expansion};
11
12// supported tag length
13const TAG_LEN: usize = 128;
14
15/// Section 7.1 from https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf
16pub fn encrypt<const NK: usize, const NB: usize, const NR: usize>(
17 key: &[u8; NK * NB],
18 nonce: &[u8; 12],
19 pt: &[u8], // plaintext
20) -> (Vec<u8>, Vec<u8>)
21where
22 [(); 4 * (NR + 1)]:,
23{
24 let a: &[u8] = &[]; // additional authenticated data // TODO maybe as input
25 let expanded_key: [[u8; 4]; 4 * (NR + 1)] = key_expansion::<NK, NB, NR>(key);
26
27 // 1. CIPH_K
28 let h = encrypt_block::<NR>(&[0u8; 16], &expanded_key);
29 let h = flatten_state(h);
30
31 // 2. J_0
32 let j0: [u8; 16] = if nonce.len() * 8 == 96 {
33 // J_0 = IV || 0^31 || 1
34 let mut out = [0u8; 16];
35 out[..12].copy_from_slice(nonce.as_slice());
36 out[12..16].copy_from_slice(&[0x00, 0x00, 0x00, 0x01]);
37 out
38 } else {
39 panic!("unsuported at initial version; nonce.len()=12 (96 bits)");
40 };
41
42 // 3. C=GCTR()
43 let c = gctr(expanded_key, &inc32(j0), pt);
44
45 // 4. u, v
46 let u: usize = 16 * (c.len() as f64 / 16_f64).ceil() as usize - c.len();
47 let v: usize = 16 * (a.len() as f64 / 16_f64).ceil() as usize - a.len();
48
49 // 5. S = GHASH()
50 let a_len: [u8; 8] = (a.len() * 8).to_be_bytes();
51 let c_len: [u8; 8] = (c.len() * 8).to_be_bytes();
52 let ghash_input = &[
53 a.to_vec(),
54 vec![0u8; v],
55 c.clone(),
56 vec![0u8; u],
57 a_len.to_vec(),
58 c_len.to_vec(),
59 ]
60 .concat();
61 let s = ghash(h, ghash_input);
62
63 // 6. T=MSB(GCTR()))
64 let t = msb_t(TAG_LEN, &gctr(expanded_key, &j0, &s));
65
66 (c, t)
67}
68
69/// GCM-Ctr, Section 6.5, Algorithm 3
70pub(crate) fn gctr<const NR: usize>(
71 key: [[u8; 4]; 4 * (NR + 1)],
72 icb: &[u8; 16],
73 x: &[u8],
74) -> Vec<u8> {
75 if x.is_empty() {
76 return x.to_vec();
77 }
78
79 let n = ((x.len() * 8) as f64 / 128_f64).ceil() as usize;
80
81 let mut y: Vec<Vec<u8>> = vec![];
82 let mut cb_i = *icb;
83 for (i, x_i_raw) in x.chunks(16).enumerate() {
84 if i > 0 {
85 cb_i = inc32(cb_i);
86 }
87
88 let l = x_i_raw.len().min(16);
89 let mut x_i = [0u8; 16];
90 x_i[..l].copy_from_slice(x_i_raw);
91
92 let ciph_cb_i = flatten_state(encrypt_block::<NR>(&cb_i, &key));
93
94 let (y_i, n_bytes) = if i < n && x_i_raw.len() == 16 {
95 (xor_blocks(x_i, ciph_cb_i), 16)
96 } else {
97 // last chunk, might be smaller than 16 bytes
98 let msb_res = msb_t(x_i_raw.len(), ciph_cb_i.as_slice());
99 let l = msb_res.len().min(16);
100 let mut m = [0u8; 16];
101 m[..l].copy_from_slice(&msb_res);
102 (xor_blocks(x_i, m), l)
103 };
104 y.push(y_i[..n_bytes].to_vec());
105 }
106 y.concat()
107}
108
109/// Section 6.4, Algorithm 2
110pub(crate) fn ghash(h: [u8; 16], x: &[u8]) -> [u8; 16] {
111 assert!(x.len().is_multiple_of(16)); // multiple of 128 bits
112 let m = x.len() / 16;
113
114 let mut y = [0u8; 16]; // (128 bits)
115 for i in 0..m {
116 let mut xi = [0u8; 16];
117 xi.clone_from_slice(&x[i * 16..i * 16 + 16]);
118 let y_xi = xor_blocks(y, xi);
119 y = gf_2_128_mul(y_xi, h);
120 }
121 y
122}
123fn xor_blocks(b1: [u8; 16], b2: [u8; 16]) -> [u8; 16] {
124 let mut r = [0u8; 16];
125 for i in 0..16 {
126 r[i] = b1[i] ^ b2[i];
127 }
128 r
129}
130
131/// multiplication of blocks (in GF(2^128)), Algorithm 1, Section 6.3
132pub fn gf_2_128_mul(x: [u8; 16], y: [u8; 16]) -> [u8; 16] {
133 // R = 11100001 || 0^120
134 const R: [u8; 16] = [
135 0xE1, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
136 0x00,
137 ];
138
139 let mut z = [0u8; 16];
140 let mut v = y;
141 for i in 0..128 {
142 dbg!(i);
143 // xi: i-th bit of x
144 let byte_index = i / 8;
145 let bit_index = 7 - (i % 8);
146 let xi = (x[byte_index] >> bit_index) & 1;
147
148 // dbg!(z, v);
149 if xi == 1 {
150 z = xor_blocks(z, v);
151 }
152 // dbg!(&z);
153 let lsb = v[15] & 1;
154 right_shift_one(&mut v);
155 dbg!(lsb == 1);
156 if lsb == 1 {
157 v = xor_blocks(v, R);
158 }
159 }
160 z
161}
162
163// auxiliary version for testing the circuit logic
164pub(crate) fn gf_2_128_mul_circuit_version(
165 x: [[bool; 8]; 16],
166 y: [[bool; 8]; 16],
167) -> [[bool; 8]; 16] {
168 let zero_byte = [false; 8];
169
170 // R: 10000111 || 0^120 (in little-endian)
171 let mut r = [zero_byte; 16];
172 r[0][0] = true;
173 r[0][5] = true;
174 r[0][6] = true;
175 r[0][7] = true;
176
177 let mut z = [zero_byte; 16];
178 let mut v = y;
179 for i in 0..128 {
180 dbg!(i);
181 let byte_index = i / 8;
182 let bit_index = 7 - (i % 8);
183 let xi = x[byte_index][bit_index];
184
185 // set z = if xi==1: z^v, else: z
186 for b in 0..16 {
187 for k in 0..8 {
188 let z_xor_v = z[b][k] ^ v[b][k];
189 z[b][k] = if xi { z_xor_v } else { z[b][k] };
190 }
191 }
192
193 // let lsb = v[15][7].clone();
194 let lsb = v[15][0].clone(); // (little-endian)
195 v = right_shift_one_circuit_version(&v);
196
197 // if lsb==1: v=v^R, else: v
198 for b in 0..16 {
199 for k in 0..8 {
200 let v_xor_r = v[b][k] ^ r[b][k];
201 v[b][k] = if lsb { v_xor_r } else { v[b][k] };
202 }
203 }
204 }
205 z
206}
207// method for debugging
208fn bools_to_u8_le(bits: [bool; 8]) -> u8 {
209 bits.iter()
210 .enumerate()
211 .fold(0u8, |acc, (i, &bit)| if bit { acc | (1 << i) } else { acc })
212}
213fn right_shift_one_circuit_version(v: &[[bool; 8]; 16]) -> [[bool; 8]; 16] {
214 let mut r: [[bool; 8]; 16] = v.clone();
215 let mut carry = false;
216 for i in 0..16 {
217 let current = v[i];
218 let next_carry = current[0];
219 let mut shifted = [false; 8];
220 for j in 0..7 {
221 shifted[j] = current[j + 1];
222 }
223 shifted[7] = carry;
224 r[i] = shifted;
225 carry = next_carry;
226 }
227 r
228}
229
230pub(crate) fn right_shift_one(block: &mut [u8; 16]) {
231 let mut carry = 0u8;
232
233 for byte in block.iter_mut() {
234 let new_carry = *byte & 1;
235 *byte = (*byte >> 1) | (carry << 7);
236 carry = new_carry;
237 }
238}
239
240/// increment the right-most 32 bits of the given block (128 bits). Section 2.
241pub(crate) fn inc32(b: [u8; 16]) -> [u8; 16] {
242 let mut r = b;
243 // counter = last 32bits
244 let counter = u32::from_be_bytes([r[12], r[13], r[14], r[15]]);
245 let incremented = counter.wrapping_add(1);
246 let bytes = incremented.to_be_bytes();
247 r[12..16].copy_from_slice(&bytes);
248 r
249}
250
251/// returns the t left-most (most-significant in BE) bits of the block
252pub(crate) fn msb_t(t_bytes: usize, block: &[u8]) -> Vec<u8> {
253 let t = t_bytes * 8;
254
255 let mut out = Vec::with_capacity(t.div_ceil(8));
256 let mut bits_left = t;
257 for byte in block.iter() {
258 if bits_left == 0 {
259 break;
260 }
261 if bits_left >= 8 {
262 out.push(*byte);
263 bits_left -= 8;
264 } else {
265 // take the top `bits_left` bits of the byte
266 let mask = 0xFFu8 << (8 - bits_left);
267 out.push(byte & mask);
268 break;
269 }
270 }
271 out
272}
273
274#[cfg(test)]
275mod tests {
276 use super::*;
277
278 use aes_gcm::{
279 aead::{Aead, KeyInit},
280 Aes128Gcm, Aes256Gcm, Nonce,
281 };
282 use rand::Rng;
283
284 fn hex_to_array<const N: usize>(h: &str) -> [u8; N] {
285 let bytes = hex::decode(h).unwrap();
286 assert_eq!(bytes.len(), N);
287 let mut r: [u8; N] = [0u8; N];
288 r.copy_from_slice(&bytes);
289 r
290 }
291
292 #[test]
293 fn test_aes_gcm_encrypt_nist_vector() {
294 // https://csrc.nist.gov/Projects/Cryptographic-Algorithm-Validation-Program/CAVP-TESTING-BLOCK-CIPHER-MODES
295
296 // test vector from line 7
297 let key: [u8; 16] = hex_to_array("cf063a34d4a9a76c2c86787d3f96db71");
298 let iv: [u8; 12] = hex_to_array("113b9785971864c83b01c787");
299 let pt = [];
300 let expected_c: &[u8] = &[];
301 let expected_tag: [u8; 16] = hex_to_array("72ac8493e3a5228b5d130a69d2510e42");
302 let (c, tag) = encrypt::<4, 4, 10>(&key, &iv, &pt);
303 assert_eq!(c, expected_c);
304 assert_eq!(tag, expected_tag);
305
306 // test vector from line 4417
307 let key: [u8; 16] = hex_to_array("e98b72a9881a84ca6b76e0f43e68647a");
308 let iv: [u8; 12] = hex_to_array("8b23299fde174053f3d652ba");
309 let pt: [u8; 16] = hex_to_array("28286a321293253c3e0aa2704a278032");
310 let expected_c: [u8; 16] = hex_to_array("5a3c1cf1985dbb8bed818036fdd5ab42");
311 let expected_tag: [u8; 16] = hex_to_array("23c7ab0f952b7091cd324835043b5eb5");
312 let (c, tag) = encrypt::<4, 4, 10>(&key, &iv, &pt);
313 assert_eq!(c, expected_c);
314 assert_eq!(tag, expected_tag);
315
316 // test vector from line 8834
317 let key: [u8; 16] = hex_to_array("387218b246c1a8257748b56980e50c94");
318 let iv: [u8; 12] = hex_to_array("dd7e014198672be39f95b69d");
319 let expected_c: [u8; 13] = hex_to_array("cdba9e73eaf3d38eceb2b04a8d");
320 let expected_tag: [u8; 16] = hex_to_array("ecf90f4a47c9c626d6fb2c765d201556");
321 let pt: [u8; 13] = hex_to_array("48f5b426baca03064554cc2b30");
322 let (c, tag) = encrypt::<4, 4, 10>(&key, &iv, &pt);
323 assert_eq!(c, expected_c);
324 assert_eq!(tag, expected_tag);
325
326 // test vector from line 13237
327 let key: [u8; 16] = hex_to_array("bfd414a6212958a607a0f5d3ab48471d");
328 let iv: [u8; 12] = hex_to_array("86d8ea0ab8e40dcc481cd0e2");
329 let expected_c: [u8; 32] =
330 hex_to_array("62171db33193292d930bf6647347652c1ef33316d7feca99d54f1db4fcf513f8");
331 let expected_tag: [u8; 16] = hex_to_array("c28280aa5c6c7a8bd366f28c1cfd1f6e");
332 let pt: [u8; 32] =
333 hex_to_array("a6b76a066e63392c9443e60272ceaeb9d25c991b0f2e55e2804e168c05ea591a");
334 let (c, tag) = encrypt::<4, 4, 10>(&key, &iv, &pt);
335 assert_eq!(c, expected_c);
336 assert_eq!(tag, expected_tag);
337 }
338
339 /// test checking against external aes-gcm lib
340 #[test]
341 fn test_with_external_lib() -> anyhow::Result<()> {
342 test_with_external_lib_op::<4, 4, 10, Aes128Gcm>()?;
343 test_with_external_lib_op::<8, 4, 14, Aes256Gcm>()
344 }
345 fn test_with_external_lib_op<const NK: usize, const NB: usize, const NR: usize, C>(
346 ) -> anyhow::Result<()>
347 where
348 [(); NK * NB]:,
349 [(); 4 * (NR + 1)]:,
350 C: KeyInit + Aead,
351 {
352 let key: &[u8; NK * NB] = &[42; NK * NB];
353 let nonce: &[u8; 12] = &[111; 12];
354 let pt: Vec<Vec<u8>> = vec![
355 vec![42u8; 0],
356 vec![42u8; 16],
357 vec![42u8; 32],
358 vec![42u8; 1],
359 vec![42u8; 17],
360 b"test plaintext".to_vec(),
361 b"test plaintext for AES-GCM".to_vec(),
362 rand_bytes(131),
363 rand_bytes(1027),
364 rand_bytes(4242),
365 ];
366
367 let nonce_ext = Nonce::from_slice(nonce);
368 let cipher = C::new_from_slice(key.as_slice()).unwrap();
369
370 for pt_i in pt.iter() {
371 let ciphertext = cipher.encrypt(nonce_ext, pt_i.as_ref()).unwrap();
372
373 let plaintext = cipher.decrypt(nonce_ext, ciphertext.as_ref()).unwrap();
374 assert_eq!(plaintext, *pt_i);
375
376 let (c, t) = encrypt::<NK, NB, NR>(key, nonce, pt_i);
377 assert_eq!(c.len() + t.len(), ciphertext.len());
378 assert_eq!([c, t].concat(), ciphertext);
379 }
380 Ok(())
381 }
382 fn rand_bytes(n: usize) -> Vec<u8> {
383 let mut v = vec![0u8; n];
384 rand::rng().fill_bytes(&mut v);
385 v
386 }
387}