use hide_sign::{SIGNATURE_LENGTH, SigningIdentity, VERIFYING_KEY_LENGTH, VerifyingIdentity};
use sha2::{Digest, Sha256};
use std::collections::BTreeMap;
use thiserror::Error;
const ENTRY_CONTEXT: &[u8] = b"HIDE/0.6 identity entry";
const MAX_ENTRIES: usize = 100_000;
const MIN_ENTRY_BYTES: usize = 8;
const ENTRY_FIELDS: u64 = 7;
const LEGACY_ENTRY_HEADER: u64 = 6;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Framing {
Current,
Legacy,
}
impl Framing {
fn header(self) -> u64 {
match self {
Self::Current => ENTRY_FIELDS,
Self::Legacy => LEGACY_ENTRY_HEADER,
}
}
}
const MAX_LABEL_BYTES: usize = 256;
pub type Sequence = u64;
pub type DeviceId = [u8; 32];
pub fn device_id(key: &VerifyingIdentity) -> DeviceId {
let mut hasher = Sha256::new();
hasher.update(b"HIDE/0.6 device id");
hasher.update(key.to_bytes());
hasher.finalize().into()
}
#[derive(Debug, Error, PartialEq, Eq)]
pub enum IdentityError {
#[error("the log is empty")]
Empty,
#[error("entry {0} is not signed by a device this log trusts at that point")]
Unauthorised(Sequence),
#[error("entry {0} has an invalid signature")]
BadSignature(Sequence),
#[error("entry {expected} was expected but the log contains {found}")]
OutOfOrder { expected: Sequence, found: Sequence },
#[error("entry {0} does not link to its predecessor")]
BrokenLink(Sequence),
#[error("the first entry must create the identity, not {0}")]
BadRoot(&'static str),
#[error("device is already enrolled at entry {0}")]
AlreadyEnrolled(Sequence),
#[error("entry {0} revokes a device that is not enrolled")]
NotEnrolled(Sequence),
#[error("entry {0} would revoke the last remaining device")]
WouldOrphan(Sequence),
#[error("the log is malformed")]
Malformed,
#[error("the log claims {0} entries, which exceeds the limit")]
TooManyEntries(usize),
#[error("a device label may not exceed {MAX_LABEL_BYTES} bytes")]
LabelTooLong,
#[error("signing failed: {0}")]
Sign(String),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Event {
Create { device: Vec<u8>, label: String },
Enrol { device: Vec<u8>, label: String },
Revoke { device: DeviceId },
Recover { device: Vec<u8>, label: String },
}
impl Event {
fn tag(&self) -> u8 {
match self {
Self::Create { .. } => 1,
Self::Enrol { .. } => 2,
Self::Revoke { .. } => 3,
Self::Recover { .. } => 4,
}
}
fn label(&self) -> Option<&str> {
match self {
Self::Create { label, .. }
| Self::Enrol { label, .. }
| Self::Recover { label, .. } => Some(label),
Self::Revoke { .. } => None,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Entry {
pub sequence: Sequence,
pub event: Event,
pub signer: DeviceId,
pub link: [u8; 32],
pub signature: Vec<u8>,
}
impl Entry {
pub fn signed_bytes(&self, previous: &[u8; 32]) -> Vec<u8> {
signed_bytes(previous, self.sequence, &self.event, &self.signer)
}
}
fn signed_bytes(
previous: &[u8; 32],
sequence: Sequence,
event: &Event,
signer: &DeviceId,
) -> Vec<u8> {
let mut out = Vec::new();
out.extend_from_slice(previous);
out.extend_from_slice(&sequence.to_be_bytes());
out.push(event.tag());
out.extend_from_slice(signer);
let mut field = |bytes: &[u8]| {
out.extend_from_slice(&(bytes.len() as u64).to_be_bytes());
out.extend_from_slice(bytes);
};
match event {
Event::Create { device, label }
| Event::Enrol { device, label }
| Event::Recover { device, label } => {
field(device);
field(label.as_bytes());
}
Event::Revoke { device } => field(device),
}
out
}
fn link_for(signed: &[u8], signature: &[u8]) -> [u8; 32] {
let mut hasher = Sha256::new();
hasher.update(b"HIDE/0.6 identity link");
hasher.update((signed.len() as u64).to_be_bytes());
hasher.update(signed);
hasher.update((signature.len() as u64).to_be_bytes());
hasher.update(signature);
hasher.finalize().into()
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Device {
pub id: DeviceId,
pub key: VerifyingIdentity,
pub label: String,
pub enrolled_at: Sequence,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Membership {
devices: BTreeMap<DeviceId, Device>,
revoked: BTreeMap<DeviceId, Sequence>,
}
impl Membership {
pub fn contains(&self, id: &DeviceId) -> bool {
self.devices.contains_key(id)
}
pub fn get(&self, id: &DeviceId) -> Option<&Device> {
self.devices.get(id)
}
pub fn devices(&self) -> impl Iterator<Item = &Device> {
self.devices.values()
}
pub fn len(&self) -> usize {
self.devices.len()
}
pub fn is_empty(&self) -> bool {
self.devices.is_empty()
}
pub fn revoked_at(&self, id: &DeviceId) -> Option<Sequence> {
self.revoked.get(id).copied()
}
}
pub struct IdentityLog {
entries: Vec<Entry>,
recovery: VerifyingIdentity,
}
impl IdentityLog {
pub fn create(
founder: &SigningIdentity,
label: &str,
recovery: &VerifyingIdentity,
) -> Result<Self, IdentityError> {
check_label(label)?;
let key = founder.verifying_key();
let event = Event::Create {
device: key.to_bytes().to_vec(),
label: label.to_owned(),
};
let signer = device_id(&key);
let signed = signed_bytes(&[0u8; 32], 0, &event, &signer);
let signature = founder.sign(ENTRY_CONTEXT, &signed).to_vec();
Ok(Self {
entries: vec![Entry {
sequence: 0,
link: link_for(&signed, &signature),
event,
signer,
signature,
}],
recovery: recovery.clone(),
})
}
fn append(
&mut self,
author: &SigningIdentity,
event: Event,
) -> Result<Sequence, IdentityError> {
if self.entries.len() >= MAX_ENTRIES {
return Err(IdentityError::TooManyEntries(self.entries.len()));
}
if let Some(label) = event.label() {
check_label(label)?;
}
let sequence = self.entries.len() as Sequence;
let previous = self.entries.last().map_or([0u8; 32], |entry| entry.link);
let signer = device_id(&author.verifying_key());
let signed = signed_bytes(&previous, sequence, &event, &signer);
let signature = author.sign(ENTRY_CONTEXT, &signed).to_vec();
let candidate = Entry {
sequence,
link: link_for(&signed, &signature),
event,
signer,
signature,
};
let mut membership = self.membership();
apply(&mut membership, &candidate, &self.recovery, previous)?;
self.entries.push(candidate);
Ok(sequence)
}
pub fn enrol(
&mut self,
author: &SigningIdentity,
device: &VerifyingIdentity,
label: &str,
) -> Result<Sequence, IdentityError> {
self.append(
author,
Event::Enrol {
device: device.to_bytes().to_vec(),
label: label.to_owned(),
},
)
}
pub fn revoke(
&mut self,
author: &SigningIdentity,
device: DeviceId,
) -> Result<Sequence, IdentityError> {
self.append(author, Event::Revoke { device })
}
pub fn recover(
&mut self,
recovery_key: &SigningIdentity,
device: &VerifyingIdentity,
label: &str,
) -> Result<Sequence, IdentityError> {
self.append(
recovery_key,
Event::Recover {
device: device.to_bytes().to_vec(),
label: label.to_owned(),
},
)
}
pub fn from_entries(
entries: Vec<Entry>,
recovery: VerifyingIdentity,
) -> Result<Self, IdentityError> {
replay(&entries, &recovery)?;
Ok(Self { entries, recovery })
}
pub fn entries(&self) -> &[Entry] {
&self.entries
}
pub fn head(&self) -> [u8; 32] {
self.entries.last().map_or([0u8; 32], |entry| entry.link)
}
pub fn membership(&self) -> Membership {
replay(&self.entries, &self.recovery).unwrap_or_default()
}
pub fn verify(
entries: &[Entry],
recovery: &VerifyingIdentity,
) -> Result<Membership, IdentityError> {
replay(entries, recovery)
}
}
fn check_label(label: &str) -> Result<(), IdentityError> {
if label.len() > MAX_LABEL_BYTES {
return Err(IdentityError::LabelTooLong);
}
Ok(())
}
fn apply(
membership: &mut Membership,
entry: &Entry,
recovery: &VerifyingIdentity,
previous: [u8; 32],
) -> Result<(), IdentityError> {
if let Some(label) = entry.event.label()
&& label.len() > MAX_LABEL_BYTES
{
return Err(IdentityError::LabelTooLong);
}
let signed = signed_bytes(&previous, entry.sequence, &entry.event, &entry.signer);
if link_for(&signed, &entry.signature) != entry.link {
return Err(IdentityError::BrokenLink(entry.sequence));
}
let signature: [u8; SIGNATURE_LENGTH] = entry
.signature
.as_slice()
.try_into()
.map_err(|_| IdentityError::BadSignature(entry.sequence))?;
let author: VerifyingIdentity = match &entry.event {
Event::Create { device, .. } => {
if entry.sequence != 0 {
return Err(IdentityError::BadRoot("a later Create"));
}
let key = parse_key(device, entry.sequence)?;
if device_id(&key) != entry.signer {
return Err(IdentityError::Unauthorised(entry.sequence));
}
key
}
Event::Recover { .. } => {
if device_id(recovery) != entry.signer {
return Err(IdentityError::Unauthorised(entry.sequence));
}
recovery.clone()
}
Event::Enrol { .. } | Event::Revoke { .. } => membership
.devices
.get(&entry.signer)
.map(|device| device.key.clone())
.ok_or(IdentityError::Unauthorised(entry.sequence))?,
};
author
.verify(ENTRY_CONTEXT, &signed, &signature)
.map_err(|_| IdentityError::BadSignature(entry.sequence))?;
match &entry.event {
Event::Create { device, label } => {
let key = parse_key(device, entry.sequence)?;
let id = device_id(&key);
membership.devices.insert(
id,
Device {
id,
key,
label: label.clone(),
enrolled_at: entry.sequence,
},
);
}
Event::Enrol { device, label } => {
let key = parse_key(device, entry.sequence)?;
let id = device_id(&key);
if membership.devices.contains_key(&id) {
return Err(IdentityError::AlreadyEnrolled(entry.sequence));
}
membership.revoked.remove(&id);
membership.devices.insert(
id,
Device {
id,
key,
label: label.clone(),
enrolled_at: entry.sequence,
},
);
}
Event::Revoke { device } => {
if !membership.devices.contains_key(device) {
return Err(IdentityError::NotEnrolled(entry.sequence));
}
if membership.devices.len() == 1 {
return Err(IdentityError::WouldOrphan(entry.sequence));
}
membership.devices.remove(device);
membership.revoked.insert(*device, entry.sequence);
}
Event::Recover { device, label } => {
let key = parse_key(device, entry.sequence)?;
let id = device_id(&key);
for old in membership.devices.keys() {
membership.revoked.insert(*old, entry.sequence);
}
membership.devices.clear();
membership.revoked.remove(&id);
membership.devices.insert(
id,
Device {
id,
key,
label: label.clone(),
enrolled_at: entry.sequence,
},
);
}
}
Ok(())
}
fn parse_key(bytes: &[u8], sequence: Sequence) -> Result<VerifyingIdentity, IdentityError> {
if bytes.len() != VERIFYING_KEY_LENGTH {
return Err(IdentityError::Malformed);
}
VerifyingIdentity::from_bytes(bytes).map_err(|_| IdentityError::BadSignature(sequence))
}
fn replay(entries: &[Entry], recovery: &VerifyingIdentity) -> Result<Membership, IdentityError> {
if entries.is_empty() {
return Err(IdentityError::Empty);
}
if entries.len() > MAX_ENTRIES {
return Err(IdentityError::TooManyEntries(entries.len()));
}
if !matches!(entries[0].event, Event::Create { .. }) {
return Err(IdentityError::BadRoot("another event"));
}
let mut membership = Membership::default();
let mut previous = [0u8; 32];
for (index, entry) in entries.iter().enumerate() {
let expected = index as Sequence;
if entry.sequence != expected {
return Err(IdentityError::OutOfOrder {
expected,
found: entry.sequence,
});
}
apply(&mut membership, entry, recovery, previous)?;
previous = entry.link;
}
Ok(membership)
}
pub fn encode(entries: &[Entry]) -> Result<Vec<u8>, IdentityError> {
encode_framed(entries, Framing::Current)
}
fn encode_framed(entries: &[Entry], framing: Framing) -> Result<Vec<u8>, IdentityError> {
let mut out = Vec::new();
let mut encoder = minicbor::Encoder::new(&mut out);
encoder
.array(entries.len() as u64)
.map_err(|_| IdentityError::Malformed)?;
for entry in entries {
encoder
.array(framing.header())
.and_then(|e| e.u64(entry.sequence))
.and_then(|e| e.u8(entry.event.tag()))
.map_err(|_| IdentityError::Malformed)?;
match &entry.event {
Event::Create { device, label }
| Event::Enrol { device, label }
| Event::Recover { device, label } => {
encoder
.bytes(device)
.and_then(|e| e.str(label))
.map_err(|_| IdentityError::Malformed)?;
}
Event::Revoke { device } => {
encoder
.bytes(device)
.and_then(|e| e.str(""))
.map_err(|_| IdentityError::Malformed)?;
}
}
encoder
.bytes(&entry.signer)
.and_then(|e| e.bytes(&entry.link))
.and_then(|e| e.bytes(&entry.signature))
.map_err(|_| IdentityError::Malformed)?;
}
Ok(out)
}
pub fn decode(bytes: &[u8]) -> Result<Vec<Entry>, IdentityError> {
let mut decoder = minicbor::Decoder::new(bytes);
let count = decoder
.array()
.map_err(|_| IdentityError::Malformed)?
.ok_or(IdentityError::Malformed)?;
if count > MAX_ENTRIES as u64 {
return Err(IdentityError::TooManyEntries(count as usize));
}
let mut entries = Vec::with_capacity((count as usize).min(bytes.len() / MIN_ENTRY_BYTES));
let mut framing: Option<Framing> = None;
for _ in 0..count {
let header = decoder
.array()
.map_err(|_| IdentityError::Malformed)?
.ok_or(IdentityError::Malformed)?;
let this = match header {
ENTRY_FIELDS => Framing::Current,
LEGACY_ENTRY_HEADER => Framing::Legacy,
_ => return Err(IdentityError::Malformed),
};
if framing.is_some_and(|seen| seen != this) {
return Err(IdentityError::Malformed);
}
framing = Some(this);
let sequence = decoder.u64().map_err(|_| IdentityError::Malformed)?;
let tag = decoder.u8().map_err(|_| IdentityError::Malformed)?;
let payload = decoder
.bytes()
.map_err(|_| IdentityError::Malformed)?
.to_vec();
let label = decoder.str().map_err(|_| IdentityError::Malformed)?;
if label.len() > MAX_LABEL_BYTES {
return Err(IdentityError::LabelTooLong);
}
let label = label.to_owned();
let event = match tag {
1 => Event::Create {
device: payload,
label,
},
2 => Event::Enrol {
device: payload,
label,
},
3 => Event::Revoke {
device: payload
.as_slice()
.try_into()
.map_err(|_| IdentityError::Malformed)?,
},
4 => Event::Recover {
device: payload,
label,
},
_ => return Err(IdentityError::Malformed),
};
let signer: DeviceId = decoder
.bytes()
.map_err(|_| IdentityError::Malformed)?
.try_into()
.map_err(|_| IdentityError::Malformed)?;
let link: [u8; 32] = decoder
.bytes()
.map_err(|_| IdentityError::Malformed)?
.try_into()
.map_err(|_| IdentityError::Malformed)?;
let signature = decoder
.bytes()
.map_err(|_| IdentityError::Malformed)?
.to_vec();
if signature.len() != SIGNATURE_LENGTH {
return Err(IdentityError::Malformed);
}
entries.push(Entry {
sequence,
event,
signer,
link,
signature,
});
}
if decoder.position() != bytes.len() {
return Err(IdentityError::Malformed);
}
if encode_framed(&entries, framing.unwrap_or(Framing::Current))? != bytes {
return Err(IdentityError::Malformed);
}
Ok(entries)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_huge_declared_count_reserves_nothing() {
let mut bytes = Vec::new();
minicbor::Encoder::new(&mut bytes).array(99_999).unwrap();
assert!(matches!(decode(&bytes), Err(IdentityError::Malformed)));
let mut huge = Vec::new();
minicbor::Encoder::new(&mut huge).array(u64::MAX).unwrap();
assert!(matches!(
decode(&huge),
Err(IdentityError::TooManyEntries(_))
));
}
#[test]
fn an_oversized_label_is_refused() {
let label = "x".repeat(MAX_LABEL_BYTES + 1);
let mut bytes = Vec::new();
let mut encoder = minicbor::Encoder::new(&mut bytes);
encoder
.array(1)
.and_then(|e| e.array(6))
.and_then(|e| e.u64(0))
.and_then(|e| e.u8(1))
.and_then(|e| e.bytes(&[0u8; 32]))
.and_then(|e| e.str(&label))
.unwrap();
assert!(matches!(decode(&bytes), Err(IdentityError::LabelTooLong)));
}
fn signer(seed: u8) -> SigningIdentity {
SigningIdentity::from_bytes(&[seed; 32]).expect("32 bytes is a seed")
}
fn sample_log() -> IdentityLog {
let founder = signer(1);
let phone = signer(2);
let recovery = signer(3);
let mut log =
IdentityLog::create(&founder, "desktop", &recovery.verifying_key()).expect("create");
log.enrol(&founder, &phone.verifying_key(), "phone")
.expect("enrol");
log.revoke(&founder, device_id(&phone.verifying_key()))
.expect("revoke");
log
}
fn entry_header_offsets(bytes: &[u8]) -> Vec<usize> {
let mut decoder = minicbor::Decoder::new(bytes);
let count = decoder.array().unwrap().unwrap();
let mut offsets = Vec::new();
for _ in 0..count {
offsets.push(decoder.position());
decoder.array().unwrap();
for _ in 0..ENTRY_FIELDS {
decoder.skip().unwrap();
}
}
offsets
}
#[test]
fn every_entry_is_written_as_an_array_of_seven() {
let bytes = encode(sample_log().entries()).unwrap();
assert_eq!(&bytes[..7], &[0x83, 0x87, 0x00, 0x01, 0x59, 0x07, 0xc0]);
for offset in entry_header_offsets(&bytes) {
assert_eq!(bytes[offset], 0x87, "entry at {offset} is not array(7)");
}
}
#[test]
fn the_current_framing_round_trips_and_verifies() {
let log = sample_log();
let bytes = encode(log.entries()).unwrap();
let decoded = decode(&bytes).unwrap();
assert_eq!(decoded, log.entries());
let membership = IdentityLog::verify(&decoded, &signer(3).verifying_key()).expect("verify");
assert_eq!(membership.len(), 1);
}
#[test]
fn a_legacy_log_decodes_to_the_same_entries() {
let log = sample_log();
let legacy = encode_framed(log.entries(), Framing::Legacy).unwrap();
assert_eq!(&legacy[..2], &[0x83, 0x86]);
let decoded = decode(&legacy).unwrap();
assert_eq!(decoded, log.entries());
IdentityLog::verify(&decoded, &signer(3).verifying_key()).expect("verify");
let upgraded = encode(&decoded).unwrap();
assert_eq!(
IdentityLog::from_entries(decode(&upgraded).unwrap(), signer(3).verifying_key())
.unwrap()
.head(),
log.head()
);
}
#[test]
fn a_log_that_mixes_framings_is_refused() {
let entries = sample_log().entries().to_vec();
for framing in [Framing::Current, Framing::Legacy] {
let mut bytes = encode_framed(&entries, framing).unwrap();
let offsets = entry_header_offsets(&bytes);
for &offset in &offsets {
let original = bytes[offset];
bytes[offset] = if original == 0x87 { 0x86 } else { 0x87 };
assert_eq!(
decode(&bytes),
Err(IdentityError::Malformed),
"mixed framing accepted at {offset}"
);
bytes[offset] = original;
}
}
}
#[test]
fn six_items_under_a_six_header_are_refused() {
let entries = sample_log().entries()[..1].to_vec();
let legacy = encode_framed(&entries, Framing::Legacy).unwrap();
let truncated = &legacy[..legacy.len() - (SIGNATURE_LENGTH + 3)];
assert_eq!(decode(truncated), Err(IdentityError::Malformed));
for header in [0x85u8, 0x88] {
let mut other = legacy.clone();
other[1] = header;
assert_eq!(decode(&other), Err(IdentityError::Malformed));
}
}
}