A Variable Size Core for Block Cipher Cryptography (original) (raw)

Cipher Blocks of Arbitrary Size with Good Data Diffusion

ACiphers By Ritter Page

Terry Ritter

AVariable Size Block Cipher (VSBC) is distinguished by its ability to cipher blocks of dynamically arbitrary size, to the byte, and yet produce good datadiffusionacross the whole block.

In dramatic contrast to conventional designs, here most diffusion occurs in simple linear BBM operations**which are not intended to provide strength!**By itself, linear mixing has nostrengthat all, but it does set the stage forkeyed substitution tableswhich do have strength. The BBM's provide a _guaranteed,_exactlybalanced and reversible mixing which, in a successful design, prevents individual tables from being distinguished and solved.

Here we present the ciphering core, the architecture of tables and mixing which performs actual ciphering. The tables are initialized or "keyed" by a separate process whichshuffleseach table independently, twice.

Variable Size Block Cipher Attributes

Contents

Background

The first known publication of the concept of a Variable Size Block Cipher (VSBC) -- and the first published VSBC design -- was the 1995 Aug 20 sci.cryptannouncement by Ritter and the resultingdiscussion. The general lack of understanding in the responses indicates that the concept was new to those who replied.

A patent has been granted on Variable Size Block Ciphers.

Components

VSBC Core

In this Variable Size Block Cipher core we have two main component types:

  1. keyed, invertiblesubstitution tables, and
  2. Balanced Block Mixers (BBM's). (We also use exclusive-OR's in the dynamic table selection.)

In the figure, each box represents a table, and each hourglass shape represents a BBM.Plaintextdata bytes enter at the top, are substituted, mixed right, substituted, mixed right, substituted, mixed left, substituted, mixed left and substituted intociphertext. Dynamic table selection is not shown.

The essence of the design is an inability to externally isolate or distinguish one table from another. This inability is directly related to the exactbalancein the high-quality BBM mixing, as opposed to an exponential increase in complexity from repeated low-quality mixing with confusion.

Tables are widely used in many designs, and even keyed tables are not that unusual. But in this design all of the inter-element diffusion occurs in distinct,one-way diffusion layerscomposed of _linear_Balanced Block Mixing (BBM) operations, and this is new.

This separation between mixing (diffusion) and keyed substitution (confusion) is beneficial in that the two operations can be seen, understood, and measured separately. In conventional designs, confusion and diffusion are often combined, which makes these ciphers difficult to understand or measure. And conventional ciphers do not scale down to testable size.

Scalability

A Variable Size Block Cipher isscalablein a way that few designs are:

This ability to scale a single design between large real ciphers and small testable models almost cannot be overemphasized.Cryptography does have better-known structures and designs, but cryptography simply does not have a proven methodology which -- if only followed -- will guarantee a strong design. This means that testing is exceedingly important, and real ciphers are far too large for many types of test.

The BBM

Orthogonal Latin Squares

A Balanced Block Mixer can be considered an orthogonal pair ofLatin squares. The two inputs select "row" and "column" and return the value from the selected element of each square. This "mixes" orcombinesthe two input values into the two output values with some useful properties for this design:

  1. A change to either input will change both outputs.
  2. No input change can keep both outputs unchanged.
  3. Any possible value (value balance) from either output can be achieved by changing either input (structural balance), regardless of the value on the other input (independence).

Even a single bit change in one mixing input will produce some change in both mixing outputs. And if each output is substituted through a keyed table, each table will produce a random result value. So even a single bit change on one input will produce a new random result on both outputs.

A Variable Size Block

A Variable Size Block Core

To have ablock cipherwhich can be expanded arbitrarily, to the byte, at ciphering time, we are necessarily limited to operations which can be applied byte-by-byte. But we are not limited to performing the whole transformation on each byte _separately_as we would in astream cipher. Instead, we can apply operations which, though byte-size, produce "carry" information as an input to the next byte operation. When we do this multiple times in both directions we can approach the desired block cipher goal of apparentoverall diffusion.

In the figure, each plaintext byte enters the top of the structure and is immediately confused through an invertiblesubstitution table. The substituted value then mixes into aone way diffusionpath running across the unknown width of the block. Each of the funny-looking hourglass shapes represents a separateBalanced Block Mixing(BBM), a two-input two-output mixing operation which proceeds in the direction of the arrow.

Dynamic Table Selection

A VSBC with Dynamic Table Select Details

While each substitution in the figures has a particular number (e.g., S00 for the leftmost top substitution), these are just_positions_ for tables and not particular _tables_themselves. Considerable strength is added by selecting the table for each next position based on an exclusive-OR of the data and substituted data values in the preceding position. This "dynamic table selection" virtually eliminates the possibility of having even two blocks ciphered under the same table arrangement.

Dynamic table selection also provides a zero-latency form of "chaining" which can be used for authentication. (The initial table values can be explicitly reset before each block if blocks are to be ciphered independently.)

Data Diffusion

The intent of the design is to mix every input byte into every output byte in a way which appears to be a huge overall random substitution. Most of this mixing occurs in the four BBM one-way diffusion layers, and some occurs in the dynamic table selection of the confusion layers.

A Variable Size Block Core

While one might think that two one-way diffusion channels would be sufficient (one each way, or both the same way with an end-around-carry), in practice, random inputs occasionally "cancel" earlier changes, so that -- occasionally -- no propagation occurs. This can be made rare by having a wide diffusion channel. And here we have not only two layers of Balanced Block Mixing in each direction, but also the dynamic table selection to carry diffusion across the block. In this particular design, there are 4 specific 8-bit one-way diffusion layers, plus 5 layers of dynamic table selection. With 64 substitution boxes, we thus have a 62-bit diffusion path between adjacent columns.

The first two right-going BBM layers assure that almost any left-side data change will be conducted across the block, and so complicate attempts to isolate the leftmost column. After the first left-going diffusion layer, we should have a complex function of_every_ input byte across the entire block. The final left-going BBM layer is used to protect against random cancellation effects which might otherwise affect the left-going diffusion.

By conducting adefined plaintext attack, and running through all values for the first few columns, it should be possible to detect cancellations in both carry paths as a lack of ciphertext changes to the right. These are all evenly distributed, however, and seem to provide no information about particular values which could be used in reconstructing the table contents. This issue is discussed inDefined Plaintext Attack on a Simplified BBM VSBCon these pages.

Deciphering

Since we use invertible substitution tables, we can "undo" any table translation by sending the resulting value through the corresponding inverse table. The form of Dynamic Table Selection used here takes both the input and output table values and exclusive-OR's them, which selects the same next table whether we have forward or inverse tables. So a right-going Dynamic Table Selection layer is reversed by a right-going Dynamic Table Selection layer using inverse tables.

The inverse of the simple linear BBM component used here is just another occurrence of that same BBM component. In the one-way diffusion layers used here, a left-going diffusion (L) is the inverse of a right-going diffusion (R), and vise versa. In the current design we have four one-way diffusion layers for enciphering, in the sequence . When deciphering, to reverse the bottom "L" layer, we need an "R", and so on. So the deciphering diffusion layer sequence is also .

This means that exactly the same ciphering routine can be used for both enciphering and deciphering. For deciphering we use inverse tables and take the initial values (IV's) in reverse layer order. Both of these conditions are easily handled during keying.

Large Blocks

DES has a fixed block size and we have somehow managed thus far, so it may seem like overkill for a cipher to have multiple block sizes. But there is almost no cost for this, and it must be admitted that having blocks of various size -- or even dynamically variable size -- sometimes can provide a better fit to the overall system than any single fixed block size. But perhaps the biggest benefit comes from the ability to cipher in very large blocks.

Large Blocks are Strong

If plaintext really does contain uniqueness at a rate of only about one bit per character, a legacy 64-bit block covers only about eight bits of uniqueness. This is the situation encountered in the classiccodebook attack. This sort of attack is not avoided by having a largerkeyspace, but _can_be avoided by using a wide, unbiased selection of plaintext blocks. Normally this is done by using a chainedoperating modeto randomize the plaintext. But increasing the block size to 64 bytes or more can collect enough uniqueness in the plaintext block so that randomization can be avoided.

Large Blocks Can Be Independent

By increasing the block size to 64 bytes or more we may be able to operate in "electronic code book" (ECB) mode instead of "cipher block chain" (CBC) mode. This means that we may not need to develop, send or store an initial value (IV), which would otherwise expand the ciphertext. And it also means that blocks can be both enciphered and deciphered independently, even if they are received out-of-sequence, as may happen in packet-switching transmission.

Large Blocks Have Room for Dynamic Keying and Authentication

In conventional block cipher designs, the block size is so small that we can scarcely consider displacing some data with other information. But when we have a large block, there is room for other information, at a relatively small overhead. Typical applications include Dynamic Keying and Authentication.

Primary Keying

Primary keying generally consists ofshuffling eachsubstitution tablewith akeyed cryptographicrandom number generator(RNG), twice. Primary keying can use fairly conventional technology, and is largely independent of the ciphering core itself. One example of a keying system is described inA Keyed Shuffling System on these pages.

Primary keying takes about 1 msec per table on a 100 MHz processor, which is fast enough on a human scale. Primary keying does take time, because it is specifically intended to perform as much computation as possible -- once -- instead of having computation repeated with every block at ciphering-time.

Strength

We assign an 8 bit strength to each table. Although an arbitrary table permutation contains 1684 bits of independence, we reason that ifThe Opponentscan find (that is, absolutely identify and confirm) one value, they can probably find another. Since each table value is 8 bits, we assume a table strength of just 8 bits.

With this sort of fiveconfusion layerand fourone-way diffusionlayer structure, we believe that only three of the layers contribute independentstrength. Therefore, for a small 8-byte block, we expect to see8 * 24 = 192 bits of strength in 40 separate tables (out of at least 64).

Dynamic Keying

True zero-latencydynamic keyingis available by placing keying values in each data block along with data. This will of course expand the ciphertext by the size of the keying field, but even a 64-bit dynamic keying field is only about 12.5 percent of a 64-byte block. This sort of keying can be used in any true (that is,avalanching or datadiffusing)block cipher with room for extra data.

Authentication

Strong block-by-blockauthenticationis available similar to dynamic keying. Authentication values are placed into each data block along with data. Potentially, this can avoid a higher-level scan across the data with a cryptographichash function. The exact same field can provide both authentication _and_dynamic keying.

Strength Arguments

Here we present variousattacksand comment on their likelihood of success on this particular cipher. Recall that attacks are not_algorithms,_ but instead just general approaches which must be reinvented for every new type of cipher.

Exhaustive Search (Brute Force on the Key)

Try each possible key until the message deciphers properly. Try most-likely keys first.

A keyspace of at least 120 bits should be sufficient to prevent exhaustive search in the foreseeable future. The keying system for the VSBC core has a keyspace substantially beyond this value, mainly because this produces a convenient design.

No cipher can do very much about key search attacks if there are only a relatively small number of possible keys, and if some keys are vastly more probable than others. It is the responsibility of the larger system to prevent this.

Chosen Key

Try various keys on known plaintext and compare the resulting ciphertext to the actual ciphertext, to try and build the correct key value.

If a user has the ability to generate specific keys which are used by the VSBC core on data, it is quite likely that the external cipher system has already failed. However, even in this situation, key selection seems unlikely to help The Opponent. Sure, they can force particular table values by manipulating the key, but they can do that without going through the keying process. The Opponent's main problem in attacking the cipher is that the one-way diffusion layers appear to couple the various tables together so that a single table cannot be isolated and worked on separately.

Ciphertext Only

The Opponent accumulates a mass of ciphertext material and tries to find relationships within the data.

This is a general class of various specialized attacks which all use only the exposed ciphertext as opposed to particular knowledge of the plaintext or access to the ciphering system itself.

Ciphertext-Only Codebook

Collect as many ciphertexts as possible and try to understand their contents through usage and relationships; then, when a ciphertext occurs, look it up. This treats the block cipher like a code, and is the classic approach to code-breaking.

Just as some letters are more frequently used than others, words and phrases also have usage frequencies, as do blocks which contain plaintext. If the cipher block size is small (under 64 bytes), and if the plaintext is not randomized, and if dynamic keying is not used, and if the ciphering key is not changed frequently, it may be possible to build a codebook of block values with their intended meanings.

Codebook attacks of any sort are ideally prevented by having a large number of block values, which implies a large block size. Once the block size is at least, say, 64 bytes, we expect the amount of uniqueness in each block to exceed anyone's ability to collect and form a codebook.

Since the complexity of any sort of a codebook attack is related to block size only, doing "triple" anything will not affect increase this complexity. In particular, this means that Triple DES is no stronger that DES itself under this sort of attack, which is based on block size and not transformation complexity.

Known Plaintext

Somehow "obtain" both the plaintext and the corresponding ciphertext for some large number of encipherings under one key.

First, since the VSBC core described here has an internal state typically 512 times as large as a 64-byte data block, we know that a single plaintext and ciphertext pair simply do not contain sufficient information to reveal the full internal state. Note that a single known plaintext and ciphertext pair probably would identify a DES key.

Larger amounts of known plaintext and ciphertext will of course surpass the required information, but the question is how The Opponent might use it. The problem is a supposed inability to distinguish one table from another and so work on one table at at time.

Known-Plaintext Codebook

Collect as many ciphertexts and associated plaintext blocks as possible; then, when a ciphertext occurs, look it up.

Small block ciphers prevent codebook attacks by randomizing the plaintext (often with Cipher Block Chaining) so that the plaintext block values are distributed evenly across all possible block values. But not all block ciphers are always applied properly.

Codebook attacks are ideally prevented by having a large number of block values, which implies a block size. To prevent this attack for the future, we need a block size of at least 128 bits, and even then still require the plaintext to be randomized. If we wish to avoid randomizing with CBC, we need a block which is large enough so the uniqueness it does contain assures that there will be too many different blocks to catalog. A reasonable power-of-2 minimum size to avoid randomization would be at least 64 bytes.

Chosen Plaintext

Without knowing the key, arrange to cipher data at will and capture the associated ciphertext. Dynamically modify the data to reveal the key, or keyed values in the cipher.

The point here is not to decipher the associated ciphertext because The Opponent is producing the original plaintext. If The Opponents have chosen plaintext capabilities, they can probably also submit arbitrary ciphertext blocks for deciphering.

The weakness to be exploited here depends upon the ciphering system beyond the core cipher _per se._If the primary keying values change with each message, and the ciphering keys are not under the control of the user (if the system uses message keys), there simply is no fixed internal state to be exposed.

If the primary key remains the same for all messages, then there will be some keyed state to try and ferret out. But if the ciphering system uses dynamic keying fields (with values again not under the control of the user), there can be no completely-known Chosen Plaintext blocks for use in analysis.

If the ciphering core is used raw, without primary re-keying and also without dynamic keying, the Dynamic Table Selection still uses whatever "uniqueness" exists in the data to change the tables used in the block transformation.

It is not clear that there exist any statistical relationships in the VSBC core which can be exploited better by Chosen Plaintext than by Known Plaintext.

Chosen-Plaintext Codebook

Create as many ciphertexts and associated plaintext blocks as possible; then, when a ciphertext occurs, look it up.

This is much like the previous codebook attacks, now with the ability to fill the codebook at will and at electronic speeds. Again, the ability to do this depends upon the cipher having a relatively small block size and not having a dynamic keying field. How difficult such an attack would be depends upon the size of the block, but a VSBC may have no particular block size.

Meet-in-the-Middle

With a multi-layered structure, given known-or defined-plaintext, search the top keyspace to find every possible result, and search the bottom keyspace to find every possible value.

With a two-level construct and a small block size, matches can be verified with a few subsequent known-plaintext/ciphertext pairs. Of course, three and more-level constructs can always be partitioned into two sections so a meet-in-the-middle attack can always be applied; this just may be pretty complex.

The Mixing core avoids meet-in-the-middle attacks by using a three-level construction, in which each layer has a huge amount of keyed state or "keyspace."

Key Bit Bias

Through extensive ciphering of fixed plaintext data under a variety of different keys, it may sometimes be possible to associate key bits with the statistical value of some ciphertext bits. This knowledge will break the cipher quickly.

This is a rather unlikely circumstance, albeit one with absolutely deadly results.

Differential Cryptanalysis

Exploit known properties of particular known substitution tables to effectively reduce the number of "rounds" in an iterated block cipher.

The original form of Differential Cryptanalysis mainly applies to iterated block ciphers with known tables, neither of which are present here. However, the general concept is like the expected VSBC attack.

The general idea of trying to relate byte values in adjacent columns is one of the major possible attacks on VSBC's. This is made difficult by using Balanced Block Mixing to conduct diffusion, and by having multiple diffusion layers. Each BBM guarantees that a change in a data value can "cancel" at most one of the mixed outputs, which leaves the other mixed output to carry the change across the block.

Another difficulty in applying Differential Cryptanalysis to a VSBC would be in handling the Dynamic Table Selection feature. Each different input value will actually select a different set of tables, and, thus, a completely different transformation. It is hard to attack a transformation which changes its structure whenever it is probed.

Summary of Advantages

Strength

Flexibility

Also see:

Last updated: 1998-03-21