Subject: [Cfrg] Protecting metadata in encrypted protocols

From: Bryan Ford <[email-masked]>
Date: Mon, 2 Nov 2015 16:11:46 +0900

In followup to my in-person comment regarding “next steps”, here is the Internet-Draft I was referring to:

	Title: Modernizing the OpenPGP Message Format
	URL: https://datatracker.ietf.org/doc/draft-ford-openpgp-format/ <https://datatracker.ietf.org/doc/draft-ford-openpgp-format/>

To clarify what I have in mind as a cross-cutting concern that “might” be relevant to CFRG, please skip to section 2.3 in the above draft and ignore the OpenPGP-specific stuff in earlier sections.  In summary, there are at least two elements:

1. Researching and developing best practices for length-padding for protection against traffic analysis and other length-related attacks (e.g., BEAST).

2. Researching ways to develop file/packet formats in which “every byte is encrypted” including what would conventionally be left unencrypted, e.g., file magic numbers, cipher selection data, negotiation chatter, TLS chunk lengths, etc.

The first topic probably isn’t highly crypto-heavy, but the second one would involve nontrivial application of crypto in somewhat unusual/novel ways, which is what makes me wonder if it might be a good fit for CFRG.

Thanks
Bryan

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 3 Nov 2015 13:18:14 +0000

Bryan Ford <[email-masked]> writes:

>2. Researching ways to develop file/packet formats in which “every byte is
>encrypted” including what would conventionally be left unencrypted, e.g.,
>file magic numbers, cipher selection data, negotiation chatter, TLS chunk
>lengths, etc.

Ugh, that opens you up to all manner of oracle attacks (as the SSH guys have
found out), because you need to decrypt and process possibly attacker-
manipulated data in order to continue.  It's also not clear what this actually
gains you, if I send you a 10K email message then encrypting the length
doesn't give you anything, you need a key ID to decrypt it (and in any case
it'll have been sent to your email address) so I know who it's for and can
figure out what PKC algorithm is used from the public key, etc.  All you've
really done is made processing difficult.

If you really care that much about privacy protection, double-wrap the
message, as is done for sending classified docs through the mail (brown paper
envelope on the outside, classification-marked envelope on the inside).  This
doesn't require any change to the PGP format, just a note somewhere about how
you apply it.

Peter.

---

From: Bryan Ford <[email-masked]>
Date: Wed, 4 Nov 2015 01:48:12 +0900

Hi Peter,

On Tuesday, November 3, 2015, Peter Gutmann <[email-masked]>
wrote:

> Bryan Ford <[email-masked] <javascript:;>> writes:
>
> manipulated data in order to continue.

It sounds like you're pre-judging my metadata-encryption scheme to be
insecure before I've even presented one.  The scheme I have in mind ensures
everything is integrity-protected throughout: if the attacker changes
anything it's obvious to the decryptor before the decryptor does anything
with it.

If you're skeptical it's possible or practical to do this securely, that's
perfectly understandable, since I haven't yet proposed a concrete scheme to
be picked apart.  I hope to be able to do that soon (the write-up is in
progress).

But as I said in the meeting, the only question I'm asking right now is: IF
we could do this securely, how interested would people be?  In other words,
is it (potentially) worth the trouble?

>   It's also not clear what this actually
> doesn't give you anything,

I'm not proposing to "encrypt the length"; in fact it's not obvious to me
how one might do so. The encrypted blob has to be of some size; there's no
way to hide that. I'm talking about two separate, orthogonal but
complementary protection mechanisms:

1. Encrypting *internal* PGP metadata that's normally part of PGP-encrypted
binary blobs but left unencrypted in that blob (magic number etc).  This
doesn't do much if anything to hide the length of the cleartext, but it's
not trying to.

2. Internally pad these blobs to reduce (not eliminate) leakage via the
encrypted length. You can't eliminate leakage via the length entirely
unless you're willing to mandate padding all PGP clear texts to a single
standard ciphertext size, which does seem patently unrealistic.

Note that encrypting both content and embedded metadata (proposal #1 above)
in principle reduces information leakage from O(L) to O(log L): i.e.,
instead of leaking the whole L-bit cleartext content itself we leak only
the log2(L)-bit exact length of that context. Thus, from a
formal/asymptotic perspective we can view the encryption of
variable-length, un-padded blobs as an operation that cuts leakage from
O(L) to O(log L).

The goal of proposal #2 above is to cut maximum information leakage further
from O(log L) to O(log log L).  The simple, obvious approach of padding all
ciphertext up to the next power of 2 (or the next power of anything you
like) achieves this, but in a somewhat wasteful fashion. The approach I
actually have in mind (which I haven't presented yet but will soon and as I
said am happy to share informally with anyone interested) cuts maximum
information leakage from O(log L) to O(log log L) in a slightly less
wasteful fashion.

Further, there's a simple argument that it's impossible to reduce maximum
information leakage from an encrypted blob of arbitrary size L to anything
less than O(log log L) unless you're willing to tolerate more than
constant-factor waste (eg some files have to be padded to arbitrarily large
multiples of their cleartext size), which as I mentioned seems patently
unrealistic.

you need a key ID to decrypt it (and in any case
> really done is made processing difficult.

Encrypted E-mail is actually not the primary motivating use case I envision
for this: indeed, the surrounding context (eg the mailbox the encrypted
blob is in) perhaps reveals more sensitive metadata than the unencrypted
metadata in the blob itself, and it'll certainly be obvious to anyone
inspecting your mail that there's some kind of encrypted blob in there.
That's a separate problem and topic that seems impossible to solve in the
context of OpenPGP (that's an email system problem). But encrypting the
embedded metadata in OpenPGP blobs could help some, even in the email
context: eg, by making it unclear who *else* besides me the blob was
encrypted for (who are my "co-conspirators"?).

But OpenPGP is also used in many contexts outside of email: eg, simply to
encrypt a sensitive file sitting on my hard disk. Right now these
self-identify as OpenPGP files. I personally would prefer if they didn't
self-identify, and could plausibly (to an attacker or a judge) be encrypted
blobs produced by some other random application that got dropped on my hard
disk without me even knowing it, eg an encrypted swap file or browser cache
database or something like that. Of course to make this deniability really
plausible we should try to eventually persuade some browser vendors and
other software vendors to encrypt their caches in uniform-random-blob
format as well; that might be a long-term goal but we gotta start somewhere.

Also, In the metadata encryption scheme I have in mind the decryptor
doesn't need to know the key-ids of the file's recipients before being able
to "break into" (and integrity-check) the file. Again, it's perfectly
reasonable to be skeptical it's possible to do what I claim before I've
shown any evidence, but please don't assume my approach to be insecure or
impossible before I've even presented it. :)

Thanks
B

---

From: "Paterson, Kenny" <[email-masked]>
Date: Tue, 3 Nov 2015 18:23:26 +0000

Hi Bryan, Peter,

On 03/11/2015 16:48, "Cfrg on behalf of Bryan Ford" <[email-masked]
on behalf of [email-masked]> wrote:
>>2. Researching ways to develop file/packet formats in which ³every byte
>>is
>>encrypted² including what would conventionally be left unencrypted, e.g.,

Indeed it does as we reported here:

http://isg.rhul.ac.uk/~kp/SandPfinal.pdf

However, the story has a happy ending: as a consequence of this attack on
SSH, we went on to study the problem of "encrypted message lengths" in a
more general context, eventually coming up with this paper:

http://eprint.iacr.org/2015/059

(which is the full version of a paper published in Eurocrypt 2012). What
this paper essentially shows is that it is possible to hide message
lengths in streams of data (like SSH might produce) whilst maintaining
appropriate levels of security (security against chosen ciphertext
attacks, basically) and resisting Denial-of-Service attacks.

Bryan, this might be useful for your intended project, though the setting
is a bit different from the one you describe below.

Cheers

Kenny

>insecure before I've even presented one.  The scheme I have in mind
>ensures everything is integrity-protected throughout: if the attacker
>changes anything it's obvious to the decryptor
> before the decryptor does anything with it.
>
>
>If you're skeptical it's possible or practical to do this securely,
>that's perfectly understandable, since I haven't yet proposed a concrete
>scheme to be picked apart.  I hope to be able to do that soon (the
>write-up is in progress).
>
>
>But as I said in the meeting, the only question I'm asking right now is:
>IF we could do this securely, how interested would people be?  In other
>words, is it (potentially) worth the trouble?
> 
>
>how one might do so. The encrypted blob has to be of some size; there's
>no way to hide that. I'm talking about two separate, orthogonal but
>1. Encrypting *internal* PGP metadata that's normally part of
>PGP-encrypted binary blobs but left unencrypted in that blob (magic
>number etc).  This doesn't do much if anything to hide the length of the
>cleartext, but it's not trying to.
>
>
>Note that encrypting both content and embedded metadata (proposal #1
>above) in principle reduces information leakage from O(L) to O(log L):
>i.e., instead of leaking the whole L-bit cleartext content itself we leak
>only the log2(L)-bit exact length of that
> context. Thus, from a formal/asymptotic perspective we can view the
>encryption of variable-length, un-padded blobs as an operation that cuts
>leakage from O(L) to O(log L).
>
>
>The goal of proposal #2 above is to cut maximum information leakage
>further from O(log L) to O(log log L).  The simple, obvious approach of
>padding all ciphertext up to the next power of 2 (or the next power of
>anything you like) achieves this, but in
> a somewhat wasteful fashion. The approach I actually have in mind (which
>I haven't presented yet but will soon and as I said am happy to share
>informally with anyone interested) cuts maximum information leakage from
>O(log L) to O(log log L) in a slightly less
> wasteful fashion.
>
>
>information leakage from an encrypted blob of arbitrary size L to
>anything less than O(log log L) unless you're willing to tolerate more
>than constant-factor waste (eg some files
> have to be padded to arbitrarily large multiples of their cleartext
>size), which as I mentioned seems patently unrealistic.
>
>
>
>Encrypted E-mail is actually not the primary motivating use case I
>envision for this: indeed, the surrounding context (eg the mailbox the
>encrypted blob is in) perhaps reveals more sensitive metadata than the
>unencrypted metadata in the blob itself, and it'll
> certainly be obvious to anyone inspecting your mail that there's some
>kind of encrypted blob in there. That's a separate problem and topic that
>seems impossible to solve in the context of OpenPGP (that's an email
>system problem). But encrypting the embedded
> metadata in OpenPGP blobs could help some, even in the email context:
>eg, by making it unclear who *else* besides me the blob was encrypted for
>(who are my "co-conspirators"?).
>
>
>self-identify, and could plausibly (to
> an attacker or a judge) be encrypted blobs produced by some other random
>application that got dropped on my hard disk without me even knowing it,
>eg an encrypted swap file or browser cache database or something like
>that. Of course to make this deniability
> really plausible we should try to eventually persuade some browser
>vendors and other software vendors to encrypt their caches in
>uniform-random-blob format as well; that might be a long-term goal but we
>gotta start somewhere.
>
>
>doesn't need to know the key-ids of the file's recipients before being
>able to "break into" (and integrity-check) the file. Again, it's
>perfectly reasonable to be skeptical it's possible
> to do what I claim before I've shown any evidence, but please don't
>assume my approach to be insecure or impossible before I've even
>presented it. :)
>
>
>Thanks
>B
>
>
>

---

From: Taylor R Campbell <[email-masked]>
Date: Tue, 3 Nov 2015 18:29:38 +0000

Date: Wed, 4 Nov 2015 01:48:12 +0900
   From: Bryan Ford <[email-masked]>

Worthwhile.  The Tor Project has gone to some effort to hide inside
mostly-ciphertext channels, starting with HTTPS, for censorship
resistance, but it would be easier to avoid protocol-specific
censorship if there were ciphertext-only protocols with no cleartext
fallback for widespread applications beyond *ahem* nefarious dissident
tools like Tor.

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 4 Nov 2015 00:39:44 +0000

>anything it's obvious to the decryptor before the decryptor does anything

... and there's the problem, the only way for that to work is if the message
includes a pile of metadata to allow the recipient to verify its integrity: A
key transport mechanism that identifies the recipient key to use (if you're
using MACs) or a signature from the sender, algorithm information, length
information telling you what you need to run your MAC over, etc.

You can come up with Rube Goldberg workarounds to this that sort of work most
of the time if the recipient can make all sorts of assumptions about what to
do with a message, but it doesn't exactly lead to a usable product...

Peter.