Path: cactus.org!ritter From: ritter@cactus.org (Terry Ritter) Newsgroups: sci.crypt Subject: The Braided Stream cipher Message-ID: <8300@cactus.org> Date: 24 Jul 91 05:37:40 GMT Organization: Capital Area Central Texas Unix Society, Austin, TX Lines: 237 Definition: The Braided Stream cipher, described by William Simon, consists of a cryptographic combiner and a key stream: * The combiner is a data multiplexer, which takes a single bit from one of multiple data channels. The unselected channels do not advance, and their data bits remain ready until selected. * There are at least two data channels. One or more of the channels may be a random key stream for confusion purposes. * The original key stream is supposed to be really random. Claimed Advantages: * "simple," "fast," "high levels of confidence" * "key management is inherent in the design" * "not vulnerable to progress in mathematics or computational technologies" Some Implications: * The original key may be "really random." But, if so, then we might as well use that key with XOR and get the provably-secure one-time pad. * ANY secure cipher can also handle "key management" data simply by enciphering it as a message. The reason this is not done is that the cipher key may have been "obtained," and the plaintext may be fully exposed, INDEPENDENT of the security of the cipher itself. Shipping key material under these conditions will just assure that the cipher will continue to be insecure. Key management is not a special feature of this particular cipher. * Key material which is reused, even in a complex way, is no longer "really random," and thus may, at least potentially, be broken. * For the one-data one-confusion system, if the key stream has a balanced distribution, the ciphertext expansion will be 100% (or the data rate will be reduced to 50% of the unenciphered rate). In contrast, a one-time pad does not expand the ciphertext at all. * Dynamically, any particular data channel may run fast (and thus be less hidden and more exposed) or slow (for an even slower data rate). Transiently, one channel may be selected repeatedly, and thus have no protection at all. Clearly, at some point, a "less hidden" message will become recoverable. Cryptanalysis of the two-channel system could proceed from the standpoint that the message is passing through a noisy channel. In this peculiar kind of noisy channel, data bits are not lost, but an arbitrary number of arbitrary confusion bits may separate data bits. Thus, any statistics in the plaintext are not lost, but merely "mellowed out" by intervening confusion data. Analysis If we are to avoid analyzing EVERY POSSIBLE configuration, we must pick one and stay with it. The weakest system may be the two-channel scheme. We choose the weakest system to analyze in the hopes that it may help us learn to attack a stronger system. The obvious way to analyze the system is to analyze its component parts. Because "key management" can be applied to any stream cipher, its analysis is irrelevant to the strength of this particular cipher. Moreover, the original key is supposed to be "really random," and no precise technique has been described for the extension of that key, so no precise analysis can be applied. Thus, we are left with the combiner: Combiner Characteristics Stream cipher combiners have been one of the major research topics in the past decade [4,5,7], although most of those in the literature are non- reversible. Such combiners mix multiple LFSR sequences and yield a resulting sequence with large linear complexity, in which the input sequences are statistically independent of the output. Statistical independence can be measured by taking the Walsh transform of the combiner output for every possible input value [5]. But for simple combiners, it is probably easier to analyze every possible case by hand: The Exclusive-OR Combiner: Invented by a cryptographic novice, using electro-mechanical relays (and without mention of "additive" or "mod 2" or "finite fields" or "Boolean logic"), exclusive-OR is the conventional stream cipher combiner. It is also directly susceptible to "known plaintext" or "probable word" attacks. A ---)\ - - )X)--- Z Z = AB + AB B ---)/ A B Z A=Z B=Z 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 --- --- --- 50% 50% 50% Note that exclusive-OR produces a balanced result. Moreover, for any given output, neither input has a preferred value. The Geffe Combiner: First described in a popular industry magazine [1], the Geffe combiner was intended to combine three LFSR's into a complex confusion sequence. One LFSR was used solely to select between two other LFSR's. Because this combining function is nonlinear, it took a long time to be deeply understood. Note that the Geffe combiner is actually a multiplexer. A ------|\ |&)--+ +--|/ +--)\ - IF C THEN C ---+ )+)--- Z Z = AC + BC or Z := A +-o|\ +--)/ ELSE |&)--+ Z := B; B ------|/ A B C Z A=Z B=Z C=Z 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 --- --- --- --- 50% 75% 75% 50% The Geffe combiner also produces a balanced result (for balanced input sequences). But whatever the output value Z, the probability is 75% that input A has that same value, and the same can be said for B. This fact was finally used to break the system. Correlation Attacks Siegenthaler [5] reasoned that, when a combiner has inputs which are correlated to the output value, it might be possible to attack each input separately with a statistical attack. We might choose to view this as a sort of biased "brute force" attack, but, given a 75% probability that the output is also the desired input, we clearly know where to start. Then, only about 25% of our decisions will be wrong, and if we are breaking a LFSR, we will soon be able to tell if we have taken the wrong path. Thus, Geffe was broken. Note that this attack is independent of the characteristics of the confusion sequence, so that various possible attempts to "hide" or "improve" the sequence are simply irrelevant. The Braided Stream Combiner: Proposed as a "simple and fast system which allows for high levels of confidence without having recourse to weak, dubious, or controlled technologies," the Braided Stream combiner is in fact a simple multiplexer. It is, therefore, exactly the same mechanism which was broken by Siegenthaler. A ---* - IF C THEN ----*--- Z Z = AC + BC or Z := A B ---* ELSE ^ Z := B; | C ------+ Now, obviously, Siegenthaler was working with LFSR's, and these mechanisms can be attacked efficiently. In contrast, the Braided Stream system works on streams of data. Certainly it could be argued that these two situations are different, and that must affect the analysis. Moreover, there could be 4 streams or more, most could be noise, so on and so forth. But to the extent that each of the streams carry identifiable statistics, those streams become susceptible to some sort of correlation attack. Can we ever hope to guarantee that different channels will have similar statistics? And if we must pre-process the data to obtain this situation, then why bother with this combiner? References [1] Geffe, P. 1973. How to protect data with ciphers that are really hard to break. Electronics. Jan 4. 99-101. [2] Meier, W. & O. Staffelbach. 1988. Fast Correlation Attacks on Stream Ciphers. Advances in Cryptology: EUROCRYPT '88 Proceedings. 301 - 314. Springer-Verlag. [3] Mund, S. D. Gollman & T. Beth. 1987. Some Remarks on the Cross Correlation Analysis of Pseudo Random Generators. Advances in Cryptology: EUROCRYPT '87 Proceedings. 25-35. Springer-Verlag. [4] Rueppel, R. 1985. Correlation Immunity and the Summation Generator. Advances in Cryptology: CRYPTO '85 Proceedings. 260-272. Springer- Verlag. [5] Rueppel, R. 1986. Analysis and Design of Stream Ciphers. Springer-Verlag. [6] Siegenthaler, T. 1985. Decrypting a Class of Stream Ciphers Using Ciphertext Only. IEEE Transactions on Computers. C-34(1): 81-85. [7] Siegenthaler, T. 1986. Design of Combiners to Prevent Divide and Conquer Attacks. Advances in Cryptology: CRYPTO '85 Proceedings. Springer-Verlag. --- Terry Ritter cs.utexas.edu!cactus.org!ritter (512) 892-0494