openpgp-cert-d 0.3.0

//! Shared OpenPGP Certificate Directory
//!
//! This crate implements a generic [OpenPGP certificate store] that can
//! be shared between implementations.  It also defines a way to root
//! trust, and a way to associate pet names with certificates.
//! Sharing certificates and trust decisions increases security by
//! enabling more applications to take advantage of OpenPGP.  It also
//! improves privacy by reducing the required certificate discoveries
//! that go out to the network.
//!
//! Note that this crate is only concerned with the low-level
//! mechanics of the certificate directory and does not depend on an
//! OpenPGP implementation.  This is the reason that it works with
//! bytes and not high-level OpenPGP data structures.  Generally, it
//! has to be combined with an OpenPGP implementation to be useful.
//!
//! [OpenPGP certificate store]: https://datatracker.ietf.org/doc/draft-nwjw-openpgp-cert-d/

use std::time::{Duration, UNIX_EPOCH};

#[macro_use]
mod macros;
mod certd;
pub use certd::CertD;
pub use certd::MergeResult;

mod error;
pub use error::*;

mod pgp;

#[cfg(unix)]
mod unixdir;

/// Special name of the trust root.
///
/// This is the [special name] under which the [trust root] is stored.
///
/// [special name]: https://www.ietf.org/archive/id/draft-nwjw-openpgp-cert-d-00.html#name-special-names
/// [trust root]: https://www.ietf.org/archive/id/draft-nwjw-openpgp-cert-d-00.html#name-trust-root
pub const TRUST_ROOT: &str = "trust-root";

// SPECIAL_NAMES must be sorted. This allows using
// SPECIAL_NAMES.binary_search(needle).is_ok() (O(log(n))) instead of
// SPECIAL_NAMES.contains(needle) (O(n))).
const SPECIAL_NAMES: &[&str] = &[TRUST_ROOT];

/// Facilitates caching of derived data.
///
/// Every time you look up a cert in the directory, the operation also
/// returns a tag.  This tag, which can be converted to a `u64`, is an
/// opaque identifier that changes whenever the cert in the directory
/// changes.
///
/// To use it, store the tag with your cached data, and every time you
/// re-do the lookup, compare the returned tag with the stored tag to
/// see if your cached data is still up-to-date.
///
/// # Examples
///
/// This demonstrates how to use the tag to prevent useless
/// recomputations.
///
/// ```
/// # use openpgp_cert_d::*;
/// # fn dosth(certd: &CertD) -> Result<()> {
/// let fp = "eb85bb5fa33a75e15e944e63f231550c4f47e38e";
/// let (tag, cert) = certd.get(fp)?.expect("cert to exist");
/// // ...
/// if let Some((new_cert, new_tag)) = certd.get_if_changed(tag, fp)? {
///     // cert changed...
/// } else {
///     // cert didn't change...
/// }
/// # Ok(()) }
/// ```
#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
pub struct Tag(pub u64);

impl Tag {
    fn new(mtime_secs: u64, mtime_nsec: u32, size: u64, is_dir: bool)
        -> Self
    {
        // We estimate the entropy of the parameters as follows:
        //
        // - mtime_secs: log2(age of least recently updated certificate)
        //
        //   Assuming the least recently updated certificate was
        //   updated a year ago and a uniform distribution of
        //   insertions and updates, there are 31536000 possible
        //   values, which corresponds to 25 bits of entropy.
        //
        // - mtime_nsecs: log2(1 billion) = just under 30 bits of entropy.
        //
        //   Since all values are equally likely, this represents
        //
        // - size: log2(large certificate size)
        //
        //   Assuming certificates can grow to be about 1 MB large and
        //   their size is uniformly distributed, we'd have log2(1 M)
        //   = 20 bits of entropy.  In practice, we expect clustering
        //   around different typical sizes.
        //
        // We can empirically estimate entropy using a maximum
        // likelihood estimator for each bit, and summing them.  This
        // is done in the `entropy` example.  On my certificate store
        // with 3285 certificates, I see:
        //
        // ```
        // $ cargo run --release --example entropy
        //  0: size:  50% ( 1639); secs:  51% ( 1664); nanos:  50% ( 1641)
        //  1: size:  50% ( 1654); secs:  48% ( 1563); nanos:  50% ( 1654)
        //  2: size:  51% ( 1663); secs:  49% ( 1625); nanos:  50% ( 1641)
        //  3: size:  50% ( 1640); secs:  55% ( 1810); nanos:  50% ( 1656)
        //  4: size:  50% ( 1632); secs:  45% ( 1466); nanos:  50% ( 1647)
        //  5: size:  48% ( 1577); secs:  55% ( 1812); nanos:  50% ( 1631)
        //  6: size:  53% ( 1730); secs:  62% ( 2039); nanos:  50% ( 1635)
        //  7: size:  51% ( 1671); secs:  63% ( 2056); nanos:  52% ( 1694)
        //  8: size:  49% ( 1618); secs:  38% ( 1246); nanos:  49% ( 1619)
        //  9: size:  49% ( 1594); secs:  63% ( 2060); nanos:  50% ( 1636)
        // 10: size:  47% ( 1536); secs:  63% ( 2055); nanos:  50% ( 1656)
        // 11: size:  53% ( 1741); secs:  63% ( 2068); nanos:  51% ( 1660)
        // 12: size:  39% ( 1274); secs:  37% ( 1218); nanos:  50% ( 1641)
        // 13: size:  28% (  935); secs:  38% ( 1254); nanos:  50% ( 1649)
        // 14: size:  21% (  701); secs:  37% ( 1225); nanos:  51% ( 1664)
        // 15: size:  12% (  381); secs:  65% ( 2124); nanos:  50% ( 1630)
        // 16: size:   6% (  210); secs:  60% ( 1972); nanos:  50% ( 1640)
        // 17: size:   3% (   97); secs:  38% ( 1240); nanos:  50% ( 1649)
        // 18: size:   1% (   33); secs:  35% ( 1144); nanos:  49% ( 1610)
        // 19: size:   0% (    7); secs:  67% ( 2216); nanos:  50% ( 1638)
        // 20: size:   0% (    3); secs:  47% ( 1534); nanos:  49% ( 1608)
        // 21: size:   0% (    1); secs:  50% ( 1641); nanos:  50% ( 1656)
        // 22: size:   0% (    0); secs:  73% ( 2405); nanos:  49% ( 1598)
        // 23: size:   0% (    0); secs:  98% ( 3218); nanos:  50% ( 1634)
        // 24: size:   0% (    0); secs:   1% (   38); nanos:  50% ( 1628)
        // 25: size:   0% (    0); secs:   0% (    0); nanos:  51% ( 1659)
        // 26: size:   0% (    0); secs: 100% ( 3284); nanos:  47% ( 1538)
        // 27: size:   0% (    0); secs:   0% (    0); nanos:  46% ( 1500)
        // 28: size:   0% (    0); secs:   0% (    0); nanos:  44% ( 1460)
        // 29: size:   0% (    0); secs: 100% ( 3284); nanos:  47% ( 1540)
        // 30: size:   0% (    0); secs: 100% ( 3284); nanos:   0% (    0)
        // 31: size:   0% (    0); secs:   0% (    0); nanos:   0% (    0)
        // ...
        // Maximum-likelihood estimate of entropy (max: 64 bits):
        //   size: 15.73 bits
        //   secs: 22.34 bits
        //   nanos: 29.98 bits
        //   max empirical entropy: 68.05 bits
        // ```
        //
        // So for me, size has a bit less than 16 bits of entropy,
        // most of which appears to be concentrated in bit 0 through
        // bit 11.
        //
        // For mtime_secs, we expect less significant bits to have
        // more entropy than higher bits, and that matches what we
        // observe.  The amount of entropy through bit 20 is pretty
        // good.  That is followed by a steep drop in the amount of
        // entropy.  After bit 25, there is no entropy.
        //
        // For nano seconds, we expect the bits needs to represent the
        // range of values to have nearly full entropy, and that is
        // also what we see, i.e., just under 30 bits of entropy.
        //
        // Empirically we observed 68 bits of entropy, which is close
        // to our intuition.
        //
        // Based on the above analysis, we mix the values by xoring
        // the parameters as follows:
        //
        // - mtime_secs as is,
        // - mtime_nsec left shifted by 34, and
        // - size left rotated by 22.
        //
        // Using this algorithm on my current certificate directory, I
        // observe the tags have nearly maximum entropy: 63.23 bits
        // out of a maximum of 64 bits of entropy:
        //
        // ```
        // $ cargo run --release --example tag-entropy /tmp/test-certd
        // ...
        // Maximum-likelihood estimate of entropy (max: 64 bits):
        //   tag: 63.23 bits
        // ```
        //
        // In conclusion, it's unclear that using a cryptographic hash
        // function will add much.
        //
        // Note: as directory sizes are not constant across file
        // systems, and we want to support synchronization, we don't
        // consider the size parameter for directories.
        Tag(mtime_secs
            ^ ((mtime_nsec as u64) << 34)
            ^ if is_dir { 0 } else { size.rotate_left(22) })
    }
}

impl std::convert::TryFrom<&std::fs::File> for Tag {
    type Error = std::io::Error;

    /// Compute a `Tag` from file metadata.
    fn try_from(fp: &std::fs::File) -> std::io::Result<Self> {
        Tag::try_from(fp.metadata()?)
    }
}

impl std::convert::TryFrom<&std::fs::Metadata> for Tag {
    type Error = std::io::Error;

    /// Compute a `Tag` from file metadata.
    fn try_from(m: &std::fs::Metadata) -> std::io::Result<Self> {
        let d = m
            .modified()?
            .duration_since(UNIX_EPOCH)
            .unwrap_or_else(|_| Duration::new(0, 0));

        Ok(Tag::new(d.as_secs(), d.subsec_nanos(), m.len(), m.is_dir()))
    }
}

impl std::convert::TryFrom<std::fs::Metadata> for Tag {
    type Error = std::io::Error;

    /// Compute a `Tag` from file metadata.
    fn try_from(m: std::fs::Metadata) -> std::io::Result<Self> {
        Tag::try_from(&m)
    }
}

impl From<u64> for Tag {
    fn from(t: u64) -> Self {
        Tag(t)
    }
}

impl From<Tag> for u64 {
    fn from(t: Tag) -> Self {
        t.0
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn special_names_is_sorted() {
        let mut sn = SPECIAL_NAMES.to_vec();
        sn.sort_unstable();
        assert_eq!(sn, SPECIAL_NAMES);
    }
}