[messaging] Encoding encrypted blobs to avoid unnecessary metadata leakage

Bryan Ford brynosaurus at gmail.com
Sun Jul 8 06:51:01 PDT 2018

Dear all,

I wanted to point out a preprint we recently put on the arXiv, which seems potentially relevant to the Autocrypt project, on more metadata-privacy-preserving encoding techniques for encrypted data blobs like those PGP produces:

	Reducing Metadata Leakage from Encrypted Files and Communication with PURBs
	https://arxiv.org/abs/1806.03160 <https://arxiv.org/abs/1806.03160>

The idea is to ensure that the encoding leaks no metadata at all other than via length - including cyphers used, number and identities of receivers, etc. - and leaks as little as possible even via the length, while still ensuring efficiency (e.g., ensuring receivers don’t need to do an exhaustive scan through a markerless stream of random bits).  This could help protect users against a variety of potential attacks, such as:

- An attacker, who can passively monitor the plaintext E-mail between only two members of a group, learning how many total members in the group there are (i.e., to how many recipients the blob is encrypted), and/or perhaps learning something about the identities of those recipients.
- An attacker learning from the unencrypted PGP header metadata exactly which PGP software implementation and version the sender is using, which ciphersuites, etc., by fingerprinting the exact structure of that metadata, as a cheap way of monitoring passively for senders who might be using old versions of encrypted software with known, exploitable vulnerabilities.

In short, by PURB-encoding encrypted blobs instead of using the traditional PGP wrapper, we can guarantee that everything in the E-mail that “looks” random and encrypted in the message (i.e., everything in the base64-encoded blob) actually *is* encrypted and provably leaks as little as possible information of any kind to any passive attacker.

We’d love to see the ideas in this paper eventually get into a next-generation E-mail standard like Autocrypt, and would be happy to help make it happen if there’s interest.  Thoughts/feedback welcome.


Most encrypted data formats, such as PGP, leak substantial metadata in their plaintext headers, such as format version, encryption schemes used, the number of recipients who can decrypt the data, and even the identities of those recipients. This leakage can pose security and privacy risks, e.g., by revealing the full membership of a group of collaborators from a single encrypted E-mail between two of them, or enabling an eavesdropper to fingerprint the precise encryption software version and configuration the sender used and to facilitate targeted attacks against specific endpoint software weaknesses. We propose to improve security and privacy hygiene by designing future encrypted data formats such that no one without a relevant decryption key learns anything at all from a ciphertext apart from its length - and learns as little as possible even from that. To achieve this goal we present Padded Uniform Random Blobs or PURBs, an encrypted format functionally similar to PGP but strongly minimizing a ciphertext's leakage via metadata or length. A PURB is indistinguishable from a uniform random bit-string to an observer without a decryption key. Legitimate recipients can efficiently decrypt the PURB even when it is encrypted for any number of recipients' public keys and/or passwords, and when those public keys are of different cryptographic schemes. PURBs use a novel padding scheme to reduce potential information leakage via the ciphertext's length L to the asymptotic minimum of O(log2(log2(L))) bits, comparable to padding to a power of two, but with much lower padding overhead of at most 12%which decreases further with large payloads.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180708/074b3396/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: Message signed with OpenPGP
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180708/074b3396/attachment.sig>

More information about the Messaging mailing list