Path: cactus.org!milano!radar!cs.utexas.edu!sun-barr!olivea!samsung!uunet! + mcsun!ukc!acorn!armltd!dseal From: dseal@armltd.co.uk (David Seal) Newsgroups: sci.crypt Subject: Re: eating pretzels Message-ID: <223@armltd.uucp> Date: 23 Jul 91 15:49:16 GMT References: <1991Jul21.133354.9428@elevia.UUCP> Sender: dseal@armltd.uucp Distribution: sci Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK Lines: 164 In article <1991Jul21.133354.9428@elevia.UUCP> alain@elevia.UUCP (W.A.Simon) writes: > 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. Because XORing with a fully random key is the "one time pad" system, and suffers from a well-known problem: you've first got to get the key to the recipient. The key is just as long as the message, so getting it to the recipient is just as hard and long a job as sending the message you really want to send. The only times it is useful are when you've got a good opportunity to transmit the pad securely before it is known what the message is - e.g. you send a spy out with a one time pad, he does his spying and transmits the results back. It depends on having been able to give the one time pad to the spy ahead of time in a secure environment. Furthermore, he'd better not want to send back more results than he has pad text available... More generally useful encryption systems use a key that is considerably shorter than the text - usually a fixed length key which is independent of how much text will actually be sent. This makes it more generally useful in practice: you can use some secure mechanism to send the key, then send as much text as you like through the resulting encrypted channel. Your Braided Streams approach is a mixture: you use one of the streams to transmit random data. But this random data has to be expanded into a longer bitstream in a deterministic fashion by the decrypter, and the result of doing this is guaranteed NOT to be random. (To see this, suppose you've transmitted M bits, and the decrypter has expanded them into N bits, where N > M. To be properly random, each of the 2^N possible streams of N bits must be an equally likely result of this expansion. But the expander only has 2^M possible bitstreams to work from, and has to be deterministic (otherwise the decryption program cannot possibly work!), so can only produce 2^M of the 2^N possible streams of N bits. Since 2^M < 2^N, they cannot all be equally likely. >[quoting me] >> 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. No - we can only conclude that there are things an XOR can do that a shuffle cannot, not that it can do "more". BUT there are also things a shuffle can do that a data-independent XOR cannot, as I argue next. >> 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. I think that something you're missing is that an encryption is a transformation, and transformations are specified by means of their behaviour on all possible inputs, not just on one of them. For instance, to specify the "swap two bits" transformation, it is not sufficient to say that it takes 01 to 10. You've got to specify a full table: 00 -> 00 01 -> 10 10 -> 01 11 -> 11 Or, more succinctly, you can say "it swaps a pair of bits" or "it takes XY to YX". But you have to say how it works on every possible input. Now look at the possible data-independent XORs. They are the following transformations: XOR with 00 XOR with 01 XOR with 10 XOR with 11 00 -> 00 00 -> 01 00 -> 10 00 -> 11 01 -> 01 01 -> 00 01 -> 11 01 -> 10 10 -> 10 10 -> 11 10 -> 00 10 -> 01 11 -> 11 11 -> 10 11 -> 01 11 -> 00 None of these produce the same results as the "swap two bits" transformation for all possible inputs. So none of them are the same transformation as "swap two bits" - i.e. even this very simple shuffle is not equivalent to a data-independent XOR. What it is equivalent to is the data-dependent XOR "XOR with 00 if the two data bits are the same, with 11 if the two data bits are different". But I repeat: (a) it is thoroughly uninteresting that a particular encryption is equivalent to a data-dependent XOR - all it means is that the encryption preserves the length of the data; (b) when people talk about "XOR encryption", they normally mean data-independent XORing. >> 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... No, they are not! The premise is that we will transmit a random bitstream which will be expanded in some way before being used. As observed above, this expansion means that the bitstream we actually use is definitely NOT random. This means that there is definitely a pattern of some sort in the expanded bitstream: my guess is that the security of your system will depend on how easy it is to exploit these patterns. >> 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. No, we can not! Data-independent XORing is a subclass of data-dependent XORing, and so cannot be stronger than it. Any encryption method you care to name that preserves the combined length of its inputs is a subclass of data-dependent XORing. Data-dependent XORing is IMHO not an interesting concept - it's too general and might just as well be called "arbitrary encryption". > In my own choice of vocabulary, the notion of data dependancy came > out as "constrained key space". It looks as if you have totally missed what I mean by "data dependency", since it has nothing whatsoever to do with "constrained key space"... To summarise my comments in this message and the last: (a) Your argument that BS is no stronger than XORing, by what appears to be your definition of "XOR encryption", is correct but uninteresting - you might just as well have made the obvious remark that it is no stronger than encryption in general. (b) Your argument that BS is no stronger than XORing, by the usual definition of "XOR encryption", is fallacious because you don't take account of the fact that the required XOR value is different for different plaintexts. (c) Although no expert, I quite like the general idea of BS. Its weakest spot would appear to me to be the expansion of the random information transmitted on the "key stream" into the longer bitstream required by the decrypter. It seems clear to me that some expansion schemes are highly vulnerable - as I believe I said before, if I can safely predict from an examination of your code that the binary expansions of N! (especially for largish N) will frequently appear in the expanded stream, all I've got to do is scan along the ciphertext for places where these binary expansions produce sensible plaintext. Anyway, I'd be interested in further discussion about how you propose to expand the key stream. I'm afraid I've said just about all I can about why your "BS is weaker than XORing" argument is wrong, and do not propose to comment further on it. David Seal I believe the "From" line problem here has been fixed now. In case it isn't, my correct email address is "dseal@armltd.co.uk". All opinions are mine only...