Newsgroups: sci.crypt
Path: cactus.org!ritter
From: ritter@cactus.org (Terry Ritter)
Subject: Block Mixing Transformations
Message-ID: <1994Mar13.051515.27175@cactus.org>
Keywords: DES replacement, Large blocks
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
Date: Sun, 13 Mar 1994 05:15:15 GMT
Ritter Software Engineering
2609 Choctaw Trail
Austin, Texas 78745
(512) 892-0494, ritter@cactus.org
Keyed Balanced Size-Preserving Block Mixing Transforms
Terry Ritter
March 12, 1994
Introduction
Modern block ciphers seek to emulate extremely large substitution
tables algorithmically, using complex combinations of various simple
internal mechanisms. These internal mechanisms include small
substitutions and trivial combinings, but the art and mystery
of block cipher design is how to couple these simple and weak
operations in ways which produce a strong overall cipher.
One apparently new type of mechanism which might be useful in block
cipher design would take two blocks in, share data between them,
and then produce two generally-different blocks as a result. In
particular, this mechanism might be used to mix data to (and from)
a pair of substitutions, thus hopefully producing a stronger result
than the two substitutions operating separately and independently.
In most cases, it would be necessary for the mechanism to have an
inverse, and to produce output blocks of the same size as the input.
The result would be a mechanism which could be inserted anywhere
in the internal data paths common in block-cipher designs.
Block Mixing Transforms
Consider constructs like this:
A B
| |
v v
Mixing Transform
| |
v v
X Y
X Y
| |
v v
Inverse Transform
| |
v v
A B
Capital letters represent data blocks. Alternately, we can
describe the transform, in general, as:
X := f1( A, B ); Y := f2( A, B );
A := f3( X, Y ); B := f4( X, Y );
The intent of such a system is to mix two input blocks in a complex
yet reversible way. This could provide two advantages:
1) It should make each output bit a function of all the input
bits (on average), thus providing a way to expand block size
while using smaller block-cipher functions. Hopefully the
construct would also defeat attempts to "divide-and-conquer"
the smaller functions separately.
2) It could provide a way to connect block-cipher functions
in sequence, while eliminating any fixed direct connection
between the blocks, such connections being vulnerable to
"fix-in-the-middle" attack.
A mixing transform is not unlike a "butterfly" section in a fast
Fourier transform (FFT) [3]. But the usual FFT operates on complex
values which are normally represented in floating-point. When
implemented in fixed-point (as needed for mixing data blocks), the
normal FFT butterfly expands the range of the input values, thus
requiring a larger amount of storage (a larger block size) for the
result. Fast Hadamard / Walsh transforms [2] behave similarly.
For cryptography, we need transforms which are "size preserving"
so that we can perform fixed-size block operations (such as DES)
either on the input data or on the transformed results. It was
not clear to me that this was going to be possible (at least with
equations of practical complexity) until Eli Biham provided some
examples of size-preserving mixing transforms:
X := A - B; Y := 2A - B;
A := Y - X; B := Y - 2X;
for n-bit blocks, A, B, X, and Y, and arithmetic mod 2^n.
There are actually many such transforms, and Biham has found a
generalized form:
(-1 1 )
(-w w-1)
and
(w-1 -1)
(w -1)
where w is some constant. For example, when w = 2:
X := -1*A + 1*B = B - A
Y := -2*A + (2-1)*B = B - 2A
A := (2-1)*X + -1*Y = X - Y
B := 2*X + -1*Y = 2X - Y
with the arithmetic mod 2^n.
To see inverse, note that
A = X - Y = (B - A) - (B - 2A) = A
B = 2X - Y = 2(B - A) - (B - 2A) = B
These are fixed, linear transformations. If we know the input
values, and the transformation, we will also know the output
values. Even when the full equation is unknown, the simplicity
and linearity of these transforms means that they require
special protection in cryptographic applications. Mixing
transforms can only be used when both the input and the output
values cannot be exposed simultaneously.
Alas, the transform mentioned above has a problem: Specifically,
the least-significant-bit (lsb); that is, lsb(Y) = lsb(B). This
is because the expression B - 2A has shifted A left one bit,
leaving the bottom bit of B exposed. This provides a bit of direct
correlation between an input value and an output value. This is
probably sufficient to support a practical "fix-in-the-middle"
attack if the transform is used to isolate two DES operations.
Consider these correlation experiments on the above transform with
4-bit blocks:
x3 x2 x1 x0 y3 y2 y1 y0
b0 64 64 64 64 64 64 64 128
b1 64 64 64 64 64 64 64 64
b2 64 64 64 64 64 64 64 64
b3 64 64 64 64 64 64 64 64
a0 64 64 64 64 64 64 64 64
a1 64 64 64 64 64 64 64 64
a2 64 64 64 64 64 64 64 64
a3 64 64 64 64 64 64 64 64
This is a 0 -> 0 correlation count. For each possible input value
(over both A and B), for each input bit which is zero (somewhere in
A and B) and each output bit which is zero (somewhere in X and Y),
a count is recorded. The count of 128 means that y0, the lsb of Y,
occurs twice as often as expected when the lsb of B is zero.
Similarly,
64 64 64 64 64 64 64 0
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
a 0 -> 1 correlation count, shows that no cases exist where the
lsb of B is a one and the lsb of Y is a zero.
Cryptographic Mixing
In [8] I introduced a new type of reversible stream-cipher combiner
(the first stream-cipher combiner, which we now call "exclusive-OR"
or "mod-2 addition" was described by Vernam [12]). "Combiner" is
the traditional cryptographic name for a mixing function. [11,5,1]
(Non-reversible combiners are also used, typically to make confusion
sequences difficult to penetrate. [e.g., 6]) Combiners and mixing
transforms have much in common.
Basically, a combiner will look like any other two-input one-output
function:
A B
| |
v v
Mixing Function
|
v
C
C B
| |
v v
Inverse Function
|
v
A
The capital letters represent the block size; in a typical stream
cipher these are byte values. A is the plaintext, B the confusion
stream, C the ciphertext. Note that exactly the same confusion
stream is needed to recover the original data; this is the heart
of stream-cipher security.
There are many two-input functions, but most are not useful as
cryptographic data combiners, which must be reversible and must
have no correlation between either input and the output. Combiners
which do have correlation [e.g., 4] fall to statistical attacks
[e.g., 10]. If we see mixing transforms as a matched-set of
cryptographic combiners, we can see that correlation is a problem
with the example transform. (Biham did have an example of one
balanced but non-keyed transform based on rotation and subtraction
mod 2^n.)
Mixing in Mod-2 Polynomials
Since the "weak" exclusive-OR form of combiner has long been
available, modern combiner designs are normally intended to be
"stronger" and, thus, are more complex. But it is not at all clear
that "stronger" is what we need in a mixing transform. Presumably,
"strength" can be provided more efficiently by some other function,
like DES, or a substitution table. Thus, we may really want a
modest-strength extremely-fast mixing solution, and one approach
is to consider the well-known field of mod-2 polynomials.
In mod-2 arithmetic, addition is the same as subtraction
X + Y = X - Y
and any value added to itself is zero
X + X = 0
so, in general, multiplication cannot be achieved by addition
X + X <> 2X
(assuming X is non-zero) but is instead achieved by shifting.
Then
2X + X = 3X
so multiplication is not restricted to binary powers. Of course
3X + X = 2X
which just shows that mod-2 arithmetic can be surprising.
It is interesting to see just how unusual good mixing transforms
are. Consider a first approach
X := A + B; Y := A - B;
(mod-2, mod-p, where p is some primitive mod-2 polynomial of
appropriate degree for the size of the data blocks). While this
is a reasonable approach in the integers, in mod-2 polys,
A + B = A - B. This means that X = Y, and the two resulting
identical blocks cannot possibly carry enough information to
provide an inverse transform for two arbitrary input blocks.
It does not work.
Next consider
X := A + B; Y := A + 2B;
with inverse operations
A := (2X + Y) / 3; B := (X + Y) / 3;
(mod-2, mod-p), and the division done by multiplying by the inverse
of 3, mod p. (Appropriate inverse equations may not always exist;
finding the inverse equations is interesting in itself.) This
works. But here X is never affected by p at all, thus producing
an extremely regular (and un-keyed) transformation. And the
inverse multiplication is, in general, far more expensive than
multiplication by a small integer.
Finally, consider
X := 2A + 3B; Y := 3A + 2B;
A := 2X + 3Y; B := 3X + 2Y;
Again, operations are mod-2 and mod-p, where p is some primitive
mod-2 polynomial of appropriate degree for the data blocks X, Y,
A and B. This works, and the transform is a self-inverse. The
primitive affects the result in both data blocks. And the
multiplications are simple.
Correlation experiments conducted as before show a nice, balanced,
uncorrelated system:
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
These functions are extremely fast. Addition is a simple
exclusive-OR. Multiplication by two is simply a left-shift and
a conditional add of the primitive. Multiplication by three is
a multiplication by two plus an addition.
Keyed Mixing Transforms
The mod-2 polynomial transforms depend on having some primitive of
the appropriate degree. Different primitives produce different
mixing functions, with similar overall performance. This leads
to the possibility of keying the transforms by selecting arbitrary
primitives. (Some references to primitive-finding algorithms
are given in [9].)
Rabin gives the number of degree-n primitives as about p^n / n
[7]. Thus, for degree 64, we have about 2^64 / 2^6 or about 2^58
primitives. This means that each randomly-selected degree-64
primitive carries about 58 bits of key. Of course, this key can
only be effective to the extent that the linear transformation
cannot be attacked and the primitive thus deduced.
Some Consequences
If a single input bit changes on one of the mixing transform input
blocks, we can be sure that at least one bit will change in both
output blocks.
If two input bits change, we can be sure that these bits will not
"cancel" each other; changes will still occur in the output blocks.
If many input bits are changed, and the transform primitive is
known, it is possible to engineer a no-change in one output block
(although this is unlikely to happen by chance). Should this be
undesirable, it might be made impossible by design (such as
ciphering the input blocks before mixing), or by keying the
transform (so the necessary bit patterns are unknown).
If it becomes possible to define the input to, and what the output
must be from a ciphering element, it will be possible to key-search
that element independent of other elements, and this is what we
hope to avoid. To prevent this it may be necessary to use keyed
input and output transforms, or even multiple ciphering levels
between transforms.
Applications
It is crucial to remember that these simple, high-speed, but linear
mixing transforms can be said to have "strength" only if the input
and output values are never both available. That is, these
structures do not by themselves handle "known-plaintext" attack.
(Of course, the same could be said for many other simple internal
mechanisms used in block cipher construction.)
Simple constructs like
A B
| |
v v
MixTrans
| |
v v
C D
are not likely to be very useful as ciphers by themselves, even if
the mixing transformation is keyed and the blocks are large.
On the other hand, constructs like
A B
| p1 |
v v v
MixTrans
| |
v v
DES1 DES2
| |
| p2 |
v v v
MixTrans
| |
v v
C D
are considerably more interesting. Note that this construct
ciphers a double-size DES block at single-DES rates. It seems to
require keyed mixing transforms. Similarly,
A B
| |
v v
DES1 DES2
| |
| p |
v v v
MixTrans
| |
v v
DES3 DES4
| |
v v
C D
will cipher a double-size DES block at double-DES rates, and at
least superficially avoids all weakness in the mixing transform by
placing strength in each input and output port. This may avoid
the need to key the mixing transform.
Alternately,
A B
| k1 |
v v |
XOR <- DES1-----|
| |
| k2 |
| v v
|---- DES2 -> XOR
| |
| p |
v v v
Mixing Transform
| |
| k3 |
v v |
XOR <- DES3 ----|
| |
| k4 |
| v v
|---- DES4 -> XOR
| |
v v
C D
also ciphers at double-DES rates.
Of course, larger external blocks mean an increase in the number
of internal data paths, making various sorts of interconnection
configurations possible. Thus
A B C D
| p1 | | p2 |
v v v v v v
MixTrans1 MixTrans2
p3 | | p4 | |
v v v v v v
-Trans3 MixTrans4 Mix-
| | | |
v v v v
DES1 DES2 DES3 DES4
| | | |
| p5 | | p6 |
v v v v v v
MixTrans5 MixTrans6
p7 | | p8 | |
v v v v v v
-Trans7 MixTrans8 Mix-
| | | |
v v v v
E F G H
will cipher quadruple-size DES blocks at single-DES rates,
A B C D
| | | |
v v v v
DES1 DES2 DES3 DES4
| | | |
| p1 | | p2 |
v v v v v v
MixTrans1 MixTrans2
p3 | | p4 | |
v v v v v v
-Trans3 MixTrans4 Mix-
| | | |
v v v v
DES5 DES6 DES7 DES8
| | | |
v v v v
E F G H
will cipher quadruple-size DES blocks at double-DES rates, and
A B C D
| k1 | | k2 |
v v | v v |
XOR <- DES1 ----| XOR <- DES2 ----|
| | | |
| k3 | | k4 |
| v v | v v
|---- DES3 -> XOR |---- DES4 -> XOR
| | | |
| | | |
| p1 | | p2 |
v v v v v v
MixingTransform1 MixingTransform2
p3 | | p4 | |
v v v v v v
-Transform3 MixingTransform4 Mixing-
| | | |
| k5 | | k6 |
v v | | v |
XOR <- DES5 ----| XOR <- DES6 ----|
| | | |
| k7 | | k8 |
| v v | v v
|---- DES7 -> XOR |---- DES8 -> XOR
| | | |
v v v v
E F G H
will also cipher quad-size blocks at double-DES rates. But in
each case, four double-level mixing transforms could be replaced
by a single double-size mixing transform:
A B C D
| | p1 | |
v v v v v
---------mix1---------
| | | |
v v v v
DES1 DES2 DES3 DES4
p2 | | | |
v v v v v
ix2--------- --------m
| | | |
v v v v
E F G H
A B C D
| | | |
v v v v
DES1 DES2 DES3 DES4
| | | |
| | p | |
v v v v v
---------mix----------
| | | |
v v v v
DES5 DES6 DES7 DES8
| | | |
v v v v
E F G H
A B C D
| k1 | | k2 |
v v | v v |
XOR <- DES1 ----| XOR <- DES2 ----|
| | | |
| k3 | | k4 |
| v v | v v
|---- DES3 -> XOR |---- DES4 -> XOR
| | | |
| | p | |
v v v v v
---------------------mix----------------------
| | | |
| k5 | | k6 |
v v | | v |
XOR <- DES5 ----| XOR <- DES6 ----|
| | | |
| k7 | | k8 |
| v v | v v
|---- DES7 -> XOR |---- DES8 -> XOR
| | | |
v v v v
E F G H
These are new ciphering architectures. Clearly, it is not known
how strong these constructs would be. However, this situation can
hardly be considered unusual.
Other opportunities exist when constructing completely new block
ciphers. These might, for example, be based on byte-wide key-
permuted substitutions, thus avoiding differential attacks on
fixed "optimal" tables. Thus
------------------------------mix------------------------------
--------------mix-------------- --------------mix--------------
------mix------ ------mix------ ------mix------ ------mix------
--mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix--
mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S
mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix
--mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix--
------mix------ ------mix------ ------mix------ ------mix------
--------------mix-------------- --------------mix--------------
------------------------------mix------------------------------
enciphers 256-bit blocks through 32 keyed 8-bit substitutions by
using five levels of input keyed mixing transform and five levels
of output keyed mixing transforms of varying size. Clearly, there
are a plethora of alternate interconnection possibilities here.
For example, the mixing rows could be permuted, different sizes
of mixing combined in some rows, the mixing not arranged on 2^n
boundaries, etc., etc. Since the mixing transforms are extremely
fast, we would expect this 256-bit system to be much faster than
64-bit single-DES.
And,
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S
mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix
--mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix--
------mix------ ------mix------ ------mix------ ------mix------
--------------mix-------------- --------------mix--------------
------------------------------mix------------------------------
--------------mix-------------- --------------mix--------------
------mix------ ------mix------ ------mix------ ------mix------
--mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix-- --mix--
mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix mix
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S
enciphers 256-bit blocks through 64 keyed 8-bit substitutions by
using nine levels of mixing transforms of varying size. With the
substitutions all keyed, we can probably avoid keying the mixing
transforms. Again, there are a plethora of alternate
interconnection possibilities.
Summary
Practical, high-speed, keyed, balanced, and size-preserving block
mixing transforms are introduced for cryptographic service.
References
[1] Arko, R. 1961. Mechanical Signal Combiner. U.S. Patent
3,159,712.
[2] Beauchamp, K. 1984. Applications of Walsh and Related
Functions. Academic Press.
[3] Brigham, E. 1974. The Fast Fourier Transform.
Prentice-Hall.
[4] Geffe, P. 1973. How to protect data with ciphers that are
really hard to break. Electronics. January 4. 99-101.
[5] Kohler, H. 1951. Combining Circuits. U.S. Patent 2,567,214.
[6] Massey, J., and R. Rueppel. 1989. Method of, and Apparatus
for, Transforming a Digital Data Sequence into an Encoded
Form. U.S. Patent 4,797,922.
[7] Rabin, M. 1980. Probabilistic Algorithms in Finite Fields.
SIAM Journal on Computing. 9(2): 273-280.
[8] Ritter, T. 1990. Substitution Cipher with Pseudo-Random
Shuffling: The Dynamic Substitution Combiner. Cryptologia.
14(4): 289-303.
[9] Ritter, T. 1991. The Efficient Generation of Cryptographic
Confusion Sequences. Cryptologia. 15(2): 81-139.
[10] Siegenthaler, T. 1985. Decrypting a Class of Stream Ciphers
Using Ciphertext Only. IEEE Transactions on Computers.
C-34: 81-85.
[11] Smith, H. 1950. Combining Circuit. U.S. Patent 2,496,317.
[12] Vernam, G. 1919. Secret Signaling System. U.S. Patent
1,310,719.
---
Terry Ritter ritter@cactus.org (alas, cactus.org dies March 18)
ritter@io.com (perhaps temporarily)