123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397 |
- /*! The encrypted table of bridges.
- The table consists of a number of buckets, each holding some number
- (currently up to 3) of bridges. Each bucket is individually encrypted
- with a bucket key. Users will have a credential containing a bucket
- (number, key) combination, and so will be able to read one of the
- buckets. Users will either download the whole encrypted bucket list or
- use PIR to download a piece of it, so that the bridge authority does not
- learn which bucket the user has access to. */
- use super::cred;
- use super::IssuerPrivKey;
- use super::CMZ_B_TABLE;
- use aes_gcm::aead;
- use aes_gcm::aead::{generic_array::GenericArray, Aead, NewAead};
- use aes_gcm::Aes128Gcm;
- use curve25519_dalek::ristretto::CompressedRistretto;
- use curve25519_dalek::ristretto::RistrettoBasepointTable;
- use curve25519_dalek::scalar::Scalar;
- use rand::RngCore;
- use serde::{Deserialize, Serialize};
- use serde_with::serde_as;
- use std::collections::{HashMap, HashSet};
- use std::convert::TryInto;
- use subtle::ConstantTimeEq;
- /// Each bridge information line is serialized into this many bytes
- pub const BRIDGE_BYTES: usize = 220;
- /// The max number of bridges per bucket
- pub const MAX_BRIDGES_PER_BUCKET: usize = 3;
- /// The minimum number of bridges in a bucket that must be reachable for
- /// the bucket to get a Bucket Reachability credential that will allow
- /// users of that bucket to gain trust levels (once they are already at
- /// level 1)
- pub const MIN_BUCKET_REACHABILITY: usize = 2;
- /// A bridge information line
- #[serde_as]
- #[derive(Serialize, Deserialize, Copy, Clone, Hash, Eq, PartialEq, Debug)]
- pub struct BridgeLine {
- /// IPv4 or IPv6 address
- pub addr: [u8; 16],
- /// port
- pub port: u16,
- /// other protocol information, including pluggable transport,
- /// public key, etc.
- #[serde_as(as = "[_; BRIDGE_BYTES - 18]")]
- pub info: [u8; BRIDGE_BYTES - 18],
- }
- /// A bucket contains MAX_BRIDGES_PER_BUCKET bridges plus the
- /// information needed to construct a Bucket Reachability credential,
- /// which is a 4-byte date, and a (P,Q) MAC
- type Bucket = (
- [BridgeLine; MAX_BRIDGES_PER_BUCKET],
- Option<cred::BucketReachability>,
- );
- /// The size of a plaintext bucket
- pub const BUCKET_BYTES: usize = BRIDGE_BYTES * MAX_BRIDGES_PER_BUCKET + 4 + 32 + 32;
- /// The size of an encrypted bucket
- pub const ENC_BUCKET_BYTES: usize = BUCKET_BYTES + 12 + 16;
- impl Default for BridgeLine {
- /// An "empty" BridgeLine is represented by all zeros
- fn default() -> Self {
- Self {
- addr: [0; 16],
- port: 0,
- info: [0; BRIDGE_BYTES - 18],
- }
- }
- }
- impl BridgeLine {
- /// Encode a BridgeLine to a byte array
- pub fn encode(&self) -> [u8; BRIDGE_BYTES] {
- let mut res: [u8; BRIDGE_BYTES] = [0; BRIDGE_BYTES];
- res[0..16].copy_from_slice(&self.addr);
- res[16..18].copy_from_slice(&self.port.to_be_bytes());
- res[18..].copy_from_slice(&self.info);
- res
- }
- /// Decode a BridgeLine from a byte array
- pub fn decode(data: &[u8; BRIDGE_BYTES]) -> Self {
- let mut res: Self = Default::default();
- res.addr.copy_from_slice(&data[0..16]);
- res.port = u16::from_be_bytes(data[16..18].try_into().unwrap());
- res.info.copy_from_slice(&data[18..]);
- res
- }
- /// Encode a bucket to a byte array, including a Bucket Reachability
- /// credential if appropriate
- pub fn bucket_encode(
- bucket: &[BridgeLine; MAX_BRIDGES_PER_BUCKET],
- reachable: &HashMap<BridgeLine, Vec<(u32, usize)>>,
- today: u32,
- bucket_attr: &Scalar,
- reachability_priv: &IssuerPrivKey,
- ) -> [u8; BUCKET_BYTES] {
- let mut res: [u8; BUCKET_BYTES] = [0; BUCKET_BYTES];
- let mut pos: usize = 0;
- let mut num_reachable: usize = 0;
- for bridge in bucket {
- res[pos..pos + BRIDGE_BYTES].copy_from_slice(&bridge.encode());
- if reachable.contains_key(bridge) {
- num_reachable += 1;
- }
- pos += BRIDGE_BYTES;
- }
- if num_reachable >= MIN_BUCKET_REACHABILITY {
- // Construct a Bucket Reachability credential for this
- // bucket and today's date
- let today_attr: Scalar = today.into();
- let mut rng = rand::thread_rng();
- let Btable: &RistrettoBasepointTable = &CMZ_B_TABLE;
- let b = Scalar::random(&mut rng);
- let P = &b * Btable;
- let Q = &(b
- * (reachability_priv.x[0]
- + reachability_priv.x[1] * today_attr
- + reachability_priv.x[2] * bucket_attr))
- * Btable;
- res[pos..pos + 4].copy_from_slice(&today.to_le_bytes());
- res[pos + 4..pos + 36].copy_from_slice(P.compress().as_bytes());
- res[pos + 36..].copy_from_slice(Q.compress().as_bytes());
- }
- res
- }
- /// Decode a bucket from a byte array, yielding the array of
- /// BridgeLine entries and an optional Bucket Reachability
- /// credential
- fn bucket_decode(data: &[u8; BUCKET_BYTES], bucket_attr: &Scalar) -> Bucket {
- let mut pos: usize = 0;
- let mut bridges: [BridgeLine; MAX_BRIDGES_PER_BUCKET] = Default::default();
- for bridge in bridges.iter_mut().take(MAX_BRIDGES_PER_BUCKET) {
- *bridge = BridgeLine::decode(data[pos..pos + BRIDGE_BYTES].try_into().unwrap());
- pos += BRIDGE_BYTES;
- }
- // See if there's a nonzero date in the Bucket Reachability
- // Credential
- let date = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
- let (optP, optQ) = if date > 0 {
- (
- CompressedRistretto::from_slice(&data[pos + 4..pos + 36]).decompress(),
- CompressedRistretto::from_slice(&data[pos + 36..]).decompress(),
- )
- } else {
- (None, None)
- };
- if let (Some(P), Some(Q)) = (optP, optQ) {
- let date_attr: Scalar = date.into();
- (
- bridges,
- Some(cred::BucketReachability {
- P,
- Q,
- date: date_attr,
- bucket: *bucket_attr,
- }),
- )
- } else {
- (bridges, None)
- }
- }
- /// Create a random BridgeLine for testing
- #[cfg(test)]
- pub fn random() -> Self {
- let mut rng = rand::thread_rng();
- let mut res: Self = Default::default();
- // Pick a random 4-byte address
- let mut addr: [u8; 4] = [0; 4];
- rng.fill_bytes(&mut addr);
- // If the leading byte is 224 or more, that's not a valid IPv4
- // address. Choose an IPv6 address instead (but don't worry too
- // much about it being well formed).
- if addr[0] >= 224 {
- rng.fill_bytes(&mut res.addr);
- } else {
- // Store an IPv4 address as a v4-mapped IPv6 address
- res.addr[10] = 255;
- res.addr[11] = 255;
- res.addr[12..16].copy_from_slice(&addr);
- };
- let ports: [u16; 4] = [443, 4433, 8080, 43079];
- let portidx = (rng.next_u32() % 4) as usize;
- res.port = ports[portidx];
- let mut fingerprint: [u8; 20] = [0; 20];
- let mut cert: [u8; 52] = [0; 52];
- rng.fill_bytes(&mut fingerprint);
- rng.fill_bytes(&mut cert);
- let infostr: String = format!(
- "obfs4 {} cert={} iat-mode=0",
- hex_fmt::HexFmt(fingerprint),
- base64::encode_config(cert, base64::STANDARD_NO_PAD)
- );
- res.info[..infostr.len()].copy_from_slice(infostr.as_bytes());
- res
- }
- }
- /// A BridgeTable is the internal structure holding the buckets
- /// containing the bridges, the keys used to encrypt the buckets, and
- /// the encrypted buckets. The encrypted buckets will be exposed to the
- /// users of the system, and each user credential will contain the
- /// decryption key for one bucket.
- #[derive(Debug, Default)]
- pub struct BridgeTable {
- pub keys: Vec<[u8; 16]>,
- pub buckets: Vec<[BridgeLine; MAX_BRIDGES_PER_BUCKET]>,
- pub encbuckets: Vec<[u8; ENC_BUCKET_BYTES]>,
- /// Individual bridges that are reachable
- pub reachable: HashMap<BridgeLine, Vec<(u32, usize)>>,
- /// bucket ids of "hot spare" buckets. These buckets are not handed
- /// to users, nor do they have any Migration credentials pointing to
- /// them. When a new Migration credential is needed, a bucket is
- /// removed from this set and used for that purpose.
- pub spares: HashSet<u32>,
- /// The date the buckets were last encrypted to make the encbucket.
- ///
- /// The encbucket must be rebuilt each day so that the Bucket
- /// Reachability credentials in the buckets can be refreshed.
- pub date_last_enc: u32,
- }
- // Invariant: the lengths of the keys and buckets vectors are the same.
- // The encbuckets vector only gets updated when encrypt_table is called.
- impl BridgeTable {
- /// Get the number of buckets in the bridge table
- pub fn num_buckets(&self) -> usize {
- self.buckets.len()
- }
- /// Append a new bucket to the bridge table, returning its index
- pub fn new_bucket(&mut self, bucket: &[BridgeLine; MAX_BRIDGES_PER_BUCKET]) -> u32 {
- // Pick a random key to encrypt this bucket
- let mut rng = rand::thread_rng();
- let mut key: [u8; 16] = [0; 16];
- rng.fill_bytes(&mut key);
- self.keys.push(key);
- self.buckets.push(*bucket);
- let bucketnum: u32 = (self.buckets.len() - 1).try_into().unwrap();
- // Mark the new bridges as available
- for (i, b) in bucket.iter().enumerate() {
- if b.port > 0 {
- if let Some(v) = self.reachable.get_mut(b) {
- v.push((bucketnum, i));
- } else {
- let v = vec![(bucketnum, i)];
- self.reachable.insert(*b, v);
- }
- }
- }
- bucketnum
- }
- /// Create the vector of encrypted buckets from the keys and buckets
- /// in the BridgeTable. All of the entries will be (randomly)
- /// re-encrypted, so it will be hidden whether any individual bucket
- /// has changed (except for entirely new buckets, of course).
- /// Bucket Reachability credentials are added to the buckets when
- /// enough (at least MIN_BUCKET_REACHABILITY) bridges in the bucket
- /// are reachable.
- pub fn encrypt_table(&mut self, today: u32, reachability_priv: &IssuerPrivKey) {
- let mut rng = rand::thread_rng();
- self.encbuckets.clear();
- // We want id to be a u32, so we use .zip(0u32..) instead of
- // enumerate()
- for ((key, bucket), id) in self.keys.iter().zip(self.buckets.iter()).zip(0u32..) {
- let mut encbucket: [u8; ENC_BUCKET_BYTES] = [0; ENC_BUCKET_BYTES];
- let plainbucket: [u8; BUCKET_BYTES] = BridgeLine::bucket_encode(
- bucket,
- &self.reachable,
- today,
- &to_scalar(id, key),
- reachability_priv,
- );
- // Set the AES key
- let aeskey = GenericArray::from_slice(key);
- // Pick a random nonce
- let mut noncebytes: [u8; 12] = [0; 12];
- rng.fill_bytes(&mut noncebytes);
- let nonce = GenericArray::from_slice(&noncebytes);
- // Encrypt
- let cipher = Aes128Gcm::new(aeskey);
- let ciphertext: Vec<u8> = cipher.encrypt(nonce, plainbucket.as_ref()).unwrap();
- encbucket[0..12].copy_from_slice(&noncebytes);
- encbucket[12..].copy_from_slice(ciphertext.as_slice());
- self.encbuckets.push(encbucket);
- }
- self.date_last_enc = today;
- }
- /// Decrypt an individual encrypted bucket, given its id, key, and
- /// the encrypted bucket itself
- pub fn decrypt_bucket(
- id: u32,
- key: &[u8; 16],
- encbucket: &[u8; ENC_BUCKET_BYTES],
- ) -> Result<Bucket, aead::Error> {
- // Set the nonce and the key
- let nonce = GenericArray::from_slice(&encbucket[0..12]);
- let aeskey = GenericArray::from_slice(key);
- // Decrypt
- let cipher = Aes128Gcm::new(aeskey);
- let plaintext: Vec<u8> = cipher.decrypt(nonce, encbucket[12..].as_ref())?;
- // Convert the plaintext bytes to an array of BridgeLines
- Ok(BridgeLine::bucket_decode(
- plaintext.as_slice().try_into().unwrap(),
- &to_scalar(id, key),
- ))
- }
- /// Decrypt an individual encrypted bucket, given its id and key
- pub fn decrypt_bucket_id(&self, id: u32, key: &[u8; 16]) -> Result<Bucket, aead::Error> {
- let encbucket = self.encbuckets[id as usize];
- BridgeTable::decrypt_bucket(id, key, &encbucket)
- }
- }
- // Unit tests that require access to the testing-only function
- // BridgeLine::random()
- #[cfg(test)]
- mod tests {
- use super::*;
- #[test]
- fn test_bridge_table() -> Result<(), aead::Error> {
- // Create private keys for the Bucket Reachability credentials
- let reachability_priv = IssuerPrivKey::new(2);
- // Create an empty bridge table
- let mut btable: BridgeTable = Default::default();
- // Make 20 buckets with one random bridge each
- for _ in 0..20 {
- let bucket: [BridgeLine; 3] =
- [BridgeLine::random(), Default::default(), Default::default()];
- btable.new_bucket(&bucket);
- }
- // And 20 more with three random bridges each
- for _ in 0..20 {
- let bucket: [BridgeLine; 3] = [
- BridgeLine::random(),
- BridgeLine::random(),
- BridgeLine::random(),
- ];
- btable.new_bucket(&bucket);
- }
- let today: u32 = time::OffsetDateTime::now_utc()
- .date()
- .julian_day()
- .try_into()
- .unwrap();
- // Create the encrypted bridge table
- btable.encrypt_table(today, &reachability_priv);
- // Try to decrypt a 1-bridge bucket
- let key7 = btable.keys[7];
- let bucket7 = btable.decrypt_bucket_id(7, &key7)?;
- println!("bucket 7 = {:?}", bucket7);
- // Try to decrypt a 3-bridge bucket
- let key24 = btable.keys[24];
- let bucket24 = btable.decrypt_bucket_id(24, &key24)?;
- println!("bucket 24 = {:?}", bucket24);
- // Try to decrypt a bucket with the wrong key
- let key12 = btable.keys[12];
- let res = btable.decrypt_bucket_id(15, &key12).unwrap_err();
- println!("bucket key mismatch = {:?}", res);
- Ok(())
- }
- }
- /// Convert an id and key to a Scalar attribute
- pub fn to_scalar(id: u32, key: &[u8; 16]) -> Scalar {
- let mut b: [u8; 32] = [0; 32];
- // b is a little-endian representation of the Scalar; put the key in
- // the low 16 bytes, and the id in the next 4 bytes.
- b[0..16].copy_from_slice(key);
- b[16..20].copy_from_slice(&id.to_le_bytes());
- // This cannot fail, since we're only using the low 20 bytes of b
- Scalar::from_canonical_bytes(b).unwrap()
- }
- /// Convert a Scalar attribute to an id and key if possible
- pub fn from_scalar(s: Scalar) -> Result<(u32, [u8; 16]), aead::Error> {
- // Check that the top 12 bytes of the Scalar are 0
- let sbytes = s.as_bytes();
- if sbytes[20..].ct_eq(&[0u8; 12]).unwrap_u8() == 0 {
- return Err(aead::Error);
- }
- let id = u32::from_le_bytes(sbytes[16..20].try_into().unwrap());
- let mut key: [u8; 16] = [0; 16];
- key.copy_from_slice(&sbytes[..16]);
- Ok((id, key))
- }
|