Redundancy in XOR encryption

[geeman at best.com]

in any practical or semi-practical application, you'll have to have a way to decompress the 
perfectly compressed data.  A dictionary?  A Huffman-tree-ish sort of thing?  Are you going
to transfer it out-of-band?  **It** becomes the target of interest.


----------
From: 	paul at fatmans.demon.co.uk[SMTP:paul at fatmans.demon.co.uk]
Sent: 	Tuesday, September 17, 1996 12:33 PM
To: 	cypherpunks at toad.com
Subject: 	Re: Redundancy in XOR encryption

> > 
> > Compress P to get perfect compression (ie. 0 redundancy)
> > Encrypt F (the compressed text) using a repeated key XOR
> > 
> > of course this is all rather theoretical as there is no such thing as
> > perfect compression, but I just thought it might be interesting to
> > see if this is indeed strong, superficially it appears so to me...
> > 
> 
> Paul:
>    I think that if the cryptanalyst knows that F has zero redundancy
> that he can run searches from 0 to n bits for the key and have
> the computer flag solutions that have zero redundancy.  

I never though of that.
 
>    I also think that a perfectly compressed file would have a relative
> entropy value close to one also, hence the computer could flag possibles 
> that have both characteristics.

yeah, these two are reasonably unlikely to occur together (only a 
reasoned guess, anyone got any comments on this?)
so we really have a weakish system.
 
>    Hence, instead of searching for plaintext by counting coincidences,
> we are searching the decrypts for solutions that have zero redundancy
> and a relative entropy value close to one.  How many solutions will
> have both these qualities?  I don't know.  But if the compression method 
> is known, brute force will be tried, and only having to try to 
> decompress (read) data that has the resultant characteristics
> of compressed information will speed things up by quite a bit.

Yeah, this is still a form of brute force but I was thinking of this 
in terms of a smallish (sub 200 bit) key, so brute force against 
solutions with 0 entropy is a realistic possibility.