Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!rutgers!bellcore!faline!karn
From: karn@faline.bellcore.com (Phil R. Karn)
Newsgroups: sci.math,sci.crypt
Subject: Re: Encryption of Hoffman coded text
Message-ID: <1034@faline.bellcore.com>
Date: Mon, 10-Aug-87 15:36:59 EDT
Article-I.D.: faline.1034
Posted: Mon Aug 10 15:36:59 1987
Date-Received: Tue, 11-Aug-87 05:12:39 EDT
References: <10489@linus.UUCP] <7876@mimsy.UUCP> <10604@linus.UUCP> <1227@hropus.UUCP>
Organization: Bell Communications Research, Inc
Lines: 29
Summary: yes, compressing helps
Xref: mnetor sci.math:1827 sci.crypt:518

> Is decryption more difficult if you use Hoffman coding..?

Yes, it is well known that increasing the entropy ("randomness") of the
plaintext before encryption is an excellent way to thwart cryptanalysis.

It's easy to see this. Suppose you have LOTS of CPU cycles available,
maybe even a parallel array of a million DES chips, but you need to know
when you've found the answer. If you've got matched ciphertext and
plaintext, no problem. But if you've only got ciphertext, you'll need to
guess the expected properties of the plaintext to know when you've found
the right answer. If the plaintext is ASCII-encoded English text, it
will leap right out at you with even the simplest statistical analysis
(all parity bits off, typical English character distribution, etc).
However, if the plaintext has been compressed, these statistics go away
(assuming the compression algorithm is doing its job). You simply don't
know when you stumble on the right answer.

I've heard it from someone that should know that "knowing when you've found
the answer" is indeed perhaps THE hardest part of cryptanalysis.

Practical point: many compression utilities put "magic numbers" at the
beginning of their compressed output so they can tell if they're being
fed random garbage when decompressing. The cryptanalyst could look for
these magic numbers, though if they're small compared to the block size
of the encryption algorithm he would get a very large number of false
alarms. (E.g. a 1 byte magic number with 8 byte DES blocks would yield
one false alarm every 256 trial keys, on average).

Phil