decaf377_fmd/
detection.rs

1use crate::{hash, hkd, Clue, ClueKey, Error, MAX_PRECISION};
2use bitvec::{order, slice::BitSlice};
3use decaf377::Fr;
4use rand_core::{CryptoRng, RngCore};
5use std::convert::{TryFrom, TryInto};
6
7/// Used to examine [`Clue`]s and determine whether they were possibly sent to
8/// the detection key's [`ClueKey`].
9pub struct DetectionKey {
10    /// The detection key.
11    dtk: Fr,
12    /// Cached copies of the child detection keys; these can be fully derived from `dtk`.
13    xs: [Fr; MAX_PRECISION as usize],
14}
15
16impl DetectionKey {
17    /// Create a random detection key using the supplied `rng`.
18    pub fn new<R: RngCore + CryptoRng>(mut rng: R) -> Self {
19        Self::from_field(decaf377::Fr::rand(&mut rng))
20    }
21
22    /// Create a detection key using the supplied field element directly.
23    ///
24    /// # Warning
25    ///
26    /// This function exists to support custom key derivation mechanisms; it's
27    /// the caller's responsibility to construct the detection key `dtk`
28    /// correctly.
29    pub fn from_field(dtk: Fr) -> Self {
30        let root_pub = dtk * decaf377::Element::GENERATOR;
31        let root_pub_enc = root_pub.vartime_compress();
32
33        let xs: [_; MAX_PRECISION as usize] = (0..MAX_PRECISION as usize)
34            .map(|i| {
35                hkd::derive_private(
36                    &dtk,
37                    &root_pub_enc,
38                    u8::try_from(i).expect("i < MAX_PRECISION < 256"),
39                )
40            })
41            .collect::<Vec<_>>()
42            // this conversion into an array will always succeed because we started with an iterator
43            // of length `MAX_PRECISION` and we're converting to an array of the same length
44            .try_into()
45            .expect("iterator of length `MAX_PRECISION`");
46
47        Self { dtk, xs }
48    }
49
50    /// Serialize this detection key to bytes.
51    pub fn to_bytes(&self) -> [u8; 32] {
52        self.dtk.to_bytes()
53    }
54
55    /// Deserialize a detection key from bytes.
56    pub fn from_bytes(bytes: [u8; 32]) -> Result<Self, Error> {
57        let dtk = Fr::from_bytes_checked(&bytes).map_err(|_| Error::InvalidDetectionKey)?;
58        Ok(Self::from_field(dtk))
59    }
60
61    /// Obtain the clue key corresponding to this detection key.
62    pub fn clue_key(&self) -> ClueKey {
63        ClueKey(
64            (self.dtk * decaf377::Element::GENERATOR)
65                .vartime_compress()
66                .0,
67        )
68    }
69
70    /// Use this detection key to examine the given `clue`, returning `true` if the
71    /// clue was possibly sent to this detection key's clue key.
72    ///
73    /// This test has false positives, but no false negatives.
74    ///
75    /// This function executes in constant time with respect to the detection
76    /// key material, but short-circuits to return early on a false detection.
77    #[allow(non_snake_case)]
78    pub fn examine(&self, clue: &Clue) -> bool {
79        let P_encoding = decaf377::Encoding::try_from(&clue.0[0..32]).expect("slice is right len");
80
81        let P = if let Ok(P) = P_encoding.vartime_decompress() {
82            P
83        } else {
84            // Invalid P encoding => not a match
85            return false;
86        };
87
88        let y = if let Ok(y) =
89            Fr::from_bytes_checked(&clue.0[32..64].try_into().expect("expected 32 bytes"))
90        {
91            y
92        } else {
93            // Invalid y encoding => not a match
94            return false;
95        };
96
97        // Reject P = 0 or y = 0, as these never occur in well-formed clues; as
98        // noted in the OpenPrivacy implementation, these could allow clues to
99        // match any detection key.
100        // https://docs.rs/fuzzytags/0.6.0/src/fuzzytags/lib.rs.html#348-351
101        if P.is_identity() || y == Fr::ZERO {
102            return false;
103        }
104
105        let precision_bits = match clue.precision() {
106            Err(_) => return false,
107            Ok(x) => x.bits() as u8,
108        };
109        let ciphertexts = BitSlice::<u8, order::Lsb0>::from_slice(&clue.0[65..68]);
110
111        let m = hash::to_scalar(&P_encoding.0, precision_bits, &clue.0[65..68]);
112        let Q_bytes = ((y * P) + (m * decaf377::Element::GENERATOR)).vartime_compress();
113
114        for i in 0..(precision_bits as usize) {
115            let Px_i = (P * self.xs[i]).vartime_compress();
116            let key_i = hash::to_bit(&P_encoding.0, &Px_i.0, &Q_bytes.0);
117            let msg_i = (ciphertexts[i] as u8) ^ key_i;
118            // Short-circuit if we get a zero; this branch is dependent on the
119            // ephemeral key bit `key_i`, not the long-term key `xs[i]`, so we
120            // don't risk leaking any long-term secrets through timing channels.
121            //
122            // On the other hand, this gives a massive speedup, since we have a
123            // 1/2 chance of rejecting after 1 iteration, 1/4 chance of
124            // rejecting after 2 iterations, ..., so (in expectation) we do <= 2
125            // iterations instead of n iterations.
126            if msg_i == 0 {
127                return false;
128            }
129        }
130
131        // Otherwise, all message bits were 1 and we return true.
132        true
133    }
134}
decaf377_fmd/detection.rs

decaf377_fmd/
detection.rs
