Subject: [openpgp] Message padding in OpenPGP

From: Justus Winter <[email-masked]>
Date: Tue, 24 Sep 2019 19:09:04 +0200

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:

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

---

From: Ryan Carboni <[email-masked]>
Date: Tue, 24 Sep 2019 18:36:03 +0000

Just encrypt a loop device. Fixed size, already padded.

---

From: Heiko Stamer <[email-masked]>
Date: Tue, 24 Sep 2019 21:12:36 +0200

> completely transparent for the recipient (for example, no weird

What's about keys that state no support for compression?

--
Heiko

---

From: Jon Callas <[email-masked]>
Date: Tue, 24 Sep 2019 17:00:17 -0400

> On Sep 24, 2019, at 1:09 PM, Justus Winter <[email-masked]> wrote:
> 
> Hello :)
> 

What actual problem are you trying to solve.

We've discussed compressed data at length, and there's a general consensus to my mind that implementations should move away from compression being the default. There's less of a consensus that it should go the way of all things, into that good night. But we agree that compression is at the very least a can of worms.

Am I correct in understanding that you're proposing adding in decoy traffic to pad out compressed data to its uncompressed length? 

If I'm missing something, what problem are you trying to solve with this?

	Jon

---

From: Justus Winter <[email-masked]>
Date: Wed, 25 Sep 2019 11:03:24 +0200

> Am I correct in understanding that you're proposing adding in decoy traffic to pad out compressed data to its uncompressed length?

No.  I'm proposing not to compress the data at all, and then add some
padding data according to some policy.  The compression container is
only a means to add the padding within the constraints of the current
ecosystem.

> If I'm missing something, what problem are you trying to solve with this?

There is a correlation between the size of the encrypted message and
the size of the plaintext.  On first sight, compression helps with
that, but that makes the size dependent on the entropy of the
plaintext, which also leads to problems as discussed previously.
Padding alleviates this problem, the tradeoff being an increased
message size.

Cheers,
Justus

---

From: Derek Atkins <[email-masked]>
Date: Wed, 25 Sep 2019 10:32:33 -0400

Justus Winter <[email-masked]> writes:

>> Am I correct in understanding that you're proposing adding in decoy
>> traffic to pad out compressed data to its uncompressed length?
>

Why not just have multiple literal packets inside the encryption?  I.e.:

  ENC{ Lit1{realData} | Lit2{pad} }

Note, of course, that this could provide a covert channel which could
leak other data, theoretically.

> Justus

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Jon Callas <[email-masked]>
Date: Wed, 25 Sep 2019 11:24:04 -0400

> On Sep 25, 2019, at 5:03 AM, Justus Winter <[email-masked]> wrote:
> 

Okay. Thanks. I think that clarifies. (Meaning I'm still slightly puzzled, but okay.)

> Padding alleviates this problem, the tradeoff being an increased

Well, if you don't compress, sure there is. The size is going to be <message-size> + <overhead> and the overhead is generally easily computed or guessed.

I understand the vague concern, but to me the proposal is security stone soup. You're throwing some stuff together and it vaguely meets the vague concern.

I think there's a way forward and that might be something like:

* Describe the actual threat. I can imagine threats, but I don't have a handle on what you're trying to do exactly.
* Describe how the solution (padding) helps and give quantification as to how it helps. There are plenty of places where padding doesn't help, it just shifts a bunch of things around. There are also places where padding ends up hurting. I've seen this in constant-traffic networks where the padding makes traffic analysis easier (hand waved explanation: the padding makes it easier to recover a timing side channel and that side channel allows you to statistically remove the padding; you end up knowing the aggregate of padding to a statistical confidence level, and on a data stream, that's good enough.)
* Look at what might be second-order effects and discuss them at the least. Costs in terms of networking and storage vs benefit need to be in here.

A few years ago, I was looking at a very similar problem, and that was removing sized-based traffic analysis from cloud storage systems. We looked at padding things out, and in many cases padding didn't really help. We looked at padding with thresholds -- e.g. round everything up to the nearest chunk size, where a chunk is something like a power of two in the 4K to 1M range. It turns out that a lot of information gets leaked anyway. For example, you can easily guess that something is likely to be a selfie, because they're all in a reasonably narrow band of sizes.

The larger your chunk is, the better you blur, but the obvious downside (that now you're writing a lot of extra data in the vast majority of cases) has such an effect on wasted networking and storage space that A Reasonable Person would likely decline to pad. Padding small enough for the concern to be insignificant gives a correspondingly insignificant benefit. We ended up doing some chunking, but we knew that the benefits were so small that we didn't even really talk about it. It was far too easy for someone to think they were getting a huge benefit that they weren't getting. (A similar situation is the way people overestimate how much private browsing or even Tor help them.)

Summing up, it's interesting, but I think a cost-benefit discussion should follow, along with at least a hand wave of metric-ish things.

	Jon

---

From: [email-masked]
Date: Wed, 25 Sep 2019 11:35:41 -0400

On 9/25/2019 at 5:04 AM, "Justus Winter" <[email-masked]> wrote:

>There is a correlation between the size of the encrypted message 
>and the size of the plaintext.  On first sight, compression helps with

=====

It really doesn't matter once the message is past a certain length.
Whatever correlation there might be with the plaintext and message size,
once the message is long enough, attackers can't do more than speculate about the plaintext content.

For very short messages, 
it's enough if the sender just presses the spacebar at the end of the message until the plaintext is the desired size.
(And even then, only if the sender feels that there might be some vulnerability with the size of the plaintext, which is usually not the case. )

In any event, it's enough if there is a cautionary note in the rfc about the correlation between plaintext size and encryption, and suggest, that if this is an issue for the sender and receiver, then a workaround could be to simply add some padding at the end which doesn't interfere or obscure the content of the plaintext.

vedaal

---

From: Justus Winter <[email-masked]>
Date: Thu, 26 Sep 2019 22:15:58 +0200

>   ENC{ Lit1{realData} | Lit2{pad} }

Because that is not a well-formed OpenPGP message.

Cheers,
Justus

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 27 Sep 2019 01:12:52 +0200

Hi Justus--

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

Thanks for this thoughtful analysis of different padding mechanisms for
OpenPGP encrypted packets.

I note that deciding on a padding mechanism ("how do i pad?") at the
OpenPGP layer is not the same as deciding on a padding policy ("how much
do i pad in a given circumstance?")

We've been having increased dicsussion around the IETF about traffic
analysis, and from what i've seen the general consensus (e.g. in TLS and
DPRIVE) has been:

 * Size-based traffic analysis is a potentially serious threat to some
   applications that rely on encrypted traffic.  Responsible protocol
   designers need to consider countermeasures.

 * The ideal place to apply padding is at the application layer -- or
   even higher in the stack -- because the upper layers are closest to
   understanding the typical size characteristics of messages that they
   emit and receive, and the risks of size-based traffic analysis at
   those layers.

 * Some application layer traffic is fairly ossified (the cleartext
   structures cannot be modified without significant cost), and has no
   native mechanism to safely pad.  And the encryption protocols
   themselves sometimes leak sizing data in unfortunate ways.  So a
   responsible encryption mechanism that might be used to encapsulate
   different application-layer traffic, or have its own size-based
   leakage should include a well-understood padding mechanism.  That
   way, an ossified application layer can exercise the encryption
   layer's padding scheme to defend against traffic analysis without
   touching the application data.

 * Designing a padding policy is likely better done independently from
   designing a padding mechanism.  As long as the padding mechanism is
   available, then the application layers can declare their preferred
   padding schemes.

 * The preferred padding policy for a given application layer may change
   over time as the use of the protocol changes.  Having it designated
   separately allows adjustment of the policy without having to fiddle
   with the mechanism.

Given the above, i agree with you that the OpenPGP specification should
explicitly warn implementers and higher-layer users of OpenPGP to
consider the risks of traffic analysis and encourage countermeasures
that obscure the size of the cleartext.

However, i don't think that the OpenPGP specification should declare a
preferred padding *policy* -- that's best discussed in the context of an
application that uses OpenPGP, and might well be different for different
applications.

I'm of two minds about declaring a standard padding *mechanism* for
OpenPGP in the main specification itself.  If there was one obvious
mechanism for padding that was already in wide use, i'd say we should
include it in 4880bis.  But as there appear to be many possible
mechanisms, and there may be subtle tradeoffs between different
mechanisms, and 4880bis is already long overdue, i'd recommend
documenting a preferred padding mechanism (without trying to impose a
preferred padding policy) in a separate draft, including a bit more
justification about why this scheme is preferable to the other
possibilities.

As for your current proposal (using a compressed packet as padding), i'm
concerned about the interaction between features -- does it mean that if
the recipient has marked their OpenPGP certificate as unable/unwilling
to use decompression, that they cannot receive padded messages?  Is
there a way to mark padding explicitly as padding so that a clever
implementation doesn't need to exercise any decompression code just to
throw away the padding packet?

Would you be interested in writing a more narrowly-scoped merge request
for 4880bis that directs application layers that use OpenPGP to consider
the risks of size-based traffic analysis, and apply padding-based
countermeasures where possible?

      --dkg

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 27 Sep 2019 01:41:55 +0100

Hiya,

I agree with all the rest of your message:-)

But not this bit:

On 27/09/2019 00:12, Daniel Kahn Gillmor wrote:
> The ideal place to apply padding is at the application layer

That's not clear to me. It may be true or it may not.
(Perhaps that's just me being suspicious of terms like
"ideal" though:-)

As a (possible) counter-example, application layer code
is perhaps not (yet) well positioned to deal with padding
of both DNS and application layer traffic, all at once.
E.g., in the case of mail, if a message from a small
sender with a big DNS name arrives at a receiver that does
SPF and DMARC lookups, packet sizes emitted by the mail
receiver might expose information about the mail sender
despite any padding of the SMTP/TLS traffic. That is
likely a bit of a contrived example but I'd worry that
arguing that all "padding policy" be set by layer-4+
might go wrong in some cases.

I do totally agree with a strategy of defining padding
mechanisms everywhere we can and then learning over
time how best to use those though, so I think it'd be
fair to consider my comment here is a bit of a nit-pick.
(But I sent the mail anyway:-)

Cheers,
S.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 27 Sep 2019 12:42:55 +0200

> of both DNS and application layer traffic, all at once.

i agree with your concerns, Stephen, though maybe not the specific
wording.  :) I mean, DNS *is* application layer traffic, right?

But you're right, as we move toward multiplexed application layer
protocols within a standard encryption layer (e.g. DNS over HTTPS on the
same endpoint that is serving "normal" HTTPS traffic as well), the
padding designs needed to mitigate size-based traffic analysis require
some sort of systemic reasoning about the combination of the application
layers involved.

So maybe the better way to say this is that padding policy should be
designed and set based on the encryption layer's properties (and padding
capabilities) and the union of all the traffic that is expected to be
encapsulated by that layer.

       --dkg

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 27 Sep 2019 12:18:09 +0100

Hiya,

> wording.  :) I mean, DNS *is* application layer traffic, right?

Yep, you're right - I should've said "DNS and other
application layer traffic."

> encapsulated by that layer.

That's better yes. I'm not sure it's correct yet though,
but I don't know how to properly characterise it myself
as tricky corner cases abound. For example, a browser
that does DoH to a local-ish recursive might be slightly
better off padding HTTPS traffic differently from that
same browser when the DoH server is more topologically
remote. But that's definitely taking us out of the scope
of PGP. Good topic for pearg [1] though I guess.

Cheers,
S.

[1] https://irtf.org/pearg

---

From: Derek Atkins <[email-masked]>
Date: Fri, 27 Sep 2019 09:44:37 -0400

> Because that is not a well-formed OpenPGP message.

Neither is anything else you are currently proposing.  If you're going
to extend the spec to add a new packet type you might as well extend the
spec to allow this, which is easier.  And honestly many parsers (at
least the parser I wrote in 1995 which AFAIK is still in use by at least
one implementation) will actually parse this structure properly.

-derek

---

From: Justus Winter <[email-masked]>
Date: Fri, 27 Sep 2019 16:03:29 +0200

On Fri, Sep 27, 2019 at 3:44 PM Derek Atkins <[email-masked]> wrote:
> Neither is anything else you are currently proposing.

That is incorrect.  Please do go back to my original message and
re-read it carefully.

> If you're going
> spec to allow this, which is easier.

I was explicitly *not* proposing a new packet type.  And I do not
believe that extending the spec is as easy as you make it seem to be,
and extending the spec doesn't help existing implementations.

> And honestly many parsers (at

I bet that your parser from 1995 will correctly handle the padding
mechanism I proposed, as long as it is able to deflate compressed data
packets.  Please do actually try that, I'd be very happy to get some
feedback.

Cheers,
Justus

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 27 Sep 2019 16:15:14 +0200

> Neither is anything else you are currently proposing.

Are you certain about that?

It looks to me like Justus has proposed several different
implementations that meet the grammar specified in
https://tools.ietf.org/html/rfc4880#section-11.3, which is almost
exactly the same as the grammar from 19 years ago in
https://tools.ietf.org/html/rfc2440#section-10.2 (the only difference is
the introduction of the SEIPD in RFC 4880).

> If you're going to extend the spec to add a new packet type you might
> as well extend the spec to allow this, which is easier.  And honestly
> many parsers (at least the parser I wrote in 1995 which AFAIK is still
> in use by at least one implementation) will actually parse this
> structure properly.

We have a documented grammar that has held up for nearly two decades --
even if some parsers are more flexible/permissive than the grammar
itself, changing the grammar could invalidate any existing strict
parsers.  In a security-sensitive context, we know that strict parsers
are safer than permissive parsers (see for example https://efail.de).
Let's not discourage strict parsers.

If we want a backward-compatible padding mechanism (i think we do,
though i'm not sure it's appropriate to document it in 4880bis), then
changing the grammar itself should probably be pretty low on the list of
options.

        --dkg