Path: utzoo!utgpu!water!watmath!clyde!rutgers!ucla-cs!cit-vax!elroy!ames!ll-xn!mit-eddie!uw-beaver!tektronix!reed!percival!bucket!leonard
From: leonard@bucket.UUCP (Leonard Erickson)
Newsgroups: sci.crypt
Subject: Re: how do you tell encrytped data from
Message-ID: <685@bucket.UUCP>
Date: 15 Jan 88 05:07:56 GMT
References: <660@bucket.UUCP> <-63293657@sneaky>
Reply-To: leonard@bucket.UUCP (Leonard Erickson)
Organization: Rick's Home Grown Unix; Portland, OR
Lines: 72

In article <-63293657@sneaky> gordon@sneaky.UUCP writes:
<> I know that transposition and *simple* substitution can be detected by
<> letter frequency analysis. But is a "flat" distibution evidence of random
<> data?
<
<No.  Among other things, crypt(1) output gives a fairly flat distribution
<in its 256-character output alphabet.  (the version of crypt I am thinking of 
<is based on a WW-II rotor machine, and uses DES only to scramble the user's 
<typed key.  (You don't need to crack the DES to crack the encryption).  This 
<version was in System III, among others).  In fact, it gives an absolutely 
<flat distribution for any message consisting of one character repeated a 
<multiple of 256 times and any key.  (If not a multiple of 256, the 
<distribution is as flat as you can get with that message length).
<
<You also get a flat distribution, more or less, by encoding techniques 
<as "encode the i th character of the message by rotating it i positions in 
<the alphabet", assuming the message was reasonably long.  This doesn't even 
<have an encryption key.  A "real" encryption might use a keyword J characters
<long, and encode the i th character of the message by rotating it by its
<position in the message (i) plus an amount determined from the (i mod J)th 
<character of the key.  For messages that are long relative to the key length 
<and the alphabet size, this will give a fairly flat distribution.  You will
<be able to detect distribution patterns by taking every (J * alphabet size)th
<character, and looking at the frequency distribution for that.  
 
All the above examples, including the crypt that simulates a rotor machine
are polyalphabetic substitutions. I have program that will do analysis of
a text by calculating the variance for all the key lengths up to a user 
specified limit. It outputs the length of with the "best fit". 

On both random text and the suspect text, it always output the limit length
as the best fit. And the fit was none too good.

<I'm not quite sure how to interpret this.  Would this mean that running the
<message through uuencode(1) (which maps every 3 characters of 8 bits each
<into 4 characters out of a 6-bit 64-character alphabet) is too complex?  It 
<doesn't even have an encryption key!  Running stuff through uuencode does tend 
<to flatten out the distribution somewhat, but a message consisting mostly of
<the letter x will still have several high-frequency characters.
<
<To REALLY flatten out the distribution, there are several popular UNIX and
<DOS utilities to do this, under the classification "data compression programs".
<These include pack, compress, ARC, and compact.  If you don't like the
<use of all 8 bits in the output, run the result through a filter to transform
<it to a smaller alphabet.  These include things like uuencode/uudecode, 
<btoa/atob (distributed with compress 4.0), encode/decode (distributed with B 
<news 2.11), and, if you're really desparate, od, the octal dump program.
<(A few years back, someone posted a program to take an octal dump and 
<re-create the file it was a dump of).  

Well, I've never even seen any _hints_ on how to attack a cipher where the 
plaintext characters can't be "localized". Since you can't do statistical
analysis on the characters (at least not and get results that _mean_ 
anything!! :-) it would appear that you are reduced to trial and error.

Uuencode and atob are at the extreme edge of the ability range expected of
the probable originators of those old messages. Compress and ARC were 
out of the question! (we're talking c-64s and BASIC here!).  

A favorite that has a fair amount of popularity, is XORing the plaintext
with a key on a byte-by-byte basis. It is simple, and you decode by running
the ciphertext thru the encryptor again. Of course it is only as secure as
key.

You would also be surprised at how long you can stump even a skilled amateur
with something silly like switching character sets. (eg using EBCDIC where
ASCII is expected)      
-- 
Leonard Erickson		...!tektronix!reed!percival!bucket!leonard
CIS: [70465,203]
"I used to be a hacker. Now I'm a 'microcomputer specialist'.
You know... I'd rather be a hacker."