Source code
Revision control
Copy as Markdown
Other Tools
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
use crate::query::{CRLiteCoverage, CRLiteKey, CRLiteQuery};
use clubcard::{AsQuery, Equation, Filterable};
use serde::Deserialize;
use std::collections::HashMap;
use base64::Engine;
use std::io::Read;
impl CRLiteCoverage {
// The ct-logs.json file tells us which CT logs the ct-fetch process
// monitored. For each log, it lists
// (1) the contiguous range of indices of Merkle tree leaves that
// ct-fetch downloaded,
// (2) the earliest and latest timestamps on those Merkle tree
// leaves, and
// (3) the maximum merge delay (MMD).
//
// Intuitively, "coverage" should reflect the [MinEntry, MaxEntry] range.
// However, certificates only include timestamps, not indices, and
// timestamps do not increase monotonically with leaf index.
//
// The timestamp in an embedded SCT is a promise from a log that it will
// assign an index in the next MMD window. So if
// timestamp(Cert A) + MMD <= timestamp(Cert B)
// then
// index(Cert A) < index(Cert B).
//
// It follows that a certificate has an index in [MinEntry, MaxEntry] if
// MinTimestamp + MMD <= timestamp(certificate) <= MaxTimestamp - MMD
//
// In the event that MinEntry = 0, we can refine this to
// 0 <= timestamp(certificate) <= MaxTimestamp - MMD
//
pub fn from_mozilla_ct_logs_json<T>(reader: T) -> Self
where
T: Read,
{
#[allow(non_snake_case)]
#[derive(Deserialize)]
struct MozillaCtLogsJson {
LogID: String,
MaxTimestamp: u64,
MinTimestamp: u64,
MMD: u64,
MinEntry: u64,
}
let mut coverage = HashMap::new();
let json_entries: Vec<MozillaCtLogsJson> = match serde_json::from_reader(reader) {
Ok(json_entries) => json_entries,
_ => return CRLiteCoverage(Default::default()),
};
for entry in json_entries {
let mut log_id = [0u8; 32];
match base64::prelude::BASE64_STANDARD.decode(&entry.LogID) {
Ok(bytes) if bytes.len() == 32 => log_id.copy_from_slice(&bytes),
_ => continue,
};
let min_covered = if entry.MinEntry == 0 {
0
} else {
entry.MinTimestamp + entry.MMD
};
let max_covered = entry.MaxTimestamp.saturating_sub(entry.MMD);
if min_covered < max_covered {
coverage.insert(log_id, (min_covered, max_covered));
}
}
CRLiteCoverage(coverage)
}
}
pub struct CRLiteBuilderItem {
/// issuer spki hash
issuer: [u8; 32],
/// serial number. TODO: smallvec?
serial: Vec<u8>,
/// revocation status
revoked: bool,
}
impl CRLiteBuilderItem {
pub fn revoked(issuer: [u8; 32], serial: Vec<u8>) -> Self {
Self {
issuer,
serial,
revoked: true,
}
}
pub fn not_revoked(issuer: [u8; 32], serial: Vec<u8>) -> Self {
Self {
issuer,
serial,
revoked: false,
}
}
}
impl AsQuery<4> for CRLiteBuilderItem {
fn as_query(&self, m: usize) -> Equation<4> {
let crlite_key = CRLiteKey::new(&self.issuer, &self.serial);
let crlite_query = CRLiteQuery::new(&crlite_key, None);
crlite_query.as_query(m)
}
fn block(&self) -> &[u8] {
&self.issuer
}
fn discriminant(&self) -> &[u8] {
&self.serial
}
}
impl Filterable<4> for CRLiteBuilderItem {
fn included(&self) -> bool {
self.revoked
}
}
#[cfg(test)]
mod tests {
use crate::builder::*;
use clubcard::builder::*;
use clubcard::Membership;
use std::collections::HashMap;
#[test]
fn test_crlite_clubcard() {
let subset_sizes = [1 << 17, 1 << 16, 1 << 15, 1 << 14, 1 << 13];
let universe_size = 1 << 18;
let mut clubcard_builder = ClubcardBuilder::new();
let mut approx_builders = vec![];
for (i, n) in subset_sizes.iter().enumerate() {
let mut r = clubcard_builder.new_approx_builder(&[i as u8; 32]);
for j in 0usize..*n {
let eq = CRLiteBuilderItem::revoked([i as u8; 32], j.to_le_bytes().to_vec());
r.insert(eq);
}
r.set_universe_size(universe_size);
approx_builders.push(r)
}
let approx_ribbons = approx_builders
.drain(..)
.map(ApproximateRibbon::from)
.collect();
println!("Approx ribbons:");
for r in &approx_ribbons {
println!("\t{}", r);
}
clubcard_builder.collect_approx_ribbons(approx_ribbons);
let mut exact_builders = vec![];
for (i, n) in subset_sizes.iter().enumerate() {
let mut r = clubcard_builder.new_exact_builder(&[i as u8; 32]);
for j in 0usize..universe_size {
let item = if j < *n {
CRLiteBuilderItem::revoked([i as u8; 32], j.to_le_bytes().to_vec())
} else {
CRLiteBuilderItem::not_revoked([i as u8; 32], j.to_le_bytes().to_vec())
};
r.insert(item);
}
exact_builders.push(r)
}
let exact_ribbons = exact_builders.drain(..).map(ExactRibbon::from).collect();
println!("Exact ribbons:");
for r in &exact_ribbons {
println!("\t{}", r);
}
clubcard_builder.collect_exact_ribbons(exact_ribbons);
let mut log_coverage = HashMap::new();
log_coverage.insert([0u8; 32], (0u64, u64::MAX));
let clubcard =
clubcard_builder.build::<CRLiteQuery>(CRLiteCoverage(log_coverage), Default::default());
println!("{}", clubcard);
let sum_subset_sizes: usize = subset_sizes.iter().sum();
let sum_universe_sizes: usize = subset_sizes.len() * universe_size;
let min_size = (sum_subset_sizes as f64)
* ((sum_universe_sizes as f64) / (sum_subset_sizes as f64)).log2()
+ 1.44 * ((sum_subset_sizes) as f64);
println!("Size lower bound {}", min_size);
println!("Checking construction");
println!(
"\texpecting {} included, {} excluded",
sum_subset_sizes,
subset_sizes.len() * universe_size - sum_subset_sizes
);
let mut included = 0;
let mut excluded = 0;
for i in 0..subset_sizes.len() {
let issuer = [i as u8; 32];
for j in 0..universe_size {
let serial = j.to_le_bytes();
let key = CRLiteKey::new(&issuer, &serial);
if clubcard.unchecked_contains(&CRLiteQuery::new(&key, None)) {
included += 1;
} else {
excluded += 1;
}
}
}
println!("\tfound {} included, {} excluded", included, excluded);
assert!(sum_subset_sizes == included);
assert!(sum_universe_sizes - sum_subset_sizes == excluded);
// Test that querying a serial from a never-before-seen issuer results in a non-member return.
let issuer = [subset_sizes.len() as u8; 32];
let serial = 0usize.to_le_bytes();
let key = CRLiteKey::new(&issuer, &serial);
assert!(!clubcard.unchecked_contains(&CRLiteQuery::new(&key, None)));
assert!(subset_sizes.len() > 0 && subset_sizes[0] > 0 && subset_sizes[0] < universe_size);
let issuer = [0u8; 32];
let revoked_serial = 0usize.to_le_bytes();
let nonrevoked_serial = (universe_size - 1).to_le_bytes();
// Test that calling contains() without a timestamp results in a NotInUniverse return
let revoked_serial_key = CRLiteKey::new(&issuer, &revoked_serial);
let query = CRLiteQuery::new(&revoked_serial_key, None);
assert!(matches!(
clubcard.contains(&query),
Membership::NotInUniverse
));
// Test that calling contains() with a timestamp in a covered interval results in a
// Member return.
let log_id = [0u8; 32];
let timestamp = (&log_id, 100);
let query = CRLiteQuery::new(&revoked_serial_key, Some(timestamp));
assert!(matches!(clubcard.contains(&query), Membership::Member));
// Test that calling contains() without a timestamp in a covered interval results in a
// Member return.
let timestamp = (&log_id, 100);
let nonrevoked_serial_key = CRLiteKey::new(&issuer, &nonrevoked_serial);
let query = CRLiteQuery::new(&nonrevoked_serial_key, Some(timestamp));
assert!(matches!(clubcard.contains(&query), Membership::Nonmember));
// Test that calling contains() without a timestamp in a covered interval results in a
// Member return.
let log_id = [1u8; 32];
let timestamp = (&log_id, 100);
let query = CRLiteQuery::new(&revoked_serial_key, Some(timestamp));
assert!(matches!(
clubcard.contains(&query),
Membership::NotInUniverse
));
}
}