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 no strength at all. Its advantage is the ability to combine two block values (here A and B) into two other block values (here X and Y) which both depend upon each of the input values, and do so in a perfectly balanced way. Yes, these results are linearly related to the inputs, but if we add four keyed substitution tables, one on each input and each output, we have a brand new situation. (Keying the tables is straightforward; see, for example: A Keyed Shuffling System, on these pages.) It is not at all clear how one can approach an analysis of such a system. But this structure is scalable, and we can scale it down, down, down, until we ought to be able either to attack it by hand, or know the reason why not. This is, of course, the truth we seek.
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 2n 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