lox/src/bridge_table.rs

/*! 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 aes_gcm::aead;
use aes_gcm::aead::{generic_array::GenericArray, Aead, NewAead};
use aes_gcm::Aes128Gcm;
use curve25519_dalek::scalar::Scalar;
use rand::RngCore;
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 size of a plaintext bucket
pub const BUCKET_BYTES: usize = BRIDGE_BYTES * MAX_BRIDGES_PER_BUCKET;

/// The size of an encrypted bucket
pub const ENC_BUCKET_BYTES: usize = BUCKET_BYTES + 12 + 16;

/// A bridge information line
#[derive(Copy, Clone, 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.
    pub info: [u8; BRIDGE_BYTES - 18],
}

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
    pub fn bucket_encode(bucket: &[BridgeLine; MAX_BRIDGES_PER_BUCKET]) -> [u8; BUCKET_BYTES] {
        let mut res: [u8; BUCKET_BYTES] = [0; BUCKET_BYTES];
        let mut pos: usize = 0;
        for bridge in bucket {
            res[pos..pos + BRIDGE_BYTES].copy_from_slice(&bridge.encode());
            pos += BRIDGE_BYTES;
        }
        res
    }
    /// Decode a bucket from a byte array
    pub fn bucket_decode(data: &[u8; BUCKET_BYTES]) -> [BridgeLine; MAX_BRIDGES_PER_BUCKET] {
        let mut pos: usize = 0;
        let mut res: [BridgeLine; MAX_BRIDGES_PER_BUCKET] = Default::default();
        for bridge in res.iter_mut().take(MAX_BRIDGES_PER_BUCKET) {
            *bridge = BridgeLine::decode(data[pos..pos + BRIDGE_BYTES].try_into().unwrap());
            pos += BRIDGE_BYTES;
        }
        res
    }
    /// 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]>,
}

// 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
    pub fn new_bucket(&mut self, bucket: [BridgeLine; MAX_BRIDGES_PER_BUCKET]) {
        // 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);
    }

    /// 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).
    pub fn encrypt_table(&mut self) {
        let mut rng = rand::thread_rng();
        self.encbuckets.clear();
        for (key, bucket) in self.keys.iter().zip(self.buckets.iter()) {
            let mut encbucket: [u8; ENC_BUCKET_BYTES] = [0; ENC_BUCKET_BYTES];
            let plainbucket: [u8; BUCKET_BYTES] = BridgeLine::bucket_encode(bucket);
            // 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);
        }
    }

    /// Decrypt an individual encrypted bucket, given its key
    pub fn decrypt_bucket(
        key: &[u8; 16],
        encbucket: &[u8; ENC_BUCKET_BYTES],
    ) -> Result<[BridgeLine; MAX_BRIDGES_PER_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(),
        ))
    }

    /// Decrypt an individual encrypted bucket, given its id and key
    pub fn decrypt_bucket_id(
        &self,
        id: u32,
        key: &[u8; 16],
    ) -> Result<[BridgeLine; MAX_BRIDGES_PER_BUCKET], aead::Error> {
        let encbucket = self.encbuckets[id as usize];
        BridgeTable::decrypt_bucket(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 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);
        }
        // Create the encrypted bridge table
        btable.encrypt_table();
        // 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))
}