The strengthless exclusive-OR combiner often used in stream ciphers can be replaced by a keyed, nonlinear Latin square. The unknown state in a Latin square combiner adds strength by hiding the stream cipher "confusion sequence" or "running key" from a known-plaintext attack. The 64K of store normally needed by an "8-bit" Latin square combiner working on byte values can be reduced to 128 bytes by instead working on 4-bit "nybbles." Nonlinear Latin squares of the necessary size can be constructed in a "checkerboard" process of replacing Latin square elements with whole Latin squares and adjusting their symbol sets.

- 1998-09-16 Terry Ritter: Practical Latin Square Combiners, the original article.
- 1998-09-16 Terry Ritter: Correction to Figure 2.
- 1998-09-18 Pierre Abbat: Three other ways to transform one Latin square into another....

From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Practical Latin Square Combiners Date: Wed, 16 Sep 1998 03:28:00 GMT Organization: Illuminati Online Lines: 476 Message-ID: <35ff2fec.12158768@news.io.com> PRACTICAL LATIN SQUARE COMBINERS Terry Ritter ritter@io.com Ritter Software Engineering http://www.io.com/~ritter/ 1998-09-15 ABSTRACT The strengthless exclusive-OR combiner often used in stream ciphers can be replaced by a keyed, nonlinear Latin square. The unknown state in a Latin square combiner adds strength by hiding the stream cipher "confusion sequence" or "running key" from a known-plaintext attack. The 64K of store normally needed by an "8-bit" Latin square combiner working on byte values can be reduced to 128 bytes by instead working on 4-bit "nybbles." Nonlinear Latin squares of the necessary size can be constructed in a "checkerboard" process of replacing Latin square elements with whole Latin squares and adjusting their symbol sets. INTRODUCTION 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 and column. See figure 1: | A Latin Square of Order 4 Fig. 1 | | 0 1 2 3 | 1 2 3 0 | 2 3 0 1 | 3 0 1 2 The particular square in figure 1 is "cyclic," in the sense that each row below the top is a rotated version of the row above it. This is a common way to produce Latin squares, but is generally undesirable for cryptography, since the resulting squares are very predictable. Latin Square Combining Stream cipher data and confusion can be combined in a Latin square: one value selects a row, the other selects a column, and the result is the selected element. If the confusion sequence selects columns, the transformation can be reversed in another Latin square which has as its columns the inverse of each column in the original square. A Latin square is an example of "balanced" combining in that every output value occurs with the same probability. Any particular output value can be produced by any value on one input, with some value on the other input. This is the same sort of combining produced by exclusive-OR, but with a large alphabet and the opportunity to have complexity and nonlinearity in the combiner itself. (There are no nonlinear exclusive-OR's.) If the combiner has substantial keyed state, known-plaintext does not immediately expose the confusion sequence as it would with an exclusive-OR combiner. Standard Form In any Latin square, the rows can be re-arranged and the result will also be a Latin square. The columns also can be re-arranged. So any Latin square can be arranged into a "standard form," where symbols occur in order across the top row and down the left column. The 576 squares of order 4 reduce to the 4 standard squares in figure 2: | The Standard Latin Squares of Order 4 Fig. 2 | | 0 1 2 3 0 1 2 3 0 1 2 3 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 0 1 2 3 0 1 | 3 0 1 2 3 2 1 0 3 2 0 1 3 2 1 0 SHUFFLING LATIN SQUARES A Latin square of order n can be shuffled into n!(n-1)! different squares: we can permute the n rows in n! ways, and then, with one column fixed, we can permute the remaining columns in (n-1)! ways. We can also permute the symbols, but this will produce no new squares. We cannot obtain all possible squares of some size simply by shuffling a single Latin square. A Latin square of order 4 can be permuted in 4!3! ways, thus producing 144 different squares, but there are 576 squares at order 4. All 576 squares can be produced by shuffling the 4 different squares of standard form. The obvious way to shuffle squares is to simulate the structure of the square, and then move whole rows and columns according to the usual shuffle process. An alternative is to shuffle tables which represent the row order, column order, and element order, and then construct the square indirectly through these transformations. THE CHECKERBOARD CONSTRUCTION One way to construct a larger square is to take some Latin square and replace each of the symbols with a full Latin square. By giving the replacement squares different symbol sets, we can arrange for symbols to be unique in each row and column, and so produce a Latin square of larger size. If we consider squares with numeric symbols, we can give each replacement square an offset value, which is itself determined by a Latin square. We can obtain offset values by multiplying the elements of a square by its order, as in figure 3: | The Construction of Offset Values Fig. 3 | | 0 1 2 3 0 4 8 12 | 1 2 3 0 * 4 = 4 8 12 0 | 2 3 0 1 8 12 0 4 | 3 0 1 2 12 0 4 8 We can use the same original square for all of the replacement squares, as in figure 4: | The Checkerboard Construction Fig. 4 | | 0+ 0 1 2 3 4+ 0 1 2 3 8+ 0 1 2 3 12+ 0 1 2 3 | 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 | 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 | 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 | | 4+ 0 1 2 3 8+ 0 1 2 3 12+ 0 1 2 3 0+ 0 1 2 3 | 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 | 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 | 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 | | 8+ 0 1 2 3 12+ 0 1 2 3 0+ 0 1 2 3 4+ 0 1 2 3 | 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 | 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 | 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 | | 12+ 0 1 2 3 0+ 0 1 2 3 4+ 0 1 2 3 8+ 0 1 2 3 | 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 | 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 | 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 which produces the order-16 square of figure 5: | The Checkerboard Result Fig. 5 | | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 1 2 3 0 5 6 7 4 9 10 11 8 13 14 15 12 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 | 3 0 1 2 7 4 5 6 11 8 9 10 15 12 13 14 | | 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 | 5 6 7 4 9 10 11 8 13 14 15 12 1 2 3 0 | 6 7 4 5 10 11 8 9 14 15 12 13 2 3 0 1 | 7 4 5 6 11 8 9 10 15 12 13 14 3 0 1 2 | | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 | 9 10 11 8 13 14 15 12 1 2 3 0 5 6 7 4 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 | 11 8 9 10 15 12 13 14 3 0 1 2 7 4 5 6 | | 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 | 13 14 15 12 1 2 3 0 5 6 7 4 9 10 11 8 | 14 15 12 13 2 3 0 1 6 7 4 5 10 11 8 9 | 15 12 13 14 3 0 1 2 7 4 5 6 11 8 9 10 Clearly, this Latin square exhibits massive structure at all levels. But in practice we would use a different order-4 table for each position, and yet another for the offsets. We would also shuffle all rows, columns, and symbols in the larger square. Keyspace There are 576 Latin squares of order 4, any one of which can be used as any of the 16 replacement squares. The offset square is another order-4 square. So we can construct 576**17 (about 8 x 10**46 or 2**155) different squares of order 16 in this way. Then we can shuffle the resulting square in 16! * 15! (about 2 x 10**25 or 2**84) different ways, thus producing about 2 x 10**72 squares, for about 240 bits of keying per square. (Even if we restrict ourselves to using only the 144 order-4 squares formed by shuffling a single standard square, we still have a 206-bit keyspace.) We could store two of the resulting order-16 squares in a 256-byte table for use in an "8 bit" combiner, and might even select a combiner dynamically from an array of such tables. RANDOM SQUARES VERSUS CONSTRUCTED SQUARES We would like to be able to compare the "checkerboard" construction to a "random" construction. Unfortunately, it is not at all clear what a random Latin square construction would be. Various complex ad hoc techniques can construct squares, *apparently* "at random," but so many squares are possible (there may be 2**339 different Latin squares of order 16) that it is difficult to know whether we really have a flat distribution or not. But we can compare construction techniques by defining an appropriate quality and then measuring that quality across large numbers of squares from each different construction. Here we have the "checkerboard" construction and a very complex "ad hoc" construction, and a reasonable quality to measure might be "Boolean function nonlinearity." Boolean Function Nonlinearity 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 function can be analyzed to find the number of bits which differ between that function and each possible "affine" function. The smallest value is the distance in bits to the closest "linear" function, and so is one view of "strength." (For an active measurement tool, see: http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM ). Nonlinearity in Latin Squares Since each Latin square consists of symbols in some permutation in each row and column, we can apply a Boolean function nonlinearity measurement to each row and column. But permutations in "small" Latin squares are very weak. An order 4 square has permutations only 4 elements long, and *all* of these are actually *linear*. While the situation is somewhat better at order 16, these are still very small permutations with a maximum nonlinearity of 4. When we measure the 16 rows and 16 columns of a Latin square of order 16, it is common for at least one of these to be linear. So if we take the minimum value over all 128 Boolean functions (16 rows plus 16 columns of 4 bits each), we will occasionally get a result of zero, often 2 and very rarely 4 (in balanced functions, Boolean nonlinearity values are always even). This is not much range for use in establishing similarity in distributions. As an alternative, I collect *both* the minimum value *and* the sum of the nonlinearities for each permutation. So for an order-16 Latin square, we have the sum of the nonlinearities for 32 different permutations. This means that the many squares with an overall minimum nonlinearity of 2 can be distinguished. Further, this is a discrete distribution with a reasonable range, and two such distributions can be compared by standard chi-square techniques. Note that Latin square nonlinearity is not directly comparable to single-permutation nonlinearity, and neither of these is an overall "strength" value: Nonlinearity is just one of the many faces of strength. And even a nonlinearity of zero is still a selection from among the various linear functions and their complements. Each row and each column will be just such a selection. Order-16 Latin squares are small (128-byte tables for mixing 4-bit nybbles) and vastly weaker than a full 64K table for mixing bytes directly. But these tables are only part of cipher strength, and the smaller tables are faster to set up and more easily support dynamic selection from among an array of such tables. MEASURED LATIN SQUARE NONLINEARITY The ad hoc construction was used to develop a reference distribution. This involved (only) two trials of 1,000,000 squares each, with the reference value being the mean of the two counts found. Here we compare *both* the "checkerboard" *and* the "ad hoc" experimental distributions to those reference expectations. Ideally we would find that each checkerboard trial would represent a modest variation about the expected value, but this turns out to not be the case. Here we have two of the worse examples. In the first bad example (figure 6), we see over half again as many low-range nonlinearities as expected at a NL of 84 or less (34 instead of 20, out of 1000), and a similar excess at NL 108 (36 instead of 24): | Nonlinearity for 1000 Checkerboard Constructions Fig. 6 | | NL Expect Got ChiSq Sum df | 76: 0 1 } | 78: 1 1 } | 80: 2 1 } | 82: 5 13 } | 84: 12 18 } 9.800 9.800 0 | 86: 23 19 0.696 10.496 1 | 88: 41 46 0.610 11.105 2 | 90: 65 51 3.015 14.121 3 | 92: 92 84 0.696 14.816 4 | 94: 117 115 0.034 14.851 5 | 96: 132 142 0.758 15.608 6 | 98: 134 121 1.261 16.869 7 | 100: 121 112 0.669 17.539 8 | 102: 98 96 0.041 17.580 9 | 104: 70 65 0.357 17.937 10 | 106: 44 50 0.818 18.755 11 | 108: 24 36 6.000 24.755 12 | 110: 12 13 } | 112: 5 11 } | 114: 2 4 } | 116: 1 0 } | 118: 0 1 } 4.050 28.805 13 But in the second bad example (figure 7), the problem is confined to an NL of 108: | Nonlinearity for 1000 Checkerboard Constructions Fig. 7 | | NL Expect Got ChiSq Sum df | 78: 1 1 } | 80: 2 3 } | 82: 5 8 } | 84: 12 14 } 1.800 1.800 0 | 86: 23 20 0.391 2.191 1 | 88: 41 51 2.439 4.630 2 | 90: 65 64 0.015 4.646 3 | 92: 92 95 0.098 4.744 4 | 94: 117 110 0.419 5.162 5 | 96: 132 114 2.455 7.617 6 | 98: 134 117 2.157 9.774 7 | 100: 121 116 0.207 9.980 8 | 102: 98 101 0.092 10.072 9 | 104: 70 71 0.014 10.086 10 | 106: 44 51 1.114 11.200 11 | 108: 24 40 10.667 21.867 12 | 110: 12 14 } | 112: 5 7 } | 114: 2 3 } | 116: 1 0 } 0.800 22.667 13 In this case both "bad" distributions do have a high count for NL 108, which is common, although by no means universal. Other than this, there seem to be no clear patterns. If we collect the chi-square results for 20 trials of 1000 constructions each in 25% probability ranges, we might hope to detect systematic problems. In figures 8 through 12 we see two groups each for both the "ad hoc" and "checkerboard" constructions: | Chi-Square Percentages for DF = 13 Fig. 8 | | 25% 50% 75% | 9.299 12.340 15.984 | Checkerboard Chi-Square 1K Trials; df = 13 Fig. 9 | | Q1 Q2 Q3 Q4 | 3.484 12.053 13.134 19.457 | 6.289 11.341 13.195 17.630 | 6.937 10.785 15.656 29.062 | 7.799 10.335 21.576 | 7.835 12.029 | 4.505 9.618 | 8.513 | Ad Hoc Chi-Square 1K Trials; df = 13 Fig. 10 | | Q1 Q2 Q3 Q4 | 7.209 10.524 15.480 20.835 | 7.575 9.588 13.731 22.583 | 5.325 10.002 14.966 | 6.501 12.011 13.031 | 8.232 11.569 12.828 | 7.413 13.534 | 6.026 | Checkerboard Chi-Square 1K Trials; df = 13 Fig. 11 | | Q1 Q2 Q3 Q4 | 8.150 11.777 14.617 19.917 | 8.089 12.290 13.597 24.312 | 9.184 14.588 24.859 | 9.118 14.798 21.879 | 5.914 31.960 | 24.376 | 16.655 | 17.482 | 19.078 | Ad Hoc Chi-Square 1K Trials; df = 13 Fig. 12 | | Q1 Q2 Q3 Q4 | 8.483 11.575 12.985 17.377 | 3.014 11.513 12.440 18.648 | 7.688 10.469 14.263 17.373 | 6.681 11.337 15.301 21.507 | 5.557 11.291 | 10.021 | 12.249 And if we go to 10,000 constructions per trial, we get the results shown in figures 13 through 15: | Chi-Square Percentages for DF = 17 Fig. 13 | | 25% 50% 75% | 12.792 16.338 20.489 | Checkerboard Chi-Square 10K Trials; df = 17 Fig. 14 | | Q1 Q2 Q3 Q4 | 47.416 | 90.871 | 46.251 | 52.950 | 46.274 | ... | Ad-Hoc Chi-Square 10K Trials; df = 17 Fig. 15 | | Q1 Q2 Q3 Q4 | 10.057 13.044 18.020 28.587 | 10.398 15.686 19.155 32.074 | 9.541 12.995 18.799 25.653 | 12.178 13.545 19.016 27.383 | 13.455 18.635 20.643 | 19.315 A detailed examination of the outrageous "checkerboard" results in figure 14 shows that some of these have excessive low-NL counts, others have excessive high-NL counts, while some have variations distributed throughout the range. Again, there is no obvious pattern. In contrast, the "ad hoc" construction seems reasonable, which is nice, seeing as the reference distribution was developed from that construction. COMMENTS These two Latin square constructions produce measurably different distributions. So if we are given a large number of squares, by measuring their nonlinearity distribution we might predict which construction produced those squares. But this is information which is not normally hidden in cryptography anyway. On the other hand, both constructions deliver a comparable range of nonlinearity values, and excessively high or low values are rare. This would seem to be evidence supporting both constructions for cryptographic use. The "checkerboard" construction seems to be a comparatively easy and efficient way to produce nonlinear Latin square combiners of useful size. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary 1998-08-27: http://www.io.com/~ritter/GLOSSARY.HTM From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Practical Latin Square Combiners Date: Wed, 16 Sep 1998 08:22:55 GMT Lines: 38 Message-ID: <35ff752e.2575846@news.io.com> References: <35ff2fec.12158768@news.io.com> On Wed, 16 Sep 1998 03:28:00 GMT, in <35ff2fec.12158768@news.io.com>, in sci.crypt ritter@io.com (Terry Ritter) wrote: >PRACTICAL LATIN SQUARE COMBINERS >[...] The 3rd square in figure 2 had a typo: Original: | The Standard Latin Squares of Order 4 Fig. 2 | | 0 1 2 3 0 1 2 3 0 1 2 3 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 0 1 <- 2 3 0 1 | 3 0 1 2 3 2 1 0 3 2 0 1 3 2 1 0 | ^ ^ | | | Correct: | The Standard Latin Squares of Order 4 Fig. 2 | | 0 1 2 3 0 1 2 3 0 1 2 3 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 --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary 1998-08-27: http://www.io.com/~ritter/GLOSSARY.HTM

From: "Pierre Abbat"Subject: Re: Practical Latin Square Combiners Newsgroups: sci.crypt References: <35ff2fec.12158768@news.io.com> <35ff752e.2575846@news.io.com> Message-ID: <01bde2a5$460bc6a0$5f4896d0@phma.trellis.net> Lines: 32 Date: Fri, 18 Sep 1998 01:42:03 GMT > | The Standard Latin Squares of Order 4 Fig. 2 > | > | 0 1 2 3 0 1 2 3 0 1 2 3 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 Three other ways to transform one Latin square into another are to invert the permutation in each row, to permute the numbers, and to transpose it. Under these operations the first three squares are equivalent. 0 1 2 3 1 3 0 2 2 0 3 1 3 2 1 0 by exchanging 3 and 2 becomes 0 1 3 2 1 2 0 3 3 0 2 1 2 3 1 0 which by exchanging rows and exchanging columns becomes 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2. phma

*Terry Ritter, his
current address, and his
top page. *

*Last updated:* 1998-09-17