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...