Nonlinear Balanced Block Mixers,

and Mixing Ciphers

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.

- 1998-09-22 Terry Ritter: Orthogonal Latin Squares, Nonlinear BBM's, the original article.

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