[Cryptography] Summary: compression before encryption

ianG iang at iang.org
Fri Jan 16 10:03:27 EST 2015

On 15/01/2015 21:11 pm, Ray Dillinger wrote:
> In general, compression algorithms ought to be beneficial in
> cryptography.  Greater information density means less redundant
> structure of the sort that results in "cribs" for the analysts
> to use.  The problem with most compression programs is that
> they have very distinctive headers that instead provide cribs
> for the analysts in the first few hundred bytes of the file.

It occurs to me that what we need, and I may be talked out my posterior 
here, is keyed compression.  If the problem is distinctive header cribs, 
then cause those headers / first few hundred bytes to be encrypted in 
some form of light scale encryption, just enough to break any realistic 
sense of cribs.

> It would actually be fairly easy to make a compression format
> that is safe to use with cryptography.  It is also easy to
> encrypt in a way that is safe to use with compression.
> So you could solve the problem in either of two ways.  On
> the encryption side, absolutely regardless of where in the
> file the predictable header information might be, you could
> simply apply a whole-file transformation during encryption.
> It would suffice to loop through the file twice in a block
> cipher using CBC mode for example, making every bit of the
> output depend on every bit of the file.
> On the compression side, where you actually know exactly
> which bytes are the header, you could do something that
> would work with streamed data, not requiring access to the
> whole ciphertext before someone can start decrypting. It's
> essentially the same thing as above, but only applied to
> the section of the file containing the header and some
> immediately adjacent compressed data. So, when someone is
> decompressing a file with a 1k header block for example,
> he might start by scrambling blocks 1-3 of the compressed
> file and XORing the result with block 0 to get the header
> information.
> We don't need security in the compression side; he could
> use a simple "scramble" here instead of a real cryptographic
> hash. The compressor could use pretty much any method that
> achieves the diffusion needed without worrying about adding
> confusion.  Confusion is the job of the cryptography (in
> the cases where the compressed format gets encrypted). But
> the scramble would make the format safe to use with
> cryptography.

You might be saying something similar.  I like the idea also of 
integrating this with a HMAC, or at least analogising it.  Question of 
whether to expand AE so it is now AE&C for Compression as well I'll 
dangle for others.


More information about the cryptography mailing list