NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/sci/crypt/3035

Internet Message Format | 1992-08-27 | 11.9 KB

Path: sparky!uunet!gatech!ukma!cs.widener.edu!dsinc!ub!acsu.buffalo.edu!ubvmsb.cc.buffalo.edu!v360eakb
From: [e-mail] (cusick)
Newsgroups: sci.crypt
Subject: Re: Multiplexing Ciphers
Keywords: Braided, Mass Encryption
Message-ID: <[e-mail]>
Date: 27 Aug 92 21:16:00 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: University at Buffalo
Lines: 295
News-Software: VAX/VMS VNEWS 1.41
Nntp-Posting-Host: ubvmsb.cc.buffalo.edu

In article <[e-mail]>, [e-mail] (Terry Ritter) writes...
>
>
> Recently, several messages have proposed cipher systems which use
> a multiplexer to combine two (or more) messages, or different parts
> of a single message, to form ciphertext.  When this was proposed
> last year in The Braided Stream Cipher, I posted a long forgotten
> analysis, which I will now revive.  But first:
>
>
> One of the problems we have in cryptology is that our few texts
> do not adequately describe the various techniques and capabilities
> of cryptanalysis, nor the major role cryptanalysis plays in the
> design of new systems.  When new cryptosystems are proposed here,
> we inevitably we end up with "it's obviously strong," "no it's not"
> arguments, ad infinitum.  And almost nobody has the kind of time
> to spare that it would take to develop the techniques to attack
> particular systems and prove weakness.  We rely on the literature
> to guide us, but newbies do not know the literature.
>
> We need to find a different way to handle the discussion of new
> designs, especially newbie designs.  For a start, I would like to
> see more comments and more participation.
>
> Moreover, many academics seem to view stream ciphers merely as
> historical oddities.  Few of the common crypto texts describe them
> otherwise.  Consequently, most any newbie in this field convinces
> his or herself that his or her particular stream cipher is new,
> unique, and obviously impossible to crack.  In reality, this is
> almost always wrong.
>
> But the problem is larger than just stream ciphers:  We need to
> find a way to convey the history of cipher designs and failures,
> even without a good design text to lean on.
>
> Yes, discussions with newbies are time-consuming and often
> irritating.  But everybody is a newbie at least once (indeed, as
> things progress, we may all be newbies many times).  Somehow we
> need to include these people, rather than just ignoring them, or
> running them off.
>
>
> Anyway, my Braided analysis, from a year ago:
>
>
>Article 3606 in sci.crypt:
>Path: cactus.org!ritter
>From: [e-mail] (Terry Ritter)
>Newsgroups: sci.crypt
>
>Subject: The Braided Stream cipher
>Message-ID: <[e-mail]>
>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   [phone]
>
> ---
> Terry Ritter   [e-mail]