ore_rs/scheme/
bit2.rs

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

ore_rs/scheme/
bit2.rs
