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.

**SPEED**-- about 1,005,000 bytes per second in 16-byte blocks and about 980,000 bytes per second in 64-byte blocks (on a 100 MHz "686," under Win95, with the Borland 32-bit Delphi 2 compiler). The typical keying overhead is around 64 milliseconds for 64 tables.**STRENGTH**-- greater than 128 bits for a block size of at least 64 bits and at least 24 keyed tables.**BLOCK SIZE**-- dynamically selectable at ciphering time in power-of-2 steps. A single program handles "legacy" 64-bit blocks, "modern" 128-bit blocks, "independent" 64-byte blocks and 512-byte disk blocks without change.**KEY SIZE**-- arbitrary, independent of block size.

- Mixing Cipher Attributes
- Background
- Components
- Scalability
- The BBM
- Using The BBM
- The BBM in FFT Patterns
- A 64-Bit Mixing Core
- Deciphering
- Large Blocks
- Primary Keying
- Strength
- Dynamic Keying
- Authentication
- Strength Arguments
- Summary of Advantages
- Also See:

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:

- keyed, invertible substitution tables, and
- Balanced Block Mixers (BBM's).

`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:

- First, the block size is dynamically selectable in power-of-2 steps. A single unchanged program can handle "legacy" 64-bit blocks, "modern" 128-bit blocks, and "independent" 64-byte (512-bit) blocks.
- Next, we can even scale down the size of the tables and the mixing elements. This means that the same design can deliver either a full-scale real cipher, or a tiny model which can be investigated experimentally for weakness.

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:

- A change to either input will change both outputs.
- No input change can keep both outputs unchanged.
- 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.

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:

- A change to any input will change all outputs.
- No input change can keep all outputs unchanged.
- Any possible value (value balance) from any output can be achieved by changing any input (structural balance), regardless of the value on the other inputs (independence).

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 acode, 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.

- The strength advantage of large blocks, which can hold huge amounts of plaintext uncertainty.
- Large blocks have room for dynamic keying information, which supports zero-latency block-by-block keying.
- Large blocks have room for authentication information, which can avoid the need for a slow higher-level authentication pass over the data
- The strength advantage of massive, keyed, nonlinear, hidden
internal state, which generally means that an attacker must
somehow
*expose*that state. - The strength advantage of a fundamentally
*scalable*design which supports tiny true models that can be exhaustively tested.

- The flexibility advantage of dynamically selectable block size.
This directly supports "legacy" 64-bit blocks, "modern" 128-bit
blocks, "independent" 64-byte blocks, and 512-byte disk sectors
in
*the exact same unchanged program*. - Large blocks can eliminate the need for plaintext randomization, chaining, and the use of ciphertext-expanding IV's.
- Large blocks support the independent ciphering of blocks, and random-access ciphering.
- The dynamically selectable block size can limit ciphertext expansion by stepping down through smaller blocks at the end of a message.
- The flexibility advantage of key processing as a part of the
cipher. This directly supports
*both*textual*and*random binary keys of arbitrary length.

- The hardware advantage of a constant ciphering rate
*per block,*independent of the size of the block. Each pair of bytes across the block in each mixing sublayer can be simultaneously processed in parallel hardware, and each sub-layer can be pipelined, for gigabyte ciphering rates in present technology. - The hardware advantage of a structurally simple design based on exactly two very dense chip structures (tables and BBM components). Ideal for tight chip layout.

*Also see:*

- The Large Block DES Open Development: our search for a new "DES" architecture started over four years ago.
- The original BBM article
- The start of a theoretical basis.
- Fenced DES
- The current BBM article
- The keying system
- The FFT mixing pattern
- Mixing on the top page

*Last updated:* 1998-03-21