Re: why compression doesn't perfectly even out entropy

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.

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.

Cheers,
Peter Monta   pmonta@qualcomm.com
Qualcomm, Inc./Globalstar

Peter Monta writes:
> 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.

Please learn what the context of the discussion was before
commenting. It was not about using cooked streams for one time pads.

Furthermore, I suggest you look up the Venona intercept work and tell
me again about how far an advesary will go with a tiny toehold.

.pm

Perry writes:
>  Furthermore, I suggest you look up the Venona intercept work
>  and tell me again about how far an advesary will go with a
>  tiny toehold.

The Venona breaks came because the NSA had a lot of encrypted traffic and  
some pads were used more than once, which is hardly a tiny toehold.  After  
years of dragging intercepted messages through each other, something finally  
popped out.  Messages encrypted with pads that were only used once are still  
unbroken, AFAIK, even though the pads were simply generated by clerks banging  
on keyboards.

Still, a tiny toehold is all a good analyist needs to break a non-OTP  
cryptosystem, which attempts to protect a lot of information with only a  
little bit entropy.


andrew

Andrew Loewenstern writes:
> Perry writes:
> >  Furthermore, I suggest you look up the Venona intercept work
> >  and tell me again about how far an advesary will go with a
> >  tiny toehold.
> 
> The Venona breaks came because the NSA had a lot of encrypted traffic and  
> some pads were used more than once, which is hardly a tiny toehold.

In general, they were used twice. Thats a pretty tiny toehold.

.pm

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

"Jon Leonard" writes:
> 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!

This could actually be used for traffic analysis in many instances;
you could succeed in extracting small amounts of information from the
passing data.

Any amount of leakage can in some instances be too much...

.pm