+     mcsun!ukc!acorn!armltd!dseal
From: (David Seal)
Newsgroups: sci.crypt

Subject: Re: eating pretzels
Message-ID: <218@armltd.uucp>
Date: 12 Jul 91 16:46:12 GMT
References: <1991Jul2.105754.11804@elevia.UUCP>
Sender: dseal@armltd.uucp
Distribution: sci
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK
Lines: 83

In article <1991Jul2.105754.11804@elevia.UUCP> alain@elevia.UUCP (W.A.Simon)

>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
>them together, we have in effect done a transposition.  A braid is a
>particular case of the more general random shuffle.  This is a shuffle
>that has constraints on the valid keys that can be used to randomize
>the order of the bits.  We are working with a reduced key space.
>Therefore, the two stream braid is weaker than the unconstrained shuffle
>or transposition.  But we know that moving bits around at random is
>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.

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
  10 -> 01
  11 -> 11

It is easy to establish that no XOR bit string will have the same effect -
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.

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

[ Aside: this might lead one to think of using a totally generic
  data-dependent XOR in practice. This doesn't work - the amount of key
  information required grows exponentially with the size of the message you
  want to send and very quickly becomes astronomical!

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.

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
streams and the key management code), but not the initial value of the key
information. You will also make some encrypted text available, of length at
least several times that of the key information (this is necessary to make
the challenge fair - if cryptanalysts are not going to see this amount of
encrypted text in practice, the "one time pad" solution is just as feasible
and provably secure).

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.

It might also be worth making a second similarly sized chunk of encrypted
text available, together with a statement of what the first few thousand
bytes of plaintext are. This would test your technique against "known
plaintext" attacks.

David Seal
I believe the "From" line problem here has been fixed now. In case it isn't,
my correct email address is "".

All opinions are mine only...