High-quality mixing makes it difficult to distinguish and attack individual components.

A Balanced Block Mixer can be seen as a pair of orthogonal Latin squares. Each square is used as a combiner to mix two input values. In a Latin square combiner, any output value can be produced by any possible value on one input, by placing some appropriate value on the other input. This is balance under all conditions, and is a generalization of the protection in common additive combiners like exclusive-OR. The advantage of orthogonal combiners is that the result is invertible: the mixing can be reversed using only the mixed result. There can be no orthogonal exclusive-OR's.

It is certainly possible to create and key large explicit Latin square tables. But even an "8-bit" combiner has 65,536 byte entries, and there would be two of those, for a total of 128K bytes. This is both larger and more of a keying delay than we might like. Consequently, the linear form (which needs no keying) seems worth exploring.

The BBM form I often use can be expressed in two equations:

X = 3A + 2B (mod 2)(mod p), Y = 2A + 3B (mod 2)(mod p).Again, this is a linear mixing, with

One of the problems understanding these simple linear BBM's
may be that they are based on
mod 2 polynomials.
While these are actually simpler than integers and conventional
arithmetic, they will be new to many people. Basically we are just
generating a mathematical
field with 2^{n} values
which supports a form of addition and multiplication which produce
values in that same field.

For example, suppose we have two 2-bit values to be combined. With 2-bit values, we only have a value range from 0 through 3, so lets choose 1 (01) and 2 (10), with the irreducible polynomial 7 (111).

First we add A and B, which is just a bit-by-bit exclusive-OR:01 A + 10 B -- 11 A+B (mod 2)Next we multiply by 2, which is just a left shift:110 2(A+B) (mod 2)But now the leftmost bit is set, which means the result is out of range. To bring it back in, we subtract p. Again, this is just a bit-by-bit exclusive-OR:110 2A+2B (mod 2) - 111 p --- 01 2A+2B (mod 2)(mod p)Then we finish off the two equations:01 2A+2B (mod 2)(mod p) + 01 A -- 00 3A+2B (mod 2)(mod p) = X = 0 01 2A+2B (mod 2)(mod p) + 10 B -- 11 2A+3B (mod 2)(mod p) = Y = 3

And, if we enter 1 and 2 below (with "2 Bit" selected), we get 0 and 3 as a result:

In the active Balanced Block Mixer above, we can place values (within the appropriate range) in the top entry fields, and get the mixed results in the bottom fields. As each value is entered, the results are updated (hit "Enter," tab to the next field, or click elsewhere to enter the value). We can also put any results we have in the bottom entry fields, which will update the inputs, and so show what inputs mix to that result.

Another way to think of the mixing is as the overall discrete transformation in the form of two explicit orthogonal Latin squares. For a particular element width and polynomial, we can make a table containing both squares by pressing the "Make Table" button. In the table, the left mixing input selects a row, the right input a column, thus selecting a particular entry. Each entry has two digits: one from the left square, and one from the right. In the "2 Bit" table, selecting row 1 and column 2 gives 03 which is the result we saw before.

If we could mix together only two elements, the BBM concept would
not be very helpful. But we *can* mix more elements, any
power-of-2 elements, to be exact. We do this by mixing two elements
at a time, and then mixing those results with other mixed results.
This is the old
FFT strategy, which results in mixing
n elements in n log n time.

The next active mixing combines 4 elements at a time. Note that changing even a single input value always changes all 4 of the output values. This is not the binomial distribution we expect from avalanche. But when each of the output values is translated through a keyed substitution table, the bit-change statistics improve nicely. And the real issue is whether the high quality of the mixing used to combine multiple substitution tables prevents those tables from being attacked individually.

Enter the desired value in an input, or an output (remember to use "Enter," or tab to the next field, or click outside the box to enter each value), or just click the "-" or "+" buttons to change the values. This mixing uses the bit-width and polynomial selected above, and so can handle 2-bit, 3-bit or 4-bit elements.

Note how changing any single input value -- even by just a single
bit -- changes *all* of the output values. This is the basis
for a guarantee that even a single bit-change absolutely will
propagate to *each* and *every* subsequent element. So if
we have a keyed substitution table on each output, we are assured
that even a single input bit-change will engage the strength of
each table, which will also produce a good bit-change distribution
result.

This is an invertible system, so it is obviously possible to supply some input change which will limit the output change to just a single element. (Just change one of the output values to see what the input would have to be.) But if we have keyed tables on the input, it would seem to be difficult to exploit the mixing linearity we know is there. This is the basis of Mixing cipher design.

*Last updated:*1998-03-29