[Cryptography] Is there a good algorithm providing both compression and encryption at the same time?

[Jerry Leichter]

On May 9, 2015, at 8:20 AM, Peter Gutmann <pgut001 at cs.auckland.ac.nz> wrote:
>> Probably compression is safe if each source of data is compressed separately.
> It's also safe if used in non-interactive environments (e.g. store-and-forward
> messaging).  One of the major drivers for compression in CMS was EDI use,
> where messages are (a) enormous, (b) highly compressible, and (c) chosen-
> plaintext attacks aren't an issue.
One can readily construct an example where this is false.  All it takes is for there to be a semantically meaningful difference in compressibility between messages.  Trivially:  If I want to prevent traffic analysis by sending random cover messages when I have no real message to send, and I feed those messages into a compress-then-encrypt engine, the real messages will probably compress much more than the cover messages.  Alternatively, if my cover messages just say "cover message" over and over again, it will be much more compressible than real messages.

Sure, you can avoid that by being careful about how you construct your cover messages - but a "safe" cryptosystem isn't supposed to require that much diligence from its users.

Also, sure, if you *don't* use compression first, most cryptosystems will leak information about message lengths.  But that's something that's much easier to understand and protect against than leaking "whatever redundancy the compression algorithm is able to find".

Also worth mentioning:  There's a bunch of work - Dan Bernstein is big on this - at making encryption algorithms side-channel free by ensuring that they don't vary anything - timing, power use, cache hits - based on their input data.  You throw all that away if you compress.  I find it hard to even imagine a side-channel-free compression algorithm.

It's not that "compress then encrypt" is *necessarily* bad.  It's just that because it introduces hidden, subtle data dependencies, it requires careful analysis *of the entire end-to-end system* before use.
                                                        -- Jerry