From: ritter@cactus.org (Terry Ritter)
Subject: A Modest Network Cipher
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
Date: Tue, 12 Jan 1993 09:30:41 GMT


 A Modest Network Cipher with Interesting Properties


 The Problem

 Consider a need to software-encipher arbitrary-length data packets
 within an existing network *without* adding *any* additional data
 to the packets.


 Approaches

 In this application, a block cipher is considered too slow, and
 would require data buffering and frequent short-block padding.

 Instead consider a stream cipher consisting of two modules: a
 "confusion" source, and a data/confusion "combiner."  A stream
 cipher can be fast, and will eliminate buffering and padding.


 The Stab-in-the-Back

 In this network, at the bottom level, there is not enough
 information (or perhaps it takes too long) to identify individual
 connections or data streams.  Each packet must, therefore, be
 enciphered independently.  (This is a customer decision.)  Recall
 also that there is no room for a message key at this level; thus
 the same confusion sequence will be used for each packet.  (Ugh!)

 In a conventional stream cipher design, with an exclusive-OR
 combiner, the result would have an immediate and direct
 susceptibility to known-plaintext attack.  In my opinion, such
 a cipher would be essentially worthless.  (I might add that the
 network designers and technical managers might think that the
 crypto design looks like enough of an improvement (over no
 encryption) to actually implement.)


 The Response

 Now consider the same design but with a Dynamic Substitution
 combiner [1,2] instead of exclusive-OR:

      [ Basically, Dynamic Substitution can be thought of as Simple
      (or polyalphabetic) Substitution where the content of the
      substitution table(s) changes while ciphering.

      Typically, the table is permuted slightly after every
      substitution operation (an inverse table is also permuted
      during deciphering).

      Usually, the permutation is an exchange of the just-used
      substitution element, with some element selected by the
      confusion sequence. ]

 The content of the DynSub tables will be reset for each packet,
 and the same sequence used for ciphering.  Identical messages
 will produce identical output up to the first different byte.
 Early different bytes will generally produce three table-entry
 differences between the two similar messages; subsequent bytes
 which use those entries will produce different ciphertext.

 In general, it would seem to be difficult for the opponent to
 identify either the repeatedly-used confusion sequence, or to
 construct the state of the DynSub tables at any time.  As far
 as I can tell, the resulting cipher has some worth as a modest
 network cipher.


 The Result

 Within the context (that is, the tremendous limitations) of the
 above design, the Dynamic Substitution combiner seems to provide
 a significant level of security where exclusive-OR gave none.
 While *I* would not *normally* consider such a design, it is
 interesting in that the reasons for the given constraints are
 fairly obvious, as are the motives for building such a system.
 It is also interesting that *anything* could help out in this
 (frustrating) crypto situation.


 [1]  Ritter, T.  1990.  Substitution Cipher with Pseudo-Random
      Shuffling: The Dynamic Substitution Combiner.  Cryptologia.
      14(4): 289-303.  (October)

 [2]  Ritter, T.  1990.  Dynamic Substitution Combiner and
      Extractor.  U.S. Patent 4,979,832, issued Dec. 25, 1990.

 ---
 Terry Ritter   ritter@cactus.org

Newsgroups: sci.crypt