For those who have not previously encountered FFT-style
mixing, we present description, figures, and routines in both
Pascal and C for a straightforward and efficient mixing pattern.
We propose this as the *standard* pattern for large-block
mixing. This pattern can be dynamically varied to cover
arbitrary power-of-2 size blocks at ciphering time.

Source code is presented for bona fide informational or experimental purposes only: The mixing mechanism is protected by patent.

We start out by picturing the mixing of two elements by a single Balanced Block Mixing or BBM. In many cases this will take two byte values into two different byte values.

In the figure we have two vertical blue lines which just represent two element values flowing down through time. When a line is bare, the previous value is unchanged, but a yellow diamond indicates a value change.

Here there are two yellow diamonds, one on each line at the
same time, connected by a broad red line between them. The
yellow diamonds indicate a change in each value at a particular
point in time and the red line connects the two parts of a
single Balanced Block Mixing *pair*.

If we are mixing just two elements, there really is no wide
range of possibilities -- we just mix one with the other. But
when we have we have more elements, we have more possibilities.

Next we consider mixing *four* elements, again using the
fundamental two-element BBM mixing. Now we need *four*
mixing operations, where before we only needed one. Although we
might wish for a larger fundamental mixing operation which we
would apply only once, we are in fact developing the internal
process of making just such an operation.

If we have four elements to be mixed as *pairs,* one way
to start is by mixing the first two elements and also mixing the
second two elements. In this way, each of the first two element
values is made a balanced result of both of the first two inputs,
and each of the second two elements is made a balanced result
of the second two inputs. In hardware, these mixing operations
can occur simultaneously, and constitute what I call a mixing
*sublevel.*

The point of the mixing is to end up with values such that
each result value has been determined by each input value.
We can do this by mixing an element from the first pair with
an element from the second pair, and similarly mixing the
remaining element from each pair, in a second *sublevel.*

Here, the selection of what to mix with what can be made in
exactly two different ways, and if we just want *some*
balanced mixing, there is no particular reason to choose one
over the other. But some mixing patterns probably are a
little more transparent than others, and some may be a
little easier to automate.

Next we consider mixing *eight* elements, again using the
fundamental two-element BBM mixing. Now we need 3 sublevels of
4 mixing pairs each. Again note that, in hardware, the 4 mixings
in any sublevel can proceed simultaneously.

To develop a general algorithmic description of this process
it is reasonable to introduce the concept of a *group* of
pairs. In the first mixing sublevel, we have only one pair in
each of four groups. But in the second sublevel, we have two
pairs, and two groups. And in the third sublevel, we have four
pairs, and only one group.

We distinguish *pairs* and *groups* because they
involve different forms of indexing through the array of data.
Pairs start out separated by a value which is the number of
pairs in each group at that sublevel. In the first sublevel,
there is always one pair per group, and the first pair in the
first group is always [0,1]. Then we step each element by one
and, if we have done all pairs for that sublevel (and we always
will have, in the first sublevel), we step to the next group.

Once we have done a pair, we need to step across the width of the data affected by the pair to the next undone element. But if we have just done the previous group (and stepped beyond it), all we have to do is increment each element by the number of pairs per group for this sublevel. At the top sublevel, we have one pair per group, and so [1,2], the result after pair stepping, becomes [2,3], which is the next pair. Similarly, we find [4,5] and [6,7].

In the second sublayer, we have two pairs per group, so we start out with [0,2], which directly steps to the next pair in that group as [1,3]. At the end of the first group we have [2,4] which is transformed to [4,6] as the first pair of the second group. Then we find [5,7] as the second pair of the second group.

In the third sublayer, we have four pairs per group, and just one group. So we start out with [0,4] and step to [1,5], then [2,6] and [3,7], at which time we have done the pairs, groups, and sublayers and so are done.

Here we show a routine in Pascal for mixing blocks of arbitrary power-of-2 size as selected at ciphering time. Dynamic size selection supports, for example, the general use of large (say, 64 byte) blocks with an end-of-message step down using at most one of each lesser block size until we reach "legacy" 8-byte (DES-size) blocks.

Note that the simple Balanced Block Mixing computations are
included. Here we use the degree-8 polynomial 01a9h.

PROCEDURE ByFFTmix( VAR DatByAR; byct: WORD ); { FFT-style byte mixing of 2**n contiguous bytes } { undo ByFFTmix with ByFFTmix; a self-inverse } VAR dat: ByteArray ABSOLUTE DatByAR; pairs, groups, el1, el2, group, pair, t: WORD; BEGIN groups := byct DIV 2; pairs := 1; WHILE (groups > 0) DO BEGIN el1 := 0; el2 := el1 + pairs; FOR group := 0 TO PRED(groups) DO BEGIN FOR pair := 0 TO PRED(pairs) DO BEGIN t := dat[el1] XOR dat[el2]; { a + b } t := t + t; { 2a + 2b } IF ((t AND $100) <> 0) THEN t := t XOR $1a9; { 2a + 2b - p } dat[el1] := dat[el1] XOR t; { 3a + 2b } dat[el2] := dat[el2] XOR t; { 2a + 3b } Inc(el1); Inc(el2); END; Inc(el1,pairs); Inc(el2,pairs) END; groups := groups DIV 2; pairs := pairs + pairs; END; END; {ByFFTmix}

Here we show the same routine in C code for mixing blocks of arbitrary power-of-2 size as selected at ciphering time.

Note that the simple Balanced Block Mixing computations are
included. Here we use the degree-8 polynomial 01a9h. The
BYTE and WORD defines are as one might expect.

/* * FFT-style byte mixing of 2**n contiguous bytes * */ void ByFFTmix( BYTE dat[], WORD byct ) { WORD pairs, groups, group, pair; BYTE *d1, *d2, t; groups = byct >> 1; pairs = 1; while (groups) { d1 = dat; d2 = d1 + pairs; for (group = 0; group < groups; group++) { for (pair = 0; pair < pairs; pair++) { t = *d1 ^ *d2; if (t & 0x80) t = (t + t) ^ 0xa9; else t = t + t; *d1++ ^= t; *d2++ ^= t; } d1 += pairs; d2 += pairs; } groups >>= 1; pairs <<= 1; } }

We have developed a description and presented working routines in Pascal and C for a particular efficient FFT-style mixing pattern. This mixing pattern is used to extend byte-wide mixing across arbitrary power-of-2 size blocks.

It is also possible to consider patterns which may be re-used
without change in each sublevel. But the major issue in a Mixing
design is likely to be table storage, rather than mixing.
Consequently, having only a single mixing sublayer may not have
much of an effect on overall cost, but *will* constrain
throughput.

There may be slightly more efficient ways to code this standard mixing pattern. But as it stands it does drop into 80x86 assembly language fairly well. Unfortunately, byte-level processing is not a big advantage of 32-bit code.

*Last updated:* 1997-06-09