August 7, 2014

HTTPS Attacks and XMPP 2: CRIME & BREACH

In part 1 I looked at BEAST and concluded that it would not be possible for XMPP. In this part, I’ll look at compression based attacks, similar to CRIME and BREACH for HTTPS.

CRIME: TLS can optionally use compression, which means it compresses the application data before encrypting it. The danger of compression is that it can make the size of the payload change by a variable amount, which depends on how much similarity exists within the content. If an attacker can convince the client or server to compress some secret data (like a cookie) together with some data chosen by the attacker, then the attacker can observe how similar his data was to the secret data. By repeating this process, the attacker can guess the cookie character by character.

BREACH: BREACH used the same principle, but applied to HTTP compression. Because HTTP only compresses the content, not the headers, this means this attack can not obtain cookies, but other secret data in the page can be obtained (like email-addresses).

XMPP

Just like HTTPS, we have two ways of compression here: TLS compression and XEP-0138: Stream Compression. They also differ in what data they compress: TLS compression compresses the entire stream after TLS started, XEP-0138 doesn’t kick in until after the user has successfully authenticated (in c2s).

What is this compression thing anyway?

Both TLS compression and XEP-0138 compression can use zlib (also known as the DEFLATE algorithm), and this appears to be the most common compression method used.

The main method used for compression is by removing duplicated blocks of data and replacing them by back-references. If the compression algorithm sees </message> in the data, it checks whether it has occurred before. If it has, it replaces it by a reference to that previous point. It’s not required to insert a reference when it is possible, and references are only allowed to data in the last 32 kiB. This means that the decompressor must always buffer the last 32 kiB (the compression window), but the compressor may choose to keep as much as it likes (to save on memory, for example).

The data generated by zlib is no longer byte-aligned, to make sure you have an integer number of bytes, it’s necessary to do a sync flush. This means zlib inserts the required padding to make it fit in a whole number of bytes, so you can write it to a socket, for example. A full flush is a sync flush, but the compressor also throws away the data buffered in its compression window. This means the compression can not create back-references to data before the full flush.

TLS compression

With TLS compression, the user’s authentication is included in the compression, which makes it a great target. Assuming, of course, that the authentication mechanism used is PLAIN, because otherwise capturing the data exchanged during the login is worthless. Inserting data to be compressed together with the password is easy: for example, a client will reply to iqs with the same id as the original message had. If the id contained a guess for the user’s password, then the attacker can observe whether their guess was correct by checking the length after compression and encryption.

I managed to get this to work pretty easily: one client logs in using PLAIN authentication repeatedly, while another client sends it iqs and observes the length of the captured TLS encrypted packets. With some extra effort, I made it possible to do multiple guesses per session, around 8 seemed to work reliably. It’s possible to try to guess as long as the password is in the compression window, but you have to ensure the previous guesses don’t affect the compression of your next guess. It is somewhat simplified scenario, as the modified client I exploited doesn’t do anything after logging in (not even retrieving its roster), so I get more guesses than I would get in a real-world scenario, but I do think you would at least get a couple.

Due to the base64 encoding, 8 guesses per login works out to about 5 logins per character of the password, on average. For a typical user with a strong 8 character password who logs in every day, this means the password can be obtained in 1.5 month. If the attacker starts randomly closing the user’s connection (and the user automatically signs in again), this could be done in less than an hour.

Method

The key to implementing this was to split the data into 3 categories:

Fully compressible data. This will always be replaced by a single back-reference.
Incompressible data. Data that is very unlikely to have occurred before in the stream.

The part of the secret that is known, followed by a single character (the guess).

This looks like (whitespace only included for demonstration):

<iq to="target@example.com/resource" type="get" id=",">
    <ping xmlns="urn:xmpp:ping" />
</iq>
<iq to="target@example.com/resource" type="get" id="}a}b}c}e}AHVzZXIAa}f}g}">
    <ping xmlns="urn:xmpp:ping" />
</iq>
<iq to="target@example.com/resource" type="get" id="|a|b|c|e|AHVzZXIAb|f|g|">
    <ping xmlns="urn:xmpp:ping" />
</iq>

Which the client will reply to with:

<iq to="attacker@nsa.gov/3v1l" type="result" id="," from="target@example.com/resource" />
<iq to="attacker@nsa.gov/3v1l" type="result" id="}a}b}c}e}AHVzZXIAa}f}g}" from="target@example.com/resource" />
<iq to="attacker@nsa.gov/3v1l" type="result" id="|a|b|c|e|AHVzZXIAb|f|g|" from="target@example.com/resource" />

The first ping isn’t a guess, but it ensures <iq to="attacker@nsa.gov/3v1l" type="result" id=" and " from="target@example.com/resource" /> occur in the compression window, therefore will be fully compressible in the next stanzas.
}a}b}c}e}, }f}g}, |a|b|c|e| and |f|g| are used as incompressible data: } and | are not valid base64 characters, so won’t match with the password, and they don’t look like anything included in normal XMPP stanzas or anything a user would likely write. They ensure different guesses can’t influence each other, because they separate the compressible data and the guess.
AHVzZXIA is what’s known so far, and a and b are the next guesses.

This method even works when used with block ciphers, where the exact length is unknown: by using the right amount of incompressible data, it’s possible to make the stanza compress to n blocks when the guess was wrong, but n-1 when the guess was correct.

XEP-0138: Stream Compression

For XEP-0138, the user’s password is safe. However, there is still other private data an attacker could try to guess. For example:

Retrieving the password to a MUC.
Obtaining your roster (as long as you don’t change it too often).
Determining whether you have recently received a message from a specific JID.
Determining whether a specific string occurs in a recent message (if it’s not too common and occurs elsewhere in the XMPP protocol).
Determining whether you have joined a specific MUC.

Conclusion

If you want to use compression: don’t.

If you absolutely have to use compression, disable TLS compression and use XEP-0138 and do a full flush after every stanza. This will be bad for your compression ratio, but the only way to be (somewhat) safe from these attacks. But keep in mind that you have to ensure both sides do this.

xnyhps’ blog