Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_crypto/src/pad.rs

7.2 KiB, 1 run

created by r1870400018:76443, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Length padding, so that a ciphertext's size says little about its plaintext's.
2//!
3//! [`padme_len`] is Padmé, Algorithm 1 of Nikitin et al., "Reducing Metadata Leakage from
4//! Encrypted Files and Communication with PURBs" (PoPETs 2019, arXiv 1806.03160, §4.4). A padded
5//! length keeps no more significant bits in its mantissa than its exponent holds, so the lengths
6//! up to M fall into O(log log M) buckets, and the overhead is below 2^(E−S)/L ≈ 1/(2 log₂ L):
7//! under 12% everywhere and falling as L grows. The paper quotes +11.11% (9 bytes to 10) as the
8//! maximum, but its Algorithm 1 pads 129 bytes to 144, +11.63%, the true maximum.
9//!
10//! [`PadRule`] frames a body as `u32 big-endian length ‖ body ‖ zeros` and pads the whole frame
11//! by the rule a [`PadConfig`] names, never below its floor; [`unpad`] needs no rule, so a
12//! reader is not tied to the writer's configuration. Pad before sealing and unpad after
13//! opening: the padding hides a length only inside an authenticated cipher.
14//!
15//! The JS twin is `fe2o3_crypto/js/pad.mjs`; both check `tests/data/padme_vectors.txt`, made
16//! by an oracle written from the paper alone (`tests/data/gen_padme_vectors.py`).
17
18use oxedyne_fe2o3_core::prelude::*;
19use oxedyne_fe2o3_jdat::{
20 prelude::*,
21 cfg::Config,
22};
23
24use std::collections::BTreeMap; // the ToDatMap derive names it
25
26/// Bytes of the length prefix. // fixed: the frame format, a u32 big-endian body length
27pub const PREFIX_LEN: usize = 4;
28
29/// Padmé's padded length for `len` bytes. Below 2, where ⌊log₂ L⌋ is undefined, the length
30/// stands, as the paper's buckets begin at 2.
31pub fn padme_len(len: u64) -> Outcome<u64> {
32 if len < 2 {
33 return Ok(len);
34 }
35 let e = 63 - len.leading_zeros() as u64; // ⌊log₂ L⌋, the exponent
36 let s = 64 - e.leading_zeros() as u64; // ⌊log₂ E⌋ + 1, the bits that hold E
37 let z = e - s; // low bits forced to zero
38 let m = (1u64 << z) - 1;
39 match len.checked_add(m) {
40 Some(v) => Ok(v & !m),
41 None => Err(err!("Padmé cannot pad a length of {} within 64 bits.", len;
42 Overflow, Size)),
43 }
44}
45
46/// How a frame's length is rounded up, each never below `floor` bytes.
47#[derive(Clone, Copy, Debug, Eq, PartialEq)]
48pub enum PadRule {
49 Padme { floor: u64 }, // Padmé buckets, sizes visible to ~12%
50 PowerOfTwo { floor: u64 }, // next power of two, up to +100%
51 Block { floor: u64, block: u64 }, // whole blocks, e.g. constant 1 MiB frames
52}
53
54impl PadRule {
55
56 /// The rounded length of a frame of `len` bytes, the prefix included.
57 pub fn round(&self, len: u64) -> Outcome<u64> {
58 let (got, floor) = match *self {
59 Self::Padme { floor } => (res!(padme_len(len)), floor),
60 Self::PowerOfTwo { floor } => {
61 let p = if len <= 1 { 1 } else {
62 match len.checked_next_power_of_two() {
63 Some(p) => p,
64 None => return Err(err!(
65 "No power of two above {} fits in 64 bits.", len; Overflow, Size)),
66 }
67 };
68 (p, floor)
69 }
70 Self::Block { floor, block } => {
71 if block == 0 {
72 return Err(err!("A block pad rule needs a block of at least one byte.";
73 Invalid, Input, Configuration));
74 }
75 let n = len / block + if len % block == 0 { 0 } else { 1 };
76 match n.checked_mul(block) {
77 Some(v) => (v, floor),
78 None => return Err(err!(
79 "{} bytes in blocks of {} overflow 64 bits.", len, block; Overflow, Size)),
80 }
81 }
82 };
83 Ok(got.max(floor))
84 }
85
86 /// The length of the frame [`Self::pad`] makes for a body of `body_len` bytes.
87 pub fn framed_len(&self, body_len: u64) -> Outcome<u64> {
88 if body_len > u32::MAX as u64 {
89 return Err(err!("A body of {} bytes is over the frame's u32 length prefix.", body_len;
90 TooBig, Size));
91 }
92 self.round(PREFIX_LEN as u64 + body_len)
93 }
94
95 /// `body` framed and padded: its length as a big-endian u32, the body, then zeros.
96 pub fn pad(&self, body: &[u8]) -> Outcome<Vec<u8>> {
97 let total = res!(self.framed_len(body.len() as u64));
98 let total = match usize::try_from(total) {
99 Ok(t) => t,
100 Err(_) => return Err(err!("A padded frame of {} bytes does not fit in memory here.",
101 total; TooBig, Size)),
102 };
103 let mut v = Vec::with_capacity(total);
104 v.extend_from_slice(&(body.len() as u32).to_be_bytes());
105 v.extend_from_slice(body);
106 v.resize(total, 0);
107 Ok(v)
108 }
109}
110
111/// The body inside a frame [`PadRule::pad`] made. Refused when the frame is shorter than its
112/// prefix, the prefix claims more than the frame holds, or the fill is not all zeros.
113pub fn unpad(frame: &[u8]) -> Outcome<&[u8]> {
114 if frame.len() < PREFIX_LEN {
115 return Err(err!("A padded frame of {} bytes is shorter than its {}-byte length prefix.",
116 frame.len(), PREFIX_LEN; Invalid, Input, Size));
117 }
118 let n = u32::from_be_bytes([frame[0], frame[1], frame[2], frame[3]]) as usize;
119 let end = match PREFIX_LEN.checked_add(n) {
120 Some(e) if e <= frame.len() => e,
121 _ => return Err(err!("A padded frame of {} bytes claims a body of {} bytes.",
122 frame.len(), n; Invalid, Input, Size)),
123 };
124 if frame[end..].iter().any(|b| *b != 0) {
125 return Err(err!("A padded frame's fill after its {}-byte body is not all zeros.", n;
126 Invalid, Input));
127 }
128 Ok(&frame[PREFIX_LEN..end])
129}
130
131/// The padding an app's configuration names: `rule` is `padme`, `pow2` or `block`; `floor` is
132/// the least frame in bytes; `block` is the block size, read only by `block`.
133#[derive(Clone, Debug, Eq, PartialEq, FromDatMap, ToDatMap)]
134pub struct PadConfig {
135 pub rule: String,
136 pub floor: u64,
137 pub block: u64,
138}
139
140impl Default for PadConfig {
141 fn default() -> Self {
142 Self {
143 rule: "padme".to_string(),
144 floor: 256,
145 block: 1_048_576, // 1 MiB
146 }
147 }
148}
149
150impl Config for PadConfig {
151 fn check_and_fix(&mut self) -> Outcome<()> {
152 let _ = res!(self.rule());
153 Ok(())
154 }
155}
156
157impl PadConfig {
158
159 /// The rule this configuration names, refused when the name is unknown or a block is empty.
160 pub fn rule(&self) -> Outcome<PadRule> {
161 let floor = self.floor;
162 match self.rule.as_str() {
163 "padme" => Ok(PadRule::Padme { floor }),
164 "pow2" => Ok(PadRule::PowerOfTwo { floor }),
165 "block" => {
166 if self.block == 0 {
167 return Err(err!("The pad rule 'block' needs 'block' of at least one byte.";
168 Invalid, Input, Configuration));
169 }
170 Ok(PadRule::Block { floor, block: self.block })
171 }
172 other => Err(err!("The pad rule {:?} is not one of padme, pow2 or block.", other;
173 Invalid, Input, Configuration)),
174 }
175 }
176}