NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/crypt/2930

Text File | 1992-08-17 | 11.2 KB | 306 lines

Newsgroups: sci.crypt
Path: sparky!uunet!cs.utexas.edu!milano!cactus.org!ritter
From: [e-mail] (Terry Ritter)
Subject: Multiplexing Ciphers
Message-ID: <[e-mail]>
Keywords: Braided, Mass Encryption
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
Date: Tue, 18 Aug 1992 05:46:00 GMT
Lines: 295



 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]