Path: cactus.org!milano!cs.utexas.edu!uunet!mcsun!ukc!acorn!armltd!dseal
From: dseal@armltd.co.uk (David Seal)
Newsgroups: sci.crypt

Subject: Re: eating pretzels
Message-ID: <220@armltd.uucp>
Date: 17 Jul 91 23:49:37 GMT
References: <1991Jul15.110725.8635@elevia.UUCP>
Sender: dseal@armltd.uucp
Distribution: sci
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK
Lines: 73

In article <1991Jul15.110725.8635@elevia.UUCP> alain@elevia.UUCP (W.A.Simon)
writes:

>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:
>>>...  So we can safely conclude that a two braid stream is weaker than a XOR.
>>
>>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'd have thought that it was pretty clear. A data-dependent XOR is one where
the value that you XOR with depends on the data being encrypted. A
data-independent XOR is one where the value that you XOR with does not
depend on this data.

Now for the reason that it is relevant to this discourse:

  Data-independent XORs are not a subset of shuffles. Proof: Consider the
    data-independent XOR of XORing all bits with 1. This swaps the number of
    0's and 1's in the stream, which a shuffle cannot possibly do in the
    general case.

  Shuffles are not a subset of data-independent XORs. Proof: look at the
    simple "swap two bits" example I gave above. The XOR value would have to
    depend on the data.

  Data-independent XORs are known to be easy to decrypt if the text is
    sufficiently longer than the key. (If the key is longer than the text,
    we can have a one-way pad, which is provably secure.) If we could
    conclude that shuffles, and hence braided streams, were weaker than
    data-independent XORs, we would be able to draw conclusions about their
    cryptographic strength. But we cannot conclude this.

  Shuffles *are* provably no stronger than data-dependent XORs. But this is
    a pointless remark: it can be made about *any* system that preserves the
    length of the text. (For any such system, you find the data-dependent
    XOR key for a particular plaintext by taking (plaintext XOR ciphertext.)
    And (as you discovered about braided streams) when looked at correctly,
    most systems preserve the length of the text. The only conclusion we can
    draw about braided streams is that they are no stronger than an almost
    completely general encryption - hardly surprising, since braided streams
    are an encryption...

  Your original argument about braided streams being weaker than XORs did
    not make it too clear whether you thought the XOR was data-independent
    or not. If you thought it was data-independent, your "proof" is wrong.
    If you thought it was data-dependent, your proof is correct, but its