Practical Latin Square Combiners
Terry Ritter
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.
Contents
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