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.

What about deterministic padding? As a (badly thought through) example: Hash the plaintext, then use the first couple of bits of that result as your padding size.

This should counteract averaging of requests. On the other hand, an attacker might work around this by adding a unique token in addition to their guess...

Yeah, the important part is to randomize the output itself, in addition to padding. Even without the padding it makes for a significant challenge to determine just where your known plaintext is to compare from. But with enough attempts, if deflate eventually succeeds in shortening a message on a successful match, you could eventually find the matching message. Like you say, probably too long to be effective (depending on the number of random permutations and the size of the secret)

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?

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)