Archive for August, 2013

Welcome to Black Hat Conference Season…

Last week, news started to spread from the Black Hat conference about a new oracle attack (called the BREACH attack) against HTTPS which may allow an attacker to guess desireable values contained within deflate compressed responses in a very short time, typically under a minute according to the presenters.

We call this an “oracle attack” because we’re not attempting the crack the HTTPS encryption and read the content directly but are instead monitoring the compressed size of the content which will fluctuate depending on the content being compressed thus leaking information about what had been encrypted. In a sense it’s also a side-channel attack on the compression algorithm - another example of a side-channel attack is using the time it takes to compare strings on a server to enumerate valid usernames and emails known by applications, all without accessing the database directly - some frameworks will feature a fixed time string comparison function for this very reason.

BREACH is shorthand for Browser Reconnaissance and Exfiltration via Adaptive Compression of Hypertext. Someone went to a lot of trouble inventing a name to fit that acronym. As the name suggests, though it’s not always made clear in current articles online, the attack isn’t just good for HTTPS - it can also work against HTTP in situations where attackers cannot get hold of the content but can access a good record of the metadata for responses. If you’re an NSA employee this may be just a few keystrokes away.

Edit: Anthony Ferrara (ircmaxell) has post his own thoughts on the BREACH attack: http://blog.ircmaxell.com/2013/08/dont-worry-about-breach.html

Note: If you do some more research about BREACH attacks, you’ll notice the prominance of CSRF token references. CSRF tokens tend to be weakly controlled in applications and frameworks, i.e. single token per session without limited use scopes or narrow expiration times. A compromised CSRF token could conceivably be valid for a user across an entire site for every single form so long as their session remains open. This said, targeted data is not exclusively tokens - email addresses, real names, credit card information, order numbers, delivery/business addresses and pretty much ANYTHING including personally identifiable information you want hidden by HTTPS encryption could also be targeted.

The attack itself isn’t that hard to understand. The data compression algorithm we call DEFLATE (the basis of gzip) uses the LZ77 algorithm which takes advantage of repeated strings to more efficiently compress output. The more repeating characters there are, the smaller the compressed output becomes. This holds true regardless of whether the compressed content is HTTPS encrypted or not.

If an attacker can inject a string into a HTTPS response intended to match another unknown string (the target secret), they can iteratively guess the secret value by monitoring the compressed size of the responses for different guesses. The more correct a guess is (i.e. matching sequential characters strings at either the beginning or end of the guess), the more efficiently LZ77 can compress the content, and the smaller the response size becomes. In hindsight, this appears obvious but we’ve never had a concrete prove of concept before now targeting content bodies in encrypted responses.

I’ll save you the trouble of a long read if you’re short on time. The only complete surefire defence against BREACH attacks is to disable HTTP compression, i.e. mod_deflate for Apache and the gzip module for nginx. This may have significant performance implications but there is no other known comprehensive defence. I’ll mention some other possible solutions later in this post but all of them have their weaknesses and limitations. BREACH is basically a fundamental flaw in HTTP - any permanent solution will need to need to come from the HTTP layer.

Attack Requirements

The attacker needs two capabilities to pull off a BREACH Attack:

1. The ability to read responses received by the user’s browser.
2. The ability to cause the user to send requests from their browser.
3. Some part of the request must be reflected in the response.

The first is an eavesdropping ability that might be gained using ARP poisoning or something more concrete like cable splitting. Some attackers may have specialised rooms at ISPs across the planet funded by three letter agencies. Note that this does not require cracking any HTTPS encryption - we just need a way to collect data on content sizes from responses.

The second can be accomplished using the time honoured method of screwing with the user by having them visit an attacker controlled website containing iframes or Javascript. Either method should allow the attacker to have the user spawn thousands of requests with attacker controlled parameters completely unnoticed by the user.

The third is a question of application design. A multipage form, for example, might carry across extra hidden fields containing attacker injected strings (bad validation). A seach form might redisplay the search terms on the page. A messages tab would redisplay submitted messages. There are lots of valid direct and indirect (via database) reflections of user data in responses of which some will be perfectly normal and others the result of security weaknesses.

Other Factors To Consider

It’s important to note that HTTPS encryption has little to no impact on the viability of this attack. BREACH works on all SSL/TLS versions and cipher suites. Some ciphers actually make it easier and others make it harder. None pose insurmountable problems, however, since attackers can adjust the makeup of the injected guesses, the number of measurements and the scoring of the results to filter out the impact of the most difficult ciphers. The attack can only become more effective over time.

The LZ77 algorithm does not operate alone - it has a partner called Huffman coding within DEFLATE. This coding pollutes the compression measurements since it sometimes prevents repeated strings from providing compression efficiencies under LZ77. This is actually simple to solve using a bit of arcane spellcasting (literally just a bit of string padding) and using twice the number of measurements as LZ77 would require were it an attacker’s sole concern.

The attacker will also need to “bootstrap” the attack by having starting comparable strings to use. For example, the string “csrftoken=” can be known in advance if used by the target site’s output (CSRF tokens can be used in GET URLs not just forms). This quickly becomes more difficult for data delimited by tightly controlled characters, for example a CSRF token in a form will be delimited with quotes as part of the form markup. Unless you are injecting user data into markup without escaping it, the attacker won’t be able to inject a matching bootstrap string (the quote would be escaped) which limits their ability to perform attacks.

They could try something else - perhaps you pad tokens with something predictable or guessable, perhaps you inject some user data into attributes so they end up quoted anyway. For example, a token prefixed with a time element would be predictable. Attackers could also blind guess the first few characters but the math isn’t favourable under those conditions. There may be other scenarios, e.g. attribute reflection, where the quotes can still be used though we hope reflecting user data in an attribute is rare given it’s an obvious Cross-Site Scripting risk.

Application Weaknesses and Defenses

From the above, we can ascertain that an attacker needs the right application behaviour in which to develop this attack into a viable threat:

1. Responses must be served from a server which has HTTP compression enabled.
2. Some part of the user request must be reflected within a response so guesses are compressed with the targeted information.
3. The response body must contain some information desired by the attacker.
4. While not strictly necessary, it would be nice for the response to have as little noise (changing content) as possible.

We can also deduce likely defenses against BREACH attacks from the same list:

1. We can disable HTTP compression altogether.

Since the BREACH Attack relies on the compression to execute a side-channel attack, it’s sort of obvious that disabling mod_deflate for Apache or the gzip module for niginx stops this attack dead in its tracks. This is basically the standard recommended defence at this time pending something provably better. You may not like the performance implications, and the attack may not yet be widespread, but don’t doubt that there are blackhats and criminals out there working on engineering easy to deploy BREACH attacks as you read this. The theory is so simple that I wouldn’t expect it to take more than a few hours to prototype - the delays may come from automating it effectively and then figuring out what to charge the criminal markets for it. The attack takes just a few thousand requests which can be completed in under a minute - time and requests increase as the length of the value wanted does but only in a linear manner.

2. We can prevent the direct and indirect reflection of user input in responses.

Direct reflection is simply dumping data from the request parameters straight into the response. Indirect reflection just means it takes a scenic route, e.g. via the database or a third party API. It’s impossible to eradicate all user data reflection - the very notion is silly. However, you can be wary of what you are reflecting back and whether it is strictly necessary. Reducing the attack’s surface area is better than doing nothing at all. For example, monitor how you transfer hidden values across multipage forms (discard invalid parameters). The attacker will need to meddle with request URIs and/or form encoded data so your validation may catch some of what they’re attempting. This will be very hit and miss unless you simply stop users from submitting and storing any data!

3. We could randomly adjust the length of responses so compression output size also becomes randomised.

Length hiding is a common enough defence you’ll see quoted everywhere in the wild for lots of security related topics. Sadly, people forget that if you take sufficient measurements of anything that has both a fixed and random element to its length, there’s this annoying thing called “standard error” which stubbornly insists on being inversely propertional to the number of measurements. Yet more statistical arcane spellcasting by hellspawn! The more you measure, the more length hiding is averaged out until it’s rendered pointless. It will force the attacker to require more requests (which means more time and coffee trips) in their BREACH attack but that’s all will accomplish.

4. We could prevent the compression of secrets and other desireable data in responses.

You can mutate only certain compressed secret data in such a way that BREACH attacks can’t iteratively uncover it (i.e. masking). For example, you can use a per request padding concatenated to a XOR of the padding with the actual data. This shifts the data per request making a BREACH attack impossible. Obviously, this will NOT work for data which is meant to be user readable. It’s also probably simpler just to generate a unique value per request and be done with it for tokens and other such information - it’s probably going to break stuff for users using multiple browser tabs either way.

5. We could rate limit requests to the server

The BREACH attack requires thousands of requests so rate limiting may be helpful. The attack unfortunately doesn’t really need a massive number of requests - a couple of thousand in the space of a minute isn’t as big as you might think - so this may or may not be realistic. High traffic sites would barely notice such a surge and it may even be expected as a result of normal user interaction.

As it stands, disabling HTTP compression is the simplest and most effective solution. For those applications/frameworks emitting CSRF tokens for GET URLs, defence 4 is a bare minimum at this point - defense in depth dictates doing something unless you have a crystal ball to predict all possible user written code. CSRF tokens in forms should have quote delimitation making BREACH attacks, we hope, more difficult but they should also be checked to ensure there is no common or predictable token padding that would help bootstrap these attacks. The community concensus may well move against single-generated CSRF session tokens altogether despite the user impact. This is likely the most immediate concern for ALL frameworks with form capabilities.

Want to read more? There’s a BREACH attack website online by the paper authors with a link to the original whitepaper.

Related articles

• Step into the BREACH: New attack developed to read encrypted web data (go.theregister.com)