Most encrypted data formats leak metadata via their plaintext headers, such as
format version, encryption schemes used, number of recipients who can decrypt
the data, and even the recipients’ identities. This leakage can pose
security and privacy risks to users, e.g., by revealing the full membership of
a group of collaborators from a single encrypted e-mail, or by enabling an
eavesdropper to fingerprint the precise encryption software version and
configuration the sender used.
We propose that future encrypted data formats improve security and privacy
hygiene by producing Padded Uniform Random Blobs or PURBs: ciphertexts
indistinguishable from random bit strings to anyone without a decryption key.
A PURB’s content leaks nothing at all, even the application that created it,
and is padded such that even its length leaks as little as possible.
Encoding and decoding ciphertexts with no cleartext markers presents efficiency
challenges, however. We present cryptographically agile encodings enabling
legitimate recipients to decrypt a PURB efficiently, even when encrypted for any
number of recipients’ public keys and/or passwords, and when these public keys
are from different cryptographic suites. PURBs employ PADMÉ, a novel padding
scheme that limits information leakage via ciphertexts of maximum length M to
a practical optimum of O(log log M) bits, comparable to padding to a power of
two, but with lower overhead of at most 12% and decreasing with larger
payloads.