Repository navigation
Chained scheme: pad strings to a length bucket to hide exact length #104
Description
Problem
Every ciphertext of the chained scheme (OreAes128Bit6Chained, #83) reveals the exact UTF-8 byte length of its plaintext. The header stores the block count, and for strings the count is ceil(8n/6), which is strictly increasing in n. The ciphertext size gives the same number: 4 + 25*count + 16 bytes for a full ciphertext and 4 + 17*count for a left. The right half alone is count * 8 bytes, so a future right-only storage format would still leak it.
This leak is per row and needs no comparison or query. In short, low-entropy columns (country codes, status values, first names), values are often unique by length or close to it, and length plus common-prefix length is a strong signal for frequency analysis. The review of #83 raised it; #83 documents it in the leakage profile.
Resolution
The original proposal (Padmé buckets, and a 65th pad symbol below every real symbol) was wrong on both counts. The comments below record the analysis; this section records what landed, on branch feat/chained-padding.
No pad symbol is needed. Strings are padded with NUL bytes. A NUL byte decomposes to zero 6-bit blocks, the same zero fill the decomposition already applies to its last partial block, so order and equality hold for every string that does not end in NUL:
- Order. Where the shorter of two strings ends, the longer one has a non-zero bit somewhere in its remaining bytes, because its last byte is not NUL. The shorter string has zeros there (padding), so it sorts first, as "shorter sorts first" requires. Where two strings differ within their common length, both carry real bits and the MSB-first packing decides it.
- Equality. Equal strings have equal lengths, so they pad to the same length and the same blocks.
The PRP domain, the right blocks and the comparator are unchanged. Pad blocks cannot be told apart from a string's own blocks, because each block's PRP is keyed by its position and prefix. The padded encryptors refuse a string that ends in NUL (OreError::TrailingNul), since padded it would encrypt the same as the string without it; Postgres text and jsonb cannot hold NUL. The raw 6-bit symbol encryptors (encrypt_var, encrypt_left_var) cannot be padded this way, since a trailing zero symbol is a real value there, and had no users beyond tests; they are test-only now, so strings are the scheme's only public plaintext.
Padmé was not used. It was prototyped and set aside. Padmé was designed for kilobyte-to-gigabyte messages; at database string lengths its buckets are near-exact (below 9 bytes it changes nothing, 9 to 31 bytes round only to an even length, 32 to 63 to a multiple of 4), so above a floor it is barely better than no padding. The simulation in the comment below put an attacker's chance of guessing an email's exact length at 53% under Padmé with a 16-byte floor, against 11% under powers of two at about 1.4× the blocks.
What landed
- A
Paddingpolicy onOreAes128Bit6Chained, chosen atinit_with_padding;inituses the default.PowerOfTwo { min_bytes }, the default withmin_bytes: 16. A string up tomin_byteslong pads tomin_bytes; a longer one pads to the next power of two, so the default buckets are 16, 32, 64, 128, … bytes. A string that would pad pastMAX_STR_BYTESis refused (TooManyBlocks), so the default accepts strings up to 32768 bytes.Fixed { max_bytes }: every string pads tomax_bytes, hiding the length entirely; longer strings are refused (ExceedsPadding). For short, bounded, low-entropy columns.None: no padding; the ciphertext reveals the exact length.
- Wire format: a 3-byte policy tag (kind byte, big-endian
u16) follows the 4-byte common header, so a full ciphertext is7 + 25*count + 16bytes and a left is7 + 17*count. The parser and the comparators reject unknown kinds, policies no cipher could be initialised with, and block counts the tagged policy cannot produce. The comparators returnNonefor two ciphertexts made under different policies, since an unpadded and a padded copy of one string have different blocks and would otherwise compare unequal. A column's stored values and its queries must use one policy; changing it means re-encrypting the column. - Verification: unit, exhaustive small-alphabet and property tests under every policy; pinned vectors for the default, unpadded and fixed policies, including strings on both sides of the 16-, 32- and 64-byte bucket edges; Kani proofs that the rules never shrink a length, are idempotent and monotone; a libFuzzer target (
chained_encrypt_str) for arbitrary string pairs; the ct-taint gate green on arm64 and amd64, with one new accepted branch (the trailing-NUL check, a single out-of-line branch that returns a constant on each path).
Leakage profile now: the length bucket, plus the order and common-prefix length that comparisons reveal. Stored full ciphertexts still compare offline (#99), which reveals common-prefix lengths and so a lower bound on each value's length; in the simulation this raised the guess rate by 2 to 7 points.
Not in scope, possible later: a configurable growth ratio (1.5), explicit bucket boundaries fitted to a column (needs a larger header tag), right-only storage (#99).
This lands before 0.9.0 freezes the chained wire format; 0.9.0-rc.1 marks it as not frozen.
Activity
docs(chained): every ciphertext reveals the exact plaintext length
coderdan commentedon Oct 15, 2026
Update: padding needs no new symbol, and Padmé is probably the wrong default
1. A 65-value domain is not needed for strings
The constraint section above says the pad symbol must sort below all 64 real symbols. That is only true for arbitrary bytes. If a string is padded with NUL bytes, the padding decomposes to zero 6-bit symbols. This is the same zero fill the decomposition already applies to its last partial block. It keeps both order and equality for every string that does not end in NUL:
"a"and"a\0"collide only because"a\0"ends in NUL. A padded encryptor must refuse such strings; Postgrestextandjsonbcannot hold NUL anyway. I checked this against a model of the decomposition and the comparator: there were no mismatches with byte order over 200k random and prefix pairs.So padding needs no change to the PRP domain, the CMAC derivation, the right blocks or the comparator. Padding blocks can't be identified in a ciphertext, because each block's PRP is keyed by its position and prefix.
The padding rule is free to choose. Any rule that always pads a given string to the same length, and never shrinks it, preserves order and equality. The padded length doesn't have to depend only on the string's length.
Decisions so far:
Nonewhen two ciphertexts were made under different policies. Without this, an unpadded"abc"and a padded"abc"would compare unequal. A column's stored values and its queries must use the same policy.encrypt_var) are never padded, because a trailing zero symbol is a real value there.A prototype exists on a local branch (
feat/chained-padding, not pushed). It implements aPaddingpolicy (Padme { min_bytes },Fixed { max_bytes },None), the header tag, and aTrailingNulrefusal, with property tests and new pinned vectors. It also passes the ct-taint gate on arm64 and amd64: the trailing-NUL check is a single out-of-line branch with one suppression. The unpadded and raw-symbol vectors are the previous bytes with only the tag inserted.2. Which padding rule?
Padmé was designed for files and messages from kilobytes to gigabytes. In that range, keeping overhead under 12% matters, and leaking O(log log L) bits is small. Database strings are mostly under 64 bytes, and there Padmé's buckets are very narrow:
A 16-byte floor hides short strings, but above the floor Padmé is barely better than no padding.
I simulated the candidate rules on four sample columns: first names (1,308), English words (20k), synthetic emails (20k) and multi-word phrases (20k), built from the
/usr/share/dictword lists. Two measures:On first names, every policy with a 16-byte floor puts all values in one bucket (2.9× cost, 26% guess rate, which is just the most common length).
Offline comparison doesn't undo the padding. Stored full ciphertexts can be compared with each other offline, and this reveals common-prefix lengths. Those give a lower bound on each value's length. I added that to the attacker in the simulation, and it raises the guess rate by only 2–7 points. For example, emails with powers of 2 go from 11% to 14%, and emails with Padmé from 53% to 55%. Right-only storage (#99) would remove even this.
Options considered and set aside:
Recommendation
Fixed { max_bytes }for short, bounded, low-entropy columns such as codes, statuses and names. It hides the length completely.This must land before 0.9.0 freezes the chained wire format. 0.9.0-rc.1 marks it as not frozen. Parked for now; we'll come back to it.
References:
[-]Chained scheme: pad strings to hide exact length (Padmé)[/-][+]Chained scheme: pad strings to a length bucket to hide exact length[/+]