fss_rs/
prg.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright (C) 2023 Yulong Ming (myl7)
3
4//! Fast PRG implementations based on one-way compression functions, AES, and precreated keys.
5
6use aes::cipher::generic_array::GenericArray;
7use aes::cipher::{BlockEncrypt, KeyInit};
8use aes::{Aes128, Aes256};
9use bitvec::prelude::*;
10
11use crate::utils::{xor, xor_inplace};
12use crate::Prg;
13
14/// Hirose double-block-length one-way compression function with AES256 and precreated keys.
15///
16/// To avoid `#![feature(generic_const_exprs)]`, you MUST ensure `OUT_BLEN % 16 = 0` and `CIPHER_N = (OUT_BLEN / 16) * OUT_BLEN_N`.
17/// We append a prefix `OUT_` to the generic constants to emphasize the PRG output is used for the output domain.
18///
19/// It actually works for OUT_BLEN * 8 - 1 bits other than OUT_BLEN bytes.
20/// The last bit of EVERY `[u8; OUT_BLEN]` of the output is always set to 0.
21pub struct Aes256HirosePrg<const OUT_BLEN: usize, const OUT_BLEN_N: usize, const CIPHER_N: usize> {
22    ciphers: [Aes256; CIPHER_N],
23}
24
25impl<const OUT_BLEN: usize, const OUT_BLEN_N: usize, const CIPHER_N: usize>
26    Aes256HirosePrg<OUT_BLEN, OUT_BLEN_N, CIPHER_N>
27{
28    pub fn new(keys: &[&[u8; 32]; CIPHER_N]) -> Self {
29        let ciphers = std::array::from_fn(|i| {
30            let key_block = GenericArray::from_slice(keys[i]);
31            Aes256::new(key_block)
32        });
33        Self { ciphers }
34    }
35
36    /// The arbitrary non-zero constant `c` for the arbitrary fixed-point-free permutation,
37    /// which is typically just XOR `c`.
38    const fn c() -> [u8; OUT_BLEN] {
39        [0xff; OUT_BLEN]
40    }
41}
42
43impl<const OUT_BLEN: usize, const OUT_BLEN_N: usize, const CIPHER_N: usize>
44    Prg<OUT_BLEN, OUT_BLEN_N> for Aes256HirosePrg<OUT_BLEN, OUT_BLEN_N, CIPHER_N>
45{
46    fn gen(&self, seed: &[u8; OUT_BLEN]) -> [([[u8; OUT_BLEN]; OUT_BLEN_N], bool); 2] {
47        // `$p(G_{i - 1})$`.
48        let seed_p = xor(&[seed, &Self::c()]);
49
50        let mut res_bufs = [[[0; OUT_BLEN]; OUT_BLEN_N]; 2];
51        let mut out_blocks = [GenericArray::default(); 2];
52        (0..OUT_BLEN_N).for_each(|blen_i| {
53            (0..OUT_BLEN / 16).for_each(|block_i| {
54                // Same as j = 0..CIHPER_N.
55                let cipher_i = blen_i * (OUT_BLEN / 16) + block_i;
56                let in_block0 = GenericArray::from_slice(&seed[block_i * 16..(block_i + 1) * 16]);
57                let in_block1 = GenericArray::from_slice(&seed_p[block_i * 16..(block_i + 1) * 16]);
58                self.ciphers[cipher_i]
59                    .encrypt_blocks_b2b(&[*in_block0, *in_block1], &mut out_blocks)
60                    .unwrap();
61                res_bufs[0][blen_i][block_i * 16..(block_i + 1) * 16]
62                    .copy_from_slice(out_blocks[0].as_ref());
63                res_bufs[1][blen_i][block_i * 16..(block_i + 1) * 16]
64                    .copy_from_slice(out_blocks[1].as_ref());
65            });
66        });
67        (0..OUT_BLEN_N).for_each(|k| {
68            xor_inplace(&mut res_bufs[0][k], &[seed]);
69            xor_inplace(&mut res_bufs[1][k], &[&seed_p]);
70        });
71        let bit0 = res_bufs[0][0].view_bits::<Lsb0>()[0];
72        let bit1 = res_bufs[1][0].view_bits::<Lsb0>()[0];
73        res_bufs.iter_mut().for_each(|bufs| {
74            bufs.iter_mut()
75                .for_each(|buf| buf[OUT_BLEN - 1].view_bits_mut::<Lsb0>().set(0, false))
76        });
77        [(res_bufs[0], bit0), (res_bufs[1], bit1)]
78    }
79}
80
81/// Matyas-Meyer-Oseas single-block-length one-way compression function with AES128 and precreated keys.
82///
83/// To avoid `#![feature(generic_const_exprs)]`, you MUST ensure `OUT_BLEN % 16 = 0` and `CIPHER_N = (OUT_BLEN / 16) * OUT_BLEN_N * 2`.
84/// We append a prefix `OUT_` to the generic constants to emphasize the PRG output is used for the output domain.
85///
86/// It actually works for OUT_BLEN * 8 - 1 bits other than OUT_BLEN bytes.
87/// The last bit of EVERY `[u8; OUT_BLEN]` of the output is always set to 0.
88pub struct Aes128MatyasMeyerOseasPrg<
89    const OUT_BLEN: usize,
90    const OUT_BLEN_N: usize,
91    const CIPHER_N: usize,
92> {
93    ciphers: [Aes128; CIPHER_N],
94}
95
96impl<const OUT_BLEN: usize, const OUT_BLEN_N: usize, const CIPHER_N: usize>
97    Aes128MatyasMeyerOseasPrg<OUT_BLEN, OUT_BLEN_N, CIPHER_N>
98{
99    pub fn new(keys: &[&[u8; 16]; CIPHER_N]) -> Self {
100        let ciphers = std::array::from_fn(|i| {
101            let key_block = GenericArray::from_slice(keys[i]);
102            Aes128::new(key_block)
103        });
104        Self { ciphers }
105    }
106}
107
108impl<const OUT_BLEN: usize, const OUT_BLEN_N: usize, const CIPHER_N: usize>
109    Prg<OUT_BLEN, OUT_BLEN_N> for Aes128MatyasMeyerOseasPrg<OUT_BLEN, OUT_BLEN_N, CIPHER_N>
110{
111    fn gen(&self, seed: &[u8; OUT_BLEN]) -> [([[u8; OUT_BLEN]; OUT_BLEN_N], bool); 2] {
112        let ciphers0 = &self.ciphers[0..CIPHER_N / 2];
113        let ciphers1 = &self.ciphers[CIPHER_N / 2..];
114
115        let mut res_bufs = [[[0; OUT_BLEN]; OUT_BLEN_N]; 2];
116        let mut out_blocks = [GenericArray::default(); 2];
117        (0..OUT_BLEN_N).for_each(|blen_i| {
118            (0..OUT_BLEN / 16).for_each(|block_i| {
119                // Same as j = 0..CIHPER_N / 2.
120                let cipher_i = blen_i * (OUT_BLEN / 16) + block_i;
121                let in_block0 = GenericArray::from_slice(&seed[block_i * 16..(block_i + 1) * 16]);
122                let in_block1 = GenericArray::from_slice(&seed[block_i * 16..(block_i + 1) * 16]);
123                // AES instruction-level parallelism does not give noticeable performance improvement according to our trials.
124                ciphers0[cipher_i].encrypt_block_b2b(in_block0, &mut out_blocks[0]);
125                ciphers1[cipher_i].encrypt_block_b2b(in_block1, &mut out_blocks[1]);
126                res_bufs[0][blen_i][block_i * 16..(block_i + 1) * 16]
127                    .copy_from_slice(out_blocks[0].as_ref());
128                res_bufs[1][blen_i][block_i * 16..(block_i + 1) * 16]
129                    .copy_from_slice(out_blocks[1].as_ref());
130            });
131        });
132        (0..OUT_BLEN_N).for_each(|k| {
133            xor_inplace(&mut res_bufs[0][k], &[seed]);
134            xor_inplace(&mut res_bufs[1][k], &[seed]);
135        });
136        let bit0 = res_bufs[0][0].view_bits::<Lsb0>()[0];
137        let bit1 = res_bufs[1][0].view_bits::<Lsb0>()[0];
138        res_bufs.iter_mut().for_each(|bufs| {
139            bufs.iter_mut()
140                .for_each(|buf| buf[OUT_BLEN - 1].view_bits_mut::<Lsb0>().set(0, false))
141        });
142        [(res_bufs[0], bit0), (res_bufs[1], bit1)]
143    }
144}
145
146#[cfg(test)]
147mod tests {
148    use arbtest::arbtest;
149
150    use super::*;
151
152    #[test]
153    fn test_128_not_trivial() {
154        arbtest(|u| {
155            let keys: [[u8; 16]; 4] = u.arbitrary()?;
156            let seed: [u8; 16] = u.arbitrary()?;
157            let prg =
158                Aes128MatyasMeyerOseasPrg::<16, 2, 4>::new(&std::array::from_fn(|i| &keys[i]));
159            let out = prg.gen(&seed);
160            (0..2).for_each(|i| {
161                (0..2).for_each(|j| {
162                    assert_ne!(out[i].0[j], [0; 16]);
163                    assert_ne!(xor(&[&out[i].0[j], &seed]), [0; 16]);
164                    assert_ne!(xor(&[&out[i].0[j], &seed]), [0xff; 16]);
165                });
166            });
167            Ok(())
168        });
169    }
170
171    #[test]
172    fn test_256_not_trivial() {
173        arbtest(|u| {
174            let keys: [[u8; 32]; 4] = u.arbitrary()?;
175            let seed: [u8; 16] = u.arbitrary()?;
176            let prg = Aes256HirosePrg::<16, 2, 2>::new(&std::array::from_fn(|i| &keys[i]));
177            let out = prg.gen(&seed);
178            (0..2).for_each(|i| {
179                (0..2).for_each(|j| {
180                    assert_ne!(out[i].0[j], [0; 16]);
181                    assert_ne!(xor(&[&out[i].0[j], &seed]), [0; 16]);
182                    assert_ne!(xor(&[&out[i].0[j], &seed]), [0xff; 16]);
183                });
184            });
185            Ok(())
186        });
187    }
188}
fss_rs/prg.rs

fss_rs/
prg.rs
