Subject: [TLS] mitigate the attack on TLS compression

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Mon, 17 Sep 2012 23:14:19 +0200

Hello,
 I'm wondering how other implementers mitigated the Rizzo's attack on
TLS compression [0]. What I've currently done is to suggest:
1. to disable compression
2. If you need compression use CBC random padding

and I plan to add a stateless compression mode (which violates RFC3749).
Any other ideas?

regards,
Nikos

[0].
http://security.blogoverflow.com/2012/09/how-can-you-protect-yourself-from-crime-beasts-successor/

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 17 Sep 2012 23:29:03 +0200

> and I plan to add a stateless compression mode (which violates RFC3749).

I'm curious, how would a stateless compression scheme work?  Compress
each record separately?  Is that enough to fix this?  I'm thinking some
applications might concatenate data from different origins into the same
TLS record anyway.

/Simon

---

From: Adam Langley <[email-masked]>
Date: Mon, 17 Sep 2012 17:33:47 -0400

On Mon, Sep 17, 2012 at 5:29 PM, Simon Josefsson <[email-masked]> wrote:
> each record separately?  Is that enough to fix this?

(We're still keeping quiet about the details of this attack at the
request of the researchers.)

A per-record compression scheme could be implemented in a backward
compatible fashion with zlib, but is insufficient to stop the attack.

Cheers

AGL

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 18 Sep 2012 00:17:44 +0200

> request of the researchers.)

I got the same request by the researcher, but I am unable to
understand/follow it, when at the same time the fact of the attack is
leaked at all the online technology forums.

> compatible fashion with zlib, but is insufficient to stop the attack.

I suppose you mean the Z_FULL_FLUSH? Why is it insufficient?

regards,
Nikos

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 18 Sep 2012 00:19:24 +0200

> applications might concatenate data from different origins into the same

Indeed, but an application such as a VPN could arrange so that data from
different sources are stored in different records (and actually I had
the VPN application in mind rather than HTTPS for that).

regards,
Nikos

---

From: Adam Langley <[email-masked]>
Date: Mon, 17 Sep 2012 18:31:19 -0400

> I suppose you mean the Z_FULL_FLUSH? Why is it insufficient?

Because, within each record, an HTTP client is including attacker
controlled data (i.e. the path) and sensitive data (i.e. a cookie).

By compressing all that together, the resulting length reveals some
information about the sensitive data. By repeating with many queries
where the sensitive data is the same (as it would be for cookies), the
sensitive data leaks.

In fact, I think a Z_FULL_FLUSH would make the attack easier because
the attacker no longer has to worry about the previous record being in
the compression window.

Cheers

AGL

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 18 Sep 2012 00:42:14 +0200

> where the sensitive data is the same (as it would be for cookies), the

I wasn't clear here. The idea is to use Z_FULL_FLUSH with the data split
in independent records. Indeed in HTTPS may not be easy to split
attacker-controlled data from other data, but I had a VPN case in mind,
where you want to separate the traffic of different users.

Nevertheless compression in TLS, or better compression before encryption
seems quite flawed in a communication channel. Maybe it is better to
disable compression altogether and wait for a compression algorithm that
may be suited for a communication scenario where the adversary controls
parts of the data.

regards,
Nikos

---

From: Adam Langley <[email-masked]>
Date: Mon, 17 Sep 2012 19:09:03 -0400

> where you want to separate the traffic of different users.

Ah, if you can compress the different classes of data separately, then
certainly that'll be sufficient. In the VPN case you have an easy way
to distinguish classes of data but, as you point that, that's
generally difficult, at least with existing APIs.

Cheers

AGL

---

From: [email-masked] (Martin Rex)
Date: Tue, 18 Sep 2012 01:35:16 +0200 (CEST)

Nikos Mavrogiannopoulos wrote:
> Adam Langley wrote:

Using a single TLS connection state to process data from different users
is a serious fallacy of the application on top of TLS.  Using seperate
TLS connection states for each user (and multiplexing the result over
a single TCP connection) would entirely prevent that problem.
Creating only the initial connection states through full handshake
and all others through abbreviated handshakes (aka session resume)
would be OK, since the traffic keys are distinct for different
connection states.

Admittedly, this might require a backwards-incompatible change to
existing SSL-VPN protocol designs.  Has anyone ever proposed that
all hosts in a subnet should be using the same IPsec traffic keys?
I wonder how/why such a flawed design got used for SSL-VPNs.

> seems quite flawed in a communication channel.

Compression after encryption seems quite a waste (since one of the
criteria for good encryption algorithms is that they make the
redundancy / repeating patterns of data disappear which existing
compression algorithms vitally need to achive any compression.

>
> Maybe it is better to disable compression altogether

or never had it implemented from the beginning :)

>
>                                                      and wait for a
> compression algorithm that may be suited for a communication scenario
> where the adversary controls parts of the data.

The compression algorithm is not the problem here.
The mixing of attacker supplied data an assumed confidential
data is the real problem.

If you ever have to do this, then you MUST NOT provide an oracle
for the attacker that he can use to repeatedly guess about
characteristics of the very same confidential data.

Think about is, guessing SSL cookies (what BEAST did and CRIME does)
is actually pretty lame.  The real problem is, that a browser will
happily execute attacker-supplied active content and insert a static
SSL-cookie or static session id that provides a disclosing
authentication across requests.  Even with compression disable,
TLSv1.2 and no possibility for the attacker to observe (let alone MitM)
the network traffic, the attacker can simply ask the browser to
perform whatever fraudulent POST the attacker wants performed, and
the browser will happily perform it.  THAT is the real problem,
and fixing that problem will require serious reengineering of
how request authentication is performed on the Web.

-Martin

---

From: Florian Weimer <[email-masked]>
Date: Tue, 18 Sep 2012 09:26:29 +0200

On 09/18/2012 01:09 AM, Adam Langley wrote:
> certainly that'll be sufficient.

Depending on the application, quite a bit of data can still leak, 
particularly if you can determine the plaintext length and thus infer 
the compression ratio.  For example, it's been demonstrated that you can 
detected a wide range of phonemes in compressed and encrypted voice traffic.

-- 
Florian Weimer / Red Hat Product Security Team

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 18 Sep 2012 11:43:58 +0200

> would be OK, since the traffic keys are distinct for different

I do not share this view. There is really no other way. The same claim
can be repeated for mixing separate application data into the same user
tunnel, and then for mixing application input with user input in the
same application tunnel and so on. Once you have a tunnel, you must make
sure the tunnel offers its promise (confidentiality) irrespective of the
data that pass from it.

> Compression after encryption seems quite a waste 

I made no point on compression after encryption.

> data is the real problem.

The problem is that there no confidential and non-confidential data for
TLS. TLS operates in an abstract way under some application protocol. It
was designed in a way to operate under any application protocol no
matter how it arranged its confidential or non-confidential data.

This proved to be more difficult than anticipated with the CBC attacks
and now the compression ones.

> characteristics of the very same confidential data.

This is a concern, that unfortunately TLS can do very little. The oracle
is typically provided by the upper layers and TLS should protect
(ideally) without having any knowledge of their operation.

regards,
Nikos

---

From: Richard Hartmann <[email-masked]>
Date: Tue, 18 Sep 2012 14:55:29 +0200

On Tue, Sep 18, 2012 at 11:43 AM, Nikos Mavrogiannopoulos
<[email-masked]> wrote:

> I do not share this view. [...]
> Once you have a tunnel, you must make

Adding more layers of security is (almost always) a Good Thing if
performance and other metrics are not impacted.

That being said, I agree that a tunnel should be secure no matter what
you send through it.

> matter how it arranged its confidential or non-confidential data.
[...]
> (ideally) without having any knowledge of their operation.

As it has to be. Everything else would be a clear violation of layering.

-- 
Richard

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 18 Sep 2012 15:20:49 +0200

> That being said, I agree that a tunnel should be secure no matter what

Secure against what?  Some length and timing information of plaintext
data will always be revealed with the current TLS design.

There are always-on systems out there that transmit data at a constant
rate and of constant size, with payload interleaved into the otherwise
random data, but from a bandwidth utilization and Internet scalability
point of view those models are fairly unappealing.

/Simon

---

From: Richard Hartmann <[email-masked]>
Date: Tue, 18 Sep 2012 15:32:24 +0200

> data will always be revealed with the current TLS design.

Fair point, I should have specified that.

Let's not descend into obvious assumptions, but you are correct in
calling me out on not being specific; thanks

-- 
Richard

---

From: Geoffrey Keating <[email-masked]>
Date: 18 Sep 2012 17:46:33 -0700

> data will always be revealed with the current TLS design.

This is an acknowledeged flaw in TLS, I don't think it contradicts
Richard's point---this 'should' be fixed, if only we knew how.

Another thing that TLS can't avoid is that it reveals the existence of
the connection.  This is often far more significant than any details of
which data is being transferred.

---

From: [email-masked] (Martin Rex)
Date: Wed, 19 Sep 2012 17:25:54 +0200 (CEST)

Nikos Mavrogiannopoulos wrote:
> Martin Rex wrote:
> I do not share this view. There is really no other way.

Of course, there is.

> The same claim can be repeated for mixing separate application data
> into the same user tunnel, and then for mixing application input
> with user input in the same application tunnel and so on. Once you
> have a tunnel, you must make sure the tunnel offers its promise
> (confidentiality) irrespective of the data that pass from it.

(Existing SSL/) TLS *is* no such tunnel, and never was.
This is *well* known, obvious and self-evident.

RFC 5246 even spells it out explicitly:

   http://tools.ietf.org/html/rfc5246#page-16

   Any protocol designed for use over TLS must be carefully designed to
   deal with all possible attacks against it.  As a practical matter,
   this means that the protocol designer must be aware of what security
   properties TLS does and does not provide and cannot safely rely on
   the latter.

   Note in particular that type and length of a record are not protected
   by encryption.  If this information is itself sensitive, application
   designers may wish to take steps (padding, cover traffic) to minimize
   information leakage.

Recall what was described as a characteristic for SSL (and is still present
in current version of TLS) in the 1996 USENIX paper from Wagner and Schneier
"Analysis of the SSL 3.0 protocol".

  http://www.schneier.com/paper-ssl.pdf

  3.1  Confidentiality: eavesdropping

  SSL will provide a lot of known plaintext to the eavesdropper,
  but there seems to be no better alternative; since the encryption
  algorithm is required to be strong against known-plaintext attacks
  anyway, this should not be problematic. 

  What Wagner/Schneier are refering to with this is describe in
  Bruce Schneiers "Applied Cryptography"
  Section 1.1 Terminology, Cryptoanalysis (page 6 in Second Edition)

   2. known-plaintext attack

What the Web-Browser is doing in the BEAST and CRIME attacks, is however
providing to the attacker for free a facility that is vaguely similar to

  4. adaptive-chosen-plaintext attack

What the attacker succeeds in doing is *NOT* breaking of the
encryption (no recovery of encryption keys is performed), but
instead recovery of specific plaintext.

> (ideally) without having any knowledge of their operation.

Similar to the general rule "attacks only get better", the security
properties of a cryptographic protocol can only be further spoiled
by how applications use a protocols.  So applications MUST NOT be
ignorant in how they employ cryptographic protocols.  Instead,
cryptographic engineering must be used to design how an application
uses a cryptographic protocol, so that the app does not spoil
all of the security properties.

To obtain the tunnel properties/characteristics that you're looking for,
a higher effort would be necessary, and the obvious "known plaintext"
property of existing TLS would have to be removed.

What comes to mind here might be a randomly sized random padding at
the start plus at the end of the plaintext, plus an additional *inner*
encryption with a symmetric stream cipher.  That mostly fixes the
"lots of known plaintext" design property of the regular/outer
symmetric encryption of TLS (it will still not completely hide
plaintext length information, though).

-Martin

---

From: Nico Williams <[email-masked]>
Date: Wed, 19 Sep 2012 11:28:57 -0500

ISTM that the right place to put compression is at the application
layer.  I.e., in the content encoding.  This being HTTP, using
transfer encoding has to work and it would indeed.  So, no compression
in TLS but compression at the application and/or proxy -> no attack.
We can do this because HTTP apps often already know how to do
compression at the app layer.

Of course, moving responsibility for compression up a layer or two
does nothing with respect to BEAST-like attacks on TLS because we're
not talking about [and no one would seriously propose, I'm sure]
moving responsibility for crypto up a layer or two either.  That said,
we know how to protect against adaptive chosen plaintext attacks, so
that should not be an issue now.

Nico
--

---

From: [email-masked] (Martin Rex)
Date: Wed, 19 Sep 2012 19:17:49 +0200 (CEST)

Nico Williams wrote:
> layer.  i.e., in the content encoding.

That does not really solve the problem that the CRIME attack feeds on.
(and I didn't comment on the compression in my last reply either,
 but also did not change the thread subject...)

Compression can easily spoil your confidentialy.  Sometimes completely.
The motivation for using compression is reduction of length of your data.
This can spoil your confidentiality whenever differences in length
are visible to an attacker, and typical compression output is completely
deterministic and predictable for known compression input.

So if the entirey set of possible "answers" to a specific question
compresses to a distinct length, and all these distinct lengths
are recognizable to an attacker, it will not matter how perfect your
encryption algorithm is, there will not be any confidentiality.

For the TLS compression situation, concatenating attacker-supplied
and assumed confidential data before feeding it to a compression
function is already dangerous, because the compression output
will vary depending on the similarities between the attacker-supplied
and the assumed confidential data.  When providing the attacker a
facility to perform an adaptive chosen attack on such a compression
(concatenation of attacker supplied and assumed confidential data),
then you will quickly spoil your entire confidentiality if the
output length of the compression function can be observed by
the attacker.

So it doesn't really matter where in the software stack you perform
compression.  The problem occurs whenever attacker-supplied and
assumed confidential data is fed into a compression function, and
differences in the resulting output length can be observed by the
attacker.

The only reliable countermeasure (pad all possible compression outputs to
the exact same length) will usually defeat the purpose of compression.

-Martin

---

From: Nico Williams <[email-masked]>
Date: Wed, 19 Sep 2012 12:40:29 -0500

> differences in the resulting output length can be observed by the

By doing compression at the application layer we allow the application
to decide which data deserve a higher quality of protection.  Static,
might-as-well-be-public data can be compressed.

Nico
--

---

From: [email-masked]
Date: Thu, 20 Sep 2012 17:50:30 +0800

> might-as-well-be-public data can be compressed.
Or let the application layer adds random to sensitive data first, then 
compress and encrypt?

> 
> Nico
> --
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Tom Ritter <[email-masked]>
Date: Thu, 20 Sep 2012 09:14:36 -0400

> Or let the application layer adds random to sensitive data first, then

You have to be careful, if the application always adds X bytes of random
data - it probably will just compress to the original length+X.

A friend and I were discussing this, and we came up with two different
ideas. Mine was to add random data (in an HTTP header) with a random
length, up to a limit L. The length of the random data was distributed
according to a Bell Curve, with random flattening/inflating parameters, to
make the curve somewhat random. I never attempted it (because I'm terrible
at statistics) but I believe with this you can mathematically prove an
attacker would need to issue, on average, a certain number more requests
per byte of data they wish to learn.

If the bell curve was instead an equal probability, they would need to
issue a little more than the maximum possible length of random data to be
certain the smallest length seen so far is indeed the smallest. With an
unaltered bell curve, they could fit the sizes onto a bell curve and know
when they had hit the short end. By randomly flattening or inflating the
bell curve you make the work harder. They could still bypass it, but you
can give a security boundary. "To protect a 9 byte secret, and attacker
would need to issue on average about 1,000,000 requests to learn each byte,
if you have a maximum random string length of X". Pump up X, pump up the
difficulty.

His idea was to instead make the deflate function randomly suboptimal.

My argument against that is that no matter what, the deflate function would
have a minimum size it can compress to, the optimal size M. What is the
probability of reaching M in your randomized deflate? If you prove it will
never reach M, then there's still an M' it *will* reach that is the new
minimum and that then becomes M. Again, what is the probability of seeing
M? Randomized Deflate will have to bucket between M and a maximum size. And
Randomized Deflate is a function of the Input I and the RNG R. (I,R) ->
{M...Max}. Although finding R is outside the possibility, hitting each
individual bucket is not.

An attacker just has to retry until they're reasonably sure they've seen M,
use the lowest length seen so far, pick it, and move on. But figuring out
the probability for finding M on a randomized deflate is waaaay harder than
calculating probabilities in a bell curve. The probabilities might say
"4,000,000 tries" or it might say "90". I know I couldn't even attempt to
figure that out, while I know the other is at least possible. So from my
perspective, you're basing your security on a hunch about randomized
deflate.

Those were two thoughts we had.

-tom

---

From: [email-masked]
Date: Fri, 21 Sep 2012 11:08:40 +0800

After reading the thread, I gave a short summary on proposed 
countermeasures:
1. stateful compression --> stateless compression.         not workable in 
some cases
2. disable TLS/SSL compression.                            works but a 
waste of bandwidth
3. randomizing plaintext (or part of sensitive plaintext) first.   e.g., 
           pre and append plaintext with randomly sized random padding. 
counter to purpose of compression
           encrypt plaintext (or sensitive data only) first at application 
level might be another  solution. double encryption, might be required for 
high value sites; encryption (all plaintext) makes compression in TLS 
meaning less 
4. compression only non-sensitive data at application level first.  need 
to change application.
5. My opinion is : the rationale of the attack is : compression turns 
palintext information (and plaintext relation information) into length 
information, but length information is not protected by encryption. In 
cases compression input is all generated by genuine application, it seems 
ok, but when compression input could be manipulated by attackers, problems 
arise. And it again attested one principle in cryptography: never blindly 
encrypt any plaintex, better do data integrity and ensure paintext 
semantics before encryption(I am sorry for the clumsy words).
So the attacke might be countered by ensuring input to TLS (compression 
and encryption) is strictly generated by applications.