lox_library/
bridge_table.rs

1/*! The encrypted table of bridges.
2
3The table consists of a number of buckets, each holding some number
4(currently up to 3) of bridges.  Each bucket is individually encrypted
5with a bucket key.  Users will have a credential containing a bucket
6(number, key) combination, and so will be able to read one of the
7buckets.  Users will either download the whole encrypted bucket list or
8use PIR to download a piece of it, so that the bridge authority does not
9learn which bucket the user has access to. */
10use super::cred;
11use super::IssuerPrivKey;
12use super::CMZ_B_TABLE;
13use aes_gcm::aead;
14use aes_gcm::aead::{generic_array::GenericArray, Aead};
15use aes_gcm::{Aes128Gcm, KeyInit};
16#[cfg(feature = "bridgeauth")]
17#[allow(unused_imports)]
18use base64::{engine::general_purpose, Engine as _};
19use curve25519_dalek::ristretto::CompressedRistretto;
20use curve25519_dalek::ristretto::RistrettoBasepointTable;
21use curve25519_dalek::scalar::Scalar;
22#[allow(unused_imports)]
23use rand::RngCore;
24use serde::{Deserialize, Serialize};
25use serde_with::{serde_as, DisplayFromStr};
26use sha1::{Digest, Sha1};
27use std::collections::{HashMap, HashSet};
28use std::convert::{TryFrom, TryInto};
29use subtle::ConstantTimeEq;
30
31/// Each bridge information line is serialized into this many bytes
32pub const BRIDGE_BYTES: usize = 250;
33
34/// The bridge info field is this many bytes long
35pub const BRIDGE_INFO_BYTES: usize = BRIDGE_BYTES - 46;
36
37/// The max number of bridges per bucket
38pub const MAX_BRIDGES_PER_BUCKET: usize = 3;
39
40/// The minimum number of bridges in a bucket that must be reachable for
41/// the bucket to get a Bucket Reachability credential that will allow
42/// users of that bucket to gain trust levels (once they are already at
43/// level 1)
44pub const MIN_BUCKET_REACHABILITY: usize = 2;
45
46/// A bridge information line
47#[serde_as]
48#[derive(Serialize, Deserialize, Copy, Clone, Hash, Eq, PartialEq, Debug)]
49pub struct BridgeLine {
50    /// IPv4 or IPv6 address
51    pub addr: [u8; 16],
52    /// port
53    pub port: u16,
54    /// fingerprint
55    #[serde_as(as = "DisplayFromStr")]
56    pub uid_fingerprint: u64,
57    /// unhashed fingerprint (20-byte bridge ID)
58    pub unhashed_fingerprint: [u8; 20], // may be changed to a string later
59    /// other protocol information, including pluggable transport,
60    /// public key, etc.
61    #[serde_as(as = "[_; BRIDGE_INFO_BYTES]")]
62    pub info: [u8; BRIDGE_INFO_BYTES],
63}
64
65impl BridgeLine {
66    pub fn get_hashed_fingerprint(&self) -> [u8; 20] {
67        let mut hasher = Sha1::new();
68        hasher.update(self.unhashed_fingerprint);
69        // If the fingerprint gets changed to a string:
70        //hasher.update(array_bytes::hex2array(&self.fingerprint).unwrap());
71        hasher.finalize().into()
72    }
73}
74
75/// A bucket contains MAX_BRIDGES_PER_BUCKET bridges plus the
76/// information needed to construct a Bucket Reachability credential,
77/// which is a 4-byte date, and a (P,Q) MAC
78type Bucket = (
79    [BridgeLine; MAX_BRIDGES_PER_BUCKET],
80    Option<cred::BucketReachability>,
81);
82
83/// The size of a plaintext bucket
84pub const BUCKET_BYTES: usize = BRIDGE_BYTES * MAX_BRIDGES_PER_BUCKET + 4 + 32 + 32;
85
86/// The size of an encrypted bucket
87pub const ENC_BUCKET_BYTES: usize = BUCKET_BYTES + 12 + 16;
88
89impl Default for BridgeLine {
90    /// An "empty" BridgeLine is represented by all zeros
91    fn default() -> Self {
92        Self {
93            addr: [0; 16],
94            port: 0,
95            uid_fingerprint: 0,
96            unhashed_fingerprint: [0; 20],
97            info: [0; BRIDGE_INFO_BYTES],
98        }
99    }
100}
101
102impl BridgeLine {
103    /// Encode a BridgeLine to a byte array
104    pub fn encode(&self) -> [u8; BRIDGE_BYTES] {
105        let mut res: [u8; BRIDGE_BYTES] = [0; BRIDGE_BYTES];
106        res[0..16].copy_from_slice(&self.addr);
107        res[16..18].copy_from_slice(&self.port.to_be_bytes());
108        res[18..26].copy_from_slice(&self.uid_fingerprint.to_be_bytes());
109        res[26..46].copy_from_slice(&self.unhashed_fingerprint);
110        res[46..].copy_from_slice(&self.info);
111        res
112    }
113    /// Decode a BridgeLine from a byte array
114    pub fn decode(data: &[u8; BRIDGE_BYTES]) -> Self {
115        let mut res: Self = Default::default();
116        res.addr.copy_from_slice(&data[0..16]);
117        res.port = u16::from_be_bytes(data[16..18].try_into().unwrap());
118        res.uid_fingerprint = u64::from_be_bytes(data[18..26].try_into().unwrap());
119        res.unhashed_fingerprint.copy_from_slice(&data[26..46]);
120        res.info.copy_from_slice(&data[46..]);
121        res
122    }
123    /// Encode a bucket to a byte array, including a Bucket Reachability
124    /// credential if appropriate
125    pub fn bucket_encode(
126        bucket: &[BridgeLine; MAX_BRIDGES_PER_BUCKET],
127        reachable: &HashMap<BridgeLine, Vec<(u32, usize)>>,
128        today: u32,
129        bucket_attr: &Scalar,
130        reachability_priv: &IssuerPrivKey,
131    ) -> [u8; BUCKET_BYTES] {
132        let mut res: [u8; BUCKET_BYTES] = [0; BUCKET_BYTES];
133        let mut pos: usize = 0;
134        let mut num_reachable: usize = 0;
135        for bridge in bucket {
136            res[pos..pos + BRIDGE_BYTES].copy_from_slice(&bridge.encode());
137            if reachable.contains_key(bridge) {
138                num_reachable += 1;
139            }
140            pos += BRIDGE_BYTES;
141        }
142        if num_reachable >= MIN_BUCKET_REACHABILITY {
143            // Construct a Bucket Reachability credential for this
144            // bucket and today's date
145            let today_attr: Scalar = today.into();
146            let mut rng = rand::thread_rng();
147            let Btable: &RistrettoBasepointTable = &CMZ_B_TABLE;
148            let b = Scalar::random(&mut rng);
149            let P = &b * Btable;
150            let Q = &(b
151                * (reachability_priv.x[0]
152                    + reachability_priv.x[1] * today_attr
153                    + reachability_priv.x[2] * bucket_attr))
154                * Btable;
155            res[pos..pos + 4].copy_from_slice(&today.to_le_bytes());
156            res[pos + 4..pos + 36].copy_from_slice(P.compress().as_bytes());
157            res[pos + 36..].copy_from_slice(Q.compress().as_bytes());
158        }
159        res
160    }
161    /// Decode a bucket from a byte array, yielding the array of
162    /// BridgeLine entries and an optional Bucket Reachability
163    /// credential
164    fn bucket_decode(data: &[u8; BUCKET_BYTES], bucket_attr: &Scalar) -> Bucket {
165        let mut pos: usize = 0;
166        let mut bridges: [BridgeLine; MAX_BRIDGES_PER_BUCKET] = Default::default();
167        for bridge in bridges.iter_mut().take(MAX_BRIDGES_PER_BUCKET) {
168            *bridge = BridgeLine::decode(data[pos..pos + BRIDGE_BYTES].try_into().unwrap());
169            pos += BRIDGE_BYTES;
170        }
171        // See if there's a nonzero date in the Bucket Reachability
172        // Credential
173        let date = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
174        let (optP, optQ) = if date > 0 {
175            (
176                CompressedRistretto::from_slice(&data[pos + 4..pos + 36])
177                    .expect("Unable to extract P from bucket")
178                    .decompress(),
179                CompressedRistretto::from_slice(&data[pos + 36..])
180                    .expect("Unable to extract Q from bucket")
181                    .decompress(),
182            )
183        } else {
184            (None, None)
185        };
186        if let (Some(P), Some(Q)) = (optP, optQ) {
187            let date_attr: Scalar = date.into();
188            (
189                bridges,
190                Some(cred::BucketReachability {
191                    P,
192                    Q,
193                    date: date_attr,
194                    bucket: *bucket_attr,
195                }),
196            )
197        } else {
198            (bridges, None)
199        }
200    }
201
202    /// Create a random BridgeLine for testing
203    #[cfg(test)]
204    pub fn random() -> Self {
205        let mut rng = rand::thread_rng();
206        let mut res: Self = Default::default();
207        // Pick a random 4-byte address
208        let mut addr: [u8; 4] = [0; 4];
209        rng.fill_bytes(&mut addr);
210        // If the leading byte is 224 or more, that's not a valid IPv4
211        // address.  Choose an IPv6 address instead (but don't worry too
212        // much about it being well formed).
213        if addr[0] >= 224 {
214            rng.fill_bytes(&mut res.addr);
215        } else {
216            // Store an IPv4 address as a v4-mapped IPv6 address
217            res.addr[10] = 255;
218            res.addr[11] = 255;
219            res.addr[12..16].copy_from_slice(&addr);
220        };
221        let ports: [u16; 4] = [443, 4433, 8080, 43079];
222        let portidx = (rng.next_u32() % 4) as usize;
223        res.port = ports[portidx];
224        res.uid_fingerprint = rng.next_u64();
225        let mut cert: [u8; 52] = [0; 52];
226        rng.fill_bytes(&mut cert);
227        let infostr: String = format!(
228            "obfs4 cert={}, iat-mode=0",
229            general_purpose::STANDARD_NO_PAD.encode(cert)
230        );
231        res.info[..infostr.len()].copy_from_slice(infostr.as_bytes());
232        res
233    }
234}
235
236#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
237#[serde(try_from = "Vec<u8>", into = "Vec<u8>")]
238pub struct EncryptedBucket([u8; ENC_BUCKET_BYTES]);
239
240impl From<EncryptedBucket> for Vec<u8> {
241    fn from(e: EncryptedBucket) -> Vec<u8> {
242        e.0.into()
243    }
244}
245
246#[derive(thiserror::Error, Debug)]
247#[error("wrong slice length")]
248pub struct WrongSliceLengthError;
249
250impl TryFrom<Vec<u8>> for EncryptedBucket {
251    type Error = WrongSliceLengthError;
252    fn try_from(v: Vec<u8>) -> Result<EncryptedBucket, Self::Error> {
253        Ok(EncryptedBucket(
254            *Box::<[u8; ENC_BUCKET_BYTES]>::try_from(v).map_err(|_| WrongSliceLengthError)?,
255        ))
256    }
257}
258
259#[derive(Debug, Serialize, Deserialize)]
260struct K {
261    encbucket: EncryptedBucket,
262}
263
264/// A BridgeTable is the internal structure holding the buckets
265/// containing the bridges, the keys used to encrypt the buckets, and
266/// the encrypted buckets. The encrypted buckets will be exposed to the
267/// users of the system, and each user credential will contain the
268/// decryption key for one bucket.
269#[serde_as]
270#[derive(Debug, Default, Serialize, Deserialize)]
271pub struct BridgeTable {
272    /// All structures in the bridgetable are indexed by counter
273    pub counter: u32,
274    /// The keys of all buckets, indexed by counter, that are still part of the bridge table.
275    pub keys: HashMap<u32, [u8; 16]>,
276    /// All buckets, indexed by counter corresponding to the key above, that are
277    /// part of the bridge table.
278    pub buckets: HashMap<u32, [BridgeLine; MAX_BRIDGES_PER_BUCKET]>,
279    pub encbuckets: HashMap<u32, EncryptedBucket>,
280    /// Individual bridges that are reachable.
281    #[serde_as(as = "HashMap<serde_with::json::JsonString, _>")]
282    pub reachable: HashMap<BridgeLine, Vec<(u32, usize)>>,
283    /// Bucket ids of "hot spare" buckets. These buckets are not handed
284    /// to users, nor do they have any Migration credentials pointing to
285    /// them. When a new Migration credential is needed, a bucket is
286    /// removed from this set and used for that purpose.
287    pub spares: HashSet<u32>,
288    /// In some instances a single bridge may need to be added to a bucket as a replacement
289    /// or otherwise. In that case, a spare bucket will be removed from the set of spares, one
290    /// bridge will be used as the replacement and the left over bridges will be appended to
291    /// unallocated_bridges.
292    pub unallocated_bridges: Vec<BridgeLine>,
293    // To prevent issues with the counter for the hashmap keys, keep a list of keys that
294    // no longer match any buckets that can be used before increasing the counter.
295    pub recycleable_keys: Vec<u32>,
296    // A list of keys that have been blocked (bucket_id: u32), as well as the
297    // time (julian_date: u32) of their blocking so that they can be repurposed with new
298    // buckets after the EXPIRY_DATE.
299    pub blocked_keys: Vec<(u32, u32)>,
300    // Similarly, a list of open entry buckets (bucket_id: u32) and the time they were
301    // created (julian_date: u32) so they will be listed as expired after the EXPIRY_DATE.
302    // TODO: add open entry buckets to the open_inv_keys only once they have been distributed
303    pub open_inv_keys: Vec<(u32, u32)>,
304    /// The date the buckets were last encrypted to make the encbucket.
305    /// The encbucket must be rebuilt at least each day so that the Bucket
306    /// Reachability credentials in the buckets can be refreshed.
307    pub date_last_enc: u32,
308}
309
310// Invariant: the lengths of the keys and bucket hashmap are the same.
311// The encbuckets hashmap only gets updated when encrypt_table is called.
312
313impl BridgeTable {
314    /// Get the number of buckets in the bridge table
315    #[cfg(feature = "bridgeauth")]
316    pub fn num_buckets(&self) -> usize {
317        self.buckets.len()
318    }
319
320    /// Insert a new bucket into the bridge table, returning its index
321    #[cfg(feature = "bridgeauth")]
322    pub fn new_bucket(&mut self, index: u32, bucket: &[BridgeLine; MAX_BRIDGES_PER_BUCKET]) {
323        // Pick a random key to encrypt this bucket
324        let mut rng = rand::thread_rng();
325        let mut key: [u8; 16] = [0; 16];
326        rng.fill_bytes(&mut key);
327        self.keys.insert(index, key);
328        self.buckets.insert(index, *bucket);
329        // TODO: maybe we don't need this if the hashtable can keep track of available bridges
330        // Mark the new bridges as available
331        for (i, b) in bucket.iter().enumerate() {
332            if b.port > 0 {
333                if let Some(v) = self.reachable.get_mut(b) {
334                    v.push((index, i));
335                } else {
336                    let v = vec![(index, i)];
337                    self.reachable.insert(*b, v);
338                }
339            }
340        }
341    }
342
343    /// Create the vector of encrypted buckets from the keys and buckets
344    /// in the BridgeTable. All of the entries will be (randomly)
345    /// re-encrypted, so it will be hidden whether any individual bucket
346    /// has changed (except for entirely new buckets, of course).
347    /// Bucket Reachability credentials are added to the buckets when
348    /// enough (at least MIN_BUCKET_REACHABILITY) bridges in the bucket
349    /// are reachable.
350    #[cfg(feature = "bridgeauth")]
351    pub fn encrypt_table(&mut self, today: u32, reachability_priv: &IssuerPrivKey) {
352        let mut rng = rand::thread_rng();
353        self.encbuckets.clear();
354        for (uid, key) in self.keys.iter() {
355            let bucket = self.buckets.get(uid).unwrap();
356            let mut encbucket: [u8; ENC_BUCKET_BYTES] = [0; ENC_BUCKET_BYTES];
357            let plainbucket: [u8; BUCKET_BYTES] = BridgeLine::bucket_encode(
358                bucket,
359                &self.reachable,
360                today,
361                &to_scalar(*uid, key),
362                reachability_priv,
363            );
364            // Set the AES key
365            let aeskey = GenericArray::from_slice(key);
366            // Pick a random nonce
367            let mut noncebytes: [u8; 12] = [0; 12];
368            rng.fill_bytes(&mut noncebytes);
369            let nonce = GenericArray::from_slice(&noncebytes);
370            // Encrypt
371            let cipher = Aes128Gcm::new(aeskey);
372            let ciphertext: Vec<u8> = cipher.encrypt(nonce, plainbucket.as_ref()).unwrap();
373            encbucket[0..12].copy_from_slice(&noncebytes);
374            encbucket[12..].copy_from_slice(ciphertext.as_slice());
375            let k = EncryptedBucket(encbucket);
376            self.encbuckets.insert(*uid, k);
377        }
378        self.date_last_enc = today;
379    }
380
381    /// Decrypt an individual encrypted bucket, given its id, key, and
382    /// the encrypted bucket itself
383    pub fn decrypt_bucket(
384        id: u32,
385        key: &[u8; 16],
386        encbucket: &EncryptedBucket,
387    ) -> Result<Bucket, aead::Error> {
388        // Set the nonce and the key
389        let k = K {
390            encbucket: *encbucket,
391        };
392        let nonce = GenericArray::from_slice(&k.encbucket.0[0..12]);
393        let aeskey = GenericArray::from_slice(key);
394        // Decrypt
395        let cipher = Aes128Gcm::new(aeskey);
396        let plaintext: Vec<u8> = cipher.decrypt(nonce, k.encbucket.0[12..].as_ref())?;
397        // Convert the plaintext bytes to an array of BridgeLines
398        Ok(BridgeLine::bucket_decode(
399            plaintext.as_slice().try_into().unwrap(),
400            &to_scalar(id, key),
401        ))
402    }
403
404    /// Decrypt an individual encrypted bucket, given its id and key
405    #[cfg(feature = "bridgeauth")]
406    pub fn decrypt_bucket_id(&self, id: u32, key: &[u8; 16]) -> Result<Bucket, aead::Error> {
407        let encbucket: &EncryptedBucket = match self.encbuckets.get(&id) {
408            Some(encbucket) => encbucket,
409            None => panic!("Provided ID not found"),
410        };
411        BridgeTable::decrypt_bucket(id, key, encbucket)
412    }
413}
414
415// Unit tests that require access to the testing-only function
416// BridgeLine::random()
417#[cfg(test)]
418mod tests {
419    use super::*;
420
421    #[test]
422    fn test_bridge_table() -> Result<(), aead::Error> {
423        // Create private keys for the Bucket Reachability credentials
424        let reachability_priv = IssuerPrivKey::new(2);
425        // Create an empty bridge table
426        let mut btable: BridgeTable = Default::default();
427        // Make 20 buckets with one random bridge each
428        for _ in 0..20 {
429            let bucket: [BridgeLine; 3] =
430                [BridgeLine::random(), Default::default(), Default::default()];
431            btable.counter += 1;
432            btable.new_bucket(btable.counter, &bucket);
433        }
434        // And 20 more with three random bridges each
435        for _ in 0..20 {
436            let bucket: [BridgeLine; 3] = [
437                BridgeLine::random(),
438                BridgeLine::random(),
439                BridgeLine::random(),
440            ];
441            btable.counter += 1;
442            btable.new_bucket(btable.counter, &bucket);
443        }
444        let today: u32 = time::OffsetDateTime::now_utc()
445            .date()
446            .to_julian_day()
447            .try_into()
448            .unwrap();
449        // Create the encrypted bridge table
450        btable.encrypt_table(today, &reachability_priv);
451        // Try to decrypt a 1-bridge bucket
452        let key7 = btable.keys.get(&7u32).unwrap();
453        let bucket7 = btable.decrypt_bucket_id(7, key7)?;
454        println!("bucket 7 = {:?}", bucket7);
455        // Try to decrypt a 3-bridge bucket
456        let key24 = btable.keys.get(&24u32).unwrap();
457        let bucket24 = btable.decrypt_bucket_id(24, key24)?;
458        println!("bucket 24 = {:?}", bucket24);
459        // Try to decrypt a bucket with the wrong key
460        let key12 = btable.keys.get(&12u32).unwrap();
461        let res = btable.decrypt_bucket_id(15, key12).unwrap_err();
462        println!("bucket key mismatch = {:?}", res);
463        Ok(())
464    }
465}
466
467/// Convert an id and key to a Scalar attribute
468pub fn to_scalar(id: u32, key: &[u8; 16]) -> Scalar {
469    let mut b: [u8; 32] = [0; 32];
470    // b is a little-endian representation of the Scalar; put the key in
471    // the low 16 bytes, and the id in the next 4 bytes.
472    b[0..16].copy_from_slice(key);
473    b[16..20].copy_from_slice(&id.to_le_bytes());
474    // This cannot fail, since we're only using the low 20 bytes of b
475    Scalar::from_canonical_bytes(b).unwrap()
476}
477
478/// Convert a Scalar attribute to an id and key if possible
479pub fn from_scalar(s: Scalar) -> Result<(u32, [u8; 16]), aead::Error> {
480    // Check that the top 12 bytes of the Scalar are 0
481    let sbytes = s.as_bytes();
482    if sbytes[20..].ct_eq(&[0u8; 12]).unwrap_u8() == 0 {
483        return Err(aead::Error);
484    }
485    let id = u32::from_le_bytes(sbytes[16..20].try_into().unwrap());
486    let mut key: [u8; 16] = [0; 16];
487    key.copy_from_slice(&sbytes[..16]);
488    Ok((id, key))
489}
lox_library/bridge_table.rs

lox_library/
bridge_table.rs
