🚀 go-pugleaf

I've seen some interesting posts here recently, but I have yet to
see the topic of padding data with garbage.  It seems to me that
if you had an algorithm that would not only encrypt the data, but would
also insert random data into the original data (without following
a regular pattern) that it would be almost impossible for someone
to tell what was real information and what was just junk.  Although
the size of the document would increase, the difficulty in decrypting
the message would also increase considerably.

The only problem I can see with this method is how do you insert data
in a non-regular pattern and still have the ability to remove it later.
Please comment on this type of procedure.  I'm sure people have thought
on these lines before and would be interested in seeing what they have
to say......

			Greg Webb

In article <1992Jul31.153719.28374@ncsu.edu> Webbge@che17.ncsu.EDU (Greg Earl Webb) writes:
>
>I've seen some interesting posts here recently, but I have yet to
>see the topic of padding data with garbage.  It seems to me that
>if you had an algorithm that would not only encrypt the data, but would
>also insert random data into the original data (without following
>a regular pattern) that it would be almost impossible for someone
>to tell what was real information and what was just junk.  Although
>the size of the document would increase, the difficulty in decrypting
>the message would also increase considerably.
>
>The only problem I can see with this method is how do you insert data
>in a non-regular pattern and still have the ability to remove it later.
>Please comment on this type of procedure.  I'm sure people have thought
>on these lines before and would be interested in seeing what they have
>to say......
>
>			Greg Webb
>

I have thought about this scheme at one point in time.  It is not
difficult to implement but it is not superior to random padding.
Actually it is less efficient.  One way to realize the scheme is to
have a pseudorandom binary string which is derived from the encryption
key, say:

	100111010100101010001110101010001...

If the i-th bit of this string is 1, the i-th symbol in the ciphertext
is taken from the plaintext.  Otherwise, the i-th symbol is randomly
chosen.

Webbge@che17.ncsu.EDU (Greg Earl Webb) writes:


>I've seen some interesting posts here recently, but I have yet to
>see the topic of padding data with garbage.  It seems to me that
>if you had an algorithm that would not only encrypt the data, but would
>also insert random data into the original data (without following
>a regular pattern) that it would be almost impossible for someone
>to tell what was real information and what was just junk.  Although
>the size of the document would increase, the difficulty in decrypting
>the message would also increase considerably.

>The only problem I can see with this method is how do you insert data
>in a non-regular pattern and still have the ability to remove it later.
>Please comment on this type of procedure.  I'm sure people have thought
>on these lines before and would be interested in seeing what they have
>to say......

>			Greg Webb

A guy names William Simon (email address: alain@elevia.UUCP) posted
some stuff long ago about "braiding" messages. Essentially you took
two streams of data (a and b) and a pseudo-random source. Everytime a
1 came from the source you took a block of data from a and everytime a
0 came from the pseudo-random source you took a block of data from b.
Reconstructing a and b is possible if you have the same pseudo-random
bit stream. 

There were long debates about how easy it is to reconstruct this, but
Simon showed that it was equivalent to the one-time pad. (I believe he
assumed that a and b had "random" patterns. Obviously if a is all
zeros and b is all ones, then reconstruction is simple.) 

In the other direction, a fellow named Dave August once wrote a paper
for Cryptologia (circa 1987) about the technique of deleting random
letters from a plaintext message. The redundancy of English left the
message still readable.

-Peter
-- 
Peter Wayner   Department of Computer Science Cornell Univ. Ithaca, NY 14850
EMail:wayner@cs.cornell.edu    Office: 607-255-9202 or 255-1008
Home: 116 Oak Ave, Ithaca, NY 14850  Phone: 607-277-6678

In article <1992Jul31.153719.28374@ncsu.edu> Webbge@che17.ncsu.EDU (Greg Earl Webb) writes:
>The only problem I can see with this method is how do you insert data
>in a non-regular pattern and still have the ability to remove it later.


I've used one method and have planned at least two others.  I now prefer
#2 for its simplicity.

1.	in one system of mine, I encrypt a vector of length 20 by
	multiplying by a 20x20 matrix.  (Hill's algorithm) Each element of
	the vector is composed of two ASCII characters plus one random bit.

		c0 + 129*(c1 + 129*b)

	(I use 129 so that I can have character 128 which means "end of
	code line") I sometimes end a code line short and just pad the
	remainder with random characters [0..128].

2.	in another system, I prefix compressed data with a fixed number of
	random bytes -- then pass the combination through a transposition
	whose key depends in part on the sum of the bytes of the first
	block of data (code posted here a month or two ago -- c/o
	setzer@math.ncsu.edu (William Setzer).

3.	in another system, I drive a state machine with 3 states (below is
	the stripping machine):

		for ( n = (getc(stdin)) % 17 ;	/* # of bytes of padding */
		      n > 0 ;
		      n-- )
		  getc( stdin ) ;	/* toss the padding */
		for ( n = getc( stdin ); n > 0 ; n-- )
		  use( getc( stdin ) ) ;	/* use good characters */

In article <1992Jul31.153719.28374@ncsu.edu> Webbge@che17.ncsu.EDU
(Greg Earl Webb) writes:
>I've seen some interesting posts here recently, but I have yet to
>see the topic of padding data with garbage.  It seems to me that
>if you had an algorithm that would not only encrypt the data, but would
>also insert random data into the original data (without following
>a regular pattern) that it would be almost impossible for someone
>to tell what was real information and what was just junk.  Although
>the size of the document would increase, the difficulty in decrypting
>the message would also increase considerably.
>
>The only problem I can see with this method is how do you insert data
>in a non-regular pattern and still have the ability to remove it later.
>Please comment on this type of procedure.

Clearly it's important that you *do* have the ability to remove it
unambiguously later.  Kahn "The Codebreakers" p.608-609 contains a
story from World War II describing the problems that once ensued
when improper padding *wasn't* removed (i.e. was taken as message
text) in a US Navy message during the battle of Leyte Gulf in 1944:

	Naval communication procedure called for the head
	and the tail of messages -- their most vulnerable
	points -- to be concealed by nulls consisting of
	meaningless words.  This ``padding'' was supposed
	to be totally alien to the text, but the enciphering
	ensign in Pearl Harbour violated this rule when he
	used a phrase that was ``just something that popped
	into my head.''  Though he correctly set the padding
	off from the text by doubled letters, communicators
	on [US Navy Admiral] Halsey's flagship decided against
	removing it on the chance that it might be part of
	the message.  Thus, the decipher tape that they rushed
	to Halsey read:

		From CINCPAC [Nimitz] action Com Third
		Fleet [Halsey] info Cominch [King] CTF
		seventy four [Kinkaid] X Where is repeat
		where is Task Force thirty four RR the
		world wonders

The final three words (the padding) were taken as a personal
insult, with various ensuing mixups resulting.

- Jonathan Thornburg
  <jonathan@einstein.ph.utexas.edu> or <jonathan@hermes.chpc.utexas.edu>
  University of Texas at Austin / Physics Dept / Center for Relativity
  and (for a few more months) U of British Columbia / {Astronomy,Physics}

In <1992Jul31.172627.1876@cs.cornell.edu> wayner@cs.cornell.edu (Peter Wayner) writes:

>Webbge@che17.ncsu.EDU (Greg Earl Webb) writes:
>A guy names William Simon (email address: alain@elevia.UUCP) posted
>some stuff long ago about "braiding" messages. Essentially you took
>two streams of data (a and b) and a pseudo-random source. Everytime a
>1 came from the source you took a block of data from a and everytime a
>0 came from the pseudo-random source you took a block of data from b.
>Reconstructing a and b is possible if you have the same pseudo-random
>bit stream. 

Yes, that was *very* interesting and I followed with great attention the
whole discussion, some months ago.

I am wondering where William Simon has gone and if any program implementing
braid-streams cryptography is available. Otherwise I am planning to write it
on my own.
-- 
David Vincenzetti  -*-  vince@ghost.dsi.unimi.it, +39-2-5500639[12]
                        Public Key Available by finger(1)

In article <1992Jul31.153719.28374@ncsu.edu> Webbge@che17.ncsu.EDU (Greg Earl Webb) writes:
>
>I've seen some interesting posts here recently, but I have yet to
>see the topic of padding data with garbage.
>[...]
>			Greg Webb

I've recently had an idea along these lines, though no doubt someone's
thought of it before...

The goal is to make the first several blocks of plaintext be (almost)
totally random.  With an error propogating cypher, this may help to
thwart a guessed plaintext attack.  Useful for encrypting something
with fixed headers.

First, you need a cryptographically strong random number generator.
It spits out a sequence of bytes many of which will eventually be
prepended to your message.  You also decide (at random, but within
given parameters) how many bytes you wish prepended.

Next, define a property that you can check each byte for.  A simple
property might be:  Is on this list of N byte values.  A more complex
property could change based on the set of bytes output so far.

Next, you say that your padding will be over when Q bytes satisfy the
above property, where Q is a small constant like 5.

Now, start generating bytes.  If a byte doesn't have the property,
just spit it out.  If it does, and the previous Q-1 bytes also had the
property, and you're not done with your padding yet, discard the byte.
When you're done with the padding, just reject bytes that don't have
the property until you have spit out Q that do.

Questions:  what would be good values for Q and N (persumably based on
the cypher block size and the desired (approximate) number of random
blocks)?  I would guess that you would want N chosen so that the
probablity of seeing Q bytes in a row with the property within your
padding is roughly .5.

Is it worth doing this?  Would it be just as secure to just say that
you'll always prepend 4 blocks of random pad to the plaintext before
encyphering?

-- eric messick

eric@parallax.com  uunet!parallax!eric



-- 
-- eric messick

eric@parallax.com  uunet!parallax!eric