[openpgp] Message padding in OpenPGP

[Justus Winter <[e-mail]>]

Hello :)

To reduce the amount of information leaked via the message length (see
e.g. [0]), encrypted OpenPGP messages should include decoy traffic.

0: https://mailarchive.ietf.org/arch/msg/openpgp/rG-X9rp2jlbyACoosnbxRXjCeys

There are a number of ways to add decoy traffic within the boundaries
of the OpenPGP protocol, keeping an eye on backwards-compatibility
with common implementations:

  - Add a decoy notation to a signature packet (up to about 60k)

  - Add a signature with a private algorithm and store the decoy
    traffic in the MPIs (up to 4 GB)

  - Use a compression container and store the decoy traffic in a chunk
    that decompresses to the empty string (unlimited)

  - Use a bunch of marker packets, which are ignored (each packet: 3
    bytes for the body, 5 bytes for the header)

  - Apparently, GnuPG understands a comment packet (tag: 61), which is
    not standardized (up to 64k)

Out of these options, the compression container is a simple and
flexible candidate, that also has very good expected compatibility.

We are currently convinced that padding the compressed data stream is
the best option, because as far as OpenPGP is concerned, it is
completely transparent for the recipient (for example, no weird
packets are inserted).

Testing some OpenPGP implementations (Sequoia, OpenKeychain, GnuPG)
revealed no problems.

To be effective, the padding layer must be placed inside the
encryption container. To increase compatibility, the padding layer
must not be signed. That is to say, the message structure should be
(encryption (padding ops literal signature)), the exact structure
GnuPG emits by default.

An example of such a message is:

-----BEGIN PGP MESSAGE-----

wV4Di9iOlMDSAzMSAQdALBAMZRuLecJf8LZvPIYhTrqmN6BLN5fEc8m7sPZAPSYw
6lm9Nmm9fo5ogkLknC4E+ME8S9v5lCJVAMZ30OXNX5is/uvdzPh3csS4I2F07Q2C
0lMBznfsZ0N0N+fz3U2jR5kyM68Vj2/W7XrIaiG7DgPe8wGJkzYMVOiXDqzLa/fh
sQH/IFpfjJQl0lCCZ2NKnIEG4s8S5eCINZZyipcGnKtrsvVviA==
=kp0k
-----END PGP MESSAGE-----

The session key is
58FBB6C39FA3626AA283E47A01690957D0B866392B9CC79E53E943FF410ED6DB.

You can view the message on [1], note the two padding bytes "wy" at
the end of the compressed data stream.

1: https://dump.sequoia-pgp.org/?data=-----BEGIN%20PGP%20MESSAGE-----%0D%0A%0D%0AwV4Di9iOlMDSAzMSAQdALBAMZRuLecJf8LZvPIYhTrqmN6BLN5fEc8m7sPZAPSYw%0D%0A6lm9Nmm9fo5ogkLknC4E%2BME8S9v5lCJVAMZ30OXNX5is/uvdzPh3csS4I2F07Q2C%0D%0A0lMBznfsZ0N0N%2Bfz3U2jR5kyM68Vj2/W7XrIaiG7DgPe8wGJkzYMVOiXDqzLa/fh%0D%0AsQH/IFpfjJQl0lCCZ2NKnIEG4s8S5eCINZZyipcGnKtrsvVviA%3D%3D%0D%0A%3Dkp0k%0D%0A-----END%20PGP%20MESSAGE-----%0D%0A&hex=on&session_key=58FBB6C39FA3626AA283E47A01690957D0B866392B9CC79E53E943FF410ED6DB

The following patch adds a section to RFC4880bis detailing the process
of padding, and recommends a suitable padding policy.

diff --git a/middle.mkd b/middle.mkd
index ca73704..beb6f57 100644
--- a/middle.mkd
+++ b/middle.mkd
@@ -2397,6 +2397,26 @@ ZLIB-style blocks.
 BZip2-compressed packets are compressed using the BZip2 [](#BZ2)
 algorithm.

+### Message padding
+
+The Compressed Data packet presents an opportunity to add an arbitrary
+amount of decoy traffic to OpenPGP Messages.  To that end,
+implementations SHOULD create a encrypted, compressed message as
+usual, and SHOULD use the ZIP algorithm with no compression
+(i.e. level 0), and append a number of random bytes to the compressed
+data stream according to a padding policy.  Note: Not actually
+compressing the data stream is important to make sure the size of the
+padded message does not depend on the entropy of the plaintext
+message.
+
+Implementations SHOULD use the Padmé padding scheme.  Padmé offers the
+same protection as the obvious scheme of padding to the next power of
+two, but with an overhead of at most most 12%, decreasing with message
+size.
+
+See Section 4 of [Reducing Metadata Leakage from Encrypted Files and
+Communication with PURBs](https://bford.info/pub/sec/purb.pdf).
+
 ## Symmetrically Encrypted Data Packet (Tag 9)

 The Symmetrically Encrypted Data packet contains data encrypted with a

Cheers,
Justus