Path: cactus.org!milano!uudell!chinacat!sequoia!execu!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: <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) writes: >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 "dseal@armltd.co.uk". All opinions are mine only...