Path: cactus.org!milano!cs.utexas.edu!rutgers!usc!zaphod.mps.ohio-state.edu!
+ rpi!news-server.csri.toronto.edu!bonnie.concordia.ca!clyde.concordia.ca!
+ altitude!elevia!alain
From: alain@elevia.UUCP (W.A.Simon)
Newsgroups: sci.crypt
Subject: Braided streams (The Leichter Side)
Message-ID: <1991Jun23.042445.9676@elevia.UUCP>
Date: 23 Jun 91 04:24:45 GMT
Organization: The Electronic Path - Global Village
Lines: 272
In <9106221400.AA01080@BULLDOG.CS.YALE.EDU> Jerry Leichter
writes:
> 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.
To be clear: I did not ask for fanfares, just exposure.
To be honest: I don't mind a bit.
To be correct: It won't be a breakthrough until we can
provide a formal proof.
> There is little really new in what Simon proposes
I did publish, separately in sci.crypt, a nostalgic piece about
a possible ancestor to this system. You can't very well accuse
me of claiming novelty. There is a lot of deviousness and a bit
of intelligence in what I proposed, but the novelty is in the
way I implement the idea, and in the beneficial side effects.
BTW, since you said there is little new in there, that could be
interpreted as an indication that you know of something similar.
Is it the case? Could you please explain?
> in fact,
> there is little there at all. And what IS new is cryptographically quite
> weak.
Quite an indictement.
> Let's consider Simon's basic "1bm" system.
Admitedly (my own words), the weakest mode. But the actual number
of streams (the bit mode selected) is key dependant. So, in fact,
you can't assume you are dealing with a 1bm case. This simple fact
happens to weaken your other points considerably. You could even
devise your implementation so it never uses a 1bm. A suggestion,
by der Mouse at McGill U, indicated that the number of braided
streams doesn't even need to be a power of two; you could use the
3bm (8 streams) and have a braid made of 5 streams only, and that
too could be key dependant.
> 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.
I said it more elegantly. |8-)
> How might we cryptanalyze such a system? Actually, it's trivial.
Could we, may I ask, get to the point? |8-)
> We first of
> all assume a known plaintext.
That's the first thing I did.
> 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.
We speak the same language, I think.
> 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.
Capital. So far, easy.
> 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.
For you, and for a limited time only, I'll use a key that has
perfect overall 50-50 distribution. Just remember that it is
not quite that simple with random keys. And it happens to be
an important factor towards the strength of the system. I also
remind you that we don't necessarily deal with two streams only.
> 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 ambi-
> guities) and repeat the process. This gets rapidly difficult to describe,
Doesn't it just, though... and the incertitude doesn't get
resolved any quicker, contrary to what you imply, but fail
to demonstrate.
> but it converges rapidly.
No it doesn't. I suggest you try an example. In fact, der Mouse
published a convincing demonstration that given any desired target
plaintext, there is a key string that will allow you to retrieve
it from the ciphertext. He did this with a 1bm only sample. I'll
let you imagine the rest. This is not a formal proof of the absolute
and perenial truth of this fact, but it is damn convincing. As you
can see, the Braided Stream (I don't like to call it BS) cipher
creates a set of assumptions that defeats the normal approach. This
is where the real novelty resides. As an alnalyst, if you know you
face a braided stream, you may as well give up on known plaintext
attacks.
At best, you will match a plaintext and a key to a given ciphertext,
but you will have achieved no progress whatsoever towards breaching
the security of the link, because a) you knew and expected the
plaintext, b) the key it does allow you to extract won't be used
right away, but at an undetermined time in the futur, depending on
the available store of key material, and on the volume of traffic,
c) you have no certitude that the known plaintext was in fact sent
at that particular time, since you can retrieve it from any other
traffic intercept just as well anyway.
To breach the security, you would have to hit on a correct plaintext
and key combination and keep hitting correctly until you intercept
the portion of message where the compromised key starts being used.
A tall order.
> The basic cause is simple: Each output bit depends
> on only one key bit and one plaintext bit.
Not quite. Each output bit depends on only one key bit (if 1bm)
to determine which of the plaintext or the key management stream
will provide its contents.
> 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!
Try to show an example.
> 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 expand-
> ing 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.
I don't, so far, provide a satisfying key management system.
I do provide a channel for doing it. That's also part of the
novelty. I may not have to "pin myself down", since any
system that uses a fully secure seed, may be used to generate
a fully secure sequence, as long as the choice of algorithm
used to expand the seed is itself dependant on the key. In
other words, if I have a hundred different algorithms that
can generate a string of 0's and 1's that's longer than the
string needed to provide the seed and to specify the choice
of algorithm, and I do that often enough during a communication,
I am home free. Example: if I send, through the key management
stream, a token saying "use the nth prime number" and a token
specifying the value of n, I can generate a string that's long
enough to defeat the key exhaustion phenomenon, but short enough
so I can move on to "use the number of ways we can arrange n
objects taken p at a time", followed by tokens for n and p, then
I can go on to "use the nth Fibonacci number"... you get the drift.
And it is all done under key control. If a hundred is not high
enough we can find many more sequences, algorithms and combinations
thereof to satisfy the needs of even lrw. But I will grant you
that this is not the strongest aspect of my system so far.
> All of the
> tricks Simon proposes are variations of old ideas.
They are often the best. That they did not work out in the
conventional setting of cryptography is not proof that they
won't in the new environment Braided Streams provide.
> 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.
You are confusing a book, the text of which educated guesses
can be made about, and files containing random garbage, which
you could try to grok out until you are blue in the face.
> Like most amatuer crypto-
> graphers, Simon has no appreciation for the power of statistics, or for the
The implication of your words is that you are not an amateur,
in which case I suggest you use the tools available to you
to put the idea to the test.
> 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.)
|8-) It is one area where the side effects of the braid shine.
The more traffic, the more confusion because every bit of traffic
adds to the incertitude. And the ciphertext being longer (by
an amount that varies according to the statistical profile of
the key) than the plaintext, this is HARD work for the opposition.
> 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.
You are really trying not to see, aren't you? If I use XOR
I have no way to renew my coorrespondant key. If I keep using
the same key over and over, it will eventually get cracked.
Of course, without the benefit of braiding, the known plaintext
attack would work. Finally, the cherry on the sundae, with
braided streams, I think that you could get away with far
sloppier key generation technics.
> Its use in "braiding" MAY spread its
> information around, but then again it may not. Proving such things is quite
> difficult.
It spreads information around. That's one big feature.
The other way of saying this is that it dilutes it, the
cryptographer has less of a handle on things.
> Simon makes snide remarks about there not being any mathematics
> 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 tanta-
> mount 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 dis-
> honest.
I just don't follow you... you obviously are upset about
something. I clearly said that a few points needed proof
(the formal kind) which I could not provide. I was not
playing mind games with the readers. You are quick in
lending me motives and intents. Now I am wondering about
YOUR honesty. What's your agenda here?
> 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
Some great people have said a number of equally self serving
things in the past. I try to avoid adopting this kind of
inbred thinking.
> 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....
I wonder why, then, you are so upset about it. One doesn't
spend so much time, energy and venom dismissing something
so obviously contemptible.
> -- Jerry
--
William "Alain" Simon
UUCP: alain@elevia.UUCP