From: J. Michael Diehl <mdiehl@triton.unm.edu>
Date: Mon, 12 Jul 93 19:30:41 PDT
To: cypherpunks@toad.com
Subject: xor data hiding?
Message-ID: <9307130230.AA20305@triton.unm.edu>
MIME-Version: 1.0
Content-Type: text/plain


     I heard something interesting which made me think. (gasp)  
 
     I heard that if you encrypt a file with the xor encryption alg.
multiple times with different keys, you get an encrypted file with a
coorisponding effective key which has some interesting properties.  The key
in such a system would have a length equal to the Least Common Multiple of
the lengths of the original key.  So, if you used keys of length
1,2,3,5,7,11,13, you would have an effective key-length of 30,030 bytes!  Of
course, you could use more than one 5-byte key if you wanted, and some of
the bytes should be greater than 127.
 
     Not knowing any better, it occurs to me that given a 30,030 byte key,
and the task of finding the original keys that make it up, (if any)  I'd be
out of luck.  It would seem that "factoring" this large key into smaller
keys would be a tough job...perhapse almost as hard as the factoring problem
in a finite group?  
 
     Brute-force and known plaintext attacks are possible, but lets forget
that for (just) a moment.  If someone DID find the required 30,030 bytes
required to read your massage, you could just as easily show them another
30,030 bytes which would  decode the message into the U.S. Bill of Rights if
you wanted to.  You could keep such One Time Pads laying around your hard
disk if you wanted to...in zip format, perhapse.  You would always be able
to get the true plaintext by simply knowing the 7 key-words.  But few others
would be so lucky.  The point being that there would be some degree of
plausible deniability with such a cypher.  
 
     For the sake of arguement, lets say that the plaintext was first
encrypted with some strong crypto.  Then we used the xor crypto with 7 keys. 
It would be pretty hard to see what had been done.
 
     Now we deal with the brute force attack to get the original keys.  Lets
say that someone does get 7 words which will decrypt your ciphertext into a
plot to distribute <your favorite scum> to <your favorite victim>?  If you
had to, I'm sure you could reverse engineer a completely different set of
keys which will form the same plaintext.  If you absolutely had to, you
might be able to come up with 7 words which will decrypt your ciphertext
back into the Bill of Rights, thus giving you absolute plausible
deniability.  
 
     As far as known plaintext attacks go...well, we hope that doesn't
happen. ;^)
 
     Well, I'm about to wrap this up.  Some time ago, I proposed hiding
messages on the end of other files such as executable.  Well, if we pgp
encrypted a file, then xor encrypted the result with 7 keys and stuck that
on the end of 4dos.com, which is over 64K BTW, I find it hard to believe
that you would be caught readily.  I haven't had time to investigate the
harmonic qualities of such a cypher, but it seems feasible.  You could
delete and wipe the encryption program from your harddisk. (after uploading
the source/executable to your local bbs)  There would be tough times for
anyone who had to pin a given message on you.  Well, what do you think?  I
hope to drum up as much discussion here as with the "radical paranoia"
thread, from which I learned a lot.  Well, I promised to wrap this up, so I
guess I'm done.
 
+-----------------------+-----------------------------+---------+
| J. Michael Diehl ;-)  | I thought I was wrong once. | PGP KEY |
| mdiehl@triton.unm.edu |   But, I was mistaken.      |available|
| mike.diehl@fido.org   |                             | Ask Me! |
| (505) 299-2282        +-----------------------------+---------+
|                                                               |
+------"I'm just looking for the opportunity to be -------------+
|            Politically Incorrect!"   <Me>                     |
+-----If codes are outlawed, only criminals wil have codes.-----+
+----Is Big Brother in your phone?  If you don't know, ask me---+