Subject: [openpgp] Disabling compression in OpenPGP

From: Alfredo Pironti <[email-masked]>
Date: Tue, 18 Mar 2014 17:00:29 +0100

Dear list,

It is well known that compressing data before encrypting them leaks much
about the plaintext [1]. Recently, this has been exploited against the TLS
protocol in the so-called CRIME attack [2].

Looking at RFC 4880, section 2.3, I read
“OpenPGP implementations SHOULD compress the message after applying the
signature but before encryption.”
And indeed, gpg faithfully follows the spec by enabling compression by
default.

I have done some preliminary work on password managers that rely on OpenPGP
(gpg, in fact) to encrypt the passwords. Unsurprisingly, it turns out that
compressing the password before encrypting it leaks much of the password
entropy, making dictionary attacks significantly easier to mount. (In my
preliminary experiments I used a password dictionary containing about 4
million passwords. If the attacker knows the original password length and
its compressed length, then for some combinations of the two the candidate
dictionary entries can reduce to as few as some hundreds.)

I believe similar attacks can be mounted in different contexts where
OpenPGP is used. Hence, I propose to start discussion to amend RFC 4880 to
at least discourage (if not forbid) the use of compression.

I welcome comments and suggestions.
Alfredo Pironti

[1] Kelsey, J.: Compression and information leakage of plaintext. In: Fast
Software Encryption. pp. 263–276 (2002)
[2] See, e.g.: http://en.wikipedia.org/wiki/CRIME_%28security_exploit%29

---

From: Gregory Maxwell <[email-masked]>
Date: Tue, 18 Mar 2014 09:07:44 -0700

On Tue, Mar 18, 2014 at 9:00 AM, Alfredo Pironti
<[email-masked]> wrote:
> I believe similar attacks can be mounted in different contexts where OpenPGP
> is used. Hence, I propose to start discussion to amend RFC 4880 to at least
> discourage (if not forbid) the use of compression.

OpenPGP compression (well, the unawareness there-of) compromised the privacy
of the Wikimedia Foundation board election a couple years ago.  Users publically
submitted ballots encrypted to the election officials, the ballots
were constant length
but the compression trivially revealed information about their content.

If it isn't disabled it may be useful to quantize the size somewhat
for a minor overhead
in order to reduce the information leak somewhat.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 18 Mar 2014 17:48:24 +0100

> in order to reduce the information leak somewhat.

TLS allow implementations to randomly pad messages to mitigate these
attacks, could something similar be what OpenPGP needs?

/Simon

---

From: Alfredo Pironti <[email-masked]>
Date: Tue, 18 Mar 2014 19:07:54 +0100

On Tue, Mar 18, 2014 at 5:48 PM, Simon Josefsson <[email-masked]>wrote:

> OpenPGP

Deterministic quantization may do in principle, but it seems to me harder
to deploy than just disabling compression, because of backward
compatibility issues and unpredictable compression ratio.

Looking at TLS, in practice compression has been disabled everywhere (with
a proposal of completely removing it in TLS 1.3), and it seems not have had
particularly negative effects.

> attacks, could something similar be what OpenPGP needs?

I'd refrain to use random padding, because it does not protect against
repeated sampling: if you encrypt the same plaintext (say, a password) over
and over, the shortest encrypted message will soon give you a hint of the
plaintext length [1].

Alfredo

> /Simon

[1] http://hal.inria.fr/hal-00732449

---

From: Jon Callas <[email-masked]>
Date: Tue, 18 Mar 2014 11:15:11 -0700

On Mar 18, 2014, at 9:00 AM, Alfredo Pironti <[email-masked]> wrote:

> Dear list,
> 
> It is well known that compressing data before encrypting them leaks much about the plaintext [1]. Recently, this has been exploited against the TLS protocol in the so-called CRIME attack [2].
> 
> “OpenPGP implementations SHOULD compress the message after applying the signature but before encryption.”
> And indeed, gpg faithfully follows the spec by enabling compression by default.
> 
> I have done some preliminary work on password managers that rely on OpenPGP (gpg, in fact) to encrypt the passwords. Unsurprisingly, it turns out that compressing the password before encrypting it leaks much of the password entropy, making dictionary attacks significantly easier to mount. (In my preliminary experiments I used a password dictionary containing about 4 million passwords. If the attacker knows the original password length and its compressed length, then for some combinations of the two the candidate dictionary entries can reduce to as few as some hundreds.)
> 
> I believe similar attacks can be mounted in different contexts where OpenPGP is used. Hence, I propose to start discussion to amend RFC 4880 to at least discourage (if not forbid) the use of compression.
> 

I think you're confusing a number of things, as well as cherry picking your data.

On the other side, there's the Katz-Schneier attack (which is more of a CFB attack than OpenPGP per se) that is essentially thwarted by compression. There are other attacks where compressing helps because it obscures plaintext. I'm eliding much, so go look at it.

OpenPGP is in general not an interactive or on-line protocol, and there are all sorts of attacks that are easy against interactive or on-line attacks and not against off-line. CRIME is one of them -- it exploits the interactive nature of TLS and makes repeated connections to learn something about the plaintext. It isn't the *compression* that does it, it's deltas between similar requests. You don't get to do that with OpenPGP. Note also that there are two easy mitigations against CRIME -- one is to disable compression and other other is to restrict the interactivity of the attack.

Similarly, most side-channel attacks aren't possible when all you have is ciphertext and you're attacking it yourself. TLS is an on-line protocol and there are many, many attacks against it that simply don't apply to blob encryption, which is what OpenPGP is.

There are a number of compression oracles that exist because of carelessness. Kelsey's paper that you quote is a fantastic paper because it flew in the face of the naive belief that compression was always good (on the grounds that it makes the plaintext less predictable). Compression is *often* good for that very reason. Compression is sometimes bad. Asserting that because compression is sometimes bad, it must always be bad is stretching the point, in my opinion.

If you believe that there are attacks that can be mounted OpenPGP because of, find one. You'll have a great paper.

Even better, come up with a generalized attack. Here's a framework that you can use:

OpenPGP is mostly bulk CFB encryption of a data blob. There are headers and stuff (which could make it easier or harder depending on data leaks), but at the core of the protocol, it's just CFB. OpenPGP compression is mostly ZIP or GZIP compression. Again, there are details with headers. In this case, the header issue might be significant, as OpenPGP often deletes some normal ZIP headers which could be used as known plaintext.

Nonetheless, here's where you should put your efforts:

* Take a file or other data blob. Call it P (for plaintext). 

* Compress P with ZIP or GZIP or even BZIP. Call that Z (for zip).

* Encrypt that with a simple CFB encryptor using some key K and some suitable cipher; I'd pick AES. Call that C (for ciphertext).

* Use comparisons between P, Z, and C to mount an attack on K -- giving a key-recovery attack. Or bypass the key and cipher and use knowledge about fragments of P and Z to undo pieces of C -- which would be some form of known plaintext attack. etc.

This gives a simplified model of what's going on inside OpenPGP, and might be easier to work with. Note, however, that OpenPGP typically throws away Z -- it's computed as an intermediate value and discarded. So it's conceivable that there's an attack that's possible but hard to mount.

Alternatively, you could use compression options in the gpg command line to get ciphertext of compressed and uncompressed outputs and do the same thing.

You describe an interesting case where there's a structured file of passwords. You could look at cases where the attacker would have knowledge of the plaintext or parts of it in varying ways. For example, it could be a sorted file, or it could contain all N-character passwords in a group (that might be itself sorted) and so on. 

You could also devise interactive and non-interactive versions of your attack. Note that the non-interactive ones are more interesting, of course. 

I hope this helps.

	Jon

---

From: David Shaw <[email-masked]>
Date: Tue, 18 Mar 2014 14:29:20 -0400

> I believe similar attacks can be mounted in different contexts where OpenPGP is used. Hence, I propose to start discussion to amend RFC 4880 to at least discourage (if not forbid) the use of compre…

It is not my intent to make light of your email, but I'm somewhat amused as a few years ago there was an attack that could be *avoided* by compression.  See https://www.schneier.com/paper-pgp.pdf for the details.  Damned if you do, damned if you don't?

Note that the use of compression in OpenPGP (at least in the public key context) is under the control of the recipient.  If a given recipient doesn't want compression used on messages to their key, they can set a preference reflecting that, and all OpenPGP implementations will not compress when encrypting a message to that key.

David

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 18 Mar 2014 12:09:30 -0700

On 03/18/2014 09:00 AM, Alfredo Pironti wrote:
>
> I have done some preliminary work on password managers that rely on
> OpenPGP (gpg, in fact) to encrypt the passwords. Unsurprisingly, it
> turns out that compressing the password before encrypting it leaks much
> of the password entropy, making dictionary attacks significantly easier
> to mount. (In my preliminary experiments I used a password dictionary
> containing about 4 million passwords. If the attacker knows the original
> password length and its compressed length, then for some combinations of
> the two the candidate dictionary entries can reduce to as few as some
> hundreds.)

I wonder why the additional piece of information is available, which is 
that both the length of the original password and the length of the 
compressed one is available from a ciphertext that is an encrypted password.

Wouldn't only one of these sizes be provided through the size of the 
ciphertext?

When you build a dictionary with 4 million passwords, you can index it 
by the password length or by password's compressed length. It's true 
that OpenPGP CFB format will leak the size either of the plaintext or of 
the compressed plaintext (so perhaps higher-level padding is the right 
thing to do in cases like these). Narrowing down the choices by the size 
of the password v.s. the size of the compressed password seems 
equivalent regarding the password recovery attack.

I do see that if we can narrow down the choices by two sizes 
simultaneously, this will indeed narrow down the possibilities further. 
However, it's unclear how both sizes are obtained from a single ciphertext.

---

From: Alfredo Pironti <[email-masked]>
Date: Wed, 19 Mar 2014 16:26:05 +0100

On Tue, Mar 18, 2014 at 7:29 PM, David Shaw <[email-masked]> wrote:

> OpenPGP (gpg, in fact) to encrypt the passwords. Unsurprisingly, it turns
> out that compressing the password before encrypting it leaks much of the
> password entropy, making dictionary attacks significantly easier to mount.
> (In my preliminary experiments I used a password dictionary containing
> about 4 million passwords. If the attacker knows the original password
> length and its compressed length, then for some combinations of the two the
> candidate dictionary entries can reduce to as few as some hundreds.)
> >
> It is not my intent to make light of your email, but I'm somewhat amused
> as a few years ago there was an attack that could be *avoided* by
> compression.  See https://www.schneier.com/paper-pgp.pdf for the details.
>  Damned if you do, damned if you don't?
>

In that case, compression incidentally thwarted the attack, by inserting
additional packet headers in the encrypted packets, hence letting some
parsing fail when decrypting a chosen ciphertext.

In general, I see two patterns:
- Compression incidentally thwarts some attacks
- Compression fundamentally breaks privacy by leaking plaintext entropy
(see the Wikimedia Foundation case for a quite convincing example)

I would not want to rely on the obfuscation provided by an optional feature
of OpenPGP to ensure secrecy. If a decryption oracle is found, it should be
systematically fixed -- also for users who decide not to use compression.

On the other hand, at least making compression disabled by default would
protect those users who are unaware of the interaction between compression
and encryption. Those who are aware of it could always explicitly enable
compression.

Cheers,
Alfredo

>
> Note that the use of compression in OpenPGP (at least in the public key
> context) is under the control of the recipient.  If a given recipient
> doesn't want compression used on messages to their key, they can set a
> preference reflecting that, and all OpenPGP implementations will not
> compress when encrypting a message to that key.
>
> David
>
>

---

From: Jon Callas <[email-masked]>
Date: Wed, 19 Mar 2014 09:43:07 -0700

> - Compression fundamentally breaks privacy by leaking plaintext entropy (see the Wikimedia Foundation case for a quite convincing example)

In general, compression does the opposite of your second bullet. It *protects* privacy by taking things that are typically not pseudo-random (what you're calling entropic) -- e.g. text -- into something that is highly pseudo-random.

In specific cases, *flaws* in this conversion when combined with an interactive protocol can lead to an attack that is in general, not applicable to a non-interactive protocol with large amounts of compressed data.

But in general, this benefits the defender, as the attacker has no idea what the *actual* plaintext is (the compressed data) unless they know the base plaintext is, and small inaccuracies in the attackers guess lead to large differences.

Of course, I could be wrong. I offered an outline for research where you could come up with some results that would be impressive. Why not do some work on it?

	Jon

---

From: Florian Weimer <[email-masked]>
Date: Wed, 19 Mar 2014 17:56:39 +0100

* Jon Callas:

> In specific cases, *flaws* in this conversion when combined with an
> interactive protocol can lead to an attack that is in general, not
> applicable to a non-interactive protocol with large amounts of
> compressed data.

It doesn't have to be interactive (in the sense of chosen-something
attacks).  For example, lossy voice compression tends to produce
length differences for different phonemes.  And the Wikimedia example
wasn't something interactive, either.

> But in general, this benefits the defender, as the attacker has no
> idea what the *actual* plaintext is (the compressed data) unless
> they know the base plaintext is, and small inaccuracies in the
> attackers guess lead to large differences.

But this doesn't matter if the encryption is sound, does it?

---

From: Alfredo Pironti <[email-masked]>
Date: Wed, 19 Mar 2014 18:19:24 +0100

On Wed, Mar 19, 2014 at 5:43 PM, Jon Callas <[email-masked]> wrote:

> In general, compression does the opposite of your second bullet. It
> *protects* privacy by taking things that are typically not pseudo-random
> (what you're calling entropic) -- e.g. text -- into something that is
> highly pseudo-random.
>

Just to clarify, I was talking in terms of the length side-channel entailed
by compression. If the attacker knows the uncompressed plaintext length,
and can measure the compressed ciphertext length, then some information
about the uncompressed plaintext content is leaked.

It may be not common, but it seems to me that this attacker model is well
within the scope of OpenPGP.

> applicable to a non-interactive protocol with large amounts of compressed
> data.
>
> But in general, this benefits the defender, as the attacker has no idea
> what the *actual* plaintext is (the compressed data) unless they know the
> base plaintext is, and small inaccuracies in the attackers guess lead to
> large differences.
>
> Of course, I could be wrong. I offered an outline for research where you
> could come up with some results that would be impressive. Why not do some
> work on it?
>
>         Jon
>
>
>

---

From: Peter Todd <[email-masked]>
Date: Wed, 19 Mar 2014 16:40:47 -0400

> In general, compression does the opposite of your second bullet. It *protects* privacy by taking things that are typically not pseudo-random (what you're calling entropic) -- e.g. text -- into some…

That's the job of encryption, and modern encryption does that job very
well.

I strongly support turning off compression by default. That the length
of the data being encrypted is leaked is pretty easy for a non-advanced
user to figure out - just compare the encrypted and unencrypted file
lengths, or for that matter, just think about it rationally. But the
fact that information on the contents of the file is being leaked too -
exactly what encryption is supposed to prevent - is not at all obvious.

-- 
'peter'[:-1]@petertodd.org
0000000000000000bb8e8e215734f2855ab6da93a8e1caf12392231696f01f83

---

From: Jon Callas <[email-masked]>
Date: Wed, 19 Mar 2014 13:47:01 -0700

> exactly what encryption is supposed to prevent - is not at all obvious.

What's being leaked by compression? Really, I don't get it.

Consider an OpenPGP blob that is compressed and encrypted. Consider that it is intercepted by whatever means. What's the leak?

Here's an example, where an unknown plaintext is encrypted both to a key, and to a passphrase:

What's the leak? What's the vuln?

	Jon

---

From: Peter Todd <[email-masked]>
Date: Wed, 19 Mar 2014 16:55:17 -0400

On Wed, Mar 19, 2014 at 01:47:01PM -0700, Jon Callas wrote:
> -----BEGIN PGP MESSAGE-----
> Comment: GPGTools - http://gpgtools.org
> 
> hQEOA2EbpgyFsrXlEAQAs63hznff9WCrq9xpT5s8dbmoabOQpfV/Crzaqn5diiCp
> x1kyqqTCpSJQ648O3bF3GYq0KfqWhzc3S+rK7yrSpSA8UDWWifVfSBKmVDvYUD/g
> GPURwlTKtUp00MzlKrT083oq/aQEotO/7botgihpEbWPrEO3ZZIFwwxmNfwUUtED
> /jyNjMfPTmeLYvPdMLFiy+AuMbGnE3L0M9+iTLJZHW6Hb/hn0TLJk69RdDkmyiql
> VaZNYE+9l1AiZpEVddmoKOTPPV0EtzeNqVZtVr3yCH0rBrN54GjHoWAnD8/IhuX8
> T11kixGJhs1228xlhK+3UTp15VGrKNQsLoGpUd45iewPjCYEAwMCe35rGZQc7xjR
> gk41KuP8CsROH0ulK1pzm/zH2gZbzhY068np63ZvnfxTQyaYBV+MRAhN2NOF1XkW
> 4QtFr2bfJCYiCzS6vuwxjRicfU9kwHaI+G3XfJGXVB/qtcgEV7JWG81VDnU2zKSh
> h1KATe/zU5zJ7RM6mwrL37Ve4SY5tLPvpxSahu8fRffeU8/pBeQCcZyKa7ZGxiFB
> xjFLBB2a3N77Bf0VZ+nRS9nE6SpTEx8tF8b8l3qMa+lzJKVZk7cP2Yc0POHtBCT6
> F2TlnMDEvRvFmbz+3Z592OCXaZoBG6fU7VKALzZ/kl6usm6mvKAtrbNQfTk5MM38
> fqwUrcLOHpxWVNKcDvmOGdsODq5lX2coHfsix8aBoRBz/q1HiOGV3F0C9hudag01
> P199G1PCYuxzX9OvJPKEZnzf6+jEZ3vE8dhkRZPrhs/Xo7A7ryj++GSKFCSyVaHk
> PryGNgJnAp82uimr9FYT8Wmwoy42o1pPCAyVoquowHxpXAgADhmwpk0wbbE5vaD/
> 81uh1843VRySOpuQCkIkI7PhIy3HBbs349FVLKnC07VF0vMHzW3QeY9JVZJH6RlJ
> DQP0G2TjBaneHRPhdoNKzWLhTfKuaDo9FkJaaTzeB/gVKnPfovcdDjZefmflCQXR
> PvtYDsms4m5slCo/MTToM4oGuBBZqqcLIv5ZSRWYr/Gu2w9ZLkysb92dtfJe4+nw
> y2Bqk9UKInw3WAbAs0rCUlPBpAOFxNHdjkzjthGx6P3W5ZI+nG9aXyB1XNeHaTYL
> /Sx0SEFU1fmlKaIynY4reM3qJjjXi/PAWn5piTrH/G0LI3CUEgXa3Mw3sG3ArbAw
> PleXVP3QWt8jf418bDA4BLH4DFhYLQk2Ayss1M/snoRip/iUqKEu0OsUJtaspHDY
> Xt2bksh35paCav0rEtGfhxC0ks7UTdRQDP4l9tX24unQZfWAEfZkPhQPh+mkDA+H
> 3u6VfmN+5QXqph8//Qk7LSTsiBgG+EswRpqDRhNjV2ibCWjMmggtJZyKq/oOsQpS
> oCQqkpgjrv+GSGCgEwIKeUZfnTtVTpKX0EiDjUTQ5Cuq1VR+NsIfHdo2ZSVQ0+mS
> D9sGjILD87c80Pcfd3i9NtZoZqX46p4CVOReaFEvll1X9YqEaX4uDPCPoubSHsqR
> EfqIT2AYRegF1Grjr16YTzqiqkfL/4lOKQHyRwGLjq8pag888IXdbKIxWbXtMESs
> =Uqr6
> -----END PGP MESSAGE-----
> 

Having a completely unknown plaintext is the best case; having
plaintexts that are not completely unknown to the attacker is both
common, and reasonable to defend against.

If I knew that the plaintext was either 1KB worth of uncompressable binary garbage,
or 1KB worth of text, it'd be pretty easy for me to figure out if I was
looking at garbage or text.

Gregory Maxwell's example of the Wikipedia vote's privacy being broken
by compression-by-default shows this is a real world risk that users are
not thinking about.

-- 
'peter'[:-1]@petertodd.org
000000000000000067c4c46a5fa2d2686559607d14450497efb2826234b18d87

---

From: Gregory Maxwell <[email-masked]>
Date: Wed, 19 Mar 2014 14:16:16 -0700

> What's being leaked by compression? Really, I don't get it.

Some people like a demonstration.

Consider that I'm going to cast one of two ballots in a secret ballot
election. The ballots are just permutations of eachother so they are
the same size.

https://people.xiph.org/~greg/ballot.1
https://people.xiph.org/~greg/ballot.2

I encrypt my secret ballot to the election officials with the public
key at https://people.xiph.org/~greg/openpgp_testpubkey.asc

using the command:
gpg -ear 9C28FC94 --compress-algo ZIP --compress-level 9 ballot.X
(just being explicit for consistency sake, using GPG 1.4.16 in Fedora
19)

And I get the encrypted result of
https://people.xiph.org/~greg/ballot.secret.asc

Which ballot did I cast?   Anyone?

---

From: Jon Callas <[email-masked]>
Date: Wed, 19 Mar 2014 14:37:50 -0700

> by compression-by-default shows this is a real world risk that users are

But it proves nothing here. It's a really, really interesting exception case. We're talking about a default. We're also talking about the protocol definition, and not implementation software.

Compression is on by default because it improves security. It meets that goal. It is, however, a default. Defaults can be changed. Moreover, there's a way to work around the issue in the existing standard. Make the vote-submission key not support compression. Poof, it works.

There are many, many other cases where it is *assumed* that compression is on by default, and that's the desired behavior for both security reasons and non-security reasons (like you want the object compressed as well as encrypted!)

When you design systems and software, one of the things you need to consider is defaults. Another is exceptions. But there's also installed base. 

Changing a standard is hard, and that's a feature, not a bug. The weaker that a standard is about something, the harder it is to change. Changing an implementation is easier, because it's just software. But there's also the issue of not only the defaults but the installed base.

If you went, for example, to someone who did an email plugin that did not expose compression and argue that they should not compress by default, you have an interesting case. I think it's still unproven, but it's interesting. I can even see the worth of turning compression off in a lot of cases. However, there are still many people who consider default compression a feature and *rely* on it for their system.

If you went to the gpg people and asked for "-z 0" (which turns off compression) to be the default, it would be a very bad idea because there's 20+ years of presumption that compression is on.

Moreover, it's very easy for anyone to opt out of compression. Put no compression in the key as a pref. 

Making a change to the standard requires a really good reason. Let's face it, even if it were easy to do, and we changed it from a SHOULD to a MAY, that would almost certainly result in no change to software because there's an expectation that it's the default across the user base and has been for twenty-some years. Changing the default in software is a really bad idea, absent a really big reason. If it went all the way from SHOULD to MUST NOT, you'd end up with lots of software even ignoring the new standard -- again, absent some compelling case.

Remember, the word SHOULD in a standard is guidance to an implementer that to do X unless there's a good reason. Any time there's a good reason, the implementation can do whatever it wants. That's it, it's merely guidance.

I'm going to repeat what I said and say that you need some actual security analysis that goes beyond finding a cool exception case. But I'll add that you might be better served by going to the people who make software and systems. It's very easy for them to do what you want. Heck, I've even made a system that does what you want, myself. (It wasn't for your reasons, though. It was because implementation constraints made it drop compression.)

	Jon

---

From: Peter Todd <[email-masked]>
Date: Wed, 19 Mar 2014 17:41:18 -0400

> Which ballot did I cast?   Anyone?

After realizing that I needed to account for the size of the "Version:"
string I got the exact same size as your secret for ballot.1, so I'm
guessing that was your vote.

Am I right?

-- 
'peter'[:-1]@petertodd.org
0000000000000000c7cb0567f1dddff05db43f9d2c32acdb26e89e69eb80c492

---

From: Gregory Maxwell <[email-masked]>
Date: Wed, 19 Mar 2014 15:04:38 -0700

> guessing that was your vote.

Indeed, you are.
https://people.xiph.org/~greg/openpgp_testpubkey.secret.asc  password:
qwertyqwerty

> But it proves nothing here. It's a really, really interesting exception case. We're talking about a default. We're also talking about the protocol definition, and not implementation software.

It's a very highly surprising failure mode which leaks information
about the plaintext by encoding it into the size, one which baffels
otherwise expert users of the sort who would post to the openpgp list
to exclaim "What's being leaked by compression? Really, I don't get
it."

Even thoughtful users who take care to make their messages constant
length will have the implicit compression sneak up and bite them.  Of
course, you could compress and pad up to the original size…

Voting isn't the only case where compression leaks data about the
plain-text, it's just one where I know that it cause and actual
compromise, with actual expert users, in actual practice.

There are a great many people who use gpg to encrypt a small number of
control messages (e.g. for updating route registries and such) where
compression can leak information about the content.

> Compression is on by default because it improves security. It meets that goal. It is, however, a default. Defaults can be changed.

It does not improve security in any practical sense. The presence of
compression harms security severely and in a very practical way in at
least some applications. No cipher should be used where the entropy of
the input is believed to be security relevant, and if one were used,
the compression in gpg still leaves non-trivial known plaintext in
cases where the input begins with known plaintext (in addition to
additional compression headers giving more known plaintext even when
the message is otherwise completely unknown).

(It's possible to design compression systems where the output is
indistinguishable, e.g. arithmetic coders bijective termination, but
none of the supported compressors are designed this way... they will
allow you to detect an incorrect symmetric key with overwhelming
probability with just a dozen bytes of decrypted output or less)

> Moreover, there's a way to work around the issue in the existing standard. Make the vote-submission key not support compression. Poof, it works.

Yea, sure, don't aim the gun at your foot and your foot will not be
shot.  It's true, but it's not always useful.  What do you care about
a specification and software? real engineers encrypt their messages by
hand with pen and paper.

Part of the purpose of the specification and software is that doing
everything 'manually' is too costly and difficult, the specification
hopefully embodies the collected wisdom of careful consideration by
the best available experts.

> However, there are still many people who consider default compression a feature and *rely* on it for their system.

Care to elaborate on how they rely on it? That seems highly suspect to me.

Compression is a useful feature, it's nice that often the base64
encoded encrypted versions are not a ton longer than ascii text... but
if we're going through the trouble of encrypting something then the
encryption really ought to not invisibly leak data about the
plaintext. When something is a general tool used for many applications
then we ought to be assuming a sum-of-all-attacks and not just a very
narrow threat model.

Obviously a size side channel still exists, and might be worth
reducing (e.g. by quantizing message size to a multiple of 512 bytes)
but at least that side channel is highly visible to technical users.

---

From: Jon Callas <[email-masked]>
Date: Wed, 19 Mar 2014 15:58:50 -0700

> to exclaim "What's being leaked by compression? Really, I don't get

It is! It's a really cool failure mode, and I think you should write it up and submit it to some security conference.

However, as I said, it's an exception case. It's also an exception case that you didn't explain very well. Let me try to help:

Zelda is collecting some ballots. The ballots are all text and constant length. The voters, Vernon_i, will each edit the text ballots with their votes, but the resultant ballots will remain constant length.

If the ballots are encrypted with compression, there may be information leaks because the different patterns of voting in the ballot. In the simplest case where there is only one item on the ballot, it is possible that vote can be discerned despite the raw plaintext being constant length.

I think I got that more or less right.

However, there are two workarounds for this:

1. Zelda adds a no-compression preference to her key.
2. The voting system uses the "-z 0" option in a gpg command.

> compromise, with actual expert users, in actual practice.

Please give other cases.

In the usual case, Alice sends a free-form message to a set of recipients. There's no leak in this case.

> compression can leak information about the content.

You're stretching it here. If those messages vary in length, there's not much of a leak. In many cases, the real thing you're doing is *signing* the control messages; in the specific example you give (route registries) the actual content of the message may not even be secret. But I know I'm quibbling.

The workarounds here are:

1. Add a no-compression flag to the receiving key.
2. Add "-z 0" to the command line that generates those messages.

> Care to elaborate on how they rely on it? That seems highly suspect to me.

tar -c source-tree | gpg key >source-tree.pgp.gz

This is also what at PGP Corp we called a "PGP Zip" file, which was implemented as a PGP encrypted tarball. It's done all the time in back-end systems, and very likely the second largest use of PGP, where signing files is the most. It's a really useful idiom.

You're asking for a change to the standard. You're not really doing that, even. You're asking for a change to the default behavior to software that's been around for 20+ years because you have a wonderful edge condition, for which there are not only per-message but per-key workarounds.

I'm really sorry your ballots got spoiled. But you can fix that with zero changes to software nor protocol. 

	Jon

---

From: ianG <[email-masked]>
Date: Wed, 19 Mar 2014 23:08:19 +0000

> to exclaim "What's being leaked by compression? Really, I don't get

Clearly, compression leaks info if there is some understanding of the
structure of the message.  Sure.  But OpenPGP is typically used to ship
lots of large documents around, and people are accustomed to getting the
compression bounty for free.

So there is a sense that in order to protect the very few who might fall
for this case, we'll end up disadvantaging a wider population who might
actually suffer more.

> course, you could compress and pad up to the original size…

The assumption here is that constant length is somehow more secure than
inconstancy.

If for example the voting procedure were this:

Send N messages, 1 for each candidate, with 0 for the ones you do not
vote for (we need reliability here...) and 1 + the name for the one
person you vote for (redundancy is good...) ...

Then you get the same problem;  *length leaks some info*.  This seems to
be with or without compression, so is this just a case of choosing ones
pathology?

There is no fundamental way to overcome the flaw of length in a packet
protocol, which is what OpenPGP is.  (In a stream protocol one can
overcome it by insisting on transmitting X bps forever;  this is what
ZKS did, and setting it at some ridiculously high number like 256kbps
lead the mode to be rather unpopular.)

> compression can leak information about the content.

I see this in my work all the time.  Error packets are 10 bytes long,
success is like 500 bytes.  This is leaking info ... my only solution is
to make all packets like 1024 bytes, but some of my packets are longer.
 How far do I go?  Answer:  I've got better things to worry about right
now.  YMMV.

> probability with just a dozen bytes of decrypted output or less)

That;s interesting.  Maybe what we need to do is look at more
pathological cases and come up with a sort of survey of with/without?

> the best available experts.

Well, it is true that PGP was conceived in a different world to today,
and carries those traditions which are now 20 years old.  But poking at
just one of those assumptions may not reward, because there are 10
others sitting and wobbling.

> but at least that side channel is highly visible to technical users.

So one of those traditions was that every byte saved was important, as
back in those days people still had 9600 baud to worry about.  These
days less so.  But if we're going to look at that, there are a whole
bunch of other things that also merit attention.

iang

---

From: Peter Todd <[email-masked]>
Date: Wed, 19 Mar 2014 19:12:30 -0400

> 2. The voting system uses the "-z 0" option in a gpg command.

I don't want a workaround; I want default behavior that is reasonably
safe for users. Removing default compression is a step forward in that
regard.

> I'm really sorry your ballots got spoiled. But you can fix that with zero changes to software nor protocol. 

Your example isn't much of a failure; the tarball will end up maybe 2x
larger than it should have been, someone might investigate, and they'll
change the command to:

   tar -c source-tree | gzip | gpg key >source-tree.pgp.gz

or something. This is a *very* low-consequence failure mode.

-- 
'peter'[:-1]@petertodd.org
00000000000000004ec562299f1cd08a38fdea8f0d612fce3923203df379c0b3

---

From: Gregory Maxwell <[email-masked]>
Date: Wed, 19 Mar 2014 16:40:57 -0700

> It is! It's a really cool failure mode, and I think you should write it up and submit it to some security conference.

Its old and well known and unsurprising to people who actually work on
cryptographic software.

No amount of presentations at security conferences will actually
protect users, however, unless the default and recommended behavior
changes.

> Please give other cases.

The original post in this thread gave another case, I was adding
another example case where security was compromised in practice.

In the original post PGP is used to encrypt messages containing a
password to access some service, just a password management use— (this
is something that I also happen to do, so I'm doubtful that it's that
fringe an application).  The poster points out that knoweldge of the
size leaks a considerable amount of information about the password.

> In the usual case, Alice sends a free-form message to a set of recipients. There's no leak in this case.

I think its debatable if free form messages are actually the most
common usage of PGP in practice. But thats not here or there, while
working on security the worst cases are usually more important.  In
the usual case no one cares to sniff your email at all and even if
they do you're not saying anything important, not using encryption
saves cpu cycles and avoids compatibility problems. ... but it isn't
the usual cases that we need to protect against.

> 2. Add "-z 0" to the command line that generates those messages.

These aren't actual workarounds because they do not address the
problem that an otherwise highly conscious user would be unaware that
they need to take these steps.  Would you also respond with "Add
--cipher aes" if I were complaining that ROT13 was not a good default
cipher? :)

> This is also what at PGP Corp we called a "PGP Zip" file, which was implemented as a PGP encrypted tarball. It's done all the time in back-end systems, and very likely the second largest use of PGP…

Okay, I think you're using a different definition of rely.  Obviously
if you don't upgrade software nothing changes. Its not unusual that
upgrading software changes behavior. If you upgraded to a version that
didn't compress by default, the end result would be those backups
would be larger.  You'd either not notice and care or you would, and
then after some hunting for the release notes you'd twilddle a knob
and nothing irreparable happens.

> I'm really sorry your ballots got spoiled.

This was years ago (IIRC 2006), I don't care about the event anymore.
I brought it up as a real world example of where this behavior
compromised the security the users reasonably expected.  Not just a
theoretical weakness to counter the claims that the compression harms
nothing, but an actual example of where it happened.

Can you show anything as remotely strong for the assertion that
compression improves security?

> for this case, we'll end up disadvantaging a wider population who might

Well, there are compromises such as padding the post-compression size
to a common interval.

I'm not a super big fan of that because you still may be invisibly
doomed by compression, but I assume (eek) that the cases where the
leaks are really fatal are ones where the messages tend to be quite
small.

> The assumption here is that constant length is somehow more secure than

It's generally fairly intuitive to users who are being thoughtful that
the length of the message is a side-channel. In the case of the
Wikimedia ballots the people who set it up thought of that, and
arranged it so that ballots were permutations.

> be with or without compression, so is this just a case of choosing ones

The distinction being that the leak happens at a level which is
immediately visible to the thoughtful user vs in a way which is pretty
thoroughly hidden and ...

> There is no fundamental way to overcome the flaw of length in a packet

which can't be completely fixed without unreasonable costs, as you note.

One shouldn't decline to make improvements in some things because
other things cannot be improved.

One point here is that it's non-deterministic too in that you could
test and confirm that your ballots all showed up the same size but the
users system has a different compression preference or library
(deflate is not deterministic, the encoder has freedom) and they're no
longer the same size when the users use them.

>  How far do I go?  Answer:  I've got better things to worry about right

Padding to reduce the leakage is interesting even if it doesn't
eliminate it entirely because its cheap, and obscures the least
significant bits which often (ahem, assumptions) are the greatest
entropy leak.

At some point it's indeed too costly to fix and not worth it. But I
argue that getting the details as right as possible is why people
should be using standards and popular software and not just encrypting
everything on their own.

---

From: Nicholas Cole <[email-masked]>
Date: Thu, 20 Mar 2014 07:53:22 +0000

>> compromise, with actual expert users, in actual practice.

This discussion reminds me (trivially) of the example of university or
job acceptance or rejection letters.  In most cases the size of the
envelope usually reveals the content of the message, since an
acceptance letter will come with all sorts of additional forms etc.
There are many cases where the size of the message reveals something
about the content, compression or no compression.

Less trivially - voting systems online are really hard.  I remember
that _Applied Cryptography_ devoted a whole chapter to the issue.
In this case compression unexpectedly (for the users) added to the
message frustrated efforts at secrecy that were based on assumptions
about message length.    It is worth someone writing up this
experience (I can't find any documentation of it online).  I think it
is a bit of a stretch to say that compression itself is bad.  It just
happened to be unhelpful in this case.  As you note above, Jon, the
key used for voting could have had no compression preference and all
would have been well.

N.

---

From: Werner Koch <[email-masked]>
Date: Thu, 20 Mar 2014 12:25:14 +0100

> zero changes to software nor protocol.

Yep.

However, this a problem of the voting protocol.  You would run into the
same problems if you use a ZIP file with encryption or require to send
an ODF document.  Both compress stuff; even text editors may do that by
replacing runs of white space by tabs.

There are a lot of possible failure modes to be investigated which is
the reason why getting electronic voting right is so hard.

Shalom-Salam,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Alfredo Pironti <[email-masked]>
Date: Thu, 20 Mar 2014 12:55:13 +0100

On Thu, Mar 20, 2014 at 12:25 PM, Werner Koch <[email-masked]> wrote:

> However, this a problem of the voting protocol.

It would be, if the voting protocol was prescribing compression, or was
using ballots of different lengths.

Instead, here OpenPGP is to blame because it silently slips in compression.

>  You would run into the
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

---

From: Werner Koch <[email-masked]>
Date: Thu, 20 Mar 2014 14:04:26 +0100

> using ballots of different lengths.
  
I already mentioned that there are many factors which need to be
consider when creating a voting protocol.  All parts involved in running
the protocol need to be considered - not just the length of the ballots
and the encryption protocol.  The described fault was made possible by a
non-well defined voting protocol.

Salam-Shalom,

   Werner

---

From: ianG <[email-masked]>
Date: Thu, 20 Mar 2014 13:51:12 +0000

> Instead, here OpenPGP is to blame because it silently slips in compression.

OpenPGP doesn't make any statement about whether it preserves the
length, up or down.  Typically crypto can enlarge a packet, or it can
shrink the packet.  It's complicated, we slap on some MACs and headers
and padding and stuff, so the packet ends up growing.  Then some of that
might be clawed back by compression or ratcheting or packet slicing or
whatever.

So we don't typically promise much about packet lengths.  This becomes a
bit more germane with say disk encryption, where for some reason people
insist on not losing much space, and it becomes convenient to encrypt
block for block.

It *also* becomes an analogous issue when emailing from one person to
another, as the trackability of names and times is an issue.

As soon as you start putting some attention on what the users are doing,
a generic broad protocol such as OpenPGP and also SSH and TLS and Skype
and etc start to show edge cases where they might not be quite perfect
for the task.  Which is why there is a continuous war going on between
the folks who say "use TLS and you're secure" and the folks who have to
protect real value.

It seems general-meets-specific brittleness has become an issue when
people have a single byte protocol such as the voting protocol in use.
It could be that OpenPGP could be improved for that protocol failure
case, at the expense of harming all the other people who love the
compression.

But actually, there is a wider question here.  Is the voting protocol
properly thought out, and is OpenPGP really the answer?

I doubt.  Voting is one of the really hard problems.  Most of the
old-timers I know here will be able to go in and rip the guts out of any
simple slapped-together voting protocol.  Most of the old-timers know
that voting protocols are very hard, and they don't get involved because
it's so darn depressing.

So I'd say, no.  OpenPGP isn't to blame at all, that I see. Voting is
hard, and I expect the people who put it together didn't do nearly
enough thinking, or perhaps they assumed to much.  I for one would not
use OpenPGP to do voting.  Or if I did, and it f**ked up, I'd say darn,
my fault, should have known better :)

iang

---

From: Alfredo Pironti <[email-masked]>
Date: Thu, 20 Mar 2014 14:56:08 +0100

> Compression is on by default because it improves security.

I disagree. Compression is not a tool designed to build secure systems. Can
you be more precise in what improvement to security compression would bring?

In this discussion, the "input distribution" argument has already been
debunked: a good crypto scheme works equally well regardless of the input
distribution.

Also attacks that seemed to be thwarted by compression turned out to be
actually thwarted by the different message format that compression implies.

What other security arguments would remain in favor of compression?

Applications that rely on compression for functionality (not security) are
another matter. If your application relies on gpg compression so crucially
that a system crash would occur otherwise, then you may want to set an
explicit -z X flag to gpg anyway.

> It meets that goal. It is, however, a default. Defaults can be changed.
> Moreover, there's a way to work around the issue in the existing standard.
> Make the vote-submission key not support compression. Poof, it works.
>

---

From: ianG <[email-masked]>
Date: Thu, 20 Mar 2014 13:57:46 +0000

On 19/03/2014 22:58 pm, Jon Callas wrote:
> However, as I said, it's an exception case. 

Is there a sense that this could be more traumatic at small packets?
Could we set a limit say 100b under which packets aren't compressed?

Actually I think not because the attack is about comparison amongst
results of different packets.  The encrypting/compressing agent only
knows about its one packet, it knows nothing about the other packets.
So it cannot know about the effect of compression on the other packet,
and how one ends up being markedly different to another.

If I get it right, it all comes back to the (hidden? agreed?) assumption
of length.  What is our preference, to meet some assumption about
length?  Or to not meet it?

Perhaps a comment needs to be put in the document "We make no claims as
to the preservation of length.  Compression can result in leaking
information which can be illuminating in known-plaintext and
multi-packet scenarios."

iang

---

From: ianG <[email-masked]>
Date: Thu, 20 Mar 2014 14:09:25 +0000

> What other security arguments would remain in favor of compression?

At the margin, if a protocol finds itself finding 2x sized messages, it
may simply fail.  This leads to a security failure if the result is that
the user switches away or does something else like cleartext message
delivery (the failure known as S/MIME).

This is a very meta-argument, in that usability over time is more
important than anything else.  It's not a particularly good theoretical
argument because it lacks context, it's more like one of those
unforeseen consequences you can only find out by trying it.  We may find
on trying it that we lose half our user base because all their backups
break;  or we may not.

It's also the case that we tend to prefer to protect our existing users
and their apps more than we tend to help people who aren't as yet firmly
in that set and dependent.  This is a tendency that I argue against
vociferously in any other context except an IETF WG ;)

Or in simpler terms, if it ain't broke, don't fix it.

iang, amused that I find myself defending the old, crusty ways!