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 | |
| 18 | use oxedyne_fe2o3_core::prelude::*; |
| 19 | use oxedyne_fe2o3_jdat::{ |
| 20 | prelude::*, |
| 21 | cfg::Config, |
| 22 | }; |
| 23 | |
| 24 | use 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 |
| 27 | pub 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. |
| 31 | pub 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)] |
| 48 | pub 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 | |
| 54 | impl 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. |
| 113 | pub 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)] |
| 134 | pub struct PadConfig { |
| 135 | pub rule: String, |
| 136 | pub floor: u64, |
| 137 | pub block: u64, |
| 138 | } |
| 139 | |
| 140 | impl 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 | |
| 150 | impl Config for PadConfig { |
| 151 | fn check_and_fix(&mut self) -> Outcome<()> { |
| 152 | let _ = res!(self.rule()); |
| 153 | Ok(()) |
| 154 | } |
| 155 | } |
| 156 | |
| 157 | impl 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 | } |