Re: [openpgp] Disabling compression in OpenPGP

Gregory Maxwell <gmaxwell@gmail.com> Wed, 19 March 2014 22:04 UTC

Return-Path: <gmaxwell@gmail.com>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 30B951A07E2 for <openpgp@ietfa.amsl.com>; Wed, 19 Mar 2014 15:04:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 3aGoONFXdfl6 for <openpgp@ietfa.amsl.com>; Wed, 19 Mar 2014 15:04:48 -0700 (PDT)
Received: from mail-la0-x22d.google.com (mail-la0-x22d.google.com [IPv6:2a00:1450:4010:c03::22d]) by ietfa.amsl.com (Postfix) with ESMTP id 1C3A51A07A1 for <openpgp@ietf.org>; Wed, 19 Mar 2014 15:04:47 -0700 (PDT)
Received: by mail-la0-f45.google.com with SMTP id hr17so6431893lab.18 for <openpgp@ietf.org>; Wed, 19 Mar 2014 15:04:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=GiJtGgrVO3cmhRqO31Nv2iaI6cYxdVrL+WKBn6Jh5+Q=; b=n76XLTQN2AjoJz3Jb2/alnoL7DIZSY/NiC/YYBqO8M+Ot/CTkr6He8gHDcqCjIvshb HxE4F3PtEOspR8CF6K8dGnyQfgHlMp/lZ8a6Z9MkPxeWiUmKL5/8cplPe1UjN96WH/1K MlyeitQ7ZXhAUBarH17iJlDGRZZlEnxvaFPeZTRfO6DlYUCmM0ATurpNQu+1BfZXMsmj W2u4RMInebgzXnWMQbWJK3cVMOba6SE555Vi7dHS0eeoqEHDRtQgFF0Ts4o+ZlRQagTZ UpsbwXeEn1sHNIVakl1KilWg+70jv4HdINXEcZqPxp/cNvqnkKim+fCIrAKNzHJy2BPO iq7Q==
MIME-Version: 1.0
X-Received: by 10.112.254.163 with SMTP id aj3mr26023174lbd.20.1395266678721; Wed, 19 Mar 2014 15:04:38 -0700 (PDT)
Received: by 10.112.184.226 with HTTP; Wed, 19 Mar 2014 15:04:38 -0700 (PDT)
In-Reply-To: <20140319214118.GA17419@savin>
References: <CALR0uiJG6GcngWMUkg6NrP7_4uwf8+QDn6aMF-qonOpRMLdo3w@mail.gmail.com> <95BD0817-D762-41DD-8444-A0C4F7AF1003@jabberwocky.com> <CALR0uiL0-Xp8E=F3idtzBkmRNLk7K_M_cqMt+i2HdNqaNkwn=w@mail.gmail.com> <849778F8-1C16-4FF8-A039-6363C158BD1F@callas.org> <20140319204047.GC30999@savin> <DE00E9BD-1D37-4750-B156-BBDC4B59DB7F@callas.org> <CAAS2fgQZPPrdehcs6TxmYikmyyfxOJqAdngaFk5=PcSGEGnejA@mail.gmail.com> <20140319214118.GA17419@savin>
Date: Wed, 19 Mar 2014 15:04:38 -0700
Message-ID: <CAAS2fgQotHyN=CFKoWO_aUdP8bhkSixEqSDQcALZ35mG+tk1tA@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/openpgp/ND6XSjzQIkIZCci2aPMzDnIQq9o
Cc: David Shaw <dshaw@jabberwocky.com>, "openpgp@ietf.org OpenPGP" <openpgp@ietf.org>, Jon Callas <jon@callas.org>, Alfredo Pironti <alfredo.pironti@inria.fr>
Subject: Re: [openpgp] Disabling compression in OpenPGP
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 19 Mar 2014 22:04:53 -0000

On Wed, Mar 19, 2014 at 2:41 PM, Peter Todd <pete@petertodd.org> wrote:
> 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?

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

On Wed, Mar 19, 2014 at 2:37 PM, Jon Callas <jon@callas.org> wrote:
> 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.