Block ciphers generally must mix each plaintext bit into each and every ciphertext bit, a result which is commonly called "diffusion." Most modern designs use a Feistel structure, in which diffusion is probabilistic and extended across the block by a series of repeated applications or "rounds." An alternative is to use small mixings, in FFT-like patterns, so each input is guaranteed to affect each output across the full width of the block, no matter how wide the block may be. The small mixings should be balanced, invertible, simple, and fit the "butterfly" model which is convenient for the FFT. This mixing is available in the orthogonal Latin squares of a Balanced Block Mixer or BBM.
The application of BBM's to invertible ciphering has been known since March 1994. From the beginning, these designs have used linear BBM's, but non linear BBM's also exist, and they can be dropped into the old designs for new cryptographic strength. Nonlinear BBM's can be constructed in a "checkerboard" process similar to that used to construct nonlinear Latin squares. A single 256-byte table can hold two orthogonal Latin squares of order 16, and is suitable for mixing 4-bit "nybbles." Two such tables, perhaps dynamically selected from an array, produce an 8-bit-wide mixing. And 8-bit mixings repeated in FFT-like patterns can mix entire blocks of huge size with practical effort and equal effect from every input.
These Mixing ciphers are scalable to small block size, and so can be investigated experimentally in ways most Feistel ciphers cannot. Hardware realizations consist almost entirely of tables, leading to extremely dense chips, high performance, and low-risk development. In software, the cipher block size can vary dynamically at ciphering time in "power-of-2" steps, thus supporting legacy 64-bit blocks, modern 128-bit blocks, and independent 64-byte blocks in the exact same unchanged program.
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt
Subject: Orthogonal Latin Squares, Nonlinear Balanced Block Mixers
Date: Tue, 22 Sep 1998 20:12:22 GMT
Lines: 658
Message-ID: <36080427.17744393@news.io.com>
ORTHOGONAL LATIN SQUARES, NONLINEAR BALANCED BLOCK MIXERS,
AND MIXING CIPHERS
Terry Ritter ritter@io.com
Ritter Software Engineering
http://www.io.com/~ritter/
1998-09-22
ABSTRACT
Block ciphers generally must mix each plaintext bit into each and
every ciphertext bit, a result which is commonly called "diffusion."
Most modern designs use a Feistel structure, in which diffusion is
probabilistic and extended across the block by a series of repeated
applications or "rounds." An alternative is to use small mixings,
in FFT-like patterns, so each input is *guaranteed* to affect each
output across the full width of the block, no matter how wide the
block may be. The small mixings should be balanced, invertible,
simple, and fit the "butterfly" model which is convenient for the
FFT. This mixing is available in the orthogonal Latin squares of
a Balanced Block Mixer or BBM.
The application of BBM's to invertible ciphering has been known since
March 1994. From the beginning, these designs have used *linear*
BBM's, but *non* linear BBM's also exist, and they can be dropped
into the old designs for new cryptographic strength. Nonlinear
BBM's can be constructed in a "checkerboard" process similar to that
used to construct nonlinear Latin squares. A single 256-byte table
can hold two orthogonal Latin squares of order 16, and is suitable
for mixing 4-bit "nybbles." Two such tables, perhaps dynamically
selected from an array, produce an 8-bit-wide mixing. And 8-bit
mixings repeated in FFT-like patterns can mix entire blocks of huge
size with practical effort and equal effect from every input.
These Mixing ciphers are scalable to small block size, and so can
be investigated experimentally in ways most Feistel ciphers cannot.
Hardware realizations consist almost entirely of tables, leading to
extremely dense chips, high performance, and low-risk development.
In software, the cipher block size can vary dynamically at ciphering
time in "power-of-2" steps, thus supporting legacy 64-bit blocks,
modern 128-bit blocks, and independent 64-byte blocks in the exact
same unchanged program.
BALANCED BLOCK MIXING
In early 1994 I had the honor to introduce to cryptography an
alternative to the Feistel structure for mixing in block ciphers,
which I now call "Balanced Block Mixing." (See the original article:
http://www.io.com/~ritter/NEWS/94031301.HTM
and the modern summary:
http://www.io.com/~ritter/BBM.HTM ).
These mixing structures typically take two values, mix them, and
produce two values as a result.
A Balanced Block Mixer is an m-input-port m-output-port mechanism
with various properties:
1. The overall mapping is one-to-one and invertible: Every
possible input value (over all ports) to the mixer produces
a different output value (including all ports), and every
possible output value is produced by a different input value;
2. Each output port is a function of every input port;
3. Any change to any one of the input ports will produce a change
to every output port;
4. Stepping any one input port through all possible values (while
keeping the other input ports fixed) will step every output
port through all possible values.
A Feistel structure may have similar guarantees, provided the "f"
function is an invertible substitution. But the "f" function is
half a block wide, compared to byte-wide BBM functions expanded by
FFT-like mixing patterns. And in a Feistel structure, for any one
round, both the input to "f" and the changes produced by "f" are
exposed in the output; in contrast, BBM's hide their input values.
Feistel structures often use a fixed and known "f" function, which
is thus open to extensive analysis, whereas Mixing designs generally
use keyed tables and now keyed BBM's as well.
BBM's have been described in various ciphering constructions. (See
the articles at:
http://www.io.com/~ritter/CRYPHTML.HTM#BBMTech ).
The previous work has assumed one or another form of *linear*
Balanced Block Mixing. But it is possible to construct *non*linear
BBM's with these *same* *mixing* *properties*. This means that
nonlinear BBM's can directly replace linear BBM's in earlier Mixing
cipher constructions (provided attention is paid to mixing order to
allow reversibility).
A TYPICAL MIXING CIPHER
In figure 1 we have a typical Mixing cipher in schematic form, with
3 "fencing" layers of 8 invertible substitutions each, and two full
"FFT-style" mixings between them. If these are 8-bit substitutions,
we have a 64-bit block cipher. Each substitution (and now each
mixing operation also) is individually keyed.
The vertical dotted lines represent typically 8-bit-wide data paths,
and the data flow is from top to bottom. Each S is a substitution
table, and *--* represents the "butterfly" action of a single BBM.
For 8 elements we have log2(8) = 3 mixing FFT sublayers (Mix0, Mix1,
Mix2) of 8/2 = 4 BBM operations each. All BBM's in the same sublayer
are independent and can occur simultaneously in parallel hardware.
The wider the block, the more BBM's needed, which also means that
more computation can occur simultaneously.
| A 64-Bit Mixing Cipher Fig. 1
|
| : : : : : : : : <- Input Block
| S S S S S S S S <- Fencing
| : : : : : : : :
| *---* *---* *---* *---* Mix0 0..0, 0..3
| : : : : : : : :
| *-------* : *-------* : Mix1 0..0, 0..1
| : *-------* : *-------* Mix1 1..1, 0..1
| : : : : : : : :
| *---------------* : : : Mix2 0..0, 0..0
| : *---------------* : : Mix2 1..1, 0..0
| : : *---------------* : Mix2 2..2, 0..0
| : : : *---------------* Mix2 3..3, 0..0
| : : : : : : : :
| S S S S S S S S <- Fencing
| : : : : : : : :
| *---------------* : : :
| : *---------------* : :
| : : *---------------* :
| : : : *---------------*
| : : : : : : : :
| *-------* : *-------* :
| : *-------* : *-------*
| : : : : : : : :
| *---* *---* *---* *---*
| : : : : : : : :
| S S S S S S S S <- Fencing
| : : : : : : : : <- Output Block
Each of the mixing BBM's uses an orthogonal pair of Latin squares.
If these are nonlinear, we must of course process the FFT-style
"sublayers" in reverse order when deciphering. So if we use the
opposite orders in the top and bottom mixing sections, we can use
the exact same structure for both enciphering and deciphering; only
the table contents then need be changed.
While Mixing cipher interconnections can seem similar to
substitution-permutation (S-P) designs, Mixing ciphers propagate
full-width diffusion from and to every component instead of using
one-bit connections iterated over multiple rounds. Because mixing
designs have diffusion guarantees, iterative rounds are neither
used nor needed. An entire Mixing cipher may consist of tables,
with no random logic, no exclusive-OR's, and no "rounds" at all.
(In practice, we would need multiplexers and write timing to load
the tables from external data, then read them back for testing,
but speed would not be an issue in those data paths.)
LATIN SQUARES
A "Latin square" of "order n" is an n x n array of n distinct
symbols, in which each symbol occurs exactly once in each row and
also exactly once in each column, as shown in figure 2.
| The Standard Latin Squares of Order 4 Fig. 2
|
| a) 0 1 2 3 b) 0 1 2 3 c) 0 1 2 3 d) 0 1 2 3
| 1 2 3 0 1 3 0 2 1 0 3 2 1 0 3 2
| 2 3 0 1 2 0 3 1 2 3 1 0 2 3 0 1
| 3 0 1 2 3 2 1 0 3 2 0 1 3 2 1 0
Each Latin square can be seen as a combiner of row and column values,
and as a generalization of exclusive-OR. (For more background, see
the previous article:
http://www.io.com/~ritter/ARTS/PRACTLAT.HTM
or the Latin square literature survey:
http://www.io.com/~ritter/RES/LATSQ.HTM ).
ORTHOGONAL LATIN SQUARES
Two Latin squares can be superimposed so that each element consists
of an ordered pair of symbols, one from each square. If no ordered
pair occurs twice, the squares are "orthogonal."
| An Othogonal Pair of Order 4 Fig. 3
|
| 0 1 2 3 0 1 2 3 00 11 22 33
| 1 0 3 2 3 2 1 0 = 13 02 31 20
| 2 3 0 1 1 0 3 2 21 30 03 12
| 3 2 1 0 2 3 0 1 32 23 10 01
In orthogonal Latin squares, each of the n*n possible ordered pairs
of symbols occurs exactly once. So if we know a particular symbol
pair, we can identify the row and column to which they belong, and
so reverse the transformation. There are no orthogonals of order 2,
so there can be no exclusive-OR analogy to orthogonal combining.
There are exactly 576 Latin squares of order 4, so there are
576 * 576 or 331,776 possible pairs which might be orthogonal. Of
these, only 6912 pairs actually are orthogonal. If we then reduce
every square of every orthogonal pair to standard form, we find that
they all reduce to exactly the same standard square, the one shown
in figure 4.
| The Standard Square for All Order 4 Orthogonals Fig. 4
|
| d) 0 1 2 3
| 1 0 3 2
| 2 3 0 1
| 3 2 1 0
This order-4 standard square generates 144 permuted squares, and
each of these has exactly 48 orthogonal partners. So if we take
one square at random, the probability of the next random square
being orthogonal to the first is exactly 1/3.
One way to construct an orthogonal pair at order 4 is to first build
a randomized Latin square, by starting with standard square (d) and
shuffling rows, columns, and symbols. Then we build other squares
repeatedly, in the same way, until some pair is orthogonal.
ORTHOGONAL CHECKERBOARD CONSTRUCTION
The earlier article, "Practical Latin Square Combiners,"
( http://www.io.com/~ritter/ARTS/PRACTLAT.HTM )
described a "checkerboard" construction for large nonlinear Latin
squares. Basically, we start with some square and replace each
symbol with a full Latin square. We use different symbol sets for
these small squares and so produce a valid larger Latin square.
A similar process applies to orthogonal pairs of Latin squares: To
make the larger pair Latin, we can provide a different "offset" for
the small squares in any row or column. The pattern of this offset
is itself an orthogonal pair of Latin squares, so for offsets we
can simply multiply the elements of some pair by the order of the
squares, as shown in figure 5.
| The Construction of Orthogonal Offset Values Fig. 5
|
| 0 1 2 3 0 1 2 3 00 11 22 33 00 44 88 cc
| 1 0 3 2 3 2 1 0 = 13 02 31 20 * 4 = 4c 08 c4 80
| 2 3 0 1 1 0 3 2 21 30 03 12 84 c0 0c 48
| 3 2 1 0 2 3 0 1 32 23 10 01 c8 8c 40 04
We can take 16 orthogonal pairs of order 4, and arrange them to
produce a larger pair of order 16, using the previously-computed
offset values, as shown in figure 6.
| The Orthogonal Checkerboard Fig. 6
|
| 00+00 11 22 33 44+00 11 22 33 88+00 11 22 33 cc+00 11 22 33
| 13 02 31 20 13 02 31 20 13 02 31 20 13 02 31 20
| 21 30 03 12 21 30 03 12 21 30 03 12 21 30 03 12
| 32 23 10 01 32 23 10 01 32 23 10 01 32 23 10 01
|
| 4c+00 11 22 33 08+00 11 22 33 c4+00 11 22 33 80+00 11 22 33
| 13 02 31 20 13 02 31 20 13 02 31 20 13 02 31 20
| 21 30 03 12 21 30 03 12 21 30 03 12 21 30 03 12
| 32 23 10 01 32 23 10 01 32 23 10 01 32 23 10 01
|
| 84+00 11 22 33 c0+00 11 22 33 0c+00 11 22 33 48+00 11 22 33
| 13 02 31 20 13 02 31 20 13 02 31 20 13 02 31 20
| 21 30 03 12 21 30 03 12 21 30 03 12 21 30 03 12
| 32 23 10 01 32 23 10 01 32 23 10 01 32 23 10 01
|
| c8+00 11 22 33 8c+00 11 22 33 40+00 11 22 33 04+00 11 22 33
| 13 02 31 20 13 02 31 20 13 02 31 20 13 02 31 20
| 21 30 03 12 21 30 03 12 21 30 03 12 21 30 03 12
| 32 23 10 01 32 23 10 01 32 23 10 01 32 23 10 01
Now we do the sums in hex and get the results shown in figure 7.
| The Orthogonal Checkerboard Result Fig. 7
|
| 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
| 13 02 31 20 57 46 75 64 9b 8a b9 a8 df ce fd ec
| 21 30 03 12 65 74 47 56 a9 b8 8b 9a ed fc cf de
| 32 23 10 01 76 67 54 45 ba ab 98 89 fe ef dc cd
|
| 4c 5d 6e 7f 08 19 2a 3b c4 d5 e6 f7 80 91 a2 b3
| 5f 4e 7d 6c 1b 0a 39 28 d7 c6 f5 e4 93 82 b1 a0
| 6d 7c 4f 5e 29 38 0b 1a e5 f4 c7 d6 a1 b0 83 92
| 7e 6f 5c 4d 3a 2b 18 09 f6 e7 d4 c5 b2 a3 90 81
|
| 84 95 a6 b7 c0 d1 e2 f3 0c 1d 2e 3f 48 59 6a 7b
| 97 86 b5 a4 d3 c2 f1 e0 1f 0e 3d 2c 5b 4a 79 68
| a5 b4 87 96 e1 f0 c3 d2 2d 3c 0f 1e 69 78 4b 5a
| b6 a7 94 85 f2 e3 d0 c1 3e 2f 1c 0d 7a 6b 58 49
|
| c8 d9 ea fb 8c 9d ae bf 40 51 62 73 04 15 26 37
| db ca f9 e8 9f 8e bd ac 53 42 71 60 17 06 35 24
| e9 f8 cb da ad bc 8f 9e 61 70 43 52 25 34 07 16
| fa eb d8 c9 be af 9c 8d 72 63 50 41 36 27 14 05
The result in figure 7 is a orthogonal pair of Latin squares of
order 16 which exhibits massive structure at all levels. In practice
we would select each of the 17 constructing pairs at random, and
would also permute the rows, columns, and symbols in the resulting
order 16 squares. This will produce a reversible discrete combining
function which is inherently balanced, and which is just one of a
myriad of such functions.
Keyspace
We use order-4 orthogonal Latin squares to build an order-16 Latin
square. We do this by selecting from among the 6912 orthogonal pairs
for each of 16 positions and the offset square. This is 6912**17
choices which is about 10**65 or 216 bits. Then we shuffle the
resulting order-16 square in 16!*15! ways which is about 10**25 or
84 bits. This is a total keyspace of about 300 bits per constructed
order-16 orthogonal Latin square. In general we will construct and
use an array of such squares.
It should be unnecessary to point out that this keyspace does not
represent the "strength" of the nonlinear BBM structure, but instead
generally describes the extent to which the resulting 256 bytes of
data are unknown. The similar description for an 8-bit substitution
table -- with the same amount of data -- is about 1684 bits, and
similarly does not represent "strength," unless the table is so well
isolated that the precisely correct table can only be found by trial
and error.
NONLINEARITY
Boolean Function Nonlinearity
One of the forms of strength in a block cipher is an inability to
extrapolate from known parts of the transformation (known plaintext)
to model or approximate the transformation at other points (message
ciphertexts). Boolean function nonlinearity measures the ability
to do such modeling -- for any bit of the result -- based on linear
functions. This is a good thing to measure, because the checkerboard
construction presumably could have some unnoticed linear structure
that could affect the cipher. And nonlinearity measurement can be
applied to permutations of reasonable size, including both tables
and ciphers.
(Another form of strength is a lack of correlation between key and
transformation. Since Mixing ciphers generally use a separate
user-key processing and table-shuffling system, the user key itself
is well isolated. But correlation between the cipher transformation
and table contents is of course an issue in any construction which
uses small tables. It is not yet clear how to measure this or any
related quantity.)
Specifically, a function is called "Boolean" when it produces just
a single result bit. When a permutation is represented in binary,
each bit-position can be seen as a different Boolean function.
Each of these can be analyzed to find the number of bits which differ
between that function and each possible "affine" function. Then the
smallest value is the distance in bits to the closest "linear"
function. (For an active measurement tool, see:
http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM ).
We can experimentally measure the extent to which 8-bit ciphering
constructs, based on 4-bit tables and mixings, have the same
nonlinearity distribution as random 8-bit tables. The experiments
will consist of trials of 10,00 constructions each. The reference
distribution (taken from the nonlinearity measurements of a single
run of 1,000,000 random tables) is shown in figure 8.
| Nonlinearity Distribution of 8-Bit Tables Fig. 8
|
| 0.35 | *
| 0.3 | *
| 0.25 | * *
| 0.2 | * * *
| 0.15 | * * *
| 0.1 | * * * *
| 0.05 | * * * * * *
| 0.00 | * * * * * * * * * * * *
| Prob +--+--+--+--+--+--+--+--+--+--+--+--+--
| 84 88 92 96 100 104 Nonlinearity
The first component is a keyed or "random" 4-bit invertible
substitution table. But 4-bit tables are very, very weak, as shown
in figure 9.
| Nonlinearity Distribution of 4-Bit Tables Fig. 9
|
| 0.6 |
| 0.5 | * *
| 0.4 | * *
| 0.3 | * *
| 0.2 | * *
| 0.1 | * *
| 0.0 | * * *
| Prob +--+--+--+--
| 0 2 4 Nonlinearity
When we place two 4-bit tables across, we do get the higher values
of figure 10, but still only 3 different values. Each of these is
exactly 16 times the values from figure 9. This appears to be the
effect of repeating a table 16 times, which is what happens with
this two-table-wide construction.
| NL Dist. of Two 4-Bit Tables Across 8 Bit Width Fig. 10
|
| 0.7 | *
| 0.6 | *
| 0.5 | *
| 0.4 | *
| 0.3 | * *
| 0.2 | * *
| 0.1 | * *
| 0.0 | * * *
| Prob +--+--//--+--//--+--
| 0 32 64 Nonlinearity
The other component is a 4-bit keyed BBM constructed by checkerboard
techniques, and producing the nonlinearity distribution of figure 11.
| Nonlinearity of Single Nybble Mixing Fig. 11
|
| 0.45 | *
| 0.40 | *
| 0.35 | *
| 0.3 | * *
| 0.25 | * *
| 0.2 | * *
| 0.15 | * * *
| 0.1 | * * *
| 0.05 | * * * *
| 0.00 | * * * * * * * * * *
| Prob +--+--+--+--+--+--+--+--+--+--+--+--+--+--
| 60 68 76 84 92 100 Nonlinearity
This is already much nicer than the relatively simple structure
from the tables, so one wonders what two such mixings would
look like, and the answer is in figure 12.
| Nonlinearity of Two Sequential Nybble Mixings Fig. 12
|
| 0.35 | *
| 0.3 | *
| 0.25 | * *
| 0.2 | * * *
| 0.15 | * * * *
| 0.1 | * * * *
| 0.05 | * * * *
| 0.00 | * * * * * * * * * * * *
| Prob +--+--+--+--+--+--+--+--+--+--+--+--+--
| 84 88 92 96 100 104 Nonlinearity
Figure 12 is not quite the ideal distribution of figure 8, but
it is getting close. And if we put a pair of substitution tables
between the mixings, we can get much closer, as shown in figure 13.
| Nonlinearity Distribution of Mix Sub Mix Fig. 13
|
| 0.35 | *
| 0.3 | *
| 0.25 | * *
| 0.2 | * * *
| 0.15 | * * *
| 0.1 | * * * *
| 0.05 | * * * * * *
| 0.00 | * * * * * * * * * * * *
| Prob +--+--+--+--+--+--+--+--+--+--+--+--+--
| 84 88 92 96 100 104 Nonlinearity
At this point we are beyond what a crude diagram can do, so we
enter the realm of numbers, in figure 14.
| Nonlinearity of Mix Sub Mix Fig. 14
|
| NL Expect Got ChiSq Sum df
| 84: 1 3 }
| 86: 4 3 }
| 88: 13 18 2.000 } 2.000 0
| 90: 46 62 5.565 7.565 1
| 92: 150 187 9.127 16.692 2
| 94: 450 492 3.920 20.612 3
| 96: 1172 1240 3.945 24.557 4
| 98: 2474 2478 0.006 24.564 5
| 100: 3412 3337 1.649 26.212 6
| 102: 2027 1972 1.492 27.705 7
| 104: 249 206 7.426 }
| 106: 2 2 7.367 } 35.071 8
This is a typical chi-squared evaluation of "closeness of fit" for
this test situation. Normally we expect a chi-squared result of
something like the "degrees of freedom" or df, from perhaps half the
df to three times the df. Here 35 is high, the distributions differ
significantly, and this is typical.
When we add substitutions on the outside of that structure, we
do not do much better, as shown in figure 15.
| Nonlinearity of Sub Mix Sub Mix Sub Fig. 15
|
| NL Expect Got ChiSq Sum df
| 84: 1 2 }
| 86: 4 4 }
| 88: 13 13 0.056 } 0.056 0
| 90: 46 58 3.130 3.186 1
| 92: 150 189 10.140 13.326 2
| 94: 450 471 0.980 14.306 3
| 96: 1172 1235 3.387 17.693 4
| 98: 2474 2592 5.628 23.321 5
| 100: 3412 3325 2.218 25.539 6
| 102: 2027 1896 8.466 34.005 7
| 104: 249 213 5.205 }
| 106: 2 2 5.163 } 39.169 8
This is another typical result. But if we add yet another mixing
layer and substitution layer, we can get very close indeed, as
shown in figure 16.
| Nonlinearity of Sub Mix Sub Mix Sub Mix Sub Fig. 16
|
| NL Expect Got ChiSq Sum df
| 84: 1 0 }
| 86: 4 3 }
| 88: 13 14 0.056 } 0.056 0
| 90: 46 54 1.391 1.447 1
| 92: 150 134 1.707 3.154 2
| 94: 450 483 2.420 5.574 3
| 96: 1172 1185 0.144 5.718 4
| 98: 2474 2436 0.584 6.301 5
| 100: 3412 3436 0.169 6.470 6
| 102: 2027 2004 0.261 6.731 7
| 104: 249 251 0.016 }
| 106: 2 0 0.000 } 6.731 8
The chi-squared result from figure 16 has a probability of about
43 percent. This means that, if the two distributions are the
same, we should get a chi-squared sum of 6.731 or lower about
43 times out of 100, on average. So we need to run this test a
few times.
Figure 17 gives various "critical values" for df = 8, including
the percentages that allow us to group results by quarter.
| Chi-Square Percentages for DF = 8 Fig. 17
|
| 1% 5% 95% 99%
| 1.647 2.733 15.507 20.090
|
| 25% 50% 75%
| 5.071 7.344 10.219
In figure 18 we group 20 contiguous trials by probability quarter.
| NL ChiSq for Sub Mix Sub Mix Sub Mix Sub; df = 8 Fig. 18
|
| Q1 Q2 Q3 Q4
| 3.774 5.918 8.083 10.896
| 3.033 5.650 7.876 10.285
| 4.950 5.492 7.691 11.897
| 3.895 5.365
| 4.978 6.634
| 2.978 5.695
| 6.861
| 6.746
The results in figure 18 seem reasonable: Nothing is suspiciously
high, or low. There are more low values than high ones, but we
expect variability in these tests of random constructions. The major
implication is that the two distributions (the reference distribution
taken from random 8-bit tables, and the distribution measured from
the constructed 8-bit block cipher) are not significantly different.
This is experimental evidence in favor of Mixing cipher construction
using nonlinear BBM's.
CONCLUSIONS
With respect to Boolean function nonlinearity, these 8-bit Mixing
constructions do not differ significantly from the ideal of random
8-bit tables. So in this sense we have succeeded in simulating an
8-bit table using a Mixing construction based on 4-bit tables and
4-bit BBM components.
These results are entirely consistent with the original experiments
using linear BBM's (see
http://www.io.com/~ritter/ARTS/MIXNONLI.HTM ).
Those experiments also needed 3 mixings to achieve the reference
distribution with 4-bit tables. But further experiments with 5-bit
tables and a 10-bit block achieved a good distribution in just 2
mixings. This implied that the need for the additional layers was
due to the weakness of the 4-bit tables, and not the Mixing
construction itself.
The checkerboard process can efficiently construct keyed, nonlinear,
Balanced Block Mixers of substantial size. Because these BBM's
retain all the mixing properties of linear BBM's, they can directly
replace the linear versions in earlier designs (perhaps with some
processing-order changes) for increased strength.
---
Terry Ritter ritter@io.com http://www.io.com/~ritter/
Crypto Glossary 1998-08-27: http://www.io.com/~ritter/GLOSSARY.HTM
Terry Ritter, his current address, and his top page.
Last updated: 1998-09-23