[Cryptography] Summary: compression before encryption

Ray Dillinger bear at sonic.net
Sun Jan 18 16:55:05 EST 2015

The idea that modern cryptographers don't use cribs is relevant
only when the keyspace cannot be reduced enough by mathematics
to actually begin a search for a key that yields a plaintext.

We may have reduced the keyspace we need to search down to a
60-bit equivalent in a cipher with an 80-bit key using pure
mathematics and on that grounds we would rightly consider a
cipher to be completely broken.

But when we actually attempt to decrypt an individual message,
we must recognize the plaintext as being plaintext.  That is
the "crib" we still use. It's gotten more abstract, and we
apply our "cribs" in gobs of millions at every file offset
without thinking about it, but with most ciphers, recognizing
the plaintext is the only way you know that what you finally
have is the message you decrypted - and of course, the one
and only key that decrypts that particular message.

It is also ridiculous to think that with any modern cipher a
one-bit difference in a megabyte file will yield a completely
different ciphertext with no way to tell which bit with any
probability greater than the file length in bits.

What modern ciphers, mostly, will tell you is what block
that bit occurred in.  In ECB mode you can tell which blocks
through the whole file have bit differences.  Worse, if an
insertion into the file happens to be a multiple of the block
size, you can tell exactly how long the insertion was and
which subsequent blocks are unchanged except for having an
insertion before them.  In CBC mode you can still tell
which block is the first block that has a bit difference.

If we never apply a whole-file transformation we do not
propagate an inability to guess where the bit difference
is beyond a single block. So, usually, an opponent who
knows there's a 1-bit difference has a 1-in-64 or
1-in-128 chance of guessing exactly where it is, even
if the file is 8 million bits long.

This is why I floated a compression mode that applies a
whole-file transformation making every output bit depend
on every input bit.  Specifically so we can achieve that
goal of having an opponent have no greater than random odds
of guessing where that one-bit difference is.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150118/0daaa0ce/attachment.sig>

More information about the cryptography mailing list