A Mixing block cipher is distinguished by the exclusive use of Balanced Block Mixing (BBM) structures for block diffusion.
In dramatic contrast to conventional designs, here all diffusion occurs in simple linear BBM operations which are not intended to provide strength! By itself, linear mixing has no strength at all, but it does set the stage for keyed substitution tables which do have strength. The BBM's provide a guaranteed, exactly balanced 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 which shuffles each table independently, twice.
The first known publication of the concept of Balanced Block Mixing and its use to build Mixing ciphers was the 1994 Mar 13 sci.crypt announcement by Ritter and the resulting discussion. The general lack of understanding in the responses shows that the concept was new to those who replied.
Mixing ciphers are protected by patent.
In a Mixing cipher core we have exactly two component types:
In the figure, each box represents a table, and each connected pair of diamonds represents one BBM. Plaintext data bytes enter at the top, are substituted, mixed, substituted, mixed and substituted into ciphertext.
The essence of the design is an inability to externally isolate or distinguish one table from another. This inability is directly related to the exact balance in 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 mixing layers composed 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.
A Mixing cipher is scalable in 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.
A Balanced Block Mixer can be considered an orthogonal pair of Latin squares. The two inputs select "row" and "column" and return the value from the selected element of each square. This "mixes" or combines the two input values into the two output values with some useful properties for this design:
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.
One way to use BBM structures is to create full-blown Latin squares: The typical "8-bit" mixing would thus require two 64K byte orthogonal tables. Now, 128K of keyed tables will combine strength with guaranteed mixing, but large keyed Latin square tables are harder to create than we might like.
The aim of the Mixing construction is different: Here we use
simple, linear, computational "Latin squares" for mixing, and then
we add smaller keyed tables for strength. And there is plenty of
strength around: we can easily realize many thousands of keying bits
even with fairly small tables (a shuffled "8-bit" table of 256 byte
elements ideally represents 1648 bits of keying). So, in a sense,
strength is not the problem; instead, the problem is in preventing
The Opponent
from isolating and analyzing individual tables, and
this is a mixing issue.
In Mixing ciphers, we typically use small "8-bit" BBM's. This gives us a reasonable 8-bit table size, and the linear BBM mixing is easy and fast. But this means that somehow we will have to mix at least 8 tables, not just 2.
In the figure, we see 3 "sub-layers" of BBM mixing. Each pair of values are mixed, and the results handed on to the next mixing sub-layer. By tracing the data paths, we can see that each and every input value from the top is represented exactly once in each and every output value at the bottom.
We can expand BBM's by mixing in FFT-like or FWT-like patterns (see An Efficient FFT-Style Mixing Pattern, on these pages). The result is essentially a single BBM with n-inputs, n-outputs, and properties analogous to the 2-input 2-output component:
Even though a linear BBM structure is inherently weak, the same
can be said of exclusive-OR, which is used in presumably strong
ciphers all the time. The balance and independence properties
created by a wide BBM force an even statistical distribution across
all values and all outputs. This mixing seems ideal for coupling
keyed tables into a large effective block.
The diagram shows the Mixing cipher core for an 8-byte (64-bit) block. Note that this structure is dynamically scalable to handle blocks of arbitrary power-of-2 size at ciphering time, simply by doing more mixing sublayer computations.
The thin vertical blue lines represent a value moving down through time. Each yellow diamond represents half of a Balanced Block Mixing and a value change. Two diamonds connected by a thick horizontal red line represent a complete byte-wide BBM operation.
Each block (e.g., S00, S15, etc.) represents an individually keyed table substitution. The actual table used in each position will be selected from an array of such tables. Each table is a keyed invertible substitution.
At the 8-byte width, each byte is processed through a BBM three times before we have a full mixing. Each doubling of the block width implies another sublayer of BBM processing, so a 64-byte (512-bit) block would need 6 sublayers, a 512-byte (4096-bit) block would need 9 sublayers, and a 4096-byte (32,768-bit) block would need 12 sublayers.
An ideal hardware realization would have a separate on-chip table for each position in three confusion layers across a 64-byte block. This would imply a particular keyed table for each of 192 table positions.
In software, we can have a smaller number of tables and re-use
them sequentially wherever a table is required. Note that it is
this ability to re-use a fixed number of tables which allows us
to handle arbitrarily huge blocks. If we have exactly 192 tables,
the software realization can be compatible with the ideal hardware.
Since we use invertible substitution tables, we can "undo" any table translation by sending the resulting value through the corresponding inverse table.
The inverse of the BBM component used here is just another occurrence of that same BBM component. Similarly, the FFT-like full mixing layer is just another occurrence of that layer.
This means that exactly the same ciphering routine (or hardware) 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. (The IV's are the starting table values for each layer.) Both of these conditions are easily handled during keying.
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 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.
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 classic codebook attack. This sort of attack is not avoided by having a larger keyspace, but can be avoided by using a wide, unbiased selection of plaintext blocks. Normally this is done by using a chained operating mode to 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.
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.
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 generally consists of shuffling each substitution table with a keyed cryptographic random 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 in A 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.
We assign an 8 bit strength to each table. Although an arbitrary table permutation contains 1684 bits of independence, we reason that if The Opponents can 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 three
confusion
layer
structure, we believe
that only two of the layers contribute independent
strength.
Therefore, in a small 8-byte block, we expect to see
True zero-latency dynamic keying is 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 data diffusing) block cipher with room for extra data.
Strong block-by-block authentication is 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 cryptographic hash function. The exact same field can provide both authentication and dynamic keying.
Here we present various attacks and 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.
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 Mixing 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.
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 Mixing 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 Opponents. 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 a Mixing cipher is that the mixing appears to couple the various tables together so that a single table cannot be isolated and worked on separately.
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.
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.
Somehow "obtain" both the plaintext and the corresponding ciphertext for some large number of encipherings under one key.
First, since the Mixing 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.
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 large 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.
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 key 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 fixed 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 question arises as to whether there exist any statistical relationships which can be exploited better by Chosen Plaintext than by Known Plaintext. None are known.
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 not having dynamic keying fields. How difficult this will be depends upon the size of the block.
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 and 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. It 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."
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.
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 more generally applicable.
Since each input byte is mixed into every mid-level substitution
operation, and these are mixed again into output substitutions,
it is hard to see how Differential Cryptanalysis could be used.
Summary of Advantages
Strength
Flexibility
Hardware
Also see:
Last updated: 1998-03-21