9
$\begingroup$

In the wake of compression-based side-channel attacks like CRIME and BREACH, are there any safe ways to combine compression and encryption?

The JWE Specification was finalised almost 2 years after BREACH, but still includes DEFLATE compression as an option. Are there cases where that could be used safely?

In my use case (storing encrypted data in a user session token), experimentation has shown compression of around 42% on average, and every bit counts, so I would dearly love to be able to turn this on safely!

Improve this question
$\endgroup$
9
  • $\begingroup$ Also does anybody know why compression is only defined in the JWE spec and not in the JWS signature spec? I would have thought that compression would be fine with signed (but not encrypted) tokens. $\endgroup$
    – Neil Madden
    Jul 24, 2016 at 13:53
  • $\begingroup$ Digital signatures (like those in JWS) are computed on digests of the data. That means the data is first hashed with a cryptographic hash function like SHA-256 and then the digital signature is applied to that. Compressing the data first wouldn't give you any advantages. $\endgroup$
    – John Downey
    Jul 24, 2016 at 17:52
  • $\begingroup$ Right. I didn't mean compression of the signature. JWS defines a format for messages + signature. You could define that to allow compression of the message before applying the signature. $\endgroup$
    – Neil Madden
    Jul 24, 2016 at 17:55
  • $\begingroup$ I found this email thread with some background on why it was left out - deemed unnecessary complexity as signed messages can still be compressed, while encrypted ones cannot. ietf.org/mail-archive/web/jose/current/msg00633.html $\endgroup$
    – Neil Madden
    Jul 24, 2016 at 18:00
  • 1
    $\begingroup$ The tradeoff would be if the compression was faster than the incremental data being fed into the message digest. I haven't run any experiments but I would be pretty surprised if it was worth it. Additionally, that would raise problems with producing a canonical representation of the compressed data before being fed into the message digest. In cryptography you need to be exact with how you compute things and compression is not always a consistent process across various machines, architectures, settings, etc. Compression gets away with that by always being universally decompress-able. $\endgroup$
    – John Downey
    Jul 24, 2016 at 18:03

2 Answers 2

Reset to default
7
$\begingroup$

I think that the answer to this question is a bit more involved than it first seems. The reason is that the compression attacks work when different lengths after compression reveal information about the plaintext. This is of course a huge problem. However, you have to ask the question without compression as well: when does the plaintext size leak information.

In practice, the plaintext size leaks information in many settings, and it's very problematic. A very nice paper that deals with this is called Side-Channel Leaks in Web Applications: a Reality Today, a Challenge Tomorrow (it appears at IEEE S&P 2010).

So, this question arises when using compression and when not using compression in exactly the same way. If you have a lot of control over your application, then you can pad to a fixed length (if this is feasible regarding efficiency). This is indeed harder to do when using compression since you typically don't have a fixed useful upper-bound on the post-compression length. If you did have such an upper bound, then you could compress and then pad.

In many cases, the actual values being encrypted are not known ahead of time and the person designing that part of the application knows nothing about security. Then you are in trouble whether you are using compression or not.

In summary, length leakage is a real problem that is way too ignored. The use of compression in some cases makes it worse (like in the CRIME and BREACH scenario), and in some cases it's the same problem as without compression. It depends on the application and you have to do the analysis.

(Just to answer the specific question: if you are saving 42% by using compression, try to estimate the maximum foreseeable size after compression and pad to that; you may very well still save 25-35%.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. This is very interesting. My application can switch between using either AES in CBC mode (with HMAC) or AES-GCM. Would it be correct to say that CBC leaks less information than GCM in this regard as it must pad to a multiple of the block size? Also, rather than padding to a fixed upper bound, could I instead add a random sized pad element (eg between 0-128 bits)? $\endgroup$
    – Neil Madden
    Jul 25, 2016 at 5:25
  • $\begingroup$ Ignore the question about random padding, it's not a workable solution now that I think about it. $\endgroup$
    – Neil Madden
    Jul 25, 2016 at 8:54
1
$\begingroup$

There are of course places where compression would be OK. Say you'd have a message space $M$ and the compression function on any message of $M$ returns a specific length, say $\#m / 2$ where $m$ is the message and $\#$ calculates the length. In that case no information is leaked.

You could make this more likely to happen by adding additional data until a certain maximum is reached. E.g. if you know everything has a compression ratio of 3 : 1 average then you could simply return half the bytes by again adding bytes until that threshold is reached.

In your case though, I would figure out what is causing the significant overhead and remove it, so you get a minimum - but statically sized - session token.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.