+     rpi!!!!
+     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 
> 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

	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