alain@elevia.UUCP (W.A.Simon) (06/13/91)
I have, on several occasions, discussed the system described
here. It did not cause much interest in the community, in
part because it was not propagated as widely as it should have
been, and in part because the principles have not been formally
proven sound. As I am still unable to provide such a proof, and
in view of the pressing need (as evidenced by recent attempts by
legislators to control the technology) for a system that
originates outside of the s p o o k controlled realm, I have
decided to publish it again, for the purpose of donating it to
the public domain (again), and giving anybody who is interested a
chance to evolve their own proof, and implementations. This
let's the horse out, if such a horse is viable, and it negates
all efforts that could be made to close the barn's door. You
will notice I have taken certain liberties with standard
terminology and spelling; know that is done on purpose, to
address the possibility that some words might trigger unwanted
attention, which could possibly result in unfriendly message
cancellations. An improper news group has been used for the
same reason. A message in the proper group will inform all
interested parties, after the flooding algorithm has done its
job. Enjoy.
Introduction
The Braided Stream (used to be known as: E n t r o p y
Insertion) Communication Multiplexer is a simple and fast
system which allows for high levels of confidence without
having recourse to weak, dubious, or controlled,
technologies. K management is inherent to the design.
Unlike pub K type systems, this is not vulnerable to
progress in mathematics or in computational technologies.
Principles of operations
Based on a K bit stream, a number of streams of data are
multiplexed into one output stream. The elementary mode of
operation is the two stream mode, which require using up the
K one bit at a time. It is also know as the one bit mode
(1bm). If the value of the next bit of K is 0, the next bit
of the first stream is output; if it is 1, the next bit of
the second stream is output. Reciprocally, at the other end
of the communication link, if the value of the next bit of K
is 0, the next bit of input is appended to the first stream;
if 1, to the second stream. In such 1bm application, the
second stream is used to communicate fresh K material. As
new K material is generated/received, it is appended to the
K string, and the used up K bits are discareded. In the two
bit mode (2bm), the value of the combined bits range from 0
to 3, therefore allowing the mixing of 4 streams. The 3bm
will obviously work on 8 streams, and the 4bm on 16... The
choice of bit mode is left to the user (I am in favor of
deferring the decision to the value of, for example, the
next 2 unused bits in the K, plus one, which would result in
either of the bit modes in the range from 1 to 4).
Two communicating stations are initially loaded with a
startup K, through conventional means, ie: c l o a k and d
a g g e r |8-). If this seed is uncompromised, so will the
link be, for as long as it is used. Management of Ks is
done on the basis of pairs of stations; if a station
communicates with more than one other station, Ks must be
kept and managed separately. Whichever bit mode is
selected, at least one stream is always reserved for K
management. The contents of all other streams is a choice
for the client to make. A channel (stream) that appears to
contain noise only, may itself be a braided stream from a
previous processing stage; such practice is left to the
users to decide; they could be useful in staggered
protective arrangements whereby a corporate system separates
streams for its divisions, which can in turn unbraid their
own material. The more streams are braided together, the
better. Unneeded channels can be used to transmit more
fresh K material or plain noise. The station initiating the
communication link generates a (very ideally) random K
stream. The stream of bits is appended to whatever existing
K string is currently in use.
There is the unavoidable problem of K exhaustion to be dealt
with. The more streams we need, the faster we use up the K.
But considering the ability of the system to provide a high
level of confidence, there is nothing to prevent us from
cheating a bit. A number of strategies for the rejuvenation
of old K material can be left to the imagination of the
clients. Basically, some K material is sent through one or
more streams, and this material is then processed through an
algorithm that will increase its length. This can be done
for all communications, or periodically, by common consent.
This should not weaken the system. Appendix A will provide
a number of sound methods.
Features
A transmitted message will have a length that is different
from that of the p l a i n text. The difference in length
is grossly determined by the selected bit mode (about double
the length in 1bm), and finely affected by the statistical
profile of the K. This is an added level of great
incertitude that confronts the opposition. This also
multiplies (the word is too weak...) the number of plausible
solutions that an e x h a u s t i v e search can generate.
Finally, the known p l a i n text approach is defeated (to
be proven).
Assuming that a randomly generated K is used to transmit one
message stream, two streams of random material to be used
for the manufacturing of a fresh K, and one stream of random
material to confuse the opposition, the output stream will
be undistinguishable from a truly random source (to be
proven). Four totally unrelated, but not random, streams
would, if braided with a random K, appear totally
unpredictable (to be proven), if not statistically unbiased.
Appendix A
K material gets exhausted faster than it can be transmitted.
Therefore, we need a method for the creation of long Ks from
short ones. It is assumed the short K is c r y p t o
analytically sound.
The first kind of recipe relies on the c o d e book
principle. The two correspondants each have a copy of
identical files. Using the safety of the system, one can
tell the other which file is to be used as fresh K material
to be appended to the current K string. As well,
instructions can be transmitted as to the kind of
transformations to be applied to the file, before use.
Another recipe involves recycling old K material. As each
bit of new K material is transmitted, a number of old K bits
are being discarded. In a 2bm transmission (4 streams), on
average 8 bits of old K get used up for every bit of new K
sent over. We could arbitrarily decide that instead of
simply appending the new bits to the K string, the bits that
would otherwise have been discarded are also re-appended.
Intuitively, one might think that this weakens the system.
I don't think so (to be proven).
A randomizing system could be used with old K material in
order to refresh it. Taking the new K material, in chunks
of, say, 8 bits, one search through the old (to be
discarded) K stream, for a match; when a match is found, the
next, say, 64 bits are appended to the current K string.
Then the search continues from the current position, with
the next chunck of 8 new bits.
A purely algorithmical recipe, involving operations of the
various streams upon each others, could be used to increase
the total length beyond a simple arithmetic sum. If I send
4 streams of random noise to be used as K material, these 4
streams, known as A B C and D must be processed as follows:
Using A as K, as many times as required, in 1-bit-mode, mix
B and C, then mix C and D, then D and B. Repeat through all
permutations, using B C and D, in turn, as K.
--
William "Alain" Simon
UUCP: alain@elevia.UUCP