Attack XOR encryption of binary data compressed by zlib with known key length (very short key)

Question

I am trying to break a packet format. The packet format simply packs several files into one big file. The file contents are plain. But the index data which contain offsets, file sizes and filenames are encrypted. The index data are about 1 KB and compressed by zlib (the DEFLATE algorithm with no zlib or gzip wrapper), and then XOR encrypted. In other words, the key is concatenated with itself many times to get a keystream of equal length as the zlib-compressed data, and then the zlib-compressed data is XORed with this keystream (like a Vigenère cipher). I know the key length is 8 bytes. Is it possible to decrypt the data?

Answer 1

To elaborate on what the comments are leading you toward...

This sort of encryption scheme is susceptible to a straight-forward known-plaintext attack.

Every byte of the ciphertext will have been encrypted in the format:

$$C_i = P_i \oplus K_{i\ \bmod{\ len(P)}}$$

where $i$ is the byte index within the ciphertext and plaintext. This expression is easily solved for the key:

$$K_{i\ \bmod{\ len(P)}} = C_i \oplus P_i$$

In words: You obviously know the ciphertext, so if you can also learn the plaintext at a given byte position then you simply XOR the plaintext byte with its corresponding ciphertext byte to learn the corresponding key byte. (Since the key is repeated you then need to determine which key byte index between 0 and 7 this key byte was copied from.) Once you learn all 8 bytes of the key, just concatenate it in the same way the encryption was done and use the resulting stream to decrypt the ciphertext.

But how can you find plaintext? The easiest place to start is to look at the specification of the compressed data format. Determine the exact format used and then look up what sorts of header values and data structure it uses. Some formats have certain byte positions that always have certain fixed values, or some structures with easy-to-guess contents. Don't only look for full bytes, if you can determine just some of the bits of a byte that is also useful.

If that isn't enough, you may want to consider trying to generate known plaintext and then encrypt that. For example, take some text and compress it with a different program that follows the exact same compression specification and that will produce the plaintext (or something very close to the plaintext) before encryption (aka, a chosen-plaintext attack).

If you can only break a few bytes of the key using those methods then you may be able to finish with brute-force. (3 to 4 bytes are certainly brute-forcable on a reasonable modern home computer if you have the patience.) Fix the key bytes you are sure about and iterate over the unknown key bytes. Use each potential key to decrypt captured packet data and see if the key generates valid decrypted compressed data (perhaps call a decompression function and see if it returns success or an error). (If too many test keys produce valid compressed plaintext, get a few packets of data encrypted with the same key and the key against all of them, the more data you have to test the more likely you will eliminate a wrong key.)

From the keys that generate valid compressed data, test the decompressed data to see if it's about what you're expecting, since you say that you have an idea of what the encrypted data is. Check to see if it looks like valid filenames and such, ASCII where appropriate, or whatnot. Eyeballing it would work well here if you have reasonably few keys that make it this far.

Answer 2

If you have known plaintext, namely one input file that is known in its entirety, this is trivial to break. So I'll explore methods that might lead to a break, if you don't know what's in the input file that was compressed.

I suggest that you start by analyzing the DEFLATE stream format carefully (see also these handy notes). This will probably help you derive some consistent relationships that the first handful of bits of the DEFLATE stream must satisfy.

On first glance, it looks to me like the beginning of the DEFLATE stream has the following structure:

• As Stephen Tousot explains, in normal operation the first 3 bits of the DEFLATE stream are likely to be 110. (You may want to double-check this with the compression program you are using.)

• The next three fields are HLIT (5 bits), HDIST (5 bits), and HCLEN (4 bits). I suggest that you take a bunch of sample inputs that would be typical for your application, compress them with the compression implementation you're using, and look at the typical range of values for HLIT, HDIST, and HCLEN in the resulting DEFLATE stream. I suspect you may find that not all values are equally likely.

• After the aforementioned 17 bits is a chunk of 3*(HCLEN+4) bits, which is interpreted as a sequence of 3-bit values. If I understand the DEFLATE algorithm correctly (and I might not), if you permute these appropriately using a fixed permutation found in the DEFLATE specification and ignore all 000-values, then the remaining 3-bit values should be in sorted order. This provides an additional constraint on possible values for those bits.

• Then there's some more stuff that I'm ignoring right now.

For example, if HCLEN=15, then the first three items above account for the first 74 bits of the DEFLATE stream. And, if I understand correctly, above structure imposes some consistency relationships on the bits: not all possible 74-bit sequences are possible (and not all possible ones are equally likely).

Now, I think you could use the following procedure to try to recover the key $K$.

• For each candidate value of the 64-bit key $K$, xor it against the first 64 bits of ciphertext to obtain $Y = C\oplus K$, a guess at the 64 bits of the DEFLATE stream. Check to see if $Y$ is consistent with the above-mentioned constraints. If it is not consistent, continue on to the next candidate for $K$.

• If it is consistent, then do a trial decryption of the entire ciphertext using $K$ (i.e., xor a repeated version of $K$ against the ciphertext, then decompress). See if the resulting plaintext looks like a plausible input. If yes, you may have found the key $K$. If not, continue on to the next candidate.

As described, this method would take $2^{64}$ iterations of the loop. However, I suspect you might be able to speed it up if you are a bit clever about how you check keys $K$. Rather than iterating over all possible 64-bit values one-by-one, I think you can use a tree-like iterative-deepening method. The idea is, roughly, if you reject a (say) 17-bit prefix of $K$ as impossible, then there is no need to try any of the keys that start with that prefix. So, an optimized algorithm might first check all candidate values for the first 17 bits of $K$ (say) to see which ones look consistent, then for each 17-bit prefix that survives, you look to find all plausible ways to extend it by 3 bits, and so on, repeating at each step.

I don't know what the running time of this more sophisticated algorithm will be, but if you study the DEFLATE format carefully and are able to identify enough consistency checks on the first 64 bits of the DEFLATE stream, you might be able to make this attack run efficiently enough to be practical.

I realize I haven't worked out all the details for you -- I've left something for you to do on your own. But hopefully this gets you started and gives you some ideas for a direction that might lead to a practical attack.