Path: cactus.org!milano!cs.utexas.edu!uunet!bonnie.concordia.ca!IRO.UMontreal.
+ CA!matrox!altitude!elevia!alain
From: alain@elevia.UUCP (W.A.Simon)
Newsgroups: sci.crypt
Subject: Re: eating pretzels
Message-ID: <1991Jul15.110725.8635@elevia.UUCP>
Date: 15 Jul 91 11:07:25 GMT
References: <1991Jul2.105754.11804@elevia.UUCP> <218@armltd.uucp>
Organization: The W.A.Simon Wild Life Fund
Lines: 96
In <218@armltd.uucp> dseal@armltd.co.uk (David Seal) writes:
>In article <1991Jul2.105754.11804@elevia.UUCP> alain@elevia.UUCP (W.A.Simon)
>writes:
>>Eating pretzels:
>>I will show that a 2 stream braids is weaker than a simple XOR.
>>If we split a plaintext into two more or less equal parts and braid
>> [ ... ]
>>weaker than flipping bits at random (for each shuffle, there is an XOR
>>that can produce it, but the reverse is not true). So we can safely
>>conclude that a two braid stream is weaker than a XOR.
^^^^^^^^^^^^^^^^^^
I meant a two stream braid |8-)
>No, we can't. For any *particular* data bit string and shuffle, there is an
>XOR bit string which will produce the same result as the shuffle. But there
>is no XOR bit string that will produce the same effect as the shuffle on
>*all* data bit strings of the correct length.
>A simple example: suppose the data bit string is of length 2 and the shuffle
>interchanges the two bits. The shuffle operation is therefore:
> 00 -> 00
> 01 -> 10
> [ ... ]
>to have the right effect on 00 and 11, the XOR string would have to be 00,
>but to have the right effect on 01 and 10, it would have to be 11.
You are essentially saying the same thing as I am. It takes
a larger key space to achieve the same result, with a XOR.
However, with a XOR, I can obtain results you can't achieve
with a shuffle. The most simple way to illustrate it is
to talk about parity conservation. I can XOR a string into ANY
other string, but a shuffle can only reach certain configurations.
>This assumes you mean a data-independent XOR string when you talk about
>XORs, as most people do. If you are claiming that braided streams are weaker
>than a data-dependent XOR, you're right, but this is not a very useful
>concept: *any* system that preserves the total length of the data is
>equivalent to some data-dependent XOR, and so is weaker than a totally
>generic data-dependent XOR...
I am not quite certain what you mean by data dependant and
how it is relevant to this discourse.
I assume my keys are random, and never use more than once.
I also believe I made that point before that ANY system
that preserve the length of the plaintext is equivalent
to some XOR with some key. I was not trying to prove this
fact again, just refresh the memory of those who are not
necessarily eating ciphers for breakfast. The usefulness
was in putting the simple braid in perspective, and show
that it was quite a bit weaker (which some of us did not
take for granted).
In retrospect, it is rather obvious, you are right. Because
of its other features, it had been difficult to compare to
a XOR. I used the part you quoted as a way to do so (find
a common ground).
>[ ... ]
>With regard to the problem of how strong "braided streams" are: most of your
>arguments so far have been along the lines of "look at the huge number of
>possibilities that the cryptanalyst has to cope with - how does (s)he ever
>get anywhere?". The trouble with such arguments is that they can be applied
>to most encryption techniques, including many that have been broken. It is
>*very* difficult indeed to produce any arguments about every possible
>approach to cracking an encryption - e.g. note that no real proof is known
>that factorisation of integers is fundamentally difficult and thus that RSA
>is secure, despite the fact that RSA encryption is particularly simple to
>state mathematically.
I believe I said something quite different. I was using this
very same point to discount RSA and DES. The braid has some
other benefits. Actually I should not call it the braid. The
braid is just a convenient application of what is the really
strong concept: the addition of a random length of random material
to the plaintext. This has the interesting consequence that
even if you come up with a solution, through exhaustive search,
or known plaintext attack, you can't know that it is the right one.
>What I would suggest you do is implement braided streams, with a key
>management system that is as good as you can make it, then issue a
>challenge: you will make the source code available (i.e. both the braided
> [ ... ]
>Then offer a small prize to anyone who provides you with the plaintext.
>Possibly make the prize conditional on them telling you how they got it -
>that way you get feedback on the weaknesses of your system.
And if nobody comes up with a valid solution, we have only
proven that nobody came up with a valid solution. We are
no better off interms of proof. I'd much rather use logic
and thought experiments to make the proof, for or against.
>David Seal
RSA is a sitting duck waiting to be shot by a better brain with a faster CPU
--
William "Alain" Simon alain@elevia.UUCP
Frank Zappa for President of the United States of North America!