14 ms·

New attack plucks secrets from HTTPS-protected pages

233 points by jamescun 13y ago

eli 13y ago
Cute attack -- takes advantage of the deflate compression shrinking the size of repetitive strings as a way to test if a given set of bytes is in the encrypted data. Has nothing to do with email addresses. That was just an illustration.
- lnanek2 13y ago
  Their other illustration wasn't terribly useful either, though, request_token. That's supposed to change each time the form is generated and meanwhile this attack takes thousands of runs against the server...
- tracker1 13y ago
  I think it is definitely interesting, if you can test for a string for encoded data, either form encoded `&key={GOLD}&nextkey=` or json encoded `"key":"{GOLD}","nextkey"` you can get to almost anything.
AnIrishDuck 13y ago
So if I understand correctly this attacks HTTP compression instead of TLS compression - which is what makes it different from the previous CRIME attack. This means there should be several important practical differences: 1) Things like cookies and other authorization headers are safe. They are not compressed according to the standard and cannot be sniffed in this attack. 2) Components of the URI are also safe. However, it seems like anyone that uses form-encoded CSRF tokens might be in for a bad time. In fact, any guessable data in a request body is not safe (phone numbers, credit card numbers, SSN numbers, email addresses, etc). Also, I'm not sure what the implications are for SPDY/HTTP 2.0, which IIRC compress headers by default as well.
- cryptbe 13y ago
  Disclaimer: CRIME co-author. It's the same attack. CRIME works for TLS compression, SPDY header compression (yes it broke HTTP/2.0 even before it's called HTTP/2.0), and HTTP gzip response. BREACH was described in slide 39 in our presentation. We didn't test it because it's an application-dependent attack, and we couldn't find a nice target. We're happy that BREACH authors have found a very good target, and proved that the attack works. See: https://docs.google.com/presentation/d/11eBmGiHbYcHR9gL5nDyZChu_-lCa2GizeuOfaLU2HOU/edit https://docs.google.com/presentation/d/11eBmGiHbYcHR9gL5nDyZ...
  - StavrosK 13y ago
    Thanks, I was wondering about that. BREACH sounds like a subset of CRIME.
  - tptacek 13y ago
    Using that comment as a springboard: CRIME is one of The Great crypto bug classes to be found in the last 10 years or so; it's a side channel leak based not on timing, error handling, or power consumption, but on pure traffic analysis. Seriously excellent work. Importantly, and I think this a point Juliano and Thai undersold, the big issue with CRIME wasn't simply that it impacted TLS, but that it implicated an entire cryptographic implementation technique (one that I'd add Applied Cryptography recommends). The immediate feeling I got when I learned about CRIME was "this is going to take out a lot of systems"; it's a serious threat anywhere you have chosen plaintext and compression. It's not surprising that there are other scenarios in TLS where CRIME works, but the big thing to learn from today's talk is that you should go out and look for other places that compress before encrypting.
    - AnIrishDuck 13y ago
      Are you aware of any research into compression schemes that address these kind of length-leak attacks? Intuitively, I'm not even sure such a thing is possible.
      - 13y ago
peterwwillis 13y ago
This isn't going to be useful to malware writers. People who can not install malware on a machine may be able to use this to extract sensitive information. The hackiest fix for this is to randomize the output of your content, or employ random padding. If the compression payload size changes every time (and if you can no longer assume the structure of the payload) you can't effectively determine if a guess was right or wrong.
- samwillis 13y ago
  That's sounds like a very quick and easy fix. You would need to include a random string of random length in the responce before compression. If it wasn't random the 'padding' itself would just get compressed. On a html page this could just be an automatically inserted comment after the /body tag. Although there may be attack against it if it is in a predictable location in the compressed output. Maybe it should be inserted somewhere random in the html?
  - peterwwillis 13y ago
    The way you implement it will be subject to a myriad of application-specific statistical analysis. To my mind, the best way to look at it is like a jigsaw puzzle. If you just took out or added a couple pieces, the whole of the jigsaw remains the same, and it can be trivial to determine what the image is. But shuffle all the pieces into random positions each time and the picture is impossible to decipher. Consider an HTML text that was 500KB, and included a social security number. You add some random padding in a couple places, but not much. There's still 499KB that the attacker probably already knows; he can probably filter out this familiar ciphertext until he's down to the ~1KB of ciphertext he's not positive about, and start drilling down from there. Don't put it past a clever hacker to find more techniques to discover the secret. Randomize the whole thing as much as you can, and pray. (Or disable gzip compression for sensitive content)
- JshWright 13y ago
  Random padding increases the number of requests necessary by a couple orders of magnitude. It would be easy enough to filter out the noise if you tried each guess enough times. It would certainly increase the number of requests necessary to a quantity that (for the vast majority of cases) would be well above any sane usage, and couple easily be rate limited. Credit where it's due, StavrosK and I were discussing this earlier, and averaging out the noise was his idea.
StavrosK 13y ago
Did anyone catch how they can insert things in your plaintext so it passes through the compression algorithm? It sounds like it can only guess things that are in the POST request to the server, only if they can write to it but cannot read it.
- seldo 13y ago
  I was confused about that too. They don't make the request, they force you to make the request (by putting a bunch of them as pixels in an HTML email, or by getting you to trigger some JS). I'm still not clear on how they see the traffic -- I guess the attack relies on having a packet sniffer that can see the encrypted packets go by?
  - StavrosK 13y ago
    No, I know that part, but I mean that this method can only sniff headers, pretty much, as long as they're being compressed. They own the body, since they're injecting data into it, the only thing they don't own is the headers, which is the only thing they can guess. If HTTPS compresses headers separately, or not at all, it's useless.
    - AnIrishDuck 13y ago
      This attack is on HTTP compression, which covers only the body of the request, not the headers [1]. 1. http://en.wikipedia.org/wiki/Http_compression http://en.wikipedia.org/wiki/Http_compression
      - StavrosK 13y ago
        Yeah, so you'll have to be able to write to, but not read, the body of the request, observe the ciphertext on the wire and guess things in the body only. So this is only good for CSRF tokens and the like, and only if you can write to the plaintext you want to guess but not just outright read it.
    - seldo 13y ago
tomfitz 13y ago
My understanding of the attack: Suppose the target web server has an endpoint /foo?probeMe=bar such that the HTTPS response will include 'bar' in the HTML. (Quite an assumption, sure.) Suppose the target web server compresses its responses. Suppose the attacker can make requests to the target web server, on behalf of the target user (e.g. when the target user is on an attacker-controlled webpage, and the attacker can make AJAX requests to the target web server). In the case that the HTTP response already contains 'bar', and doesn't contain 'cbs', then a HTTP response to /foo?probeMe=bar will have a shorter length, than a HTTP response to /foo?probeMe=cbs , since compression will mean 'bar' is deduplicated. Using this, the attacker is able to mount an Oracle attack. That is, if they know something of the form *@gmail.com , and they want to know the whole email address, they can make 26 probes, with probeMe set to: a@gmail.com, b@gmail.com, ..., z@gmail.com and whichever produces the shortest response is part of the response. Suppose the shortest is the probe for probeMe=y@gmail.com . They try another letter: ay@gmail.com, by@gmail.com, ..., zy@gmail.com . Again, one probe will have a shorter response than the rest. They continue, until they find larry@gmail.com . Now they know larry@gmail.com appears in the response. Success!
- tptacek 13y ago
  For what it's worth, it's not "quite an assumption"; it's an almost universal property of web applications of any significant size.
  - tomfitz 13y ago
    You're right. My mistake. Search functionality on sites will often exhibit this. Maybe even stylised 404 pages would too.
- citrin_ru 13y ago
  It seems to be  in html sent by server, will be useful to protect from this attack. Length of response will be always different, and this difference can't be guessed by attacker.
  - 13y ago
deleted 13y ago
[deleted]
luizg 13y ago
There's a copy of the PDF for the BREACH attack at https://kyhwana.org/US-13-Prado-SSL-Gone-in-30-seconds-A-BREACH-beyond-CRIME-WP.pdf https://kyhwana.org/US-13-Prado-SSL-Gone-in-30-seconds-A-BRE...
pygy_ 13y ago
I don't know if the browsers would tolerate this, but it should be possible to pad the compressed payload, rather than the source document. A DEFLATE stream [0] is made of blocks whose first bit determines whether it is the last one. One could add a number of random bytes after the last block such that the payload always has the same length, or is a multiple of a reasonably large number of bytes. This assumes that the decoder will ignore it whatever follows the last block. Another, cleaner option: Use a Trailer HTTP header, using Chunked transfer encoding[1]. The technique should also work with gzip. -- [0] http://en.wikipedia.org/wiki/DEFLATE#Stream_format http://en.wikipedia.org/wiki/DEFLATE#Stream_format, http://www.ietf.org/rfc/rfc1951.txt http://www.ietf.org/rfc/rfc1951.txt [1] https://en.wikipedia.org/wiki/Chunked_transfer_encoding https://en.wikipedia.org/wiki/Chunked_transfer_encoding
- FZeroX 13y ago
  It's not a sure fix though, there will be occasions where you can change the page length enough to hit the padding boundary.
  - pygy_ 13y ago
    Indeed. You could do what CRIME does to TLS (I just discovered these attacks). You could also add a random amount of random padding. It would slow down the attack linearly if the random amount is taken from a uniform distribution. I wonder if it would be possible to make it slower by taking another distribution.

233 points by jamescun 13y ago

eli 13y ago

Cute attack -- takes advantage of the deflate compression shrinking the size of repetitive strings as a way to test if a given set of bytes is in the encrypted data. Has nothing to do with email addresses. That was just an illustration.

lnanek2 13y ago
Their other illustration wasn't terribly useful either, though, request_token. That's supposed to change each time the form is generated and meanwhile this attack takes thousands of runs against the server...
tracker1 13y ago
I think it is definitely interesting, if you can test for a string for encoded data, either form encoded `&key={GOLD}&nextkey=` or json encoded `"key":"{GOLD}","nextkey"` you can get to almost anything.

AnIrishDuck 13y ago

So if I understand correctly this attacks HTTP compression instead of TLS compression - which is what makes it different from the previous CRIME attack. This means there should be several important practical differences: 1) Things like cookies and other authorization headers are safe. They are not compressed according to the standard and cannot be sniffed in this attack. 2) Components of the URI are also safe. However, it seems like anyone that uses form-encoded CSRF tokens might be in for a bad time. In fact, any guessable data in a request body is not safe (phone numbers, credit card numbers, SSN numbers, email addresses, etc). Also, I'm not sure what the implications are for SPDY/HTTP 2.0, which IIRC compress headers by default as well.

cryptbe 13y ago
Disclaimer: CRIME co-author. It's the same attack. CRIME works for TLS compression, SPDY header compression (yes it broke HTTP/2.0 even before it's called HTTP/2.0), and HTTP gzip response. BREACH was described in slide 39 in our presentation. We didn't test it because it's an application-dependent attack, and we couldn't find a nice target. We're happy that BREACH authors have found a very good target, and proved that the attack works. See: https://docs.google.com/presentation/d/11eBmGiHbYcHR9gL5nDyZChu_-lCa2GizeuOfaLU2HOU/edit https://docs.google.com/presentation/d/11eBmGiHbYcHR9gL5nDyZ...
- StavrosK 13y ago
  Thanks, I was wondering about that. BREACH sounds like a subset of CRIME.
- tptacek 13y ago
  Using that comment as a springboard: CRIME is one of The Great crypto bug classes to be found in the last 10 years or so; it's a side channel leak based not on timing, error handling, or power consumption, but on pure traffic analysis. Seriously excellent work. Importantly, and I think this a point Juliano and Thai undersold, the big issue with CRIME wasn't simply that it impacted TLS, but that it implicated an entire cryptographic implementation technique (one that I'd add Applied Cryptography recommends). The immediate feeling I got when I learned about CRIME was "this is going to take out a lot of systems"; it's a serious threat anywhere you have chosen plaintext and compression. It's not surprising that there are other scenarios in TLS where CRIME works, but the big thing to learn from today's talk is that you should go out and look for other places that compress before encrypting.
  - AnIrishDuck 13y ago
    Are you aware of any research into compression schemes that address these kind of length-leak attacks? Intuitively, I'm not even sure such a thing is possible.
    - 13y ago

peterwwillis 13y ago

This isn't going to be useful to malware writers. People who can not install malware on a machine may be able to use this to extract sensitive information. The hackiest fix for this is to randomize the output of your content, or employ random padding. If the compression payload size changes every time (and if you can no longer assume the structure of the payload) you can't effectively determine if a guess was right or wrong.

samwillis 13y ago
That's sounds like a very quick and easy fix. You would need to include a random string of random length in the responce before compression. If it wasn't random the 'padding' itself would just get compressed. On a html page this could just be an automatically inserted comment after the /body tag. Although there may be attack against it if it is in a predictable location in the compressed output. Maybe it should be inserted somewhere random in the html?
- peterwwillis 13y ago
  The way you implement it will be subject to a myriad of application-specific statistical analysis. To my mind, the best way to look at it is like a jigsaw puzzle. If you just took out or added a couple pieces, the whole of the jigsaw remains the same, and it can be trivial to determine what the image is. But shuffle all the pieces into random positions each time and the picture is impossible to decipher. Consider an HTML text that was 500KB, and included a social security number. You add some random padding in a couple places, but not much. There's still 499KB that the attacker probably already knows; he can probably filter out this familiar ciphertext until he's down to the ~1KB of ciphertext he's not positive about, and start drilling down from there. Don't put it past a clever hacker to find more techniques to discover the secret. Randomize the whole thing as much as you can, and pray. (Or disable gzip compression for sensitive content)
JshWright 13y ago
Random padding increases the number of requests necessary by a couple orders of magnitude. It would be easy enough to filter out the noise if you tried each guess enough times. It would certainly increase the number of requests necessary to a quantity that (for the vast majority of cases) would be well above any sane usage, and couple easily be rate limited. Credit where it's due, StavrosK and I were discussing this earlier, and averaging out the noise was his idea.

StavrosK 13y ago

Did anyone catch how they can insert things in your plaintext so it passes through the compression algorithm? It sounds like it can only guess things that are in the POST request to the server, only if they can write to it but cannot read it.

seldo 13y ago
I was confused about that too. They don't make the request, they force you to make the request (by putting a bunch of them as pixels in an HTML email, or by getting you to trigger some JS). I'm still not clear on how they see the traffic -- I guess the attack relies on having a packet sniffer that can see the encrypted packets go by?
- StavrosK 13y ago
  No, I know that part, but I mean that this method can only sniff headers, pretty much, as long as they're being compressed. They own the body, since they're injecting data into it, the only thing they don't own is the headers, which is the only thing they can guess. If HTTPS compresses headers separately, or not at all, it's useless.
  - AnIrishDuck 13y ago
    This attack is on HTTP compression, which covers only the body of the request, not the headers [1]. 1. http://en.wikipedia.org/wiki/Http_compression http://en.wikipedia.org/wiki/Http_compression
    - StavrosK 13y ago
      Yeah, so you'll have to be able to write to, but not read, the body of the request, observe the ciphertext on the wire and guess things in the body only. So this is only good for CSRF tokens and the like, and only if you can write to the plaintext you want to guess but not just outright read it.
  - seldo 13y ago

tomfitz 13y ago

My understanding of the attack: Suppose the target web server has an endpoint /foo?probeMe=bar such that the HTTPS response will include 'bar' in the HTML. (Quite an assumption, sure.) Suppose the target web server compresses its responses. Suppose the attacker can make requests to the target web server, on behalf of the target user (e.g. when the target user is on an attacker-controlled webpage, and the attacker can make AJAX requests to the target web server). In the case that the HTTP response already contains 'bar', and doesn't contain 'cbs', then a HTTP response to /foo?probeMe=bar will have a shorter length, than a HTTP response to /foo?probeMe=cbs , since compression will mean 'bar' is deduplicated. Using this, the attacker is able to mount an Oracle attack. That is, if they know something of the form *@gmail.com , and they want to know the whole email address, they can make 26 probes, with probeMe set to: a@gmail.com, b@gmail.com, ..., z@gmail.com and whichever produces the shortest response is part of the response. Suppose the shortest is the probe for probeMe=y@gmail.com . They try another letter: ay@gmail.com, by@gmail.com, ..., zy@gmail.com . Again, one probe will have a shorter response than the rest. They continue, until they find larry@gmail.com . Now they know larry@gmail.com appears in the response. Success!

tptacek 13y ago
For what it's worth, it's not "quite an assumption"; it's an almost universal property of web applications of any significant size.
- tomfitz 13y ago
  You're right. My mistake. Search functionality on sites will often exhibit this. Maybe even stylised 404 pages would too.
citrin_ru 13y ago
It seems to be  in html sent by server, will be useful to protect from this attack. Length of response will be always different, and this difference can't be guessed by attacker.
- 13y ago

deleted 13y ago

[deleted]

luizg 13y ago

There's a copy of the PDF for the BREACH attack at https://kyhwana.org/US-13-Prado-SSL-Gone-in-30-seconds-A-BREACH-beyond-CRIME-WP.pdf https://kyhwana.org/US-13-Prado-SSL-Gone-in-30-seconds-A-BRE...

pygy_ 13y ago

I don't know if the browsers would tolerate this, but it should be possible to pad the compressed payload, rather than the source document. A DEFLATE stream [0] is made of blocks whose first bit determines whether it is the last one. One could add a number of random bytes after the last block such that the payload always has the same length, or is a multiple of a reasonably large number of bytes. This assumes that the decoder will ignore it whatever follows the last block. Another, cleaner option: Use a Trailer HTTP header, using Chunked transfer encoding[1]. The technique should also work with gzip. -- [0] http://en.wikipedia.org/wiki/DEFLATE#Stream_format http://en.wikipedia.org/wiki/DEFLATE#Stream_format, http://www.ietf.org/rfc/rfc1951.txt http://www.ietf.org/rfc/rfc1951.txt [1] https://en.wikipedia.org/wiki/Chunked_transfer_encoding https://en.wikipedia.org/wiki/Chunked_transfer_encoding

FZeroX 13y ago
It's not a sure fix though, there will be occasions where you can change the page length enough to hit the padding boundary.
- pygy_ 13y ago
  Indeed. You could do what CRIME does to TLS (I just discovered these attacks). You could also add a random amount of random padding. It would slow down the attack linearly if the random amount is taken from a uniform distribution. I wonder if it would be possible to make it slower by taking another distribution.