lox/src/lib.rs

/*! Implementation of a new style of bridge authority for Tor that
allows users to invite other users, while protecting the social graph
from the bridge authority itself.

We use CMZ14 credentials (GGM version, which is more efficient, but
makes a stronger security assumption): "Algebraic MACs and
Keyed-Verification Anonymous Credentials" (Chase, Meiklejohn, and
Zaverucha, CCS 2014)

The notation follows that of the paper "Hyphae: Social Secret Sharing"
(Lovecruft and de Valence, 2017), Section 4.  */

// We really want points to be capital letters and scalars to be
// lowercase letters
#![allow(non_snake_case)]

#[macro_use]
extern crate zkp;

pub mod bridge_table;
pub mod cred;
pub mod dup_filter;
pub mod migration_table;

use sha2::Sha512;

use rand::rngs::OsRng;
use rand::RngCore;
use std::convert::{TryFrom, TryInto};

use curve25519_dalek::constants as dalek_constants;
use curve25519_dalek::ristretto::RistrettoBasepointTable;
use curve25519_dalek::ristretto::RistrettoPoint;
use curve25519_dalek::scalar::Scalar;
#[cfg(test)]
use curve25519_dalek::traits::IsIdentity;

use ed25519_dalek::{Keypair, PublicKey, Signature, SignatureError, Signer, Verifier};
use subtle::ConstantTimeEq;

use lazy_static::lazy_static;

lazy_static! {
    pub static ref CMZ_A: RistrettoPoint =
        RistrettoPoint::hash_from_bytes::<Sha512>(b"CMZ Generator A");
    pub static ref CMZ_B: RistrettoPoint = dalek_constants::RISTRETTO_BASEPOINT_POINT;
    pub static ref CMZ_A_TABLE: RistrettoBasepointTable = RistrettoBasepointTable::create(&CMZ_A);
    pub static ref CMZ_B_TABLE: RistrettoBasepointTable =
        dalek_constants::RISTRETTO_BASEPOINT_TABLE;
}

#[derive(Clone, Debug)]
pub struct IssuerPrivKey {
    x0tilde: Scalar,
    x: Vec<Scalar>,
}

impl IssuerPrivKey {
    /// Create an IssuerPrivKey for credentials with the given number of
    /// attributes.
    pub fn new(n: u16) -> IssuerPrivKey {
        let mut rng = rand::thread_rng();
        let x0tilde = Scalar::random(&mut rng);
        let mut x: Vec<Scalar> = Vec::with_capacity((n + 1) as usize);

        // Set x to a vector of n+1 random Scalars
        x.resize_with((n + 1) as usize, || Scalar::random(&mut rng));

        IssuerPrivKey { x0tilde, x }
    }
}

#[derive(Clone, Debug)]
pub struct IssuerPubKey {
    X: Vec<RistrettoPoint>,
}

impl IssuerPubKey {
    /// Create an IssuerPubKey from the corresponding IssuerPrivKey
    pub fn new(privkey: &IssuerPrivKey) -> IssuerPubKey {
        let Atable: &RistrettoBasepointTable = &CMZ_A_TABLE;
        let Btable: &RistrettoBasepointTable = &CMZ_B_TABLE;
        let n_plus_one = privkey.x.len();
        let mut X: Vec<RistrettoPoint> = Vec::with_capacity(n_plus_one);

        // The first element is a special case; it is
        // X[0] = x0tilde*A + x[0]*B
        X.push(&privkey.x0tilde * Atable + &privkey.x[0] * Btable);

        // The other elements (1 through n) are X[i] = x[i]*A
        for i in 1..n_plus_one {
            X.push(&privkey.x[i] * Atable);
        }
        IssuerPubKey { X }
    }
}

/// The BridgeDb.  This will typically be a singleton object.  The
/// BridgeDb's role is simply to issue signed "open invitations" to
/// people who are not yet part of the system.
#[derive(Debug)]
pub struct BridgeDb {
    /// The keypair for signing open invitations
    keypair: Keypair,
    /// The public key for verifying open invitations
    pub pubkey: PublicKey,
    /// The number of open-invitation buckets
    num_openinv_buckets: u32,
}

/// An open invitation is a [u8; OPENINV_LENGTH] where the first 32
/// bytes are the serialization of a random Scalar (the invitation id),
/// the next 4 bytes are a little-endian bucket number, and the last
/// SIGNATURE_LENGTH bytes are the signature on the first 36 bytes.
pub const OPENINV_LENGTH: usize = 32 // the length of the random
                                     // invitation id (a Scalar)
    + 4 // the length of the u32 for the bucket number
    + ed25519_dalek::SIGNATURE_LENGTH; // the length of the signature

impl BridgeDb {
    /// Create the BridgeDb.
    pub fn new(num_openinv_buckets: u32) -> Self {
        let mut csprng = OsRng {};
        let keypair = Keypair::generate(&mut csprng);
        let pubkey = keypair.public;
        Self {
            keypair,
            pubkey,
            num_openinv_buckets,
        }
    }

    /// Produce an open invitation.  In this example code, we just
    /// choose a random open-invitation bucket.
    pub fn invite(&self) -> [u8; OPENINV_LENGTH] {
        let mut res: [u8; OPENINV_LENGTH] = [0; OPENINV_LENGTH];
        let mut rng = rand::thread_rng();
        // Choose a random invitation id (a Scalar) and serialize it
        let id = Scalar::random(&mut rng);
        res[0..32].copy_from_slice(&id.to_bytes());
        // Choose a random bucket number (mod num_openinv_buckets) and
        // serialize it
        let bucket_num = rng.next_u32() % self.num_openinv_buckets;
        res[32..(32 + 4)].copy_from_slice(&bucket_num.to_le_bytes());
        // Sign the first 36 bytes and serialize it
        let sig = self.keypair.sign(&res[0..(32 + 4)]);
        res[(32 + 4)..].copy_from_slice(&sig.to_bytes());
        res
    }

    /// Verify an open invitation.  Returns the invitation id and the
    /// bucket number if the signature checked out.  It is up to the
    /// caller to then check that the invitation id has not been used
    /// before.
    pub fn verify(
        invitation: [u8; OPENINV_LENGTH],
        pubkey: PublicKey,
    ) -> Result<(Scalar, u32), SignatureError> {
        // Pull out the signature and verify it
        let sig = Signature::try_from(&invitation[(32 + 4)..])?;
        pubkey.verify(&invitation[0..(32 + 4)], &sig)?;
        // The signature passed.  Pull out the bucket number and then
        // the invitation id
        let bucket = u32::from_le_bytes(invitation[32..(32 + 4)].try_into().unwrap());
        match Scalar::from_canonical_bytes(invitation[0..32].try_into().unwrap()) {
            // It should never happen that there's a valid signature on
            // an invalid serialization of a Scalar, but check anyway.
            None => Err(SignatureError::new()),
            Some(s) => Ok((s, bucket)),
        }
    }
}

/// The bridge authority.  This will typically be a singleton object.
#[derive(Debug)]
pub struct BridgeAuth {
    /// The private key for the main Lox credential
    lox_priv: IssuerPrivKey,
    /// The public key for the main Lox credential
    pub lox_pub: IssuerPubKey,
    /// The private key for migration credentials
    migration_priv: IssuerPrivKey,
    /// The public key for migration credentials
    pub migration_pub: IssuerPubKey,
    /// The private key for migration key credentials
    migrationkey_priv: IssuerPrivKey,
    /// The public key for migration key credentials
    pub migrationkey_pub: IssuerPubKey,
    /// The private key for bucket reachability credentials
    reachability_priv: IssuerPrivKey,
    /// The public key for bucket reachability credentials
    pub reachability_pub: IssuerPubKey,
    /// The private key for invitation credentials
    invitation_priv: IssuerPrivKey,
    /// The public key for invitation credentials
    pub invitation_pub: IssuerPubKey,

    /// The public key of the BridgeDb issuing open invitations
    pub bridgedb_pub: PublicKey,

    /// The bridge table
    bridge_table: bridge_table::BridgeTable,

    /// The migration table
    migration_table: migration_table::MigrationTable,

    /// Duplicate filter for open invitations
    openinv_filter: dup_filter::DupFilter<Scalar>,
    /// Duplicate filter for credential ids
    id_filter: dup_filter::DupFilter<Scalar>,
    /// Duplicate filter for trust promotions (from untrusted level 0 to
    /// trusted level 1)
    trust_promotion_filter: dup_filter::DupFilter<Scalar>,

    /// For testing only: offset of the true time to the simulated time
    time_offset: time::Duration,
}

impl BridgeAuth {
    pub fn new(bridgedb_pub: PublicKey) -> Self {
        // Create the private and public keys for each of the types of
        // credential, each with the appropriate number of attributes
        let lox_priv = IssuerPrivKey::new(6);
        let lox_pub = IssuerPubKey::new(&lox_priv);
        let migration_priv = IssuerPrivKey::new(3);
        let migration_pub = IssuerPubKey::new(&migration_priv);
        let migrationkey_priv = IssuerPrivKey::new(2);
        let migrationkey_pub = IssuerPubKey::new(&migrationkey_priv);
        let reachability_priv = IssuerPrivKey::new(2);
        let reachability_pub = IssuerPubKey::new(&reachability_priv);
        let invitation_priv = IssuerPrivKey::new(4);
        let invitation_pub = IssuerPubKey::new(&invitation_priv);
        Self {
            lox_priv,
            lox_pub,
            migration_priv,
            migration_pub,
            migrationkey_priv,
            migrationkey_pub,
            reachability_priv,
            reachability_pub,
            invitation_priv,
            invitation_pub,
            bridgedb_pub,
            bridge_table: Default::default(),
            migration_table: Default::default(),
            openinv_filter: Default::default(),
            id_filter: Default::default(),
            trust_promotion_filter: Default::default(),
            time_offset: time::Duration::zero(),
        }
    }

    #[cfg(test)]
    /// For testing only: manually advance the day by 1 day
    pub fn advance_day(&mut self) {
        self.time_offset += time::Duration::days(1);
    }

    #[cfg(test)]
    /// For testing only: manually advance the day by the given number
    /// of days
    pub fn advance_days(&mut self, days: u16) {
        self.time_offset += time::Duration::days(days.into());
    }

    /// Get today's (real or simulated) date
    fn today(&self) -> u32 {
        // We will not encounter negative Julian dates (~6700 years ago)
        // or ones larger than 32 bits
        (time::OffsetDateTime::now_utc().date() + self.time_offset)
            .julian_day()
            .try_into()
            .unwrap()
    }

    /// Get a reference to the encrypted bridge table.
    ///
    /// Be sure to call this function when you want the latest version
    /// of the table, since it will put fresh Bucket Reachability
    /// credentials in the buckets each day.
    pub fn enc_bridge_table(&mut self) -> &Vec<[u8; bridge_table::ENC_BUCKET_BYTES]> {
        let today = self.today();
        if self.bridge_table.date_last_enc != today {
            self.bridge_table
                .encrypt_table(today, &self.reachability_priv);
        }
        &self.bridge_table.encbuckets
    }

    #[cfg(test)]
    /// Verify the two MACs on a Lox credential
    pub fn verify_lox(&self, cred: &cred::Lox) -> bool {
        if cred.P.is_identity() {
            return false;
        }

        let Q = (self.lox_priv.x[0]
            + cred.id * self.lox_priv.x[1]
            + cred.bucket * self.lox_priv.x[2]
            + cred.trust_level * self.lox_priv.x[3]
            + cred.level_since * self.lox_priv.x[4]
            + cred.invites_remaining * self.lox_priv.x[5]
            + cred.blockages * self.lox_priv.x[6])
            * cred.P;

        Q == cred.Q
    }

    #[cfg(test)]
    /// Verify the MAC on a Migration credential
    pub fn verify_migration(&self, cred: &cred::Migration) -> bool {
        if cred.P.is_identity() {
            return false;
        }

        let Q = (self.migration_priv.x[0]
            + cred.lox_id * self.migration_priv.x[1]
            + cred.from_bucket * self.migration_priv.x[2]
            + cred.to_bucket * self.migration_priv.x[3])
            * cred.P;

        Q == cred.Q
    }

    #[cfg(test)]
    /// Verify the MAC on a Bucket Reachability credential
    pub fn verify_reachability(&self, cred: &cred::BucketReachability) -> bool {
        if cred.P.is_identity() {
            return false;
        }

        let Q = (self.reachability_priv.x[0]
            + cred.date * self.reachability_priv.x[1]
            + cred.bucket * self.reachability_priv.x[2])
            * cred.P;

        Q == cred.Q
    }

    #[cfg(test)]
    /// Verify the MAC on a Invitation credential
    pub fn verify_invitation(&self, cred: &cred::Invitation) -> bool {
        if cred.P.is_identity() {
            return false;
        }

        let Q = (self.invitation_priv.x[0]
            + cred.inv_id * self.invitation_priv.x[1]
            + cred.date * self.invitation_priv.x[2]
            + cred.bucket * self.invitation_priv.x[3]
            + cred.blockages * self.invitation_priv.x[4])
            * cred.P;

        Q == cred.Q
    }
}

/// Try to extract a u64 from a Scalar
pub fn scalar_u64(s: &Scalar) -> Option<u64> {
    // Check that the top 24 bytes of the Scalar are 0
    let sbytes = s.as_bytes();
    if sbytes[8..].ct_eq(&[0u8; 24]).unwrap_u8() == 0 {
        return None;
    }
    Some(u64::from_le_bytes(sbytes[..8].try_into().unwrap()))
}

/// Try to extract a u32 from a Scalar
pub fn scalar_u32(s: &Scalar) -> Option<u32> {
    // Check that the top 28 bytes of the Scalar are 0
    let sbytes = s.as_bytes();
    if sbytes[4..].ct_eq(&[0u8; 28]).unwrap_u8() == 0 {
        return None;
    }
    Some(u32::from_le_bytes(sbytes[..4].try_into().unwrap()))
}

/// Double a Scalar
pub fn scalar_dbl(s: &Scalar) -> Scalar {
    s + s
}

/// Double a RistrettoPoint
pub fn pt_dbl(P: &RistrettoPoint) -> RistrettoPoint {
    P + P
}

/// The protocol modules.
///
/// Each protocol lives in a submodule.  Each submodule defines structs
/// for Request (the message from the client to the bridge authority),
/// State (the state held by the client while waiting for the reply),
/// and Response (the message from the bridge authority to the client).
/// Each submodule defines functions request, which produces a (Request,
/// State) pair, and handle_response, which consumes a State and a
/// Response.  It also adds a handle_* function to the BridgeAuth struct
/// that consumes a Request and produces a Result<Response, ProofError>.
pub mod proto {
    pub mod issue_invite;
    pub mod level_up;
    pub mod migration;
    pub mod open_invite;
    pub mod trust_promotion;
}

// Unit tests
#[cfg(test)]
mod tests;