Path: cactus.org!milano!cs.utexas.edu!usc!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: Re: eating pretzels Message-ID: <1991Jul21.133354.9428@elevia.UUCP> Date: 21 Jul 91 13:33:54 GMT References: <1991Jul15.110725.8635@elevia.UUCP> <220@armltd.uucp> Organization: The Electronic Path - Global Village Lines: 58 In <220@armltd.uucp> dseal@armltd.co.uk (David Seal) writes: > 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: >>>> [ ... ] >>> [ ... 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. In a real life cryptographic sesssion, why would anyone use anything else than a fully random key to XOR the plaintext with? This qualifies as data independant. My choice of data dependant XOR keys is for the purpose of analysis only. > 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. OK, so it would seem that a XOR can do more... but that was the conclusion all along anyway. > 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. For any shuffle you care to effect on a string, there is a XOR that will achieve the same result. I don't see that you have proven otherwise. I am not proposing to use specialy picked key material in order to make a XOR behave like a shuffle, I am just saying there exists a XOR that will do what the shuffle does. > 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 Our premises were, all along, that infinite length one-time pads are being used... > 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. I have shown that (to use your vocable) there is a data dependant XOR that will achieve the same result as the braid or the shuffle. We can safely assume that a data independant XOR will be stronger. In my own choice of vocabulary, the notion of data dependancy came out as "constrained key space". > [ ... ] -- William "Alain" Simon alain@elevia.UUCP