xor data hiding?

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---+

J. Michael Diehl <mdiehl@triton.unm.edu> says:
>      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.

Sadly, the Friedmans already cracked the "multiple repeating xored
keys" cypher a while back -- about fifty years ago.

Don't be embarassed, by the way -- everyone comes up with cyphers that
have been cracked before. However, I would suggest reading "The
Codebreakers" and the current literature before proposing new systems.

Perry

According to Perry E. Metzger:
> Sadly, the Friedmans already cracked the "multiple repeating xored
> keys" cypher a while back -- about fifty years ago.

I knew it was crackable.  That wasn't the point.  The point was data hiding.

> Don't be embarassed, by the way -- everyone comes up with cyphers that
> have been cracked before. However, I would suggest reading "The
> Codebreakers" and the current literature before proposing new systems.

I'm not embarassed; I didn't develope the crypto I was discussing.  I was simply
discussing a new application for it.  I will read Codebreakers.  

Thanx.

+-----------------------+-----------------------------+---------+
| 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---+

What you are talking about sounds like the original Vernam cipher that Dave
Kahn talks about in _CodeBreakers_.  There, he was using a teletype with two 
XORing tapes.  One tape was 1000 characters long, the other was 999.  Thus,
999000 characters would have to go past before the system repeated.  HOWEVER,
once it does repeat, all security is compromized.  Even before that time,
I believe there are subtle attacks you can use based on the repetition of the 
keys.  So, this is not a secure cipher method.  I would personally 
suggest tacking an 128 bit IDEA key onto 4dos.com instead.  Or use
DES even.

BTW: Though you could come up with a 30Kb+ string which when XORed would
give you any plaintext, you could not come up with a few small strings
which when used over each other would give you that.  There just isn't enough
information to make that possible.
-- 
PGP 2.3 Key by finger

According to Douglas Sinclair:
> 
> What you are talking about sounds like the original Vernam cipher that Dave
> Kahn talks about in _CodeBreakers_.  There, he was using a teletype with two 
> XORing tapes.  One tape was 1000 characters long, the other was 999.  Thus,
> 999000 characters would have to go past before the system repeated.  HOWEVER,
> once it does repeat, all security is compromized.  Even before that time,
> I believe there are subtle attacks you can use based on the repetition of the 
> keys.  So, this is not a secure cipher method.  I would personally 
> suggest tacking an 128 bit IDEA key onto 4dos.com instead.  Or use
> DES even.

The point wasn't to be unbreakably secure; it was to be UNFINDABLY secure.  We
convolute an allready encrypted message to the point of not being recognizable
as cyphertext, then we hide it on the end of a file.  We want it to look like
garbage.

> BTW: Though you could come up with a 30Kb+ string which when XORed would
> give you any plaintext, you could not come up with a few small strings
> which when used over each other would give you that.  There just isn't enough
> information to make that possible.

Agreed.  This leaves us with several OTP's laying around in zip format.  This 
isn't so bad as long as we don't forget the original 7 keys.  The main purpose
of all of this is plausible deniability.

Thanx for your comments.  Still listening.

+-----------------------+-----------------------------+---------+
| 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---+

J. Michael Diehl <mdiehl@triton.unm.edu> says:
> According to Douglas Sinclair:

> The point wasn't to be unbreakably secure; it was to be UNFINDABLY
> secure.  We convolute an allready encrypted message to the point of
> not being recognizable as cyphertext, then we hide it on the end of
> a file.  We want it to look like garbage.

Cyphertext from any decent system ALREADY looks random. Whats the
point of doing more to it?

Perry

According to Perry E. Metzger:
> J. Michael Diehl <mdiehl@triton.unm.edu> says:
> > According to Douglas Sinclair:
> > The point wasn't to be unbreakably secure; it was to be UNFINDABLY
> > secure.  We convolute an allready encrypted message to the point of
> > not being recognizable as cyphertext, then we hide it on the end of
> > a file.  We want it to look like garbage.
> 
> Cyphertext from any decent system ALREADY looks random. Whats the
> point of doing more to it?

Many encryption tools such as ripem, pgp, and dolphin can recognize their own
output...which indicates that there is a footprint to that particular
implimentation.

+-----------------------+-----------------------------+---------+
| 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---+

J. Michael Diehl <mdiehl@triton.unm.edu> writes:

> Many encryption tools such as ripem, pgp, and dolphin can recognize their own
> output...which indicates that there is a footprint to that particular
> implimentation.

in this case, you're just trying to garble what people see so why not 
just xor "hello, world." /bin/csh or \command.com on top of it to avhieve 
that result.  No need for anything significant, I mean, if you xor 'X' 
over the whole thing, you've achieved the same result - after all, if 
someone wants to xor 'X' to knock that level of encryption(if I may call 
simple substitution "encryption") then it's fair to assume that the 
person knows it's cyphertext and they want the information below it, so 
that's a good place to use some decent encryption.. "congratulations, you 
have found the secret message. send the answer to old pink care of the 
funny farm" (Pink Floyd, The Wall (backmasking)) is what readily comes to 
mind when i see what you're getting at.. after all, searching a disk for 
data that fits specific patterns is one thing, figuring out that one of 
the index files for a database program with literally hundreds of 
database files and indecies (I used to work on programming such a 
database, so I know they exist and that they are a perfect hiding place 
for just about everything) is actually an encrypted file isn't a walk in 
the park.  anyway, enough babbling - hope some of it makes sense. =)
the park


--
Mike Sherwood
internet: mike@EGFABT.ORG     uucp: ...!sgiblab!egfabt!mike

J. Michael Diehl <mdiehl@triton.unm.edu> says:
> According to Perry E. Metzger:
> > J. Michael Diehl <mdiehl@triton.unm.edu> says:
> > > According to Douglas Sinclair:
> > > The point wasn't to be unbreakably secure; it was to be UNFINDABLY
> > > secure.  We convolute an allready encrypted message to the point of
> > > not being recognizable as cyphertext, then we hide it on the end of
> > > a file.  We want it to look like garbage.
> > 
> > Cyphertext from any decent system ALREADY looks random. Whats the
> > point of doing more to it?
> 
> Many encryption tools such as ripem, pgp, and dolphin can recognize their own
> output...which indicates that there is a footprint to that particular
> implimentation.

Intentionally. They INTENTIONALLY put magic numbers at the head of the
file. If you remove that, the file is random. You can hack PGP not to
use headers if you really want to. Proposing some useless cryptosystem
just to hide the headers is completely unneeded.

Perry