lib.rs 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550
  1. /*! Implementation of a new style of bridge authority for Tor that
  2. allows users to invite other users, while protecting the social graph
  3. from the bridge authority itself.
  4. We use CMZ14 credentials (GGM version, which is more efficient, but
  5. makes a stronger security assumption): "Algebraic MACs and
  6. Keyed-Verification Anonymous Credentials" (Chase, Meiklejohn, and
  7. Zaverucha, CCS 2014)
  8. The notation follows that of the paper "Hyphae: Social Secret Sharing"
  9. (Lovecruft and de Valence, 2017), Section 4. */
  10. // We really want points to be capital letters and scalars to be
  11. // lowercase letters
  12. #![allow(non_snake_case)]
  13. #[macro_use]
  14. extern crate zkp;
  15. pub mod bridge_table;
  16. pub mod cred;
  17. pub mod dup_filter;
  18. pub mod migration_table;
  19. use sha2::Sha512;
  20. use rand::rngs::OsRng;
  21. use rand::Rng;
  22. use std::convert::{TryFrom, TryInto};
  23. use curve25519_dalek::constants as dalek_constants;
  24. use curve25519_dalek::ristretto::RistrettoBasepointTable;
  25. use curve25519_dalek::ristretto::RistrettoPoint;
  26. use curve25519_dalek::scalar::Scalar;
  27. #[cfg(test)]
  28. use curve25519_dalek::traits::IsIdentity;
  29. use ed25519_dalek::{Keypair, PublicKey, Signature, SignatureError, Signer, Verifier};
  30. use subtle::ConstantTimeEq;
  31. use std::collections::HashSet;
  32. use bridge_table::{
  33. BridgeLine, BridgeTable, ENC_BUCKET_BYTES, MAX_BRIDGES_PER_BUCKET, MIN_BUCKET_REACHABILITY,
  34. };
  35. use migration_table::{MigrationTable, MigrationType};
  36. use lazy_static::lazy_static;
  37. lazy_static! {
  38. pub static ref CMZ_A: RistrettoPoint =
  39. RistrettoPoint::hash_from_bytes::<Sha512>(b"CMZ Generator A");
  40. pub static ref CMZ_B: RistrettoPoint = dalek_constants::RISTRETTO_BASEPOINT_POINT;
  41. pub static ref CMZ_A_TABLE: RistrettoBasepointTable = RistrettoBasepointTable::create(&CMZ_A);
  42. pub static ref CMZ_B_TABLE: RistrettoBasepointTable =
  43. dalek_constants::RISTRETTO_BASEPOINT_TABLE;
  44. }
  45. #[derive(Clone, Debug)]
  46. pub struct IssuerPrivKey {
  47. x0tilde: Scalar,
  48. x: Vec<Scalar>,
  49. }
  50. impl IssuerPrivKey {
  51. /// Create an IssuerPrivKey for credentials with the given number of
  52. /// attributes.
  53. pub fn new(n: u16) -> IssuerPrivKey {
  54. let mut rng = rand::thread_rng();
  55. let x0tilde = Scalar::random(&mut rng);
  56. let mut x: Vec<Scalar> = Vec::with_capacity((n + 1) as usize);
  57. // Set x to a vector of n+1 random Scalars
  58. x.resize_with((n + 1) as usize, || Scalar::random(&mut rng));
  59. IssuerPrivKey { x0tilde, x }
  60. }
  61. }
  62. #[derive(Clone, Debug)]
  63. pub struct IssuerPubKey {
  64. X: Vec<RistrettoPoint>,
  65. }
  66. impl IssuerPubKey {
  67. /// Create an IssuerPubKey from the corresponding IssuerPrivKey
  68. pub fn new(privkey: &IssuerPrivKey) -> IssuerPubKey {
  69. let Atable: &RistrettoBasepointTable = &CMZ_A_TABLE;
  70. let Btable: &RistrettoBasepointTable = &CMZ_B_TABLE;
  71. let n_plus_one = privkey.x.len();
  72. let mut X: Vec<RistrettoPoint> = Vec::with_capacity(n_plus_one);
  73. // The first element is a special case; it is
  74. // X[0] = x0tilde*A + x[0]*B
  75. X.push(&privkey.x0tilde * Atable + &privkey.x[0] * Btable);
  76. // The other elements (1 through n) are X[i] = x[i]*A
  77. X.extend(privkey.x.iter().skip(1).map(|xi| xi * Atable));
  78. IssuerPubKey { X }
  79. }
  80. }
  81. /// The BridgeDb. This will typically be a singleton object. The
  82. /// BridgeDb's role is simply to issue signed "open invitations" to
  83. /// people who are not yet part of the system.
  84. #[derive(Debug)]
  85. pub struct BridgeDb {
  86. /// The keypair for signing open invitations
  87. keypair: Keypair,
  88. /// The public key for verifying open invitations
  89. pub pubkey: PublicKey,
  90. /// The set of open-invitation buckets
  91. openinv_buckets: HashSet<u32>,
  92. }
  93. /// An open invitation is a [u8; OPENINV_LENGTH] where the first 32
  94. /// bytes are the serialization of a random Scalar (the invitation id),
  95. /// the next 4 bytes are a little-endian bucket number, and the last
  96. /// SIGNATURE_LENGTH bytes are the signature on the first 36 bytes.
  97. pub const OPENINV_LENGTH: usize = 32 // the length of the random
  98. // invitation id (a Scalar)
  99. + 4 // the length of the u32 for the bucket number
  100. + ed25519_dalek::SIGNATURE_LENGTH; // the length of the signature
  101. impl BridgeDb {
  102. /// Create the BridgeDb.
  103. pub fn new() -> Self {
  104. let mut csprng = OsRng {};
  105. let keypair = Keypair::generate(&mut csprng);
  106. let pubkey = keypair.public;
  107. Self {
  108. keypair,
  109. pubkey,
  110. openinv_buckets: Default::default(),
  111. }
  112. }
  113. /// Insert an open-invitation bucket into the set
  114. pub fn insert_openinv(&mut self, bucket: u32) {
  115. self.openinv_buckets.insert(bucket);
  116. }
  117. /// Remove an open-invitation bucket from the set
  118. pub fn remove_openinv(&mut self, bucket: u32) {
  119. self.openinv_buckets.remove(&bucket);
  120. }
  121. /// Produce an open invitation. In this example code, we just
  122. /// choose a random open-invitation bucket.
  123. pub fn invite(&self) -> [u8; OPENINV_LENGTH] {
  124. let mut res: [u8; OPENINV_LENGTH] = [0; OPENINV_LENGTH];
  125. let mut rng = rand::thread_rng();
  126. // Choose a random invitation id (a Scalar) and serialize it
  127. let id = Scalar::random(&mut rng);
  128. res[0..32].copy_from_slice(&id.to_bytes());
  129. // Choose a random bucket number (from the set of open
  130. // invitation buckets) and serialize it
  131. let openinv_vec: Vec<&u32> = self.openinv_buckets.iter().collect();
  132. let bucket_num = *openinv_vec[rng.gen_range(0, openinv_vec.len())];
  133. res[32..(32 + 4)].copy_from_slice(&bucket_num.to_le_bytes());
  134. // Sign the first 36 bytes and serialize it
  135. let sig = self.keypair.sign(&res[0..(32 + 4)]);
  136. res[(32 + 4)..].copy_from_slice(&sig.to_bytes());
  137. res
  138. }
  139. /// Verify an open invitation. Returns the invitation id and the
  140. /// bucket number if the signature checked out. It is up to the
  141. /// caller to then check that the invitation id has not been used
  142. /// before.
  143. pub fn verify(
  144. invitation: [u8; OPENINV_LENGTH],
  145. pubkey: PublicKey,
  146. ) -> Result<(Scalar, u32), SignatureError> {
  147. // Pull out the signature and verify it
  148. let sig = Signature::try_from(&invitation[(32 + 4)..])?;
  149. pubkey.verify(&invitation[0..(32 + 4)], &sig)?;
  150. // The signature passed. Pull out the bucket number and then
  151. // the invitation id
  152. let bucket = u32::from_le_bytes(invitation[32..(32 + 4)].try_into().unwrap());
  153. match Scalar::from_canonical_bytes(invitation[0..32].try_into().unwrap()) {
  154. // It should never happen that there's a valid signature on
  155. // an invalid serialization of a Scalar, but check anyway.
  156. None => Err(SignatureError::new()),
  157. Some(s) => Ok((s, bucket)),
  158. }
  159. }
  160. }
  161. impl Default for BridgeDb {
  162. fn default() -> Self {
  163. Self::new()
  164. }
  165. }
  166. /// The bridge authority. This will typically be a singleton object.
  167. #[derive(Debug)]
  168. pub struct BridgeAuth {
  169. /// The private key for the main Lox credential
  170. lox_priv: IssuerPrivKey,
  171. /// The public key for the main Lox credential
  172. pub lox_pub: IssuerPubKey,
  173. /// The private key for migration credentials
  174. migration_priv: IssuerPrivKey,
  175. /// The public key for migration credentials
  176. pub migration_pub: IssuerPubKey,
  177. /// The private key for migration key credentials
  178. migrationkey_priv: IssuerPrivKey,
  179. /// The public key for migration key credentials
  180. pub migrationkey_pub: IssuerPubKey,
  181. /// The private key for bucket reachability credentials
  182. reachability_priv: IssuerPrivKey,
  183. /// The public key for bucket reachability credentials
  184. pub reachability_pub: IssuerPubKey,
  185. /// The private key for invitation credentials
  186. invitation_priv: IssuerPrivKey,
  187. /// The public key for invitation credentials
  188. pub invitation_pub: IssuerPubKey,
  189. /// The public key of the BridgeDb issuing open invitations
  190. pub bridgedb_pub: PublicKey,
  191. /// The bridge table
  192. bridge_table: BridgeTable,
  193. /// The migration tables
  194. trustup_migration_table: MigrationTable,
  195. blockage_migration_table: MigrationTable,
  196. /// Duplicate filter for open invitations
  197. openinv_filter: dup_filter::DupFilter<Scalar>,
  198. /// Duplicate filter for Lox credential ids
  199. id_filter: dup_filter::DupFilter<Scalar>,
  200. /// Duplicate filter for Invitation credential ids
  201. inv_id_filter: dup_filter::DupFilter<Scalar>,
  202. /// Duplicate filter for trust promotions (from untrusted level 0 to
  203. /// trusted level 1)
  204. trust_promotion_filter: dup_filter::DupFilter<Scalar>,
  205. /// For testing only: offset of the true time to the simulated time
  206. time_offset: time::Duration,
  207. }
  208. impl BridgeAuth {
  209. pub fn new(bridgedb_pub: PublicKey) -> Self {
  210. // Create the private and public keys for each of the types of
  211. // credential, each with the appropriate number of attributes
  212. let lox_priv = IssuerPrivKey::new(6);
  213. let lox_pub = IssuerPubKey::new(&lox_priv);
  214. let migration_priv = IssuerPrivKey::new(4);
  215. let migration_pub = IssuerPubKey::new(&migration_priv);
  216. let migrationkey_priv = IssuerPrivKey::new(2);
  217. let migrationkey_pub = IssuerPubKey::new(&migrationkey_priv);
  218. let reachability_priv = IssuerPrivKey::new(2);
  219. let reachability_pub = IssuerPubKey::new(&reachability_priv);
  220. let invitation_priv = IssuerPrivKey::new(4);
  221. let invitation_pub = IssuerPubKey::new(&invitation_priv);
  222. Self {
  223. lox_priv,
  224. lox_pub,
  225. migration_priv,
  226. migration_pub,
  227. migrationkey_priv,
  228. migrationkey_pub,
  229. reachability_priv,
  230. reachability_pub,
  231. invitation_priv,
  232. invitation_pub,
  233. bridgedb_pub,
  234. bridge_table: Default::default(),
  235. trustup_migration_table: MigrationTable::new(MigrationType::TrustUpgrade),
  236. blockage_migration_table: MigrationTable::new(MigrationType::Blockage),
  237. openinv_filter: Default::default(),
  238. id_filter: Default::default(),
  239. inv_id_filter: Default::default(),
  240. trust_promotion_filter: Default::default(),
  241. time_offset: time::Duration::zero(),
  242. }
  243. }
  244. /// Insert a set of open invitation bridges.
  245. ///
  246. /// Each of the bridges will be given its own open invitation
  247. /// bucket, and the BridgeDb will be informed. A single bucket
  248. /// containing all of the bridges will also be created, with a trust
  249. /// upgrade migration from each of the single-bridge buckets.
  250. pub fn add_openinv_bridges(
  251. &mut self,
  252. bridges: [BridgeLine; MAX_BRIDGES_PER_BUCKET],
  253. bdb: &mut BridgeDb,
  254. ) {
  255. let bnum = self.bridge_table.new_bucket(&bridges);
  256. let mut single = [BridgeLine::default(); MAX_BRIDGES_PER_BUCKET];
  257. for b in bridges.iter() {
  258. single[0] = *b;
  259. let snum = self.bridge_table.new_bucket(&single);
  260. bdb.insert_openinv(snum);
  261. self.trustup_migration_table.table.insert(snum, bnum);
  262. }
  263. }
  264. /// Insert a hot spare bucket of bridges
  265. pub fn add_spare_bucket(&mut self, bucket: [BridgeLine; MAX_BRIDGES_PER_BUCKET]) {
  266. let bnum = self.bridge_table.new_bucket(&bucket);
  267. self.bridge_table.spares.insert(bnum);
  268. }
  269. /// Mark a bridge as unreachable
  270. ///
  271. /// This bridge will be removed from each of the buckets that
  272. /// contains it. If any of those are open-invitation buckets, the
  273. /// trust upgrade migration for that bucket will be removed and the
  274. /// BridgeDb will be informed to stop handing out that bridge. If
  275. /// any of those are trusted buckets where the number of reachable
  276. /// bridges has fallen below the threshold, a blockage migration
  277. /// from that bucket to a spare bucket will be added, and the spare
  278. /// bucket will be removed from the list of hot spares. In
  279. /// addition, if the blocked bucket was the _target_ of a blockage
  280. /// migration, change the target to the new (formerly spare) bucket.
  281. /// Returns true if sucessful, or false if it needed a hot spare but
  282. /// there was none available.
  283. pub fn bridge_unreachable(&mut self, bridge: &BridgeLine, bdb: &mut BridgeDb) -> bool {
  284. let mut res: bool = true;
  285. let positions = self.bridge_table.reachable.get(bridge);
  286. if let Some(v) = positions {
  287. for (bucketnum, offset) in v.iter() {
  288. // Count how many bridges in this bucket are reachable
  289. let numreachable = self.bridge_table.buckets[*bucketnum as usize]
  290. .iter()
  291. .filter(|br| self.bridge_table.reachable.get(br).is_some())
  292. .count();
  293. // Remove the bridge from the bucket
  294. assert!(self.bridge_table.buckets[*bucketnum as usize][*offset] == *bridge);
  295. self.bridge_table.buckets[*bucketnum as usize][*offset] = BridgeLine::default();
  296. // Is this bucket an open-invitation bucket?
  297. if bdb.openinv_buckets.contains(bucketnum) {
  298. bdb.openinv_buckets.remove(bucketnum);
  299. self.trustup_migration_table.table.remove(bucketnum);
  300. continue;
  301. }
  302. // Does this removal cause the bucket to go below the
  303. // threshold?
  304. if numreachable != MIN_BUCKET_REACHABILITY {
  305. // No
  306. continue;
  307. }
  308. // This bucket is now unreachable. Get a spare bucket
  309. if self.bridge_table.spares.is_empty() {
  310. // Uh, oh. No spares available. Just delete any
  311. // migrations leading to this bucket.
  312. res = false;
  313. self.trustup_migration_table
  314. .table
  315. .retain(|_, &mut v| v != *bucketnum);
  316. self.blockage_migration_table
  317. .table
  318. .retain(|_, &mut v| v != *bucketnum);
  319. } else {
  320. // Get the first spare and remove it from the spares
  321. // set.
  322. let spare = *self.bridge_table.spares.iter().next().unwrap();
  323. self.bridge_table.spares.remove(&spare);
  324. // Add a blockage migration from this bucket to the spare
  325. self.blockage_migration_table
  326. .table
  327. .insert(*bucketnum, spare);
  328. // Remove any trust upgrade migrations to this
  329. // bucket
  330. self.trustup_migration_table
  331. .table
  332. .retain(|_, &mut v| v != *bucketnum);
  333. // Change any blockage migrations with this bucket
  334. // as the destination to the spare
  335. for (_, v) in self.blockage_migration_table.table.iter_mut() {
  336. if *v == *bucketnum {
  337. *v = spare;
  338. }
  339. }
  340. }
  341. }
  342. }
  343. self.bridge_table.reachable.remove(bridge);
  344. res
  345. }
  346. #[cfg(test)]
  347. /// For testing only: manually advance the day by 1 day
  348. pub fn advance_day(&mut self) {
  349. self.time_offset += time::Duration::days(1);
  350. }
  351. #[cfg(test)]
  352. /// For testing only: manually advance the day by the given number
  353. /// of days
  354. pub fn advance_days(&mut self, days: u16) {
  355. self.time_offset += time::Duration::days(days.into());
  356. }
  357. /// Get today's (real or simulated) date
  358. fn today(&self) -> u32 {
  359. // We will not encounter negative Julian dates (~6700 years ago)
  360. // or ones larger than 32 bits
  361. (time::OffsetDateTime::now_utc().date() + self.time_offset)
  362. .julian_day()
  363. .try_into()
  364. .unwrap()
  365. }
  366. /// Get a reference to the encrypted bridge table.
  367. ///
  368. /// Be sure to call this function when you want the latest version
  369. /// of the table, since it will put fresh Bucket Reachability
  370. /// credentials in the buckets each day.
  371. pub fn enc_bridge_table(&mut self) -> &Vec<[u8; ENC_BUCKET_BYTES]> {
  372. let today = self.today();
  373. if self.bridge_table.date_last_enc != today {
  374. self.bridge_table
  375. .encrypt_table(today, &self.reachability_priv);
  376. }
  377. &self.bridge_table.encbuckets
  378. }
  379. #[cfg(test)]
  380. /// Verify the two MACs on a Lox credential
  381. pub fn verify_lox(&self, cred: &cred::Lox) -> bool {
  382. if cred.P.is_identity() {
  383. return false;
  384. }
  385. let Q = (self.lox_priv.x[0]
  386. + cred.id * self.lox_priv.x[1]
  387. + cred.bucket * self.lox_priv.x[2]
  388. + cred.trust_level * self.lox_priv.x[3]
  389. + cred.level_since * self.lox_priv.x[4]
  390. + cred.invites_remaining * self.lox_priv.x[5]
  391. + cred.blockages * self.lox_priv.x[6])
  392. * cred.P;
  393. Q == cred.Q
  394. }
  395. #[cfg(test)]
  396. /// Verify the MAC on a Migration credential
  397. pub fn verify_migration(&self, cred: &cred::Migration) -> bool {
  398. if cred.P.is_identity() {
  399. return false;
  400. }
  401. let Q = (self.migration_priv.x[0]
  402. + cred.lox_id * self.migration_priv.x[1]
  403. + cred.from_bucket * self.migration_priv.x[2]
  404. + cred.to_bucket * self.migration_priv.x[3])
  405. * cred.P;
  406. Q == cred.Q
  407. }
  408. #[cfg(test)]
  409. /// Verify the MAC on a Bucket Reachability credential
  410. pub fn verify_reachability(&self, cred: &cred::BucketReachability) -> bool {
  411. if cred.P.is_identity() {
  412. return false;
  413. }
  414. let Q = (self.reachability_priv.x[0]
  415. + cred.date * self.reachability_priv.x[1]
  416. + cred.bucket * self.reachability_priv.x[2])
  417. * cred.P;
  418. Q == cred.Q
  419. }
  420. #[cfg(test)]
  421. /// Verify the MAC on a Invitation credential
  422. pub fn verify_invitation(&self, cred: &cred::Invitation) -> bool {
  423. if cred.P.is_identity() {
  424. return false;
  425. }
  426. let Q = (self.invitation_priv.x[0]
  427. + cred.inv_id * self.invitation_priv.x[1]
  428. + cred.date * self.invitation_priv.x[2]
  429. + cred.bucket * self.invitation_priv.x[3]
  430. + cred.blockages * self.invitation_priv.x[4])
  431. * cred.P;
  432. Q == cred.Q
  433. }
  434. }
  435. /// Try to extract a u64 from a Scalar
  436. pub fn scalar_u64(s: &Scalar) -> Option<u64> {
  437. // Check that the top 24 bytes of the Scalar are 0
  438. let sbytes = s.as_bytes();
  439. if sbytes[8..].ct_eq(&[0u8; 24]).unwrap_u8() == 0 {
  440. return None;
  441. }
  442. Some(u64::from_le_bytes(sbytes[..8].try_into().unwrap()))
  443. }
  444. /// Try to extract a u32 from a Scalar
  445. pub fn scalar_u32(s: &Scalar) -> Option<u32> {
  446. // Check that the top 28 bytes of the Scalar are 0
  447. let sbytes = s.as_bytes();
  448. if sbytes[4..].ct_eq(&[0u8; 28]).unwrap_u8() == 0 {
  449. return None;
  450. }
  451. Some(u32::from_le_bytes(sbytes[..4].try_into().unwrap()))
  452. }
  453. /// Double a Scalar
  454. pub fn scalar_dbl(s: &Scalar) -> Scalar {
  455. s + s
  456. }
  457. /// Double a RistrettoPoint
  458. pub fn pt_dbl(P: &RistrettoPoint) -> RistrettoPoint {
  459. P + P
  460. }
  461. /// The protocol modules.
  462. ///
  463. /// Each protocol lives in a submodule. Each submodule defines structs
  464. /// for Request (the message from the client to the bridge authority),
  465. /// State (the state held by the client while waiting for the reply),
  466. /// and Response (the message from the bridge authority to the client).
  467. /// Each submodule defines functions request, which produces a (Request,
  468. /// State) pair, and handle_response, which consumes a State and a
  469. /// Response. It also adds a handle_* function to the BridgeAuth struct
  470. /// that consumes a Request and produces a Result<Response, ProofError>.
  471. pub mod proto {
  472. pub mod blockage_migration;
  473. pub mod check_blockage;
  474. pub mod issue_invite;
  475. pub mod level_up;
  476. pub mod migration;
  477. pub mod open_invite;
  478. pub mod redeem_invite;
  479. pub mod trust_promotion;
  480. }
  481. // Unit tests
  482. #[cfg(test)]
  483. mod tests;