Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!lll-crg!seismo!rochester!pt.cs.cmu.edu!g.cs.cmu.edu!byee
From: byee@g.cs.cmu.edu (Bennet Yee)
Newsgroups: net.crypt
Subject: Re: randomly adding bits/bytes
Message-ID: <1026@g.cs.cmu.edu>
Date: Tue, 5-Aug-86 22:44:53 EDT
Article-I.D.: g.1026
Posted: Tue Aug  5 22:44:53 1986
Date-Received: Thu, 7-Aug-86 05:59:28 EDT
References: <8608042018.AA04376@ucbjade.Berkeley.Edu>
Organization: Carnegie-Mellon University, CS/RI
Lines: 57
Keywords: bandwidth, in-place encryption

If I remember correctly, randomly adding bits is frowned upon mostly
because many encryption applications would like to be able to perform
the cryption in-place, i.e., take a chunk of cleartext, encrypt it, put
the ciphertext back in place, then pick up another chunk, etc.  These
would be applicatons where memory is limited, say, encrypting a huge
file, or where you only want to encrypt a certain field of a record
(just the password and leave rest readable by all -- ala /etc/passwd.
Also something like confidential records where you want to enable
statistical gathering access) and don't want to have to copy things
around.  Of course, this is also important if you're transmitting data
and don't want to be limited by the bandwidth -- would you rather send
everything in 1/2 sec (low probability of detection) using a
run-of-the-mill crypto-system or blast the air-waves for 5 minutes
using the latest-and-the-greatest?  If you're working for the CIA from
inside of USSR....

As you (simson@wisdom.bitnet) said, adding random bits or compressing
data really amounts to a modification to the encryption algorithm.  The
Typical Assumption of cryptographic system design is that the enemy
knows the algorithm.  The only secret is the key and the plaintext.
Sometimes, the pattern of the original plaintext (layout) may be public
knowledge also -- this is quite realistic since *everybody* likes to
use standard formats (file formats, source level indentation style,
etc).  Occasionally, this criterion is weakened even more to allow the
opponent to have a few copies of matching plaintext available (a mole,
perhaps -- or a user who knows what his *own* entry looks like).  The
strength of a cryptographic system is determined by the probability of
having the opponent discover the key given x amount of ciphertext.

The main method used to crack simple block ciphers is frequency
analysis.  Using data compression will certainly help.  The problem is
that the compression key for the file must be transmitted also, and it
usually resides at a standard place in a standard format -- more
information for the opponent.

One method that I considered for block ciphers is as follows:  assuming
that data expansion is okay, choose as a function of the key a mapping
from the space of ciphertext to plaintext such that the map is
surjective and (the important part) the number of ciphertext blocks
that map onto each plaintext block approximates the frequency of that
plaintext block.  (This approximation can be made as close as desired
by allowing greater expansion.)  This induces an equivalence class
relation on the space of ciphertext blocks.  The inverse "function"
will map plaintext blocks to equivalence classes.  Now, when we
encrypt, we apply this function to the plaintext block to obtain an
equivalence class.  From this equivalence class *randomly* chose a
representative (use true random hw).

Immune to frequency analysis, no special location for uncompress keys.

Comments?


-Bsy
-- 

-Bsy