From: "Jon Leonard" <jleonard@divcom.umop-ap.com>
Date: Sat, 20 Apr 1996 07:12:23 +0800
To: pmonta@qualcomm.com (Peter Monta)
Subject: Re: why compression doesn't perfectly even out entropy
In-Reply-To: <199604190607.XAA17848@mage.qualcomm.com>
Message-ID: <9604191918.AA17670@divcom.umop-ap.com>
MIME-Version: 1.0
Content-Type: text


Peter Monta wrote:
 
> Perry Metzger writes:
> 
> > > 1.  If "cooking" a byte sequence in a manner that reduces its
> > > maximum entropy by less than 1% allows an attacker to break your
> > > cryptosystem, then it is crap to begin with.  With only a little
> > > more effort, he could break it anyway.
> >
> > I would suggest that you look at differential and linear cryptanalysis
> > to learn what a tiny little statistical toehold will give you.
> >
> > My "ad hominem PSA" stands. I suggest people not trust Mr. Wienke's
> > pronouncements. He appears to be suffering from significant hubris.
> 
> No, he's correct; cryptanalytic schemes like those you mention rely
> on statistical toeholds *in the context of a deterministic cipher
> algorithm*.  For one-time pads that are "cooked" or "screened" (and
> I agree that it's a silly thing to do), the toehold is much weaker,
> infinitesimal in fact.

Perry's right: giving up any statistical information is too much.
 
A slightly contrived example of why tossing out duplicated bytes is bad:
 
Suppose that a military organization is using this almost one-time-pad
system, and my spies tell my they've fallen into the habit of sending
"attack" and "defend" as their only 6-byte messages.  This isn't a problem
with a real one-time pad (except for traffic analysis...), but this lets
me determine the message 3.8% of the time!
 
For example, if I see:
 
0xfce8e8c7f4f7 (cyphertext I see)
 
which was generated by:
 
  d e f e n d  (message)
0x646566656e64 (message in hex)
0x988d8ea29a93 (pad)
 
Then I know that I'm not going to be attacked.  Attack couldn't have had
the e8e8, because they threw out those pads.
 
> For example, suppose we take 1024-bit blocks from a physical RNG
> (which we'll agree is "good", has entropy close to 1024 bits,
> whatever that means).  There are 2^1024 such blocks.  Obtain one
> and apply the magical test---if the block fails, toss it in the
> bit bucket. Suppose, conservatively, that half the sequences fail.
> The cryptanalyst now knows that the plaintext cannot be
> ( failed_pad xor ciphertext ) for any of the 2^1023 failed_pads.
> Thus, it must be one of the other 2^1023.  This is the *only*
> toehold he gets.

That's plenty big to be a problem.
 
Jon Leonard