From: Brian Durham <bdurham@metronet.com>
Date: Wed, 18 Sep 1996 19:58:15 +0800
To: cypherpunks@toad.com
Subject: Re: Redundancy in XOR encryption
Message-ID: <323F94D1.EC0@metronet.com>
MIME-Version: 1.0
Content-Type: message/rfc822


To: <bdurham@metronet.com>
Subject: Undeliverable Message
From: <MAILER-DAEMON@mqg-smtp3.usmc.mil>
Date: Tue, 17 Sep 96 7:15:44 -24000

To:            <paul@fatmans.demon.co.uk>,<cypherpunks@toad.com>
Cc:            
Subject:       Re: Redundancy in XOR encryption

Message not delivered to recipients below.  Press F1 for help with VNM
error codes.               

	VNM3043:  BANYAN SERVER@MAG26@2DMAW NEW RIVER


VNM3043 -- MAILBOX IS FULL

   The message cannot be delivered because the
   recipient's mailbox contains the maximum number of 
   messages, as set by the system administrator.  The
   recipient must delete some messages before any
   other messages can be delivered.
    The maximum message limit for a user's mailbox is 
   10,000.  The default message limit is 1000 messages.  
   Administrators can set message limits using the 
   Mailbox  Settings function available in the 
   Manage User menu  (MUSER). 

   When a user's mailbox reaches the limit, the 
   user must delete some of the messages before 
   the mailbox can accept any more incoming messages.

UNDEFINEDpaul@fatmans.demon.co.uk wrote:
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> 
> I have a question I hope someone here might be able to answer:
> 
> As the method of cryptanalysis of XOR (Ie. index of coincidence)
> relies on redundancy in the plaintext, would the following be strong:
> 
> 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 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.

   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.

   Others may disagree with my thought-experiment and my approach,
but I think this is quite possible ... even to persons with limited
computing resources.

   Brian Durham
   bdurham@metronet.com