Dynamic Substitution in Stream Cipher Cryptography (original) (raw)

A Reversible Nonlinear Combiner with Internal State

ACiphers By Ritter Page

Terry Ritter

Dynamic Substitution is a replacement for the weak exclusive-ORcombiner normally used instream ciphers. Dynamic Substitution is generally nonlinear, with substantial internal state. Multiple nonlinear combining levels are practical, as are selections among multiple different combiners. The resulting strength can support the use of weaker but faster keying generators. Additional strength is available in "hardened" and customized versions.

Contents

• Introduction
• Structure
  Substitution Tables, Changes Controller
• Operation
  Enciphering, Deciphering
• Design Opportunities
  Use Modern VLSI Strengths, Make Each Combiner Unique, Use Nonlinear Combiners, Use Multiple Combiners in Sequence, Use a Dynamic Selection Among Multiple Combiners
• Negatives
  Size, Speed, Error-Expansion
• Strength
  Indisputably Stronger than Exclusive-OR,Known Plaintext Attack,Defined Plaintext Attack
• Hardening Dynamic Substitution
  Customization Opportunities
• Summary
• Acknowledgments

Introduction

Dynamic Substitution is a reversible nonlinearcombiner based onsubstitution.

A combiner is a cryptographic mechanism which mixes a confusion or keying sequence with data. A combiner is the heart of a stream cipher, which generally uses an "additive" combiner such as exclusive-OR.

Unfortunately, additive combiners have absolutely no strength at all: If an Opponent somehow comes up with some plaintext and matching ciphertext, an additive combiner immediately reveals the confusion sequence. This allows the Opponent to begin work on breaking the confusion sequence generator.

In a similarknown-plaintextsituation, Dynamic Substitution hides the confusion sequence (to some extent). This strengthens the cipher and allows the use of a weaker (and faster) confusion sequence generator.

The sources of the Dynamic Substitution idea were:

• a need to improve the strength of a conventional stream cipher, and
• a desire to negate the attacks on simple substitution. Attacks on simple substitution usually contain the implicit assumption that thesubstitution tableis static or unchanging. One way to avoid these attacks is to change the contents of the table dynamically. The signal needed to control these changes makes simple substitution into a new type of combiner, thus solving both problems at once.

Structure

The Dynamic Substitution mechanism consists of one or more invertiblesubstitution tables, and some way to change the arrangement of the values in the tables.

Substitution Tables

An invertible substitution table contains each possible value exactly once. For example, a "byte-wide" table will have 256 byte-value entries. Any entry in the table can be selected by a value in the range 0..255, and every possible substitution value 0..255 will occur exactly once.

Each substitution table is "keyed" orshuffled under the control of akeyed random number generator(RNG). The keying process is very conventional. However, in Dynamic Substitution, a form of shuffling continues during operation, and this is unique.

Changes Controller

One way to "harden"simple substitutionis to re-shuffle the entire table after every character substituted. But what does this gain us? The only entry in the table which can possibly be revealed by a substitution operation is the particular entry which was just used. Accordingly, if we change the table after each substitution, the only entry in the table that we really need to change is the just-used entry.

What do we change the just-used entry to? Well, we want the new entry to be "unknown," that is, an even-probability selection from among all possible values. One way to do this is to use a random numerical value to select some entry in the table. Then we swap the just-used and selected entries (which are occasionally the same).

Operation

In operation, a data character is substituted into ciphertext or a result character. Then the substitution table is permuted. In the usual case, the content of the just-used entry is swapped with the content of some entry selected by a keyed random number stream.

Enciphering

Suppose we have a simple four-element substitution table, initialized as: (D,B,A,C) for addresses A..D. That is, address A contains D, address Bcontains B, and so on. In this way, the table transforms any input value in the range A..D into some output value in the same range. This is classical Simple Substitution.

INITIAL STATE Forward Table --- --- --- --- Table Value | D | B | A | C | --- --- --- --- Table Location A B C D

Data In (DI): C Random In (RI): D

Data Out (DO) = Fwd[DI] = Fwd[C] = A Swap( Fwd[DI], Fwd[RI] ) = Swap( Fwd[C], Fwd[D] )

FINAL STATE Forward Table --- --- --- --- Table Value | D | B | C | A | --- --- --- --- Table Location A B C D

Suppose we have a Data input of C and RNG input ofD: The data value uses location C, which contains the value A; this is the result or "ciphertext." The RNG value selects location D, and then the values in the "used" and "selected" locations are exchanged. This produces the changed table: (D,B,C,A). (This is perhaps the most efficient of many possible forms of Dynamic Substitution.)

In the table, each substitution element changes "at random" whenever it is used, and the more often it is used, the more often it changes. The effect of this is to adaptively "even out" symbol-frequency statistics which are the principle weakness of simple substitution. Also, the elements are changed "behind the scenes" (the exchange is not visible until future data selects one of the exchanged elements), and this tends to hide the confusion sequence.

Deciphering

Dynamic Substitution is deciphered by maintaining an inverse table, and by updating the inverse table dynamically whenever elements in the forward table are exchanged. This generally also requires maintaining a forward table.

Suppose we have the same substitution table we had before:(D,B,A,C). For deciphering we also need the inverse table:(C,B,D,A) which we originally compute from the forward table. We assume that we will have the transmitted ciphertext and also exactly the same RNG value as at the far end. The RNG is initialized from the same key and so produces exactly the same sequence on both ends.

INITIAL STATE Inverse Table Forward Table --- --- --- --- --- --- --- --- Table Value | C | B | D | A | | D | B | A | C | --- --- --- --- --- --- --- --- Table Location A B C D A B C D

Data In (DI): A Random In (RI): D

Data Out (DO) = Inv[DI] = Inv[A] = C Swap( Inv[DI], Inv[Fwd[RI]] ) = Swap( Inv[A], Inv[C] ) Swap( Fwd[Inv[DI]], Fwd[RI] ) = Swap( Fwd[C], Fwd[D] )

FINAL STATE Inverse Table Forward Table --- --- --- --- --- --- --- --- Table Value | D | B | C | A | | D | B | C | A | --- --- --- --- --- --- --- --- Table Location A B C D A B C D

Suppose we have a Ciphertext value of A and RNG input ofD: The ciphertext uses location A in the inverse table, which contains the value C, which is the result or "plaintext": our original value. The RNG selects location Din the forward table, which contains value C. Then we exchange the values in locations A,C (the enciphered data and enciphered RNG values) in the inverse table. Then we exchange the values in locations C,D (the plaintext data and plaintext RNG values) in the forward table, just as occurs during enciphering. This serves to keep both the forward and inverse tables "in sync" with the enciphering system.

The point of this is to minimize the amount of work we have to do to maintain the inverse table (which does the deciphering). The locations to be swapped in the inverse table are the enciphered plaintext and the enciphered RNG value. Now, the enciphered plaintext is just the ciphertext value, which we have, but the enciphered RNG value is something we do not have. Therefore, we also maintain a forward table to encipher the RNG value so we can update the inverse table. This means that the forward table also must be maintained or "kept in sync." The forward table is updated by swapping elements selected by the plaintext and RNG values, which we now have, just as occurs during enciphering.

If we consider a substitution table and changes controller as a single component, we find that one such component can be used to encipher, and two such components can be used to decipher:

The difference between the normal and inverse components is just the arrangement of the substitution table.

Design Opportunities

Dynamic Substitution can be used to replace exclusive-OR combining in stream ciphers. But when we find a component with new properties we also gain new design opportunities:

• Use Modern VLSI Strengths: A Dynamic Substitution table contains substantial internal state; the usual byte-wide combiner uses 256 bytes (and so has 256 factorial possible arrangements). This allows us to make good use of dense on-chip memory, and this is a big advantage over the limited hardware which was available to mid-70's designs. (For example, theCloak2 design uses 17 byte-wide Dynamic Substitution combiners, each having two byte-wide tables. This is a total combiner store of 8704 bytes -- 69632 bits -- which is less than 1/2 of one percent of the store available in a single commonly-used high-production 16Mb dynamic RAM chip.)
• Make Each Combiner Unique: Because a Dynamic Substitution combiner contains internal state which is shuffled upon initialization, each Dynamic Substitution combiner is unique. This means that The Opponent must somehow recover or reproduce the state of each particular Dynamic Substitution combiner. (In contrast, exclusive-OR's have no state, and so provide no uncertainty which The Opponent must analyze, and thus require more strength in some other part of the system.)
• Use Nonlinear Combiners: Because a Dynamic Substitution combiner is shuffled, it is extremely unlikely to be linear, and continued combining operations will re-arrange it in any case. (In contrast, all additive combiners, including exclusive-OR, are absolutely linear.)
• Use Multiple Combiners in Sequence: Because Dynamic Substitution is nonlinear, it is reasonable to use multiple combiners in sequence. That is, by first enciphering in one combiner, and then another, we can force The Opponent to confront_both_ combiners, each of which is separately changing dynamically and differently. (Since exclusive-OR is linear, there is very little advantage to using sequential exclusive-OR's.)
• **Use a Dynamic Selection Among Multiple Combiners:**Because multiple Dynamic Substitution combiners are likely to be very different, it is reasonable to dynamically select among an array of such combiners. For The Opponent, this means that contiguous ciphertext bytes may not have even been processed in the same combiner. (In contrast, all exclusive-OR's are exactly the same, and a selection between identical exclusive-OR's can provide no advantage at all.)

Negatives

Whenever we have a different design, we can expect that some characteristics will be disadvantageous, at least in particular situations:

• Size: Dynamic Substitution requires table storage; exclusive-OR does not. If we assume the usual byte-wide table, and two tables to allow deciphering, we are talking 1/2 KB per combiner. While this could be a substantial amount of store in the special case of some single-chip processors, in most cases, an extra 1/2 K is insignificant.
• Speed: Dynamic Substitution requires an exchange operation; exclusive-OR does not. For deciphering, we need two exchanges per byte deciphered. This implies something like 8 instructions, whereas exclusive-OR needs only one. However, in most cases, 8 simple instructions is a relatively small part of the overall computation, which typically involves reading and writing files. Normally, there is only a modest speed difference between exclusive-OR and Dynamic Substitution combining. And the added strength of Dynamic Substitution might support the use of a simpler and faster confusion generator.
  Dynamic Substitution also requires that tables be shuffled or keyed prior to use; exclusive-OR does not. Usually, though, such "initialization overhead" is a small part of the overall computation.
• Error Expansion: If a ciphertext transmission error occurs, Dynamic Substitution swaps the wrong element, which will affect future parts of the message; exclusive-OR does not. This is a natural consequence of the mechanism which "smoothes out" character-frequency differences in the message. Most modern communications and storage subsystems deliver virtually error-free data (they have their own error-detection and correction subsystems). Where transmission errors do occur, the data stream can be partitioned into small blocks or "lines," and any error confined to within a particular block. (See, for example, the design ofthe Penknife cipher.)

Strength

Dynamic Substitution is indisputably stronger than the exclusive-OR combiner used in most stream ciphers: With exclusive-OR, each byte ofknown-plaintextand associatedciphertext will reveal a byte from theconfusion sequence. In a similar situation, Dynamic Substitution does not directly expose confusion sequence bytes.

But Dynamic Substitution is a tool, and is not by itself a guarantee of unbreakable strength. There are at least two methods for finding confusion sequence values from the basic unhardened design:known-plaintextanddefined-plaintext.

Known Plaintext Attack

One way to deduce confusion values (in a simple system with one non-hardened combiner) is to examine the ciphertext for "close" repeats of the same value. When a ciphertext value repeats, it means that a plaintext value has found where the earlier ciphertext value was moved. This plaintext value is naively the same as the earlier confusion value.

When we use Dynamic Substitution, we expect to find particular ciphertext values separated by about the same number of steps as there are different values. But over this same period there will be about twice as many values moved in the internal table as there are values in that table. This means that repeats of the expected distance often will have moved twice, and so will _not_identify the first confusion value. For this reason, we can use only "close" repeats, and unless the repeats are adjacent, even some of those values will not be the desired confusion value. We might instead use only "adjacent" repeats, but these are much less frequent.

So instead of known confusion values, we normally get_probable_ confusion values, and we find those at random positions in the sequence. Or, if The Opponent has enough known-plaintext and the ability to use widely-spaced values in a solution, perhaps adjacent repeats would be used. Whether or not this is a real weakness depends on various things, including the size and strength of the confusion sequence generator or random number generator (RNG):

• Large RNG: If The Opponent is using _probable_confusion values and the confusion RNG is linear, with a small amount of state, it may be possible to try various sets of confusion values until the system is solved. (Although false values probably will produce some solution, if we run that system long enough a bad set of values should conflict with known ciphertext.) But if the RNG has a large amount of state, selecting a set of correct confusion values from the larger set of probable confusion values by trial-and-error will be very difficult.
• Nonlinear Confusion Sequence: Even if The Opponent has confusion sequence values, it will normally be necessary to_solve_ the RNG system. One technique to complicate this is to use a nonlinear confusion sequence, which should be difficult to solve, even given the correct values. Although nonlinear confusion generators generally have problems, a _linear_sequence can be modified to be nonlinear in a number of ways. These would include discarding random amounts of the sequence at random times, and exclusive-ORing random amounts of the sequence with a random element from the sequence.
• Multi-Level Combining: One technique which virtually eliminates the known-plaintext weakness is to place two combinings in sequence. Although close ciphertext repetitions will still indicate the re-use of a confusion value in the second combiner, since the data value hidden between the combiners is unknown, the confusion value cannot be identified. The use of two combiners also implies that two confusion values are used when ciphering a single data value. There simply is not enough information in a single plaintext / ciphertext pair to define _two_confusion values.
• Dynamic Combiner Selection: Another technique which virtually eliminates the known-plaintext weakness is to dynamically select one of multiple active combiners. This makes it difficult for The Opponent to know which values come from which combiner, information which seems necessary for use of repetition data. This scheme also expands the amount of confusion used in ciphering, and a single plaintext / ciphertext pair simply does not have enough information to define more than a single confusion value.

As usual in cryptography, we cannot expect a simple mechanism to be secure on its own. Instead, each mechanism must be used in suitably secure ways. For Dynamic Substitution, secure techniques include sequential ciphering and dynamic combiner selection, and both of these are really only useful for nonlinear combiners with internal state.

Defined Plaintext Attack

Another way to deduce confusion (again, in a simple system with one non-hardened combiner) values is to explore the table arrangement both before and after any particular substitution occurs. That is, The Opponent tries one plaintext value, then resets the system and tries another, until all possible values have been covered. (This of course implies that The Opponent_can_ reset the system, cipher any desired message, and capture the ciphertext result. The ability to reset the system is generally not available in real designs.)

If The Opponent conducts a full table exploration just_before_ any particular substitution, and then again_after_ that operation, typically two table elements will have changed places. This will identify the element selected by the data value and the element selected by the confusion value. But the data value is known (since The Opponent generated the message), so the confusion value can be deduced from the original state of the table.

On the other hand, "table exploration" generally implies adefined plaintext attack, which can be prevented in other parts of the cipher. For example, when a cipher uses a randommessage key, the actual data-ciphering key is a random value not under the control of the user. In general, this means that every ciphering will have a different table initialization, and this means that it will be impossible for The Opponent as a user to reset the system to a known state, even though repeatedly using the same User Key. This makes it impossible for The Opponent to conduct even _one_table exploration.

Similarly, by selecting from among an array of separate Dynamic Substitution combiners, The Opponent would seemingly need to isolate the ciphering from each individual table. And even a_small_ array makes it hard to associate each result with a particular table, even if a defined-plaintext attack is otherwise enabled.

Hardening Dynamic Substitution

Various constructions can be used to strengthen the basic Dynamic Substitution operation, up to and including re-shuffling the entire table after every character. But the combining operation can be very significantly strengthened with far less overhead than this. Two interesting approaches may be called_Doubly Indirect Data_ and Double Random, and these may be used either separately or together.

Doubly Indirect Data

Encipher data through the table twice, and exchange the second selected element with the random selected element.

Enciphering:

INITIAL STATE Forward Table --- --- --- --- Table Value | B | D | A | C | --- --- --- --- Table Location A B C D

Data In (DI): C Random In (RI): D

Data Out (DO) = Fwd[Fwd[DI]] = Fwd[Fwd[C]] = B Swap( Fwd[Fwd[DI]], Fwd[RI] ) = Swap( Fwd[A], Fwd[D] )

FINAL STATE Forward Table --- --- --- --- Table Value | C | D | A | B | --- --- --- --- Table Location A B C D

Deciphering:

INITIAL STATE Inverse Table Forward Table --- --- --- --- --- --- --- --- Table Value | C | A | D | B | | B | D | A | C | --- --- --- --- --- --- --- --- Table Location A B C D A B C D

Data In (DI): B Random In (RI): D

Data Out (DO) = Inv[Inv[DI]] = Inv[Inv[B]] = C temp = Inv[DI] = Inv[B] = A Swap( Inv[DI], Inv[Fwd[RI]] ) = Swap( Inv[B], Inv[C] ) Swap( Fwd[temp], Fwd[RI] ) = Swap( Fwd[A], Fwd[D] )

FINAL STATE Inverse Table Forward Table --- --- --- --- --- --- --- --- Table Value | C | D | A | B | | C | D | A | B | --- --- --- --- --- --- --- --- Table Location A B C D A B C D

The advantage here is the added protection of decoupling the input data from the output entry. This generally prevents The Opponent from finding a previous random value when a data in value produces a match to a preceding data out.

The cost of this added strength is quite modest, being just one more indirect access when enciphering, and perhaps a new temp variable when deciphering.

Double Random

Encipher data through the table once. To form an ultimate random value, encipher one random input value and additively combine it with a second random input. Then exchange the selected element with the random selected element.

Enciphering:

INITIAL STATE Forward Table --- --- --- --- Table Value | D | B | A | C | --- --- --- --- Table Location A B C D

Data In (DI): C Random In A (RIA): D Random In B (RIB): C

Data Out (DO) = Fwd[DI] = Fwd[C] = A temp = RIB + Fwd[RIA] = C + Fwd[D] = C + C = A Swap( Fwd[DI], Fwd[temp] ) = Swap( Fwd[C], Fwd[A] )

FINAL STATE Forward Table --- --- --- --- Table Value | A | B | D | C | --- --- --- --- Table Location A B C D

Deciphering:

INITIAL STATE Inverse Table Forward Table --- --- --- --- --- --- --- --- Table Value | C | B | D | A | | D | B | A | C | --- --- --- --- --- --- --- --- Table Location A B C D A B C D

Data In (DI): A Random In A (RIA): D Random In B (RIB): C

Data Out (DO) = Inv[DI] = Inv[A] = C temp1 = RIB + Fwd[RIA] = C + Fwd[D] = C + C = A temp2 = Inv[DI] = Inv[A] = C Swap( Inv[DI], Inv[Fwd[temp1]] ) = Swap( Inv[A], Inv[D] ) Swap( Fwd[temp2], Fwd[temp1] ) = Swap( Fwd[C], Fwd[A] )

FINAL STATE Inverse Table Forward Table --- --- --- --- --- --- --- --- Table Value | A | B | D | C | | A | B | D | C | --- --- --- --- --- --- --- --- Table Location A B C D A B C D

The advantage of this method is that we absolutely know_that a single byte of ciphertext cannot possibly resolve_two bytes of random input.

The cost, of course, is the need for twice as many random values (which may be available anyway, when using a wide Additive RNG), plus another indirect access and exclusive-OR, when enciphering. Two new temp variables may be needed for deciphering, but if that storage is available, the cost may be just the extra indirect access and exclusive-OR.

As these two hardening methods show, a wide variety of simple manipulations can be used to strengthen the fundamental combining operation. These methods can be used in addition to the ability to use a wide range of more extensive permutations far beyond just one or two swap operations. And all of these Dynamic Substitution flavors can be used in a sequence of combinings or a selection among multiple combinings.

Summary

An effective cryptographic system should be seen as a system designed to protect the inevitable weaknesses in each of the components. For example, the fact that exclusive-OR is trivially weak does not prevent it from being used to good advantage as a balanced mixer in many ciphering designs. But a stronger component needs less protection.

Perhaps the biggest advantages of Dynamic Substitution follow from a construction based on substantial internal state. It is the Dynamic Substitution internal state which supports the use of (nonlinear) combinings in sequence. In contrast, multiple combining rarely improves strength when using (linear) exclusive-OR. It is the Dynamic Substitution internal state which also makes each combiner different, and thus supports the use of a selection from among several combiners. And, of course, there are no "different" exclusive-OR combiners. The cost is a need to store and initialize this state information.

By making use of the Dynamic Substitution internal state, a cipher can remain secure even if weakness is later found in the confusion generator subsystem. Indeed, a simpler and faster RNG can be used from the start. These are significant advantages.

Acknowledgments

Thanks to John Savard (seward@netcom.ca) for pointing out that "close" repeats in normal Dynamic Substitution ciphertext can expose confusion values.

Thanks to Keith Lockstone (klockstone@cix.compulink.co.uk) for suggesting ways to "harden" Dynamic Substitution and prevent confusion exposure.

Terry Ritter, hiscurrent address, and his top page.

Last updated: 1997-01-16