The use of Balanced Block Mixers is new in cryptography, as are one-way diffusion layers. Here we present description, figures, and routines in both Pascal and C for variable-size one-way diffusion layers using Balanced Block Mixing technology. These handle an arbitrary block size as selected at ciphering time.
Source code is presented for bona fide informational or experimental purposes only: The mechanism described is protected by patent.
Good data mixing is at the heart of block cipher design. Normally, we expect every input bit to be mixed into every output bit in some complex way. In Mixing ciphers based on Balanced Block Mixing (BBM) operations in FFT patterns, this can be achieved in log n sublevels of n operations each, but only for power-of-2 size blocks. In a Variable Size Block Cipher (VSBC), this is not good enough, because we want to handle blocks of dynamically arbitrary size, to the byte.
The original VSBC proposal chained data values across a block with exclusive-OR. This handled diffusion, and arbitrary block size, but may be easier to attack. Since the exclusive-OR operation produces just a single result, it is easier to externally manipulate by introducing two adjacent data values which "cancel" the diffusion. This immediately leads to establishing relationships between tables. Dynamic table selection may complicate this, but it is important to provide independent strength on multiple levels.
The BBM component seems better at resisting external manipulation, because if one of the data values is changed, there is no second data value which can cancel both outputs from the BBM. If we could assure that both outputs are sent across the block unchanged, we could guarantee that any input change whatsoever would produce overall diffusion. But because of the limited width of each diffusion channel, it is possible for diffusion to be canceled by chance. This is the reason for having multiple diffusion channels, and multiple diffusion mechanisms.
Here we have the schematic representation for the BBM operation described in other articles (e.g., the current BBM article). Basically, we have a two-input two-output operation which is invertible.
In particular we have the equations shown in the figure, computed in mod-2 polynomials with some appropriate irreducible p. We say the results are computed "mod-2, mod p".
There are two immediate consequences of this construction:
These consequences help us reason about the flow of diffusion
and the ability to attack the result.
Here we have a typical BBM one-way diffusion layer. We first note that the input block size (the number of data paths on the top) is the same as the output block size (the data paths on the bottom). Further, no Initial Values are required.
Basically, this particular layer collects the uniqueness present in the input, and transports across the block. Clearly, the amount of uniqueness transported is limited by the size of the diffusion path, here a single byte. But any uniqueness to the left will be carried across the full block if no other uniqueness intrudes. And if other uniqueness does intrude, we have transported the information up to that point, and the fact that we eventually exceed the information limits of the diffusion path may not matter.
Clearly, the amount of transported diffusion is limited by the
size of the diffusion path, which is ample reason to have multiple
diffusion layers.
Here we have the left-going analog to the right-going layer described above. This particular left-going diffusion layer is also the inverse of the earlier right-going diffusion layer. By feeding the output of the right-going layer into the left-going layer, we can "undo" what the first layer did. This of course gives us a way to build deciphering operations.
A full VSBC design is typically composed of multiple one-way
diffusion layers, plus confusion layers containing keyed "byte-wide"
substitution tables. The designer first has the task of seeing
that any uniqueness is transported to one side of the block.
Then the task is to move it back the other way, all the way to
the other end of the block. (Or, in other designs, perhaps
around again via an intermediate carry).
Here we show routines in Pascal for providing one-way diffusion across blocks of dynamically arbitrary size. Dynamic block size selection supports, for example, the general use of large (say, 64 byte) blocks until the end of the message, when perhaps two smaller blocks will be produced, without expanding the ciphertext.
Note that the simple Balanced Block Mixing computations are
part of the routine. Here we use the degree-8 polynomial 01a9h.
PROCEDURE BBMixRt( VAR buf; byct: WORD );
{ buf[0] -> c; BBM(c,[i]) -> [i-1],c; c -> [byct-1] }
{ undo BBMixRt with BBMixLt }
VAR
ba: ByteArray ABSOLUTE buf;
i, t: WORD;
a, b: BYTE;
BEGIN
IF (byct < 2) THEN Exit;
a := ba[0];
FOR i := 1 TO PRED(byct) DO
BEGIN
b := ba[i];
t := (a XOR b) Shl 1; { 2a + 2b }
IF ((t AND $100) <> 0) THEN
t := t XOR $1a9; { 2a + 2b - p }
ba[PRED(i)] := t XOR a; { 3a + 2b }
a := t XOR b; { 2a + 3b }
END;
ba[PRED(byct)] := a;
END; {BBMixRt}
PROCEDURE BBMixLt( VAR buf; byct: WORD );
{ buf[byct-1] -> c; BBM([i],c) -> c,[i+1]; c -> [0] }
{ undo BBMixLt with BBMixRt }
VAR
ba: ByteArray ABSOLUTE buf;
i, t: WORD;
a, b: BYTE;
BEGIN
IF (byct < 2) THEN Exit;
b := ba[PRED(byct)];
FOR i := byct-2 DOWNTO 0 DO
BEGIN
a := ba[i];
t := (a XOR b) Shl 1; { 2a + 2b }
IF ((t AND $100) <> 0) THEN
t := t XOR $1a9; { 2a + 2b - p }
ba[SUCC(i)] := t XOR b; { 2a + 3b }
b := t XOR a; { 3a + 2b }
END;
ba[0] := b;
END; {BBMixLt}
Here we show routines in C for providing one-way diffusion across blocks of dynamically arbitrary size.
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.
/*
* buf[0] -> c; BBM(c,[i]) -> [i-1],c; c -> [byct-1]
*
*/
void
BBMixRt( BYTE buf[], WORD byct )
{
WORD i;
BYTE *bp = buf, *sp = buf, a, b, t;
a = *bp++;
for (i = 1; i < byct; i++)
{
b = *bp++;
t = a ^ b;
if (t & 0x80)
t = (t + t) ^ 0xa9;
else
t = t + t;
*sp++ = t ^ a;
a = t ^ b;
}
*sp = a;
}
/*
* buf[0] -> c; BBM(c,[i]) -> [i-1],c; c -> [byct-1]
*
*/
void
BBMixLt( BYTE buf[], WORD byct )
{
WORD i;
BYTE *bp, *sp, a, b, t;
bp = sp = buf + byct -1;
b = *bp--;
for (i = 1; i < byct; i++)
{
a = *bp--;
t = a ^ b;
if (t & 0x80)
t = (t + t) ^ 0xa9;
else
t = t + t;
*sp-- = t ^ b;
b = t ^ a;
}
*sp = b;
}
We have developed a description and presented working routines in both Pascal and C for a particular efficient one-way diffusion.
There may be slightly more efficient ways to code this, although, 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-10