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

Internet Message Format | 1993-01-06 | 1.8 KB

Path: sparky!uunet!spool.mu.edu!olivea!charnel!rat!ucselx!crash!ziggys!scs
From: [e-mail] 619/262-6384 (Stewart C. Strait)
Newsgroups: sci.crypt
Subject: Re: another well-intentioned novice's question
Message-ID: <[e-mail]>
Date: 6 Jan 93 19:08:55 GMT
Organization: Ziggy's Den Of Iniquity, East of East SD CA
Lines: 25

I'm something of a novice myself, but I suspect that the added security
from compression before encryption will vary from negative (message
easier to break) to enormous.  Consider an adversary who can carry
out a known plaintext attack in some time t, with n bits of plaintext.
Further suppose that this adversary can only attack unknown plaintext
problems by succesive guesses at "probable words" n bits long.

If the compression algorithm starts the message with a fixed string
of bytes, or introduces some other regularity, one or a few guesses
at probable words may be enough.  On the other hand, if n is somewhat
large (I would guess 100-1000 bits) and the compression reduces a
lot of common strings longer than n bits to ones a lot shorter, the
task might be very difficult.  The extreme case is where the
compression is perfect in the eyes of the adversary, that is, based
on the adversary's state of knowledge, all compressed messages of
the same length as the intercepted one are equally likely.  In
this case cryptanalysis is impossible unless the encryption lengthens
the message in such a way that only one compressed message can yield
the given ciphertext.  I do wish to emphasize that perfect compression
implies perfect knowledge of your adversary's knowledge of the
probabilities of all plaintexts, and thus is usually an unreasonable
possiblity to even approach.

              [e-mail] - BBS [phone]
                 Ziggy's Den Of Iniquity