Path: utzoo!telecom-request Date: Sat, 22 Jun 91 10:01:36 EDT From: Jerry Leichter Newsgroups: comp.dcom.telecom Subject: Re: SPECIAL REPORT: Braided Streams Message-ID: Organization: TELECOM Digest Sender: Telecom@eecs.nwu.edu Approved: Telecom@eecs.nwu.edu X-Submissions-To: telecom@eecs.nwu.edu X-Administrivia-To: telecom-request@eecs.nwu.edu X-Telecom-Digest: Volume 11, Issue 479, Message 1 of 8 Lines: 100 TELECOM Digest recently published a special issue containing an article by W.A. Simon on his proposal for an encryption technique known as Braided Streams. Simon makes all sorts of very strong claims for this technique. Given the way it was published, readers might get the impression that they are looking at a breakthrough in cryptography. Nothing could be further from the truth. There is little really new in what Simon proposes -- in fact, there is little there at all. And what IS new is cryptographically quite weak. Let's consider Simon's basic "1bm" system. In this system, we start with a plaintext bitstream P[0,1,...] and a random key bitstream K[0, 1,,...]. We assume that both ends initially know K[0,k-1]. At time t (starting at 0) we inspect K[t]. If K[t] is 0, the next bit sent in the encrypted bitstream E[0,1,...] is the next bit of P, initially 0; if K[t] is 1, the next bit sent is the next bit of P, initially k. Thus, the new key material is sent along with the data in the stream. How might we cryptanalyze such a system? Actually, it's trivial. We first of all assume a known plaintext. This is a common assumption in cryptography because experience shows that (a) eventually, a known plaintext/encrypted message text will end up in the hands of the cryptanalyst; (b) even if the cryptanalyst doesn't know the exact plaintext, he can usually guess at pieces that are highly likely to be there; (c) even without successful guesses as to the exact contents of the plaintext, statistical information will often yield the same results. So let's start off by guessing that the first bit of the key, K[0] is 0. Hence, E[0] should be P[0]. If this DOESN'T match, we know K[0] is in fact 1. If it DOES match, we have a 50-50 chance that the match is fortuitous - after all, even if E[0] is really a key bit, half the time it will match the plaintext. To eliminate that possibility, we need to guess more bits of the key. As we go along, we learn more bits of the key -- every time we learn for certain that key bit was 1, we look ahead to the corresponding position (or positions, if there are any earlier ambiguities) and repeat the process. This gets rapidly difficult to describe, but it converges rapidly. The basic cause is simple: Each output bit depends on only one key bit and one plaintext bit. There is also a second-order dependence on the number of previous 1 bits in the key, which determines WHICH single key or plaintext bit it is; but for n bits of key, there are only log n possible values for the count of previous bits. Normally, we want the cryptanalyst to be faced with an exponential explosion; but no such explosion occurs here! Simon goes on to various elaborations, in particular using multiple key bits to select one of many input streams. As he himself notes, this will exhaust the key stream rapidly. So he has to fall back on various tricks for expanding the key stream. He won't pin himself down to any one technique -- he lets the client choose. This is pointless: Cryptographers always assumes that the opponent knows EVERYTHING about the system except for the key; again because history has shown that that's the only safe assumption. All of the tricks Simon proposes are variations of old ideas. For example, the use of some commonly-known (but non-random) file is the same as using a multi-alpha- betic cipher, with the particular cipher based on successive letters in some book known to both sender and receiver. This variation was broken many, many years ago -- WITHOUT knowledge of the common book. Like most amatuer cryptographers, Simon has no appreciation for the power of statistics, or for the truely massive amounts of intercepted data available to a cryptanalyst in the situations cryptographers actually worry about. If all you are ever going to transmit is, say, a couple of thousand bytes of data, there are plenty of simple cryptographic techniques that are, in practice, quite secure. Once you start sending megabytes, it's a whole other story. (And, of course, since Simon is proposing this as a cryptographic technique to be used by sellers of network services, there are quickly going to be tens and hundreds of megabytes of data to work with.) In any case, if Simon's tricks for key expansion are secure, there is no reason to use the elaborate "braiding" technique, especially since it expands the message considerably. Instead, just XOR the expanded key with the plain text. If the expanded key really is secure, then this encryption is also secure; conversely, if this encryption can be broken, then the expanded key wasn't really secure to begin with. Its use in "braiding" MAY spread its information around, but then again it may not. Proving such things is quite difficult. Simon makes snide remarks about there not being any mathematics in his writing (which is obviously correct). He then proceeds to make a number of claims, followed by parenthetical "to be proven" remarks. Some of his claims are clearly false as stated, and others, if true, would be VERY hard to prove. Asserting that something is "to be proven" in such a context is tantamount to a claim that you pretty much know how to prove it -- you just haven't worked out the details. Making such claims as Simon does is just plain dishonest. I don't remember which cryptographer first stated that he would never accept a new cryptosystem from anyone who had not already broken a strong one, but this is (in some form) generally accepted in the cryptographic community. I see no reason to believe Simon has done anything of the sort, or in fact that he knows anything in particular about cryptography. He's of course welcome to suggest anything he likes, but if anyone relies on his techniques without a GREAT deal of additional work -- well, I've got this bridge available.... Jerry