Path: cactus.org!milano!cs.utexas.edu!qt.cs.utexas.edu!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: A good attack on braids
Message-ID: <1991Jun28.134354.9485@elevia.UUCP>
Date: 28 Jun 91 13:43:54 GMT
References: <1991Jun26.171120.3653@elevia.UUCP> <1991Jun26.222753.1543@agate.
+           berkeley.edu>  <1991Jun27.200445.
+           9692@agate.berkeley.edu>
Organization: The Electronic Path - Global Village
Lines: 78

In <1991Jun27.200445.9692@agate.berkeley.edu> shirriff@sprite.berkeley.edu
(Ken Shirriff) writes:
In article  a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
writes:
>>I think braiding is a little better than Xor for text; probably no worse for
>>most inputs.  I don't actually have any evidence for this, but, I have much
>>experience in information theory, and it seems reasonable.
> [ ... ]
>are braided and the result is 00001010...  From this we know that at least
>one stream starts with at least two zeros.  Thus, the results of braiding
>gives you information,
> [ ... ]

	This is a good way to attack the braid.  But when I tried it myself,
	during the design stages, I found out that beyond the first two bits,
	you can't really pursue this line of reasonning.  After the first
	two bits, you can make guesses and each additional bit multiplies
	the odds against your finding out more certitudes.

	But even this little bit of info, given away at the start of
	the braid, bothered me.  There should be no handle whatsoever.
	So I tried to come up with a way to remove this knowledge.

	The idea of using the first two bits of the key to decide how many
	bits would be used to decide on how many streams would be braided
	together was what I found.  This removes even the little knowledge
	you had with a braid of two streams only.  And it added a lot of
	extra security in many other areas.  Here is (again) how it works:

	If the first two bits of the key are "10" (2) then, from now on,
	the key will be treated as a stream of 2 bit chuncks, meaning I
	will be braiding 4 streams together.  Since you don't know how
	many streams I am actually braiding (it is under key control),
	the attack you offer can't even guess as much as before.  The
	conclusions you draw become "there is a possibility that at least
	one stream... but there are a number of other possibilities which
	say that... ", instead of "we know that...".

>I ran some experiments to calculate the entropy of receiving various
>braids, to find out how much information braiding lets through, assuming
>a uniform distribution of keys.  (From the received braided string,
>I calculated the probabilities of all possible input strings and plugged
>them into the entropy equation, to find out how much information we received.)
>[ ... ]
>So (at least in the first 8 bits), braiding lets about half the information
>through.  Thus, it seems clear to me that braiding is a bad idea.

	These calculations are based on two erroneous assumptions:
	    a) there are only two streams in the braid.
	    b) you can pursue your reasonning beyond the first two bits.

	I like this line of attack.  If the two stream braid is to be
	cracked, I believe that's more or less how it will be done.
	But you have not really proven it yet.  I still can't foresee
	a valid attack on the n stream braid.

>                       while the result of xor doesn't.

	XOR wouldn't give you that much information of that kind,
	but for what it's worth, that's not really important.  And
	it is so weak against a known plaintext attack... up to a
	point, it is just as weak in the face of educated guesses
	and the various routine searches for patterns.

	I must remind you of four very interesting features of braids,
	which put them way above XOR:

	   - they introduce incertitude as to the length of the message,
	   - multiple passes add security at every iteration,
	   - they cater to wishful thinking (any PT can be extracted),
	   - they allow for secure key management.

	As pointed out a number of times by the few experts around here,
	"who cares about yet another scrambler, what we need is secure
	key management".

>Ken Shirriff			shirriff@sprite.Berkeley.EDU
-- 
William "Alain" Simon
                                                   UUCP: alain@elevia.UUCP