Practical Latin Square Combiners


A Ciphers By Ritter Page


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