From: alain@elevia.uniforum.qc.ca (W.A.Simon)
Newsgroups: sci.crypt
Subject: well braid
Date: 17 Aug 92 22:38:30 GMT

In years past, I proposed and explained (many times and in various
manners) a new way to confuse the ennemy, whomever this might be.

A number of weaknesses were found in my proposal, all of them relating
-- in my opinion -- to the telling rather than to the tale.

I still have not addressed them adequately, but I do not propose to
sneak by.  My purpose today is to ask questions and try casting a new
light on the subject.

My own renewed interest is the result of an avalanche of e-mail (3
messages!!!) asking for details, following a recent reference to my
work in sci.crypt.


Quick recap

The proposed system works by multiplexing (braiding) two or more bit
streams.  Depending on the value of key bits, the next bit of output
is taken from one or the other input.

One or more of these streams is/are made of relevant text, the balance
being random noise, rude noises and other confusing non messages.

One or more (this too is key dependant) of the noise streams can be used
as fresh material to be expanded/added into a future key.  This resolves
the tricky problem of key distribution without extra cost.

Once the braid has been constructed, the level of security (confusion)
is such that it is not required (but not forbidden) to encrypt the
resulting stream.  As the number of braided streams increases, so does
the level of security.

A braided stream could be used as input to the manufacture of yet
another braid, in order to increase the level of security some more.

The larger the difference between the length of the plaintext and that
of the braid, the more an opponent is likely to find a "known plaintext".
This is called the "wishfull plaintext" defense.

In anticipation of being forced to divulge the plaintext, one of the
streams (or more) could be designated as a decoy and an ad hoc key
manufactured to produce any particular stream as the only intelligible
result.

A braided stream could easily pass for a random stream (assuming a
well randomized key).


Tiny regret

So far, no implementation has been produced.  I did not do anything
about it because I'd rather play with the concept than write code.
I have not exhausted the exploration of this concept, and I found
new (related) concepts to play with...

A number of people have expressed interest in writing a working
application, but I am yet to hear of a single project that reached
completion.


Big questions

Let's assume for a moment that we have a good random source for a key.
Now, we take two text files and we braid them (witout injection of
random material).  We know the two files are plain English text.
Using the tools of the cryptographic trade, can we recover the two
files?

What clues do we have?  To begin, the high order bit of each plaintext
byte is always 0; how far can we reason on this knowledge alone?  What
help is the knowledge of letter frequencies in rebuilding individual
bytes?  How many possible ways can 2 bytes be combined at the bit level?
How many valid byte pairs can we rebuild from 16 bits? What are the odds
for each successive bit to belong to one byte rather than to the other?
How can the problem be formally stated?

Now, we make the second text random instead of English.  How is the
complexity of the problem affected? How are the odds changed?  And
if we make the number of streams more than two?  If we make all streams
8 bit non English? Is the problem too much or is it just more of the
same with higher horse power requirements?

A really kinky one now: we have two known plaintext streams.  We have
their braid (still no injection of random material).  How many possible
keys could have produced the same braid from these two plaintexts?  If
we only know one plaintext in advance, how many possible guesses would
be suitable for the second plaintext?  How many of them plausible?

Finally, the hard one: we don't know the number of streams in the braid.
We don't know the key.  We suspect there is injection of random noise (in
other words, not all streams are meaningfull).  We think we know the
plaintext.  How many streams was the plaintext divided into? How can we
be certain the plaintext we know about was really the one sent out? How
do we know that it was the only meaningfull one in the braid? How many
streams were there?  Which ones will be used to rejuvenate the key?


Good random source?

This is a whole story by itself...  to be continued, I am sure.



--
 The Vacuum Cleaner Man (reality sucks)
 God made me a chauvinist, my woman made me clean the house