1use hide_crypto::{CryptoError, RecipientPublic, RecipientSecret};
32use sha2::{Digest, Sha256};
33use thiserror::Error;
34use zeroize::Zeroize;
35
36pub type EpochNumber = u64;
38
39const MAX_CHAIN_ENTRIES: usize = 1_000_000;
42
43const MIN_RECORD_BYTES: usize = 4;
47
48const CHAIN_INFO: &[u8] = b"HIDE/0.6 epoch chain";
49
50const PUBLIC_KEY_LENGTH: usize = 1216;
52
53#[derive(Debug, Error, PartialEq, Eq)]
54pub enum EpochError {
55 #[error("epoch {0} has been erased and can never be recovered")]
56 Erased(EpochNumber),
57 #[error("epoch {0} is not in this chain")]
58 UnknownEpoch(EpochNumber),
59 #[error("epoch chain is malformed")]
60 Malformed,
61 #[error("epoch chain claims {0} entries, which exceeds the limit")]
62 TooManyEntries(usize),
63 #[error("epoch {expected} was expected but the chain links to {found}")]
64 BrokenLink {
65 expected: EpochNumber,
66 found: EpochNumber,
67 },
68 #[error("the chain's hash linkage does not verify at epoch {0}")]
69 BrokenHash(EpochNumber),
70 #[error("epoch {number} carries a {actual}-byte key; {expected} expected")]
71 WrongKeyLength {
72 number: EpochNumber,
73 expected: usize,
74 actual: usize,
75 },
76 #[error("the secret held for epoch {0} does not match the chain's public key")]
77 SecretMismatch(EpochNumber),
78 #[error("epoch {0}'s secret was supplied twice")]
79 DuplicateSecret(EpochNumber),
80 #[error("cryptographic operation failed: {0}")]
81 Crypto(String),
82}
83
84impl From<CryptoError> for EpochError {
85 fn from(error: CryptoError) -> Self {
86 Self::Crypto(error.to_string())
87 }
88}
89
90struct EpochSecret {
95 number: EpochNumber,
96 secret: Option<RecipientSecret>,
97}
98
99impl EpochSecret {
100 fn erase(&mut self) {
102 self.secret = None;
103 }
104}
105
106#[derive(Debug, Clone, PartialEq, Eq)]
108pub struct EpochRecord {
109 pub number: EpochNumber,
110 pub public_key: Vec<u8>,
111 pub link: [u8; 32],
114}
115
116fn link_for(previous: &[u8; 32], number: EpochNumber, public_key: &[u8]) -> [u8; 32] {
119 let mut hasher = Sha256::new();
120 hasher.update(CHAIN_INFO);
121 hasher.update(previous);
122 hasher.update(number.to_be_bytes());
123 hasher.update((public_key.len() as u64).to_be_bytes());
127 hasher.update(public_key);
128 hasher.finalize().into()
129}
130
131pub struct EpochChain {
133 records: Vec<EpochRecord>,
134 secrets: Vec<EpochSecret>,
135}
136
137impl EpochChain {
138 pub fn new() -> Result<Self, EpochError> {
140 let mut chain = Self {
141 records: Vec::new(),
142 secrets: Vec::new(),
143 };
144 chain.advance()?;
145 Ok(chain)
146 }
147
148 pub fn advance(&mut self) -> Result<EpochNumber, EpochError> {
151 let number = self.records.len() as EpochNumber;
152 if self.records.len() >= MAX_CHAIN_ENTRIES {
153 return Err(EpochError::TooManyEntries(self.records.len()));
154 }
155
156 let secret = RecipientSecret::generate()?;
157 let public_key = secret.public_key()?.to_bytes();
158 let previous = self.records.last().map_or([0u8; 32], |record| record.link);
159
160 self.records.push(EpochRecord {
161 number,
162 link: link_for(&previous, number, &public_key),
163 public_key,
164 });
165 self.secrets.push(EpochSecret {
166 number,
167 secret: Some(secret),
168 });
169 Ok(number)
170 }
171
172 pub fn current(&self) -> EpochNumber {
174 (self.records.len() as EpochNumber).saturating_sub(1)
175 }
176
177 pub fn public_key(&self, number: EpochNumber) -> Result<&[u8], EpochError> {
179 self.records
180 .get(number as usize)
181 .map(|record| record.public_key.as_slice())
182 .ok_or(EpochError::UnknownEpoch(number))
183 }
184
185 pub fn secret(&self, number: EpochNumber) -> Result<&RecipientSecret, EpochError> {
187 let held = self
188 .secrets
189 .get(number as usize)
190 .ok_or(EpochError::UnknownEpoch(number))?;
191 held.secret.as_ref().ok_or(EpochError::Erased(number))
192 }
193
194 pub fn erase(&mut self, number: EpochNumber) -> Result<(), EpochError> {
196 let held = self
197 .secrets
198 .get_mut(number as usize)
199 .ok_or(EpochError::UnknownEpoch(number))?;
200 held.erase();
201 Ok(())
202 }
203
204 pub fn erase_before(&mut self, keep_from: EpochNumber) -> usize {
206 let mut erased = 0;
207 for held in &mut self.secrets {
208 if held.number < keep_from && held.secret.is_some() {
209 held.erase();
210 erased += 1;
211 }
212 }
213 erased
214 }
215
216 pub fn is_readable(&self, number: EpochNumber) -> bool {
218 self.secrets
219 .get(number as usize)
220 .is_some_and(|held| held.secret.is_some())
221 }
222
223 pub fn records(&self) -> &[EpochRecord] {
225 &self.records
226 }
227
228 pub fn head(&self) -> [u8; 32] {
232 self.records.last().map_or([0u8; 32], |record| record.link)
233 }
234
235 pub fn secrets(&self) -> impl Iterator<Item = (EpochNumber, &RecipientSecret)> + '_ {
239 self.secrets
240 .iter()
241 .filter_map(|held| held.secret.as_ref().map(|secret| (held.number, secret)))
242 }
243
244 pub fn restore(
250 records: Vec<EpochRecord>,
251 secrets: impl IntoIterator<Item = (EpochNumber, RecipientSecret)>,
252 ) -> Result<Self, EpochError> {
253 Self::verify(&records)?;
254 if records.is_empty() {
255 return Err(EpochError::Malformed);
256 }
257 let mut held: Vec<EpochSecret> = records
258 .iter()
259 .map(|record| EpochSecret {
260 number: record.number,
261 secret: None,
262 })
263 .collect();
264 for (number, secret) in secrets {
265 let index = usize::try_from(number)
267 .ok()
268 .filter(|index| *index < records.len())
269 .ok_or(EpochError::UnknownEpoch(number))?;
270 if secret.public_key()?.to_bytes() != records[index].public_key {
271 return Err(EpochError::SecretMismatch(number));
272 }
273 let slot = &mut held[index];
274 if slot.secret.is_some() {
275 return Err(EpochError::DuplicateSecret(number));
276 }
277 slot.secret = Some(secret);
278 }
279 Ok(Self {
280 records,
281 secrets: held,
282 })
283 }
284
285 pub fn verify(records: &[EpochRecord]) -> Result<(), EpochError> {
288 if records.len() > MAX_CHAIN_ENTRIES {
289 return Err(EpochError::TooManyEntries(records.len()));
290 }
291 let mut previous = [0u8; 32];
292 for (index, record) in records.iter().enumerate() {
293 let expected = index as EpochNumber;
294 if record.number != expected {
295 return Err(EpochError::BrokenLink {
296 expected,
297 found: record.number,
298 });
299 }
300 if record.public_key.len() != PUBLIC_KEY_LENGTH {
304 return Err(EpochError::WrongKeyLength {
305 number: record.number,
306 expected: PUBLIC_KEY_LENGTH,
307 actual: record.public_key.len(),
308 });
309 }
310 let link = link_for(&previous, record.number, &record.public_key);
311 if link != record.link {
312 return Err(EpochError::BrokenHash(record.number));
313 }
314 previous = record.link;
315 }
316 Ok(())
317 }
318}
319
320impl Drop for EpochChain {
321 fn drop(&mut self) {
322 for held in &mut self.secrets {
323 held.erase();
324 }
325 }
326}
327
328pub fn encode_records(records: &[EpochRecord]) -> Result<Vec<u8>, EpochError> {
332 let mut out = Vec::new();
333 let mut encoder = minicbor::Encoder::new(&mut out);
334 encoder
335 .array(records.len() as u64)
336 .map_err(|_| EpochError::Malformed)?;
337 for record in records {
338 encoder
339 .array(3)
340 .and_then(|e| e.u64(record.number))
341 .and_then(|e| e.bytes(&record.public_key))
342 .and_then(|e| e.bytes(&record.link))
343 .map_err(|_| EpochError::Malformed)?;
344 }
345 Ok(out)
346}
347
348pub fn decode_records(bytes: &[u8]) -> Result<Vec<EpochRecord>, EpochError> {
349 let mut decoder = minicbor::Decoder::new(bytes);
350 let count = decoder
351 .array()
352 .map_err(|_| EpochError::Malformed)?
353 .ok_or(EpochError::Malformed)?;
354 if count > MAX_CHAIN_ENTRIES as u64 {
356 return Err(EpochError::TooManyEntries(count as usize));
357 }
358
359 let mut records = Vec::with_capacity((count as usize).min(bytes.len() / MIN_RECORD_BYTES));
363 for _ in 0..count {
364 let fields = decoder
365 .array()
366 .map_err(|_| EpochError::Malformed)?
367 .ok_or(EpochError::Malformed)?;
368 if fields != 3 {
369 return Err(EpochError::Malformed);
370 }
371 let number = decoder.u64().map_err(|_| EpochError::Malformed)?;
372 let public_key = decoder.bytes().map_err(|_| EpochError::Malformed)?.to_vec();
373 let link_bytes = decoder.bytes().map_err(|_| EpochError::Malformed)?;
374 let link: [u8; 32] = link_bytes.try_into().map_err(|_| EpochError::Malformed)?;
375 records.push(EpochRecord {
376 number,
377 public_key,
378 link,
379 });
380 }
381 if decoder.position() != bytes.len() {
382 return Err(EpochError::Malformed);
383 }
384 if encode_records(&records)? != bytes {
389 return Err(EpochError::Malformed);
390 }
391 Ok(records)
392}
393
394pub fn recipient_for(
396 records: &[EpochRecord],
397 number: EpochNumber,
398) -> Result<RecipientPublic, EpochError> {
399 let record = records
400 .get(number as usize)
401 .ok_or(EpochError::UnknownEpoch(number))?;
402 Ok(RecipientPublic::from_bytes(&record.public_key)?)
403}
404
405pub fn erase_bytes(buffer: &mut [u8]) {
408 buffer.zeroize();
409}
410
411#[cfg(test)]
412mod tests {
413 use super::*;
414
415 #[test]
416 fn a_new_chain_starts_at_epoch_zero() {
417 let chain = EpochChain::new().unwrap();
418 assert_eq!(chain.current(), 0);
419 assert!(chain.is_readable(0));
420 }
421
422 #[test]
425 fn a_huge_declared_count_reserves_nothing() {
426 let mut bytes = Vec::new();
428 minicbor::Encoder::new(&mut bytes).array(999_999).unwrap();
429 assert_eq!(decode_records(&bytes), Err(EpochError::Malformed));
430 let mut huge = Vec::new();
432 minicbor::Encoder::new(&mut huge).array(u64::MAX).unwrap();
433 assert!(matches!(
434 decode_records(&huge),
435 Err(EpochError::TooManyEntries(_))
436 ));
437 }
438
439 #[test]
440 fn advancing_keeps_the_previous_epoch_readable() {
441 let mut chain = EpochChain::new().unwrap();
442 chain.advance().unwrap();
443 assert_eq!(chain.current(), 1);
444 assert!(chain.is_readable(0));
446 assert!(chain.is_readable(1));
447 }
448
449 #[test]
450 fn erasure_is_irreversible() {
451 let mut chain = EpochChain::new().unwrap();
452 chain.advance().unwrap();
453 chain.erase(0).unwrap();
454
455 assert!(!chain.is_readable(0));
456 assert_eq!(chain.secret(0).err(), Some(EpochError::Erased(0)));
457 assert!(chain.public_key(0).is_ok());
459 chain.advance().unwrap();
461 assert_eq!(chain.secret(0).err(), Some(EpochError::Erased(0)));
462 }
463
464 #[test]
465 fn each_epoch_has_a_distinct_key() {
466 let mut chain = EpochChain::new().unwrap();
467 chain.advance().unwrap();
468 chain.advance().unwrap();
469 let zero = chain.public_key(0).unwrap().to_vec();
470 let one = chain.public_key(1).unwrap().to_vec();
471 let two = chain.public_key(2).unwrap().to_vec();
472 assert_ne!(zero, one);
473 assert_ne!(one, two);
474 assert_ne!(zero, two);
475 }
476
477 #[test]
480 fn an_erased_epoch_is_not_derivable_from_later_ones() {
481 let mut chain = EpochChain::new().unwrap();
482 chain.advance().unwrap();
483
484 let erased_public = chain.public_key(0).unwrap().to_vec();
485 chain.erase(0).unwrap();
486
487 let later = chain.secret(1).unwrap().export_test_secret();
489 let records = chain.records().to_vec();
490
491 let public_from_later = RecipientSecret::from_bytes(&later)
494 .unwrap()
495 .public_key()
496 .unwrap()
497 .to_bytes();
498 assert_ne!(public_from_later, erased_public);
499 for record in &records {
500 if record.number == 0 {
501 continue;
502 }
503 assert_ne!(record.public_key, erased_public);
504 }
505 }
506
507 #[test]
508 fn erase_before_keeps_the_retention_window() {
509 let mut chain = EpochChain::new().unwrap();
510 for _ in 0..4 {
511 chain.advance().unwrap();
512 }
513 let erased = chain.erase_before(3);
514 assert_eq!(erased, 3);
515 assert!(!chain.is_readable(0));
516 assert!(!chain.is_readable(2));
517 assert!(chain.is_readable(3));
518 assert!(chain.is_readable(4));
519 }
520
521 #[test]
522 fn erase_before_is_idempotent() {
523 let mut chain = EpochChain::new().unwrap();
524 chain.advance().unwrap();
525 assert_eq!(chain.erase_before(1), 1);
526 assert_eq!(chain.erase_before(1), 0);
528 }
529
530 #[test]
531 fn a_chain_verifies_against_itself() {
532 let mut chain = EpochChain::new().unwrap();
533 for _ in 0..3 {
534 chain.advance().unwrap();
535 }
536 EpochChain::verify(chain.records()).unwrap();
537 }
538
539 #[test]
540 fn a_reordered_chain_is_refused() {
541 let mut chain = EpochChain::new().unwrap();
542 chain.advance().unwrap();
543 let mut records = chain.records().to_vec();
544 records.swap(0, 1);
545 assert!(EpochChain::verify(&records).is_err());
546 }
547
548 #[test]
549 fn a_spliced_out_epoch_is_refused() {
550 let mut chain = EpochChain::new().unwrap();
551 for _ in 0..3 {
552 chain.advance().unwrap();
553 }
554 let mut records = chain.records().to_vec();
555 records.remove(1);
556 assert!(EpochChain::verify(&records).is_err());
557 }
558
559 #[test]
564 fn an_entry_cannot_be_transplanted_from_another_chain() {
565 let mut ours = EpochChain::new().unwrap();
566 ours.advance().unwrap();
567 let mut theirs = EpochChain::new().unwrap();
568 theirs.advance().unwrap();
569
570 let mut records = ours.records().to_vec();
572 records[1] = theirs.records()[1].clone();
573
574 assert_eq!(
575 EpochChain::verify(&records).unwrap_err(),
576 EpochError::BrokenHash(1)
577 );
578 }
579
580 #[test]
583 fn links_differ_even_for_the_same_epoch_number() {
584 let ours = EpochChain::new().unwrap();
585 let theirs = EpochChain::new().unwrap();
586 assert_ne!(ours.records()[0].link, theirs.records()[0].link);
587 }
588
589 #[test]
595 fn a_different_key_gives_a_different_link() {
596 let mut key_a = vec![0u8; PUBLIC_KEY_LENGTH];
597 key_a[0] = 0xFF;
598 let key_b = vec![0u8; PUBLIC_KEY_LENGTH];
599 assert_ne!(
600 link_for(&[0u8; 32], 0, &key_a),
601 link_for(&[0u8; 32], 0, &key_b)
602 );
603 }
604
605 #[test]
606 fn a_different_epoch_number_gives_a_different_link() {
607 let key = vec![0u8; PUBLIC_KEY_LENGTH];
608 assert_ne!(link_for(&[0u8; 32], 0, &key), link_for(&[0u8; 32], 1, &key));
609 }
610
611 #[test]
612 fn a_wrong_length_key_never_reaches_hashing() {
613 let short = vec![0xAB; PUBLIC_KEY_LENGTH - 1];
614 let records = vec![EpochRecord {
615 number: 0,
616 link: link_for(&[0u8; 32], 0, &short),
617 public_key: short.clone(),
618 }];
619 assert_eq!(
620 EpochChain::verify(&records).unwrap_err(),
621 EpochError::WrongKeyLength {
622 number: 0,
623 expected: PUBLIC_KEY_LENGTH,
624 actual: short.len(),
625 }
626 );
627 }
628
629 #[test]
630 fn a_real_chain_carries_full_length_keys() {
631 let chain = EpochChain::new().unwrap();
632 assert_eq!(chain.public_key(0).unwrap().len(), PUBLIC_KEY_LENGTH);
633 }
634
635 #[test]
636 fn a_substituted_key_is_refused() {
637 let mut chain = EpochChain::new().unwrap();
638 chain.advance().unwrap();
639 let mut records = chain.records().to_vec();
640 let other = RecipientSecret::generate()
641 .unwrap()
642 .public_key()
643 .unwrap()
644 .to_bytes();
645 records[1].public_key = other;
646 assert_eq!(
647 EpochChain::verify(&records).unwrap_err(),
648 EpochError::BrokenHash(1)
649 );
650 }
651
652 #[test]
653 fn an_appended_forgery_is_refused() {
654 let mut chain = EpochChain::new().unwrap();
655 let mut records = chain.records().to_vec();
656 chain.advance().unwrap();
657 records.push(EpochRecord {
659 number: 1,
660 public_key: RecipientSecret::generate()
661 .unwrap()
662 .public_key()
663 .unwrap()
664 .to_bytes(),
665 link: [0u8; 32],
666 });
667 assert_eq!(
668 EpochChain::verify(&records).unwrap_err(),
669 EpochError::BrokenHash(1)
670 );
671 }
672
673 #[test]
674 fn records_round_trip_through_cbor() {
675 let mut chain = EpochChain::new().unwrap();
676 for _ in 0..3 {
677 chain.advance().unwrap();
678 }
679 let encoded = encode_records(chain.records()).unwrap();
680 let decoded = decode_records(&encoded).unwrap();
681 assert_eq!(decoded, chain.records());
682 EpochChain::verify(&decoded).unwrap();
683 }
684
685 #[test]
686 fn trailing_bytes_are_refused() {
687 let chain = EpochChain::new().unwrap();
688 let mut encoded = encode_records(chain.records()).unwrap();
689 encoded.push(0);
690 assert_eq!(decode_records(&encoded).unwrap_err(), EpochError::Malformed);
691 }
692
693 #[test]
694 fn a_non_canonical_encoding_is_refused() {
695 assert_eq!(
699 decode_records(&[0x9a, 0, 0, 0, 0]).unwrap_err(),
700 EpochError::Malformed
701 );
702
703 let mut chain = EpochChain::new().unwrap();
705 chain.advance().unwrap();
706 let canonical = encode_records(chain.records()).unwrap();
707 assert_eq!(canonical[0], 0x82, "two records encode as a short array");
708 let mut widened = vec![0x98, 0x02];
709 widened.extend_from_slice(&canonical[1..]);
710 assert_eq!(decode_records(&widened).unwrap_err(), EpochError::Malformed);
711 assert_eq!(decode_records(&canonical).unwrap().len(), 2);
712 }
713
714 #[test]
715 fn a_truncated_encoding_is_refused() {
716 let mut chain = EpochChain::new().unwrap();
717 chain.advance().unwrap();
718 let encoded = encode_records(chain.records()).unwrap();
719 for cut in 1..encoded.len() {
720 assert!(
721 decode_records(&encoded[..cut]).is_err(),
722 "accepted a {cut}-byte prefix"
723 );
724 }
725 }
726
727 #[test]
728 fn an_absurd_entry_count_is_refused_before_allocating() {
729 let mut out = Vec::new();
731 let mut encoder = minicbor::Encoder::new(&mut out);
732 encoder.array(u32::MAX as u64).unwrap();
733 assert!(matches!(
734 decode_records(&out).unwrap_err(),
735 EpochError::TooManyEntries(_)
736 ));
737 }
738
739 #[test]
740 fn an_unknown_epoch_is_named_in_the_error() {
741 let chain = EpochChain::new().unwrap();
742 assert_eq!(chain.secret(9).err(), Some(EpochError::UnknownEpoch(9)));
743 assert_eq!(
744 chain.public_key(9).unwrap_err(),
745 EpochError::UnknownEpoch(9)
746 );
747 }
748}