NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/sci/crypt/6359

Text File | 1993-01-04 | 5.6 KB | 116 lines

Newsgroups: sci.crypt
Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
From: [e-mail] (Larry Loen)
Subject: Re: Another well-intentioned novice's question
Sender: [e-mail]
Message-ID: <[e-mail]>
Date: Mon, 04 Jan 1993 17:08:47 GMT
Reply-To: [e-mail]
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
References:  <[e-mail]>
Nntp-Posting-Host: wo0z.rchland.ibm.com
Organization: IBM Rochester
Lines: 101

In article <[e-mail]>, [e-mail] (Rusty) writes:
|>
|>
|>     Hmmmm. I've been pondering this question for some time
|> now, and making little headway, so I thought I'd better run it
|> by the net's crypto wizards:
|>
|>     A few months ago, in the letters section of the
|> _Communications of the ACM_, there was published a letter which
|> commented that, in the opinion of the author, cryptographic
|> efficiency would be greatly enhanced by compressing a message
|> before encrypting it, the better to remove repetitive patterns
|> from the plaintext.
|>

A lot of people have this opinion, but compression is overrated.  It helps,
but a lot less than people think.  Suppose, for instance, that one is
attacking DES with brute force.  Suppose further that one is able to guess
a fairly long input string (say, of 20 or 30 bytes).  At first, this
seems impossible, until one remembers the large amount of "boilerplate"
in most documents, signature files, and the like ("From the desk of
Wilfred P. Pettifogger").  It is clear, however, that with such a string,
the regular DES attacks can eventually be mounted or can be mounted multiple
times.

It will certainly be more difficult to place the LZW compressed version of
such texts, correctly, than ordinary uncompressed text.  Even if the
compression is fixed (eg Huffman encoding), one at least has to deal with
the likelyhood of the compressed text starting on an aribtrary bit
boundary.  However, the total number of variations to try
might be acceptably small.  Suppose there were only 64
trial texts to be attempted where, in the uncompressed version, only 1 was
needed.  Remember, too, that "smart ordering" of the potential texts may make
an apparently large number of possible placements smaller in actual practice.

LZW, besides being a quality compression, is "adaptive" and that may well make
for a lot of actual variability and be of more than average value, unless the
"boilerplate" is near the start of the message.  For this example, let's assume
something like that is the case and so keeps the number of possibilities added
low.

In the hypothetical example, compression moves the overall cost up to 2 to the 60
from the original 2 to the 54.  That ain't chicken feed, but it will probaby
not make a serious difference in overall security, in the end.  If one can
exhaustively break DES in a day, having to wait 64 days will defeat some
opponents, but others will be just as happy on the 64th day as the first.

Note, however, that the key technology remains breaking the basic DES.  Once
one can spring for a cost on the order of 2 to the 54th, it does not seem
like the typical opponent will run out of money at 2 to the 60th or that they
will not simply wait the extra time if they do.

|>     I don't see, though, that standard (i.e. LZW) compression
|> algorithms actually do remove any of the redundancy from the text;
|> they merely encode and substitute for lengthy repetitive patterns
|> with smaller ones. Mathematically, the whole of the message is
|> still there, is it not?

Well, the minimum number of bits needed to encode a message is certainly
invariant; the information content is the same.  But, LZW really does eliminate
redundancy because the ordinary representation is introduces "extra" bits over
the theoretical minimum.

|>
|>     Admittedly, if one does not know the full details of
|> the algorithm used in the compression, decompression will be far
|> from easy, and I can certainly conceive of several simple hacks to
|> the basic LZW technique which would be tantamount to simple shift
|> encoding and the like, making it harder yet to unravel.
|>

True, but in cryptography, one usually assumes every detail that is "fixed"
becomes known to the attacker.  Accordingly, one assumes that the exact
details of the compression scheme are known, including any hacks.
As a practical matter, such fiddling may be of value.  In most published
discussion of this, however, such minor fiddling is not at issue;
what is at issue is whether compression helps, generally and by how much.

|>     Can someone more learned elucidate at greater length on
|> this question? And is there any merit at all to the original letter
|> writer's argument?
|>

Some merit.  It is very difficult to generalize about cryptography.  It is
always a war of specifics.  I can imagine compressions that are completely
worthless.  I can imagine a proper use of LZW being of some help, but one
might not be able, in a certain usage environment, to get anything like the
full value out of it.  This especially applies to the many environments where
predictable "boilerplate" appears near the front of text messages.

|>
|>
|>
|> --
|> ||||||||   Russ Teasdale -- [e-mail]  --  (Rusty)  ||||||||
|> -------------------------------------------------------------------------------
|> "Gentlemen, if we do not succeed, then we run the risk of failure." - D. Quayle

--
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer