ore_rs/scheme/
bit2.rs

1/*
2 * Block ORE Implemenation using a 2-bit indicator function
3 */
4
5use crate::{
6    ciphertext::*,
7    primitives::{
8        hash::Aes128Z2Hash, prf::Aes128Prf, prp::KnuthShufflePRP, AesBlock, Hash, HashKey, Prf,
9        Prp, NONCE_SIZE,
10    },
11    OreCipher, OreError, PlainText,
12};
13
14use aes::cipher::generic_array::GenericArray;
15use lazy_static::lazy_static;
16use rand::{Rng, SeedableRng};
17use rand_chacha::ChaCha20Rng;
18use std::cell::RefCell;
19use std::cmp::Ordering;
20use subtle_ng::{Choice, ConditionallySelectable, ConstantTimeEq};
21use zeroize::ZeroizeOnDrop;
22
23pub mod block_types;
24pub use self::block_types::*;
25
26/* Define our scheme */
27#[derive(Debug, ZeroizeOnDrop)]
28pub struct OreAes128<R: Rng + SeedableRng> {
29    prf1: Aes128Prf,
30    prf2: Aes128Prf,
31    #[zeroize(skip)]
32    rng: RefCell<R>,
33}
34
35pub type OreAes128ChaCha20 = OreAes128<ChaCha20Rng>;
36
37/* Define some convenience types */
38type EncryptLeftResult<R, const N: usize> = Result<Left<OreAes128<R>, N>, OreError>;
39type EncryptResult<R, const N: usize> = Result<CipherText<OreAes128<R>, N>, OreError>;
40
41fn cmp(a: u8, b: u8) -> u8 {
42    u8::from(a > b)
43}
44
45impl<R: Rng + SeedableRng> OreCipher for OreAes128<R> {
46    type LeftBlockType = LeftBlock16;
47    type RightBlockType = RightBlock32;
48
49    fn init(k1: &[u8; 16], k2: &[u8; 16]) -> Result<Self, OreError> {
50        // TODO: k1 and k2 should be Key types and we should have a set of traits to abstract the
51        // behaviour ro parsing/loading etc
52
53        let rng: R = SeedableRng::from_entropy();
54
55        return Ok(OreAes128 {
56            prf1: Prf::new(GenericArray::from_slice(k1)),
57            prf2: Prf::new(GenericArray::from_slice(k2)),
58            rng: RefCell::new(rng),
59        });
60    }
61
62    fn encrypt_left<const N: usize>(&self, x: &PlainText<N>) -> EncryptLeftResult<R, N> {
63        let mut output = Left::<Self, N>::init();
64
65        // Build the prefixes
66        // TODO: Don't modify struct values directly - use a function on a "Left" trait
67        output.f.iter_mut().enumerate().for_each(|(n, block)| {
68            block[0..n].clone_from_slice(&x[0..n]);
69            // TODO: Include the block number in the prefix to avoid repeating values for common
70            // blocks in a long prefix
71            // e.g. when plaintext is 4700 (2-bytes/blocks)
72            // xt = [17, 17, 17, 17, 17, 17, 223, 76]
73        });
74
75        self.prf2.encrypt_all(&mut output.f);
76
77        for (n, xn) in x.iter().enumerate().take(N) {
78            // Set prefix and create PRP for the block
79            let prp: KnuthShufflePRP<u8, 256> = Prp::new(&output.f[n])?;
80
81            output.xt[n] = prp.permute(*xn)?;
82        }
83
84        // Reset the f block
85        // We don't actually need to clear sensitive data here, we
86        // just need fast "zero set". Reassigning the value will drop the old one and allocate new
87        // data to the stack
88        output.f = [Default::default(); N];
89
90        for n in 0..N {
91            output.f[n][0..n].clone_from_slice(&x[0..n]);
92            output.f[n][n] = output.xt[n];
93            // Include the block number in the value passed to the Random Oracle
94            output.f[n][N] = n as u8;
95        }
96        self.prf1.encrypt_all(&mut output.f);
97
98        Ok(output)
99    }
100
101    fn encrypt<const N: usize>(&self, x: &PlainText<N>) -> EncryptResult<R, N> {
102        let mut left = Left::<Self, N>::init();
103        let mut right = Right::<Self, N>::init();
104
105        // Generate a 16-byte random nonce
106        self.rng.borrow_mut().try_fill(&mut right.nonce)?;
107
108        // Build the prefixes
109        // TODO: Don't modify struct values directly - use a function on a "Left"
110        left.f.iter_mut().enumerate().for_each(|(n, block)| {
111            block[0..n].clone_from_slice(&x[0..n]);
112        });
113
114        self.prf2.encrypt_all(&mut left.f);
115
116        // To make zeroizing / resetting the RO keys
117        // Since the AesBlock type is stack allocated this should get optimised to a single memcpy
118        lazy_static! {
119            static ref ZEROED_RO_KEYS: [AesBlock; 256] = [Default::default(); 256];
120        }
121
122        let mut ro_keys = *ZEROED_RO_KEYS;
123
124        for n in 0..N {
125            // Set prefix and create PRP for the block
126            let prp: KnuthShufflePRP<u8, 256> = Prp::new(&left.f[n])?;
127
128            left.xt[n] = prp.permute(x[n])?;
129
130            // Reset the f block
131            left.f[n].default_in_place();
132
133            left.f[n][0..n].clone_from_slice(&x[0..n]);
134            left.f[n][n] = left.xt[n];
135            // Include the block number in the value passed to the Random Oracle
136            left.f[n][N] = n as u8;
137
138            for (j, ro_key) in ro_keys.iter_mut().enumerate() {
139                /*
140                 * The output of F in H(F(k1, y|i-1||j), r)
141                 */
142                ro_key[0..n].clone_from_slice(&x[0..n]);
143                ro_key[n] = j as u8;
144                ro_key[N] = n as u8;
145            }
146
147            self.prf1.encrypt_all(&mut ro_keys);
148
149            /* TODO: This seems to work but it is technically using the nonce as the key
150             * (instead of using it as the plaintext). This appears to be how the original
151             * ORE implementation does it but it feels a bit wonky to me. Should check with David.
152             * It is useful though because the AES crate makes it easy to encrypt groups of 8
153             * plaintexts under the same key. We really want the ability to encrypt the same
154             * plaintext (i.e. the nonce) under different keys but this may be an acceptable
155             * approximation.
156             *
157             * If not, we will probably need to implement our own parallel encrypt using intrisics
158             * like in the AES crate: https://github.com/RustCrypto/block-ciphers/blob/master/aes/src/ni/aes128.rs#L26
159             */
160            let hasher: Aes128Z2Hash = Hash::new(AesBlock::from_slice(&right.nonce));
161            let hashes = hasher.hash_all(&mut ro_keys);
162
163            // FIXME: force casting to u8 from usize could cause a panic
164            for (j, h) in hashes.iter().enumerate() {
165                let jstar = prp.invert(j as u8)?;
166                let indicator = cmp(jstar, x[n]);
167                right.data[n].set_bit(j, indicator ^ h);
168            }
169
170            // Zeroize / reset the RO keys before the next loop iteration
171            ro_keys.clone_from_slice(&*ZEROED_RO_KEYS);
172        }
173
174        self.prf1.encrypt_all(&mut left.f);
175
176        Ok(CipherText { left, right })
177    }
178
179    fn compare_raw_slices(a: &[u8], b: &[u8]) -> Option<Ordering> {
180        if a.len() != b.len() {
181            return None;
182        };
183        let left_size = Self::LeftBlockType::BLOCK_SIZE;
184        let right_size = Self::RightBlockType::BLOCK_SIZE;
185
186        // TODO: This calculation slows things down a bit - maybe store the number of blocks in the
187        // first byte?
188        let num_blocks = (a.len() - NONCE_SIZE) / (left_size + right_size + 1);
189
190        let mut is_equal = Choice::from(1);
191        let mut l: u64 = 0; // Unequal block
192
193        // Slices for the PRF ("f") blocks
194        let a_f = &a[num_blocks..];
195        let b_f = &b[num_blocks..];
196
197        for n in 0..num_blocks {
198            let prp_eq: Choice = !a[n].ct_eq(&b[n]);
199            let left_block_comparison: Choice = !left_block(a_f, n).ct_eq(left_block(b_f, n));
200            let condition: Choice = prp_eq | left_block_comparison;
201
202            l.conditional_assign(&(n as u64), is_equal & condition);
203            is_equal.conditional_assign(&Choice::from(0), is_equal & condition);
204        }
205
206        let l: usize = l as usize;
207
208        if bool::from(is_equal) {
209            return Some(Ordering::Equal);
210        }
211
212        let b_right = &b[num_blocks * (left_size + 1)..];
213        let hash_key = HashKey::from_slice(&b_right[0..NONCE_SIZE]);
214        let hash: Aes128Z2Hash = Hash::new(hash_key);
215        let h = hash.hash(left_block(a_f, l));
216
217        let target_block = right_block(&b_right[NONCE_SIZE..], l);
218        let test = get_bit(target_block, a[l] as usize) ^ h;
219
220        if test == 1 {
221            return Some(Ordering::Greater);
222        }
223
224        Some(Ordering::Less)
225    }
226}
227
228// TODO: Move these to block_types
229#[inline]
230fn left_block(input: &[u8], n: usize) -> &[u8] {
231    let f_pos = n * LeftBlock16::BLOCK_SIZE;
232    &input[f_pos..(f_pos + LeftBlock16::BLOCK_SIZE)]
233}
234
235#[inline]
236fn right_block(input: &[u8], n: usize) -> &[u8] {
237    let f_pos = n * RightBlock32::BLOCK_SIZE;
238    &input[f_pos..(f_pos + RightBlock32::BLOCK_SIZE)]
239}
240
241#[inline]
242fn get_bit(block: &[u8], bit: usize) -> u8 {
243    debug_assert!(block.len() == RightBlock32::BLOCK_SIZE);
244    debug_assert!(bit < 256);
245    let byte_index = bit / 8;
246    let position = bit % 8;
247    let v = 1 << position;
248
249    (block[byte_index] & v) >> position
250}
251
252impl<const N: usize> PartialEq for CipherText<OreAes128ChaCha20, N> {
253    fn eq(&self, b: &Self) -> bool {
254        matches!(self.cmp(b), Ordering::Equal)
255    }
256}
257
258impl<const N: usize> Ord for CipherText<OreAes128ChaCha20, N> {
259    fn cmp(&self, b: &Self) -> Ordering {
260        let mut is_equal = Choice::from(1);
261        let mut l: u64 = 0; // Unequal block
262
263        for n in 0..N {
264            let condition: Choice =
265                !(self.left.xt[n].ct_eq(&b.left.xt[n])) | !(self.left.f[n].ct_eq(&b.left.f[n]));
266
267            l.conditional_assign(&(n as u64), is_equal & condition);
268            is_equal.conditional_assign(&Choice::from(0), is_equal & condition);
269        }
270
271        let l: usize = l as usize;
272
273        if bool::from(is_equal) {
274            return Ordering::Equal;
275        }
276
277        let hash: Aes128Z2Hash = Hash::new(AesBlock::from_slice(&b.right.nonce));
278        let h = hash.hash(&self.left.f[l]);
279
280        let test = b.right.data[l].get_bit(self.left.xt[l] as usize) ^ h;
281        if test == 1 {
282            return Ordering::Greater;
283        }
284
285        Ordering::Less
286    }
287}
288
289impl<const N: usize> PartialOrd for CipherText<OreAes128ChaCha20, N> {
290    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
291        Some(self.cmp(other))
292    }
293}
294
295/*
296 * (From the Rust docs)
297 * This property cannot be checked by the compiler, and therefore Eq implies PartialEq, and has no extra methods.
298 */
299impl<const N: usize> Eq for CipherText<OreAes128ChaCha20, N> {}
300
301#[cfg(test)]
302mod tests {
303    use super::*;
304    use crate::encrypt::OreEncrypt;
305    use quickcheck::TestResult;
306
307    type ORE = OreAes128ChaCha20;
308
309    fn init_ore() -> ORE {
310        let mut k1: [u8; 16] = Default::default();
311        let mut k2: [u8; 16] = Default::default();
312
313        let mut rng = ChaCha20Rng::from_entropy();
314
315        rng.fill(&mut k1);
316        rng.fill(&mut k2);
317
318        OreCipher::init(&k1, &k2).unwrap()
319    }
320
321    quickcheck! {
322        fn compare_u64(x: u64, y: u64) -> bool {
323            let ore = init_ore();
324            let a = x.encrypt(&ore).unwrap();
325            let b = y.encrypt(&ore).unwrap();
326
327            match x.cmp(&y) {
328                Ordering::Greater => a > b,
329                Ordering::Less    => a < b,
330                Ordering::Equal   => a == b
331            }
332        }
333
334        fn compare_u64_raw_slices(x: u64, y: u64) -> bool {
335            let ore = init_ore();
336            let a = x.encrypt(&ore).unwrap().to_bytes();
337            let b = y.encrypt(&ore).unwrap().to_bytes();
338
339            match ORE::compare_raw_slices(&a, &b) {
340                Some(Ordering::Greater) => x > y,
341                Some(Ordering::Less)    => x < y,
342                Some(Ordering::Equal)   => x == y,
343                None                    => false
344            }
345        }
346
347        fn equality_u64(x: u64) -> bool {
348            let ore = init_ore();
349            let a = x.encrypt(&ore).unwrap();
350            let b = x.encrypt(&ore).unwrap();
351
352            a == b
353        }
354
355        fn equality_u64_raw_slices(x: u64) -> bool {
356            let ore = init_ore();
357            let a = x.encrypt(&ore).unwrap().to_bytes();
358            let b = x.encrypt(&ore).unwrap().to_bytes();
359
360            match ORE::compare_raw_slices(&a, &b) {
361                Some(Ordering::Equal) => true,
362                _ => false
363            }
364        }
365
366        fn compare_u32(x: u32, y: u32) -> bool {
367            let ore = init_ore();
368            let a = x.encrypt(&ore).unwrap();
369            let b = y.encrypt(&ore).unwrap();
370
371            match x.cmp(&y) {
372                Ordering::Greater => a > b,
373                Ordering::Less    => a < b,
374                Ordering::Equal   => a == b
375            }
376        }
377
378        fn equality_u32(x: u64) -> bool {
379            let ore = init_ore();
380            let a = x.encrypt(&ore).unwrap();
381            let b = x.encrypt(&ore).unwrap();
382
383            a == b
384        }
385
386        fn compare_f64(x: f64, y: f64) -> TestResult {
387            if x.is_nan() || x.is_infinite() || y.is_nan() || y.is_infinite() {
388                return TestResult::discard();
389            }
390
391            let ore = init_ore();
392            let a = x.encrypt(&ore).unwrap();
393            let b = y.encrypt(&ore).unwrap();
394
395            match x.partial_cmp(&y) {
396                Some(Ordering::Greater) => TestResult::from_bool(a > b),
397                Some(Ordering::Less)    => TestResult::from_bool(a < b),
398                Some(Ordering::Equal)   => TestResult::from_bool(a == b),
399                None                    => TestResult::failed()
400            }
401        }
402
403        /*
404         * Note that we don't discard any values for the equality check
405         * because NaN == NaN works with the integer encoding
406         * */
407        fn equality_f64(x: f64) -> bool {
408            let ore = init_ore();
409            let a = x.encrypt(&ore).unwrap();
410            let b = x.encrypt(&ore).unwrap();
411
412            a == b
413        }
414
415        fn compare_plaintext(x: u64, y: u64) -> bool {
416            let ore = init_ore();
417            let a = x.to_be_bytes().encrypt(&ore).unwrap();
418            let b = y.to_be_bytes().encrypt(&ore).unwrap();
419
420            match x.cmp(&y) {
421                Ordering::Greater => a > b,
422                Ordering::Less    => a < b,
423                Ordering::Equal   => a == b
424            }
425        }
426
427        fn equality_plaintext(x: f64) -> bool {
428            let ore = init_ore();
429            let a = x.to_be_bytes().encrypt(&ore).unwrap();
430            let b = x.to_be_bytes().encrypt(&ore).unwrap();
431
432            a == b
433        }
434    }
435
436    #[test]
437    fn smallest_to_largest() {
438        let ore = init_ore();
439        let a = 0u64.encrypt(&ore).unwrap();
440        let b = 18446744073709551615u64.encrypt(&ore).unwrap();
441
442        assert!(a < b);
443    }
444
445    #[test]
446    fn largest_to_smallest() {
447        let ore = init_ore();
448        let a = 18446744073709551615u64.encrypt(&ore).unwrap();
449        let b = 0u64.encrypt(&ore).unwrap();
450
451        assert!(a > b);
452    }
453
454    #[test]
455    fn smallest_to_smallest() {
456        let ore = init_ore();
457        let a = 0u64.encrypt(&ore).unwrap();
458        let b = 0u64.encrypt(&ore).unwrap();
459
460        assert!(a == b);
461    }
462
463    #[test]
464    fn largest_to_largest() {
465        let ore = init_ore();
466        let a = 18446744073709551615u64.encrypt(&ore).unwrap();
467        let b = 18446744073709551615u64.encrypt(&ore).unwrap();
468
469        assert!(a == b);
470    }
471
472    #[test]
473    fn comparisons_in_first_block() {
474        let ore = init_ore();
475        let a = 18446744073709551615u64.encrypt(&ore).unwrap();
476        let b = 18446744073709551612u64.encrypt(&ore).unwrap();
477
478        assert!(a > b);
479        assert!(b < a);
480    }
481
482    #[test]
483    fn comparisons_in_last_block() {
484        let ore = init_ore();
485        let a = 10u64.encrypt(&ore).unwrap();
486        let b = 73u64.encrypt(&ore).unwrap();
487
488        assert!(a < b);
489        assert!(b > a);
490    }
491
492    #[test]
493    fn compare_raw_slices_mismatched_lengths() {
494        let ore = init_ore();
495        let a_64 = 10u64.encrypt(&ore).unwrap().to_bytes();
496        let a_32 = 10u32.encrypt(&ore).unwrap().to_bytes();
497
498        assert_eq!(ORE::compare_raw_slices(&a_64, &a_32), Option::None);
499    }
500
501    #[test]
502    fn binary_encoding() {
503        let ore = init_ore();
504        let a = 10u64.encrypt(&ore).unwrap();
505        let bin = a.to_bytes();
506        assert_eq!(
507            a,
508            CipherText::<OreAes128ChaCha20, 8>::from_slice(&bin).unwrap()
509        );
510    }
511
512    #[test]
513    #[should_panic(expected = "ParseError")]
514    fn binary_encoding_invalid_length() {
515        let bin = vec![0, 1, 2, 3];
516        CipherText::<OreAes128ChaCha20, 8>::from_slice(&bin).unwrap();
517    }
518
519    #[test]
520    fn test_different_prf_keys() {
521        let k1: [u8; 16] = [
522            97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112,
523        ];
524        let k2: [u8; 16] = [
525            129, 4, 114, 186, 102, 145, 225, 73, 166, 57, 244, 251, 56, 92, 188, 36,
526        ];
527        let k3: [u8; 16] = [
528            49, 50, 51, 52, 53, 54, 55, 56, 57, 48, 97, 98, 99, 100, 101, 102,
529        ];
530
531        let ore1: OreAes128ChaCha20 = OreCipher::init(&k1, &k2).unwrap();
532        let ore2: OreAes128ChaCha20 = OreCipher::init(&k3, &k2).unwrap();
533
534        let a = 1000u32.encrypt(&ore1).unwrap().to_bytes();
535        let b = 1000u32.encrypt(&ore2).unwrap().to_bytes();
536
537        assert_ne!(Some(Ordering::Equal), ORE::compare_raw_slices(&a, &b));
538    }
539
540    #[test]
541    fn test_different_prp_keys() {
542        let k1: [u8; 16] = [
543            97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112,
544        ];
545        let k2: [u8; 16] = [
546            129, 4, 114, 186, 102, 145, 225, 73, 166, 57, 244, 251, 56, 92, 188, 36,
547        ];
548        let k3: [u8; 16] = [
549            49, 50, 51, 52, 53, 54, 55, 56, 57, 48, 97, 98, 99, 100, 101, 102,
550        ];
551
552        let ore1: OreAes128ChaCha20 = OreCipher::init(&k1, &k2).unwrap();
553        let ore2: OreAes128ChaCha20 = OreCipher::init(&k1, &k3).unwrap();
554
555        let a = 1000u32.encrypt(&ore1).unwrap().to_bytes();
556        let b = 1000u32.encrypt(&ore2).unwrap().to_bytes();
557
558        assert_ne!(Some(Ordering::Equal), ORE::compare_raw_slices(&a, &b));
559    }
560}
ore_rs/scheme/bit2.rs

ore_rs/scheme/
bit2.rs
