telecom@eecs.nwu.edu (TELECOM Moderator) (06/21/91)
The special article which follows has been in sci.crypt, and when Mr.
Simon passed it along to c.d.t. he edited it with a special emphasis
on telecommunications. I thought youo might enjoy reading it. PAT
Subject: Braided Streams (better, bigger and unobfuscated)
Date: Mon, 17 Jun 91 18:37:19 EDT
From: "W.A.Simon" <alain%elevia.UUCP@larry.mcrcim.mcgill.edu>
Warning: the following material was created neither in the United
States, nor in a US owned corporation or a US government establishment
abroad, nor by a US citizen. It has also been previously published,
in whole and in parts, outside the US, as well as within. It would
therefore be ridiculous and useless to subject it to restrictive
orders regarding the distribution of cryptographic material.
-------------
There were a few preliminary postings, in the past three years, but
this one is easier to read and to understand. It also addresses, more
in depth, some of the points which have been fingered by a number of
people, as being unclear. Finally, it explores variations on the
theme. Two concepts are explored here, one is the multiplexing/
encrypting algorithm, the other is the manufacturing of cryptologically
useful keys. The first concept depends on the existence of the second
one to exist in the way it is described here, but it would be best to
assume the second problem has been resolved in order to evaluate the
first one fairly.
There are a number of unproven assertions, for which I make no
apologies; if the readers of c.d.t can contribute anything for, or
against, I'll be very happy.
Of course, since it contains no dazzling mathematical pyrotechnics, a
number of the inner cryptology cognoscenti crowd will just up their
nose and poopoo; but who said they owned the place |8-)? To those who
are still with us by now, I say: Relax, be happy and enjoy the pretty
pictures.
-------------
Introduction
The Braided Stream Secure Communication System is a simple
and fast multiplexer system which provides high levels of
cryptographic security without having recourse to weak,
dubious, or government controlled technologies. Key
management is inherent to the design. Unlike public key
systems, it is not vulnerable to progress in mathematics or
in computational technologies, however unlikely we think
these may be. Based on a key which is read n bit(s) at a
time (bit stream), and forever refreshed (infinite length
one-time pad), a number of streams of data are multiplexed
into one output stream. The choice of which input stream,
to take the next bit to be output from, is determined by the
value of the bit(s) from the key stream.
Principles of operations
The elementary (and least secure) mode of operation is the
two stream mode, which require using up the key one bit at a
time, is also known as the 1-bit-mode (1bm). If the value
of the next bit of key is 0, the next bit of the first input
stream is output; if it is 1, the next bit of the second
input stream is output. The contents of each stream are
normally a plaintext and a key management channel.
Reciprocally, at the other end of the communication link, if
the value of the next bit of key 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 key material. As new key material is
generated/received, it is appended to the key string, and
the used up key bits are discarded. In the 2-bit-mode (2bm)
the key is read 2 bits at a time; 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 this decision to the value of, for
example, the next 2 unused bits in the key, 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 key, through conventional means (cloak and dagger?).
If this seed is uncompromised, so will the link be, for as
long as it is used. Management of keys is done on the basis
of pairs of stations; if a station communicates with more
than one other station, keys must be kept and managed
separately. Whichever bit mode is selected, at least one
stream is always reserved for key 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; this 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 the security. One or more
channel(s) could contain innocuous "give up" message(s), for
the relief of duress, should one be forced to divulge some
plaintext |8-( ...
Unneeded channels can be used to transmit more fresh key
material or plain noise. The station initiating the
communication link generates a, very ideally, random (see
Appendix B) key stream. The stream of bits is appended to
whatever existing key string is currently in use. There is
the unavoidable problem of key exhaustion to be dealt with.
The more streams we need, the faster we use up the key. But
considering the high level of security available, there is
nothing to prevent us from cheating a bit. A number of
strategies for the rejuvenation of old key material can be
left to the imagination of the clients. Basically, some key
material is sent through one or more streams, and this
material is then processed through an algorithm that will
artificially increase its length. This can be done for all
communications, or periodically, by common consent. A much
better way would be to use one channel as a key manager, not
just as a pipe for key material; this would require that we
develop a simple key management language and a few algorithm
to implement it. This should not weaken the security of the
system. Appendix A will provide a number of sound methods.
Appendix B will address the issue of random keys.
Features
A transmitted message will have a length that is different
from that of the plaintext. 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 key. This is an added level of great
incertitude that confronts the opposition. This also
multiplies (the word is much too weak!) the number of
plausible solutions that an exhaustive search can generate.
Finally, the "known plaintext" approach is defeated (to be
proven) as just any arbitrary plaintext can be retrieved,
given a sufficiently long ciphertext, with an adhoc key.
Assuming, in a 2bm operation, that a randomly generated key
is used to transmit two message streams, one stream of key
management information, and one stream of random material to
confuse the opposition, the output stream will be
undistinguishable from a truly random source (to be proven,
but probably wrong in the absolute sense). Four totally
unrelated, but not random, streams would, if braided with a
random key, appear totally unpredictable (to be proven), if
not statistically unbiased.
Applications and variations
An obvious application would be in multiplexing. A provider
of services could, without added effort, multiplex several
client channels, and insure confidentiality from mux to
demux.
In a reversal of roles, the decryption method (unbraiding)
could be used to split a long plaintext in 2, 4, 8 or n
segments, which could be transmitted "en clair" without
further processing. The braiding algorithm could then be
used to put the file back together (radio frequency hopping
could also be used that way). This is a strong variation,
but not quite as strong as the original idea, as it
conserves the length of the plaintext. This variation is
very useful for schemes in which several communication
channels are used, which in itself adds a lot of security.
For example, if four courrier runners are to be entrusted
each with a piece of the message, this message can be split
up in such a way that none of them possesses enough
information to guess even a little bit of the contents.
Even three of them together don't have enough material. All
four segments are required to retrieve any information at
all, plus the key. This could be usefull for electronic
banking arrangements whereby several people must provide an
authentification string, but only the banker knows the
decoding key.
One could, of course, combine the two approaches, by first
mixing plaintext and noise into one stream then, using
another key, the result would be split into a number of
separate communication channels.
With a slight modification in the way keys are managed, we
could provide people with varying amounts of information,
depending on their security clearance and their need to
know, from the same source.
Appendix A - Key regeneration
Key material gets exhausted faster than it can be
transmitted. Therefore, we need a method for the creation
of long keys from short ones. It is assumed the short key
is cryptoanalytically sound.
The first kind of recipe relies on the codebook 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 key material to be appended to
the current key string. Likewise, instructions can be
transmitted as to the kind of transformations to be applied
to the file, before use. There are ways to process data in
such a way that it loses enough information contents to
become useable in this application. The methods are
wasteful (See Appendix D for an example).
Another recipe involves recycling old key material. As each
bit of new key material is transmitted, a number of old key
bits are being discarded; in a 2bm transmission (4 streams),
on average 8 bits of old key get used up for every bit of
new key sent over. We could arbitrarily decide that instead
of simply appending the new bits to the key 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 key material in
order to refresh it. Taking the new key material, in chunks
of, say, 8 bits, one search through the old (to be
discarded) key stream, for a match; when a match is found,
the next, say, 64 bits are cyclically rotated left by one
bit, and appended to the current key string. Then the
search continues from the current position, with the next
chunck of 8 new bits, within the circular buffer. Kind of
weak, but still quite usable...
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 of the
respective segment lengths. If we send 4 streams of random
noise to be used as key material, these 4 streams, known as
A B C and D are processed as follows: Using A as key, 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 key. I think this method would
not be acceptable for use in a conventional cryptographic
system, as the processing would always involve the same
material but, in this case, new material is used every time.
These were all first draft samples; imaginative clients can
find their own. The basic idea is that if some key material
is secure and sound, the results of applying algorithmic
transformations to it are secure and sound as well (to be
proven).
The preferred approach would be to develop a key management
language and use one channel to "program" key production.
Appendix B - Randomness requirements
Key material, ideally, should be random. Manufacturing
random number, algorithmically, is not possible. A good
compromise must be found, which does not compromise security
while allowing automated generation. Should a non
deterministic device be available, it would be wise to take
advantage of it. Failing this, a pseudo-random number
generator (PRNG or prang) will be used.
A prang is considered to be cryptographically useful if it
is unpredictable. In other words, if we generate a string
of 0's and 1's, and we can't guess the next value more than
half of the time, we have a good prang. In order to be
statistically unpredictable, a prang must be unbiased, as
any bias will increase the odds in favor of guessing right.
It is not the purpose of this document to provide a good
prang. It is assumed that random key material, once
processed through an algorithm, can keep its random
attributes. The choice of algorithm is critical.
Appendix C - How do we know when to stop
The stopping problem is another hurdle we have to address.
Plaintext streams, key management streams, noise streams,
don't all contain the same number of bytes, nor do they get
exhausted at the same rythm, because of key randomness.
Another problem arises from the fact that most current
communication interfaces work with 8 bit bytes and, inherent
to the algorithm, we may find ourselves stopping before a
whole byte can be i/o'd. The first principle is that the
longest plaintext stream dictates the earliest stopping
time; so we pad the shorter streams with garbage. The
second principle is that we pad the ciphertext up to the
next full 8 bit byte.
When transmitting noise or key management material, there is
no objection to padding. But when processing plaintext, we
must have a way of knowing where the end of the plaintext
is. There is, so far, no elegant solution. I suggest
reserving a character for escape purposes, and use this
character as end of file marker, unless it is itself
escaped. The ASCII escape character seems to be indicated.
When padding an uncomplete byte up to its full 8 bit
complement, we don't actually use up any key bits, but for
the sake of synchronicity, we must discard as many dummy key
bits as there are padding bits. These key bits must all
point to a plaintext stream, as it is the only type of
stream in which we know where the actual material stops.
Appendix D - Recipes for "almost-randomness"
Any file, when analyzed, will yield a number of patterns.
Contents dependant characteristics and redundancies
resulting from the presence of natural language will appear.
These are artifacts which cryptanalysts exploit to make
educated guesses about the key you have used. But if you
are willing to sacrifice efficiency, you can subject your
file to a number of reducing algorithm that will remove
these hints. The result will still not qualify as fully
random, but unless you have been very careless in your
choice of files, chances are that you will have reached the
limit at which order turns to chaos.
The most simple algorithm would be to discard all bits
except the parity bits. A better one would be to split a
file into two parts (in any way you choose), or to use two
distinct and unrelated files, and compare bytes from each
file, one pair at a time, to output a binary 0 or 1,
depending on the result of the comparaison (skip when
equal). The approximative 16 to 1 ratio of "entropization"
(?) would bring you very close to having a random output.
A sure way of reducing redundancies is to compress the file,
but this process usually leaves tell tales patterns. So it
is necessary to subject it to further processing. One of my
favorite recipes is to take two compressed and unrelated
files; I then swap the high order nibbles from one file with
the high order nibbles from the other (shades of genetic
manipulations). I finally subject the two files to a
reducing process, through pair comparaison, as outlined
above.
-----------------
Enjoy...
Alain UUCP: alain@elevia.UUCPJerry Leichter <leichter@lrw.com> (06/22/91)
TELECOM Digest recently published a special issue containing an article by W.A. Simon on his proposal for an encryption technique known as Braided Streams. Simon makes all sorts of very strong claims for this technique. Given the way it was published, readers might get the impression that they are looking at a breakthrough in cryptography. Nothing could be further from the truth. There is little really new in what Simon proposes -- in fact, there is little there at all. And what IS new is cryptographically quite weak. Let's consider Simon's basic "1bm" system. In this system, we start with a plaintext bitstream P[0,1,...] and a random key bitstream K[0, 1,,...]. We assume that both ends initially know K[0,k-1]. At time t (starting at 0) we inspect K[t]. If K[t] is 0, the next bit sent in the encrypted bitstream E[0,1,...] is the next bit of P, initially 0; if K[t] is 1, the next bit sent is the next bit of P, initially k. Thus, the new key material is sent along with the data in the stream. How might we cryptanalyze such a system? Actually, it's trivial. We first of all assume a known plaintext. This is a common assumption in cryptography because experience shows that (a) eventually, a known plaintext/encrypted message text will end up in the hands of the cryptanalyst; (b) even if the cryptanalyst doesn't know the exact plaintext, he can usually guess at pieces that are highly likely to be there; (c) even without successful guesses as to the exact contents of the plaintext, statistical information will often yield the same results. So let's start off by guessing that the first bit of the key, K[0] is 0. Hence, E[0] should be P[0]. If this DOESN'T match, we know K[0] is in fact 1. If it DOES match, we have a 50-50 chance that the match is fortuitous - after all, even if E[0] is really a key bit, half the time it will match the plaintext. To eliminate that possibility, we need to guess more bits of the key. As we go along, we learn more bits of the key -- every time we learn for certain that key bit was 1, we look ahead to the corresponding position (or positions, if there are any earlier ambiguities) and repeat the process. This gets rapidly difficult to describe, but it converges rapidly. The basic cause is simple: Each output bit depends on only one key bit and one plaintext bit. There is also a second-order dependence on the number of previous 1 bits in the key, which determines WHICH single key or plaintext bit it is; but for n bits of key, there are only log n possible values for the count of previous bits. Normally, we want the cryptanalyst to be faced with an exponential explosion; but no such explosion occurs here! Simon goes on to various elaborations, in particular using multiple key bits to select one of many input streams. As he himself notes, this will exhaust the key stream rapidly. So he has to fall back on various tricks for expanding the key stream. He won't pin himself down to any one technique -- he lets the client choose. This is pointless: Cryptographers always assumes that the opponent knows EVERYTHING about the system except for the key; again because history has shown that that's the only safe assumption. All of the tricks Simon proposes are variations of old ideas. For example, the use of some commonly-known (but non-random) file is the same as using a multi-alpha- betic cipher, with the particular cipher based on successive letters in some book known to both sender and receiver. This variation was broken many, many years ago -- WITHOUT knowledge of the common book. Like most amatuer cryptographers, Simon has no appreciation for the power of statistics, or for the truely massive amounts of intercepted data available to a cryptanalyst in the situations cryptographers actually worry about. If all you are ever going to transmit is, say, a couple of thousand bytes of data, there are plenty of simple cryptographic techniques that are, in practice, quite secure. Once you start sending megabytes, it's a whole other story. (And, of course, since Simon is proposing this as a cryptographic technique to be used by sellers of network services, there are quickly going to be tens and hundreds of megabytes of data to work with.) In any case, if Simon's tricks for key expansion are secure, there is no reason to use the elaborate "braiding" technique, especially since it expands the message considerably. Instead, just XOR the expanded key with the plain text. If the expanded key really is secure, then this encryption is also secure; conversely, if this encryption can be broken, then the expanded key wasn't really secure to begin with. Its use in "braiding" MAY spread its information around, but then again it may not. Proving such things is quite difficult. Simon makes snide remarks about there not being any mathematics in his writing (which is obviously correct). He then proceeds to make a number of claims, followed by parenthetical "to be proven" remarks. Some of his claims are clearly false as stated, and others, if true, would be VERY hard to prove. Asserting that something is "to be proven" in such a context is tantamount to a claim that you pretty much know how to prove it -- you just haven't worked out the details. Making such claims as Simon does is just plain dishonest. I don't remember which cryptographer first stated that he would never accept a new cryptosystem from anyone who had not already broken a strong one, but this is (in some form) generally accepted in the cryptographic community. I see no reason to believe Simon has done anything of the sort, or in fact that he knows anything in particular about cryptography. He's of course welcome to suggest anything he likes, but if anyone relies on his techniques without a GREAT deal of additional work -- well, I've got this bridge available.... Jerry
The Watcher <J.P.Knight@loughborough.ac.uk> (06/22/91)
> When transmitting noise or key management material, there is > no objection to padding. But when processing plaintext, we > must have a way of knowing where the end of the plaintext > is. There is, so far, no elegant solution. I suggest > reserving a character for escape purposes, and use this > character as end of file marker, unless it is itself > escaped. The ASCII escape character seems to be indicated. As you're treating the streams as bit pipes, can't you just use bit stuffing to allow you to use a flag character such as SDLC's 01111110? Using ASCII escape could cause problems if your plaintext to be encrypted isn't ASCII plaintext but binary, EBCDIC, etc. I should not think that the limitation on the number of sequentially transmitted 1's in any one stream should make much difference as the whole point of the exercise is that your cryptanalyst/spy/cracker doesn't know what stream any one bit belongs to. Then again I'm no cryptanalyst/ spy/hacker... 8-) Jon JANET: J.P.Knight@uk.ac.lut Internet: J.P.Knight@lut.ac.uk Dept. Comp.Sci., LUT, Ashby Road, Loughbourgh, Leics, England. LE11 3TZ