Attack XOR encryption of binary data compressed by zlib with known key length (very short key) 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?
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.