An 8-bit-wide model block cipher enciphers toy "messages" of two hex characters each. The intent is not to protect information, but rather to support analysis of the design. The model presents cryptographic "strength" at a reduced level where it hopefully can be confronted and understood. This appears to be a fairly novel approach to the study of cryptographic strength, both in a particular cipher design, and in general.
The 8-bit model is one of the smallest incarnations of a scalable design which constructs both tiny models and real-size ciphers from components which differ only in size. Presumably, any possible weakness in the larger realizations also must be present in the tiny version, where it should be easier to find. The goal is an understanding of strength or weakness which scales up to real cipher sizes.
A previous article proposed a similar 4-bit block version which is vulnerable to many attacks simply because of its tiny size. While these attacks are real enough, they do not scale up, do not weaken real-size versions, and so do not provide insight into the general design. Size-based attacks are almost eliminated in this 8-bit version, and this greatly simplifies the discussion.
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt
Subject: Break This 8-Bit Block Cipher (long)
Date: Sun, 19 Apr 1998 20:49:09 GMT
Lines: 549
Message-ID: <353a6292.2214286@news.io.com>
BREAK THIS 8-BIT BLOCK CIPHER!
Terry Ritter ritter@io.com
Ritter Software Engineering
http://www.io.com/~ritter/
1998-04-19
ABSTRACT
An 8-bit-wide *model* block cipher enciphers toy "messages" of two
hex characters each. The intent is not to protect information, but
rather to support analysis of the design. The model presents
cryptographic "strength" at a reduced level where it hopefully can
be confronted and understood. This appears to be a fairly novel
approach to the study of cryptographic strength, both in a
particular cipher design, and in general.
The 8-bit model is one of the smallest incarnations of a *scalable*
design which constructs both tiny models and real-size ciphers from
components which differ only in size. Presumably, *any* possible
weakness in the larger realizations also *must* be present in the
tiny version, where it should be easier to find. The goal is an
understanding of strength or weakness which scales up to real
cipher sizes.
A previous article proposed a similar 4-bit block version which is
vulnerable to many attacks simply because of its tiny size. While
these attacks are real enough, they do not scale up, do not weaken
real-size versions, and so do not provide insight into the general
design. Size-based attacks are almost eliminated in this 8-bit
version, and this greatly simplifies the discussion.
THE PROBLEM
We have a block cipher composed of four shuffled substitution
tables and a linear Balanced Block Mixer. (Converting a binary
key value into shuffled tables is well-known technology; see,
for example:
http://www.io.com/~ritter/KEYSHUF.HTM
.) We assume that we know every possible plaintext and ciphertext
pair, plus the everything about the mixer. The goal is to develop
the table permutations -- the internal key -- from the known
information, using some sort of scalable algorithm. Since we know
all possible messages and corresponding ciphertexts, we always have
substantially more known information than the internal state we are
trying to resolve.
Note that this reduced model cannot be a great cipher in any sense.
It is known from previous work that a single mixing does not produce
the nonlinearity distribution of the larger block (see:
http://www.io.com/~ritter/ARTS/MIXNONLI.HTM
). But it is *also* known that multiple mixings and wider tables
*do* produce the right distribution. Here we investigate whether
a single mixing layer, with associated table layers, will *protect*
whatever other layers happen to be used.
The Balanced Block Mixer (BBM) basically consists of two Latin
squares. Each square mixes two half-size blocks into a single
half-size result; two of those thus give a full mixed block. The
BBM can be computed or modeled as a table, and has been discussed
extensively (see, for example:
http://www.io.com/~ritter/JAVASCRP/ACTIVBBM.HTM
). In the 8-bit model, the substitution tables are 4-bit invertible
tables, each having exactly 16 entries of 4 bits each. In marked
contrast to 2-bit tables, most 4-bit tables have at least some
nonlinearity. (Nonlinearity is discussed in detail at:
http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM
.) Since the only nonlinearity in the system is in the tables,
when the selected tables have no nonlinearity, neither does the
cipher. But at the real cipher size, finding a linear table is
almost impossible. Which brings us to the issue of strength:
STRENGTH
The meaning of "strength" in this model is *not* the protection of
information, since we assume that we *know* the ciphertext for
every possible plaintext "message." The model emulates a Simple
Substitution on one 8-bit character, and so is much like the puzzles
we find in newspapers. But the same design scales up, stacks in
added layers, and extends to wide blocks of dynamically selected
size where we cannot even *store* all possible transformations.
Only in those enhanced structures will the cipher protect data.
*Nor* is the meaning of "strength" a huge keyspace. The 8-bit
version does have an apparent 177-bit keyspace, which should prevent
"brute force" attacks on the table permutations. But this value
probably *does* *not* represent the true strength of the structure,
and the true strength is what we are trying to find.
In the strength analysis of the larger versions of these ciphers,
I assume that if attackers could provably resolve even *one* table
entry, they could similarly resolve the rest of the table. So I
assign a strength value of just the bit-width for each table.
Further, I assume that in any structure like this, one table layer
does not provide strength. This means that I would assign a total
strength of *just* *8* *bits* to the 8-bit model. In real-size
designs, where we have 3 or 5 layers of tables, with a minimum
width of 64 or 128 bits, even these minimalist assumptions imply
a strength of at least 128 bits, which is "large enough."
The meaning of "strength" is also *not* the nonlinearity of the
overall block transformation. While it is true that some 4-bit
tables are linear (which makes the resulting cipher linear),
finding a linear 8-bit table at random is harder than guessing a
cipher key. So overall linearity is *also* not going to solve
the problem, unless some form of it somehow scales up with the
cipher.
At this point, one might reasonably ask "What is left?", and the
answer is: "Anything that will reveal the key and also scale to
real size implementations."
In particular, the mixing transformation is both linear and known,
and is an obvious focal point for an attack. But eventually the
"attack" should be some process which exposes one table entry then
another -- or all at once -- independent of table size and block
size. This is not because the problem is "rigged," but instead
because the whole point is to understand any weakness inherent in
the scalable design, instead of weaknesses of size which will not
exist in a real version.
SCALABILITY
Scalability is a relatively new concept in cipher design, so it is
easy to miss what "attack" means in this context. The usual way
to discuss cipher strength would be to present a real-size version
and say "Attack it!" But a serious attack is usually a complex,
time-consuming process, so it is desirable to find a better way of
revealing cipher weakness.
The point of a truly scalable design is to have a fixed definition
which is scalable in the same way that we expect arithmetic to work
on numbers both large and small. Obviously large values are not
the same as small values, but the *concepts* should be the same.
This particular design consists of exactly two components: tables
and a mixer. There is no particular problem in constructing or
keying tables of any reasonable size (although one might think that
8-bit tables would be of sufficient size in practice).
The mixer is defined algebraically (albeit in mod-2 polynomials),
and so *also* scales as desired. The only specific difference in
mixer size is the use of some particular irreducible polynomial.
But there always *is* some such polynomial, and we assume that the
attacker *will* know what one we use. It does seem unlikely that
a particular irreducible would be "weak" just as it seems unlikely
that a particular prime would be "weak" in number theory ciphers.
But if so, that would be good to know, and then we would use an
irreducible which does not have that problem.
If there is a weakness in the larger versions, the very *same*
weakness should be present in the tiny model, where it should be
easier to find.
THE DESIGN
Here we have a system which has 4-bit tables and data paths, and
an 8-bit block size. This is a scaled-down *model* which is not
useful for hiding data, but is useful for analysis.
| INPUT BLOCK
| InA | | InB
| v v
| -------- --------
| | TA | | TB |
| -------- --------
| | |
| +--*-----------------+ |
| | | |
| | +------------------*-+
| A | | B A | | B
| v v v v
| -------- --------
| | L0 | BBM | L1 |
| -------- --------
| X | | Y
| v v
| -------- --------
| | TX | | TY |
| -------- --------
| | |
| OutX v v OutY
| OUTPUT BLOCK
In the figure, the tables are TA, TB, TX and TY, and the Balanced
Block Mixer is shown as two Latin square combiners L0 and L1.
A MIXING OVERVIEW
The orthogonal Latin squares in the BBM are developed algorithmically
as follows:
X = 3A + 2B (mod 2)(mod p), p = 10011
Y = 2A + 3B (mod 2)(mod p)
These equations can make it awkward to think about the system, so we
can use a table instead. Here A selects a row, B selects a column,
and the selected entry is XY:
4-Bit Els, Poly 10011 = 0x13
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 00 23 46 65 8c af ca e9 3b 18 7d 5e b7 94 f1 d2
1 32 11 74 57 be 9d f8 db 09 2a 4f 6c 85 a6 c3 e0
2 64 47 22 01 e8 cb ae 8d 5f 7c 19 3a d3 f0 95 b6
3 56 75 10 33 da f9 9c bf 6d 4e 2b 08 e1 c2 a7 84
4 c8 eb 8e ad 44 67 02 21 f3 d0 b5 96 7f 5c 39 1a
5 fa d9 bc 9f 76 55 30 13 c1 e2 87 a4 4d 6e 0b 28
6 ac 8f ea c9 20 03 66 45 97 b4 d1 f2 1b 38 5d 7e
7 9e bd d8 fb 12 31 54 77 a5 86 e3 c0 29 0a 6f 4c
8 b3 90 f5 d6 3f 1c 79 5a 88 ab ce ed 04 27 42 61
9 81 a2 c7 e4 0d 2e 4b 68 ba 99 fc df 36 15 70 53
a d7 f4 91 b2 5b 78 1d 3e ec cf aa 89 60 43 26 05
b e5 c6 a3 80 69 4a 2f 0c de fd 98 bb 52 71 14 37
c 7b 58 3d 1e f7 d4 b1 92 40 63 06 25 cc ef 8a a9
d 49 6a 0f 2c c5 e6 83 a0 72 51 34 17 fe dd b8 9b
e 1f 3c 59 7a 93 b0 d5 f6 24 07 62 41 a8 8b ee cd
f 2d 0e 6b 48 a1 82 e7 c4 16 35 50 73 9a b9 dc ff
This mixing structure is clearly weak: it is in fact *linear*.
But it is intended to be used with very *non*linear tables, and
the resulting cipher is *not* linear. We can implement the mixing
structure as two 2-dimension indexable arrays L0 and L1, which we
fill by computation.
This means that the whole cipher can be expressed as just 2 input
substitutions, 2 mixings, and 2 output substitutions:
// input substitutions
A = TA[ InA ];
B = TB[ InB ];
// BBM mixing
X = L0[A][B];
Y = L1[A][B];
// output substitutions
OutX = TX[ X ];
OutY = TY[ Y ];
Or we could just *compute* the mixing values each time, instead of
using tables:
int
L0( int a, int b ) {
// return 3a + 2b (mod 2)(mod p)
int t;
t = a^b; // a + b (mod 2)
t <<= 1; // 2a + 2b (mod 2)
if (t & 0x10) // if msb is 1, going out of range
t ^= 0x13; // so subtract irreducible p (mod 2)
return a^t; // 3a + 2b (mod 2)(mod p)
}
And L1 would be the same except for "return b^t", thus calculating
"2a + 3b (mod 2)(mod p)". This is probably how we would want to
do the real-size designs, since a single "8-bit" Latin square has
65,536 byte entries, and we need two. (But if we did that we could
make the tables nonlinear, and might use multiple different mixings.)
ATTACKS
Normally, we think of attacking a cipher to gain some of the
information it protects. Perhaps we have some known plaintext (with
associated ciphertext), and wish to somehow expose the key, which
will of course expose the rest of the ciphertext. With the 8-bit
model proposed here, there is no "rest of the ciphertext" to expose,
but there *is* a key, which consists of the state of the 4 shuffled
tables. Since we have all possible plaintexts and ciphertexts, we
can mount any possible known-plaintext or defined-plaintext attack.
More elaborate attacks, such as Linear Cryptanalysis or Differential
Cryptanalysis usually depend upon a knowledge of fixed nonlinear
tables in a cipher, and there are no such tables here. While it
would be much too casual to say that such techniques could not be
applied, it is just not clear how they could.
COMMENTS
The model is a single linear mixing with unknown tables on both the
input and output. This seems to be the ultimate simplification of
both the Mixing and VSBC ciphers, and in fact may be a step too far.
The real ciphers have at least three layers of tables and two mixings,
so that "known plaintext" is not available across any single mixing.
This tiny model demonstrates the analytic advantage of true cipher
scalability. One would think that a cipher with a 256-element
codebook would be small enough to attack on even the smallest
personal computer. And if an attack is *not* possible, the model
may be small enough to know *why* not. This last possibility would
be An Important Result. Presumably, such an outcome would for the
first time make it possible to prove strength in a practical
full-size cipher, something I never expected to see.
It seems to me that the guaranteed balance of the BBM protects the
tables from being separated and exposed. If so, the simple linear
BBM contributes to strength in an essential way, despite having
absolutely no strength of its own.
Many articles on the larger systems and their general design
principles can be found on my web pages.
ACKNOWLEDGMENT
My thanks to Randall Williams for his efforts on the 4-bit cipher,
which identified a whole range of problems with the earlier
presentation.
APPENDIX A: The 8-Bit Block Cipher in C
// for research analysis; not a useful cipher
#include <time.h> // randomize
#include <stdlib.h> // random
#include <stdio.h> // printf
// BBM by lookup
int L0[16][16];
int L1[16][16];
// BBM by computation
int
FL0( int a, int b ) {
int t;
t = (a^b) << 1;
if (t & 0x10) t ^= 0x13;
return a^t;
}
int
FL1( int a, int b ) {
int t;
t = (a^b) << 1;
if (t & 0x10) t ^= 0x13;
return b^t;
}
// use computed BBM to fill global lookup
void
InitLS( int lastel ) {
int a, b;
for( a=0; a<=lastel; a++ ) {
for( b=0; b<=lastel; b++ ) {
L0[a][b] = FL0( a, b );
L1[a][b] = FL1( a, b );
}
}
}
// keyed tables
int TA[16];
int TB[16];
int TX[16];
int TY[16];
void
InitTab( int tab[], int lastel ) {
int i;
for (i=0; i<=lastel; i++) {
tab[i] = i;
}
}
int
Rand0thruN( int mask, int N ) {
// return integer 0..N, N < 256
// mask MUST be 2**n - 1 for some n
int b;
do {
b = rand(); // 32-bit value
b ^= b >> 16;
b ^= b >> 8;
b &= mask; // b is 0..mask
} while (b > N);
return b;
}
void
ShufTab( int tab[], int mask ) {
// shuffle the table
// mask MUST be 2**n - 1 for some n
int nxtmsk, N, rand, by;
do {
nxtmsk = mask >> 1;
for (N = mask; N > nxtmsk; N--) {
rand = Rand0thruN( mask, N );
by = tab[N];
tab[N] = tab[rand];
tab[rand] = by;
}
mask = nxtmsk;
} while (mask);
}
// global state ciphering
int InA, InB, A, B, X, Y, OutX, OutY;
void
Mix8( void ) {
A = TA[ InA ];
B = TB[ InB ];
X = L0[ A ][ B ];
Y = L1[ A ][ B ];
OutX = TX[ X ];
OutY = TY[ Y ];
}
// functional ciphering
int
Mix8X( int ina, int inb ) {
return TX[ L0[ TA[ina] ][ TB[inb] ] ];
}
int
Mix8Y( int ina, int inb ) {
return TY[ L1[ TA[ina] ][ TB[inb] ] ];
}
void
main( void ) {
int ina, inb, outx, outy;
randomize(); // start out new
// fill the 2 global Ls tables as the BBM
InitLS( 15 );
// shuffle the 4 global keying tables
InitTab( TA, 15 ); ShufTab( TA, 15 );
InitTab( TB, 15 ); ShufTab( TB, 15 );
InitTab( TX, 15 ); ShufTab( TX, 15 );
InitTab( TY, 15 ); ShufTab( TY, 15 );
// show every possible plaintext and ciphertext
// first the inb column labels
printf( "\n " );
for( inb = 0; inb<=15; inb++ ) printf( " %x ", inb );
// then each ina row
for( ina = 0; ina<=15; ina++ ) {
printf( "\n %x ", ina ); // start row with ina label
for( inb=0; inb<=15; inb++ ) {
outx = Mix8X( ina, inb );
outy = Mix8Y( ina, inb );
printf( " %x%x ", outx, outy );
}
}
printf( "\n" ); // end last line
}
APPENDIX B: Sample Output
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 06 67 da 54 45 e0 88 2d ae 3f c1 1c b3 9b 72 f9
1 a3 c5 28 79 37 be 1a dc 00 41 6f 8d e6 f2 5b 94
2 c2 ad 71 2e ec 49 9f 57 64 b8 0a f5 3b 83 d6 10
3 fc 8b 40 bf d2 7a 6e 33 98 24 19 c6 5d a7 e5 01
4 15 93 e9 38 76 d1 a4 bb 8f 5e f0 02 27 6d 4c ca
5 2a 74 a6 c7 99 8c e3 0e dd fb 52 b0 18 4f 61 35
6 9d 12 3e e1 2b 58 c0 46 fa d9 84 63 7c 05 b7 af
7 b9 48 85 f3 6a a2 d7 1f eb cd 3c 21 04 7e 90 56
8 4e b1 fd 82 0f c3 5c 9a 36 a5 e7 78 60 29 14 db
9 d8 59 03 65 f4 1d b6 a0 2c 92 7b ee 8a 31 cf 47
a e4 3a 17 96 c8 0b 25 81 b2 6c 4d df a9 50 fe 73
b 30 ef 9c 1b a1 66 7d f8 43 07 b5 5a ce d4 89 22
c 7f 20 cb ac 1e f7 32 69 55 86 d3 44 91 ba 08 ed
d 51 de 62 0d 80 95 4b c4 77 13 26 39 ff e8 aa bc
e 6b 0c 5f d0 bd 34 f1 75 c9 ea a8 97 42 16 23 8e
f 87 f6 b4 4a 53 2f 09 e2 11 70 9e ab d5 cc 3d 68
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 df 41 10 83 38 02 9c 67 59 bb e4 7d c6 2e fa a5
1 53 1d 46 9f f5 6e 89 0b dc 27 aa c1 70 b2 34 e8
2 b1 af e9 6d 77 9a 06 88 20 d5 1e 33 fc 54 c2 4b
3 47 d8 5a 7b 61 f9 ce 3f 12 a3 26 85 94 ec 00 bd
4 3e 64 05 a2 d6 13 e7 4c fb 79 91 ba 28 cf 5d 80
5 a8 b7 22 35 8f c0 f4 71 ea 4d 5c 6b 0e 16 99 d3
6 09 f0 31 2c 1a d7 b3 52 6f 9e 75 e6 ad 8b 48 c4
7 74 8e 9b 4a bc ed 18 a6 c5 30 0f d2 57 f1 23 69
8 6c 36 fd b9 44 5b 2f de 03 82 c8 a0 e1 97 15 7a
9 1b 55 d4 c7 0d 3c 72 f3 4e ef b0 98 8a a9 66 21
a e5 2b be f8 93 76 3a cd a4 11 d9 07 62 40 8c 5f
b 86 7c c3 d0 ae 25 51 b4 9d 6a f7 49 1f 08 eb 32
c ca 92 87 14 29 a1 45 e0 78 f6 63 5e db 3d bf 0c
d 2d e3 ac 01 cb 84 60 95 b6 58 42 ff 39 da 7e 17
e 90 c9 7f 56 e2 b8 dd 2a 81 04 3b 1c 43 65 a7 fe
f f2 0a 68 ee 50 4f ab 19 37 cc 8d 24 b5 73 d1 96
---
Terry Ritter ritter@io.com http://www.io.com/~ritter/
The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: David Hopwood <hopwood@zetnet.co.uk>
Newsgroups: sci.crypt
Subject: Re: Break This 8-Bit Block Cipher (long)
Date: Sat, 25 Apr 1998 10:59:13 +0100
Message-ID: <1998042510591374952@zetnet.co.uk>
References: <353a6292.2214286@news.io.com>
Lines: 450
-----BEGIN PGP SIGNED MESSAGE-----
In message <353a6292.2214286@news.io.com>
ritter@io.com (Terry Ritter) wrote:
> THE PROBLEM
> We have a block cipher composed of four shuffled substitution
> tables and a linear Balanced Block Mixer. [...]
> We assume that we know every possible plaintext and ciphertext
> pair, plus the everything about the mixer. The goal is to develop
> the table permutations -- the internal key -- from the known
> information, using some sort of scalable algorithm.
That is _a_ goal, but not necessarily the goal. It would also be a
weakness in the cipher if it were possible, given some subset of the
plaintext/ciphertext pairs, to find other plaintext/ciphertext
pairs that were not given (using a scalable algorithm).
This might not require finding the internal key, and in fact this
8-bit cipher construction is a good example of that; see below.
> A MIXING OVERVIEW
> The orthogonal Latin squares in the BBM are developed algorithmically
> as follows:
> X = 3A + 2B (mod 2)(mod p), p = 10011
> Y = 2A + 3B (mod 2)(mod p)
[table snipped]
> This mixing structure is clearly weak: it is in fact *linear*.
> But it is intended to be used with very *non*linear tables, and
> the resulting cipher is *not* linear. We can implement the mixing
> structure as two 2-dimension indexable arrays L0 and L1, which we
> fill by computation.
> This means that the whole cipher can be expressed as just 2 input
> substitutions, 2 mixings, and 2 output substitutions:
> // input substitutions
> A = TA[ InA ];
> B = TB[ InB ];
> // BBM mixing
> X = L0[A][B];
> Y = L1[A][B];
> // output substitutions
> OutX = TX[ X ];
> OutY = TY[ Y ];
I.e.
OutX = TX[ 3 TA[InA] + 2 TB[InB] (mod 2)(mod p) ]
Suppose we vary InA while keeping InB fixed. Then
OutX = TX[ 3 TA[InA] + constant (mod 2)(mod p) ]
Since TA, multiplication by 3 (in the relevant ring), addition
of a constant, and TX are all permutations, their composition is
also a permutation. This means that when InB is held constant and
InA is varied from 0 to 15 (i.e. a column in the output table),
OutX will take on each value from 0 to 15 exactly once. The same
applies to OutY in each column, and to OutX and OutY in each row.
Here is a sample output table; the fact that X and Y are permutations
within each row and column stands out clearly once you know what to
look for:
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 E2 48 3C 70 D9 95 2B 1E 5D A4 BF 01 F6 67 8A C3
1 47 E1 B4 25 FA 50 7D AF 9B 1C 3E 68 D3 02 C9 86
2 84 CE 57 13 6D B6 AA 78 39 22 91 FF 05 DC EB 40
3 BD 35 4A D1 74 88 F7 66 C2 09 E3 A0 2E 1B 9C 5F
4 71 27 FE ED B3 6B 45 8C 00 CF D4 52 3A 98 16 A9
5 28 72 DF 4B 36 0D E0 C4 65 8E FC 97 B9 51 A3 1A
6 5A 93 8D 0E A7 4F 64 F0 EC DB C5 76 11 29 32 B8
7 F5 DD 73 37 4E A2 B1 59 18 96 2A 8B E4 C0 0F 6C
8 3B B0 E9 F8 2C C1 D2 03 87 6A 46 15 7F AD 54 9E
9 D0 FB 26 B2 EF 17 38 9A A1 53 79 CD 4C 85 6E 04
A 99 56 CB 6F 12 EE 0C D5 44 FD 80 23 A8 7A B7 31
B CC 8F 92 A6 0B 33 19 21 BA 77 58 DE 60 F4 4D E5
C 63 0A A5 94 81 7C 5E BB 2F 30 1D 49 C7 E6 D8 F2
D 06 69 10 5C C8 24 9F 3D 7E B5 AB EA 82 43 F1 D7
E AE 14 61 CA 55 F9 83 42 D6 E8 07 BC 9D 3F 20 7B
F 1F AC 08 89 90 DA C6 E7 F3 41 62 34 5B BE 75 2D
This is a significant weakness because it leaks information about
plaintext/ciphertext pairs that would not otherwise be known. For
example, suppose that an attacker knows the ciphertext for input
blocks 00 to 0E inclusive in the above table. He/she can infer that
the ciphertext for 0F is C3, and can decrypt this ciphertext if it
is encountered.
Alternatively, probabilistic information can be obtained. E.g. if
the attacker only knows blocks 00 to 0D inclusive, and encounters
one of {83, 8A, C3, CA} as a ciphertext, there is a 50% chance that
the corresponding plaintext is 0E or 0F; much higher than for a
random function.
Actually, there is also another attack that gives key information,
but I thought I'd point out this pattern first, as a demonstration
that not all attacks necessarily involve obtaining the key.
> COMMENTS
> The model is a single linear mixing with unknown tables on both the
> input and output. This seems to be the ultimate simplification of
> both the Mixing and VSBC ciphers, and in fact may be a step too far.
Yes, it is; the linear BBM is not sufficiently well hidden by the
tables. Consider
OutX = TX[ 3 TA[InA] + 2 TB[InB] (mod 2)(mod p) ]
Suppose we have two plaintext blocks, (InA1 InB1) and (InA2 InB2),
that map to the same value for OutX (e.g. 0B => 01 and 1D => 02 in
the sample table given above).
Then we can write (taking all arithmetic to be implicitly
(mod 2)(mod p)):
TX[ 3 TA[InA1] + 2 TB[InB1] ] = TX[ 3 TA[InA2] + 2 TB[InB2] ]
Since TX is a permutation, this implies
3 TA[InA1] + 2 TB[InB1] = 3 TA[InA2] + 2 TB[InB2]
or
3 TA[InA1] + 2 TB[InB1] - 3 TA[InA2] - 2 TB[InB2] = 0
which is a linear equation with the table entries as variables.
For the example of 0B => 01 and 1D => 02, we would get
3 TA[0x0] + 2 TB[0xB] - 3 TA[0x1] - 2 TB[0xD] = 0
Blocks that map to the same value for OutY can also be used; they
will yield equations of the form
2 TA[InA1'] + 3 TB[InB1'] - 2 TA[InA1'] - 3 TB[InB2'] = 0
If we can find 32 suitable linearly independent equations (which
simply requires having enough known or chosen text), we can solve
for the 32 unknowns TA[0]..TA[15] and TB[0]..TB[15]. Once the TA
and TB tables are known, it is trivial to find TX and TY.
I haven't implemented code to solve the system of equations (my
linear algebra is a little rusty), but here is the rest as a Java
program:
import java.util.Random;
import java.util.Vector;
import java.util.Enumeration;
/**
* The 8-Bit Block Cipher in Java. For research analysis; not a useful
* cipher.
*
* @author Terry Ritter (C implementation)
* @author David Hopwood (Java conversion)
*/
public class EightBit {
// BBM by lookup
private static int[][] L0;
private static int[][] L1;
public static int[][] getL0() { return L0; }
public static int[][] getL1() { return L1; }
// BBM by computation
public static int FL0( int a, int b ) {
int t = (a^b) << 1;
if ((t & 0x10) != 0)
t ^= 0x13;
return a^t;
}
public static int FL1( int a, int b ) {
int t = (a^b) << 1;
if ((t & 0x10) != 0)
t ^= 0x13;
return b^t;
}
static {
// use computed BBM to fill global lookup
initLS(15);
}
private static void initLS( int lastel ) {
int size = lastel+1;
L0 = new int[size][size];
L1 = new int[size][size];
for (int a = 0; a <= lastel; a++) {
for (int b = 0; b <= lastel; b++) {
L0[a][b] = FL0( a, b );
L1[a][b] = FL1( a, b );
}
}
}
// keyed tables
private int TA[];
private int TB[];
private int TX[];
private int TY[];
public int[] getTA() { return TA; }
public int[] getTB() { return TB; }
public int[] getTX() { return TX; }
public int[] getTY() { return TY; }
private static void initTab( int tab[], int lastel ) {
for (int i = 0; i <= lastel; i++) {
tab[i] = i;
}
}
private static Random random = new Random();
/**
* Return an integer from 0..N, N < 256.
* mask MUST be 2**n - 1 for some n.
*/
private static int rand0thruN( int mask, int N ) {
int b;
do {
b = random.nextInt(); // 32-bit value
b ^= b >> 16;
b ^= b >> 8;
b &= mask; // b is 0..mask
} while (b > N);
return b;
}
/**
* Shuffle the table.
* mask MUST be 2**n - 1 for some n.
*/
private static void shufTab( int tab[], int mask ) {
int nxtmsk, N, rand, by;
do {
nxtmsk = mask >> 1;
for (N = mask; N > nxtmsk; N--) {
rand = rand0thruN( mask, N );
by = tab[N];
tab[N] = tab[rand];
tab[rand] = by;
}
mask = nxtmsk;
} while (mask != 0);
}
// object state ciphering
private int InA, InB, A, B, X, Y, OutX, OutY;
public void setInput(int a, int b) { InA = a; InB = b; mix8(); }
public int getInA() { return InA; }
public int getInB() { return InB; }
public int getA() { return A; }
public int getB() { return B; }
public int getX() { return X; }
public int getY() { return Y; }
public int getOutX() { return OutX; }
public int getOutY() { return OutY; }
private void mix8() {
A = TA[ InA ];
B = TB[ InB ];
X = L0[ A ][ B ];
Y = L1[ A ][ B ];
OutX = TX[ X ];
OutY = TY[ Y ];
}
// functional ciphering
public int mix8X( int ina, int inb ) {
return TX[ L0[ TA[ina] ][ TB[inb] ] ];
}
public int mix8Y( int ina, int inb ) {
return TY[ L1[ TA[ina] ][ TB[inb] ] ];
}
/**
* Constructor for an EightBit cipher. The keying tables are set
* randomly.
*/
public EightBit() {
// initialise and shuffle the 4 keying tables
TA = new int[16]; initTab( TA, 15 ); shufTab( TA, 15 );
TB = new int[16]; initTab( TB, 15 ); shufTab( TB, 15 );
TX = new int[16]; initTab( TX, 15 ); shufTab( TX, 15 );
TY = new int[16]; initTab( TY, 15 ); shufTab( TY, 15 );
}
}
/**
* Demonstration of attacks against the 8-Bit Block Cipher.
*
* @author David Hopwood
*/
class EightBitDemo {
private static final String[] hexDigits = {
"0", "1", "2", "3", "4", "5", "6", "7",
"8", "9", "A", "B", "C", "D", "E", "F",
};
public static void main( String[] args ) {
EightBit cipher = new EightBit();
int ina, inb, outx, outy;
boolean seenXinThisRow[], seenYinThisRow[],
seenXinCol[][], seenYinCol[][];
Vector[] plaintextsForX = new Vector[16];
Vector[] plaintextsForY = new Vector[16];
for (int i = 0; i <= 15; i++) {
plaintextsForX[i] = new Vector();
plaintextsForY[i] = new Vector();
}
int[] pt;
// show every possible plaintext and ciphertext, and demonstrate
// that no X or Y output is repeated within a row or column.
// first print the inb column labels
System.out.print(" ");
for (inb = 0; inb <= 15; inb++)
System.out.print(" " + hexDigits[inb]);
seenXinCol = new boolean[16][16]; // all false
seenYinCol = new boolean[16][16]; // all false
for (ina = 0; ina <= 15; ina++) {
seenXinThisRow = new boolean[16]; // all false
seenYinThisRow = new boolean[16]; // all false
// start row with ina label
System.out.print("\n " + hexDigits[ina]);
for (inb = 0; inb <= 15; inb++) {
cipher.setInput(ina, inb);
outx = cipher.getOutX();
outy = cipher.getOutY();
System.out.print(" " + hexDigits[outx] + hexDigits[outy]);
if (seenXinThisRow[outx] || seenXinCol[inb][outx])
throw new Error(
"X output was repeated; prediction failed");
seenXinThisRow[outx] = seenXinCol[inb][outx] = true;
if (seenYinThisRow[outy] || seenYinCol[inb][outy])
throw new Error(
"Y output was repeated; prediction failed");
seenYinThisRow[outy] = seenYinCol[inb][outy] = true;
pt = new int[] { ina, inb };
plaintextsForX[outx].addElement(pt);
plaintextsForY[outy].addElement(pt);
}
}
System.out.println("\n\nNo X or Y outputs were repeated in a " +
"row or column.\n");
// find linear equations that can be solved to reveal the 32
// TA and TB entries
Enumeration e;
int ina1, inb1, x1, y1;
int[][] L0 = EightBit.getL0();
int[][] L1 = EightBit.getL1();
int[] TA = cipher.getTA(); // for checking only
int[] TB = cipher.getTB(); // for checking only
for (int a = 0; a < 16; a++) {
e = plaintextsForX[a].elements();
pt = (int[]) (e.nextElement());
ina1 = pt[0];
inb1 = pt[1];
x1 = L0[TA[ina1]][TB[inb1]];
while (e.hasMoreElements()) {
pt = (int[]) (e.nextElement());
System.out.println("3 TA[0x" + hexDigits[ina1] + "] + " +
"2 TB[0x" + hexDigits[inb1] + "] - " +
"3 TA[0x" + hexDigits[pt[0]] + "] - " +
"2 TB[0x" + hexDigits[pt[1]] + "] = 0");
if (x1 != L0[TA[pt[0]]][TB[pt[1]]])
throw new Error("incorrect X equation");
}
e = plaintextsForY[a].elements();
pt = (int[]) (e.nextElement());
ina1 = pt[0];
inb1 = pt[1];
y1 = L1[TA[ina1]][TB[inb1]];
while (e.hasMoreElements()) {
pt = (int[]) (e.nextElement());
System.out.println("2 TA[0x" + hexDigits[ina1] + "] + " +
"3 TB[0x" + hexDigits[inb1] + "] - " +
"2 TA[0x" + hexDigits[pt[0]] + "] - " +
"3 TB[0x" + hexDigits[pt[1]] + "] = 0");
if (y1 != L1[TA[pt[0]]][TB[pt[1]]])
throw new Error("incorrect Y equation");
}
}
System.out.println("\nAll equations were correct.");
}
}
- --
David Hopwood <hopwood@zetnet.co.uk>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
Key fingerprint = 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Key type/length = RSA 2048-bit (always check this as well as the fingerprint)
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBNUGy/zkCAxeYt5gVAQFPcQgAhMQ71kDKK0RqC5a7JJDD1wf6klWSIagZ
GN8AmXs64Ir7pDZ3sBX9+4T88zV4RcRbxOy7QbZRk8QzfLLTFirMO63iU2FqDAxV
xHVyvOH9nYQl65QHVhF/bzeuyWWBfTwMYl7fJeWNwXliaXK0cxLQeeJVffj7CNJ3
hsrq6g79Gq400vy50Tc9IRy2Aa2wC7v6HSDPxvdmk7Q5vLuGnCyXhEXxSjiTsKLl
FMgPXD73uZYzRaHDY5FVjEJOtDU51iVKGv0VNI98ByroqfDMjRZuoAwhSyjF7B61
5NFhsfe5qddb/Oyv8I5ta1fNAsgBrpaD7Mw43l7xA2Tg/NsNeM05Ww==
=VFWB
-----END PGP SIGNATURE-----
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt
Subject: Re: Break This 8-Bit Block Cipher (long)
Date: Tue, 28 Apr 1998 04:12:10 GMT
Lines: 105
Message-ID: <354555fd.3948563@news.io.com>
References: <353a6292.2214286@news.io.com> <1998042510591374952@zetnet.co.uk>
Note: This is a quick response since I am being otherwise occupied. I
also do want to actually work out the attack before speculating on the
consequences.
On Sat, 25 Apr 1998 10:59:13 +0100, in
<1998042510591374952@zetnet.co.uk> in sci.crypt David Hopwood
<hopwood@zetnet.co.uk> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>In message <353a6292.2214286@news.io.com>
> ritter@io.com (Terry Ritter) wrote:
>
>> THE PROBLEM
>
>> We have a block cipher composed of four shuffled substitution
>> tables and a linear Balanced Block Mixer. [...]
>> We assume that we know every possible plaintext and ciphertext
>> pair, plus the everything about the mixer. The goal is to develop
>> the table permutations -- the internal key -- from the known
>> information, using some sort of scalable algorithm.
>
>That is _a_ goal, but not necessarily the goal. It would also be a
>weakness in the cipher if it were possible, given some subset of the
>plaintext/ciphertext pairs, to find other plaintext/ciphertext
>pairs that were not given (using a scalable algorithm).
I find it hard to take this complaint too literally, since this
"weakness" is of course inherent in every possible block cipher under
known-plaintext conditions: Simply by knowing *one* known-plaintext
pair we *have* reduced the uncertainty for every *other* ciphertext
(whose associated plaintext now cannot be the one we already know).
>[...]
>when InB is held constant and
>InA is varied from 0 to 15 (i.e. a column in the output table),
>OutX will take on each value from 0 to 15 exactly once. The same
>applies to OutY in each column, and to OutX and OutY in each row.
Yes, of course. This is inherent in the Latin square nature of the
mixing, and is neither secret nor surprising. The effect is
demonstrated in the Active BBM page:
http://www.io.com/~ritter/JAVASCRP/ACTIVBBM.HTM
>This is a significant weakness because it leaks information about
>plaintext/ciphertext pairs that would not otherwise be known.
Again, at least in the abstract, this "weakness" is inherent in any
block cipher under known-plaintext conditions. Presumably the issue
here is the small sub-block size, but even in this case, the attack
seems strange.
>For
>example, suppose that an attacker knows the ciphertext for input
>blocks 00 to 0E inclusive in the above table. He/she can infer that
>the ciphertext for 0F is C3, and can decrypt this ciphertext if it
>is encountered.
But The Opponents have just collected *all*but*one* of the ciphertexts
associated with changing just one plaintext input (with the others
fixed). And all they get out of this is the one remaining ciphertext.
So exactly what prevents them from getting the remaining ciphertext
the same way they got all the others?
>[...]
>Suppose we have two plaintext blocks, (InA1 InB1) and (InA2 InB2),
>that map to the same value for OutX (e.g. 0B => 01 and 1D => 02 in
>the sample table given above).
>
>Then we can write (taking all arithmetic to be implicitly
>(mod 2)(mod p)):
>
> TX[ 3 TA[InA1] + 2 TB[InB1] ] = TX[ 3 TA[InA2] + 2 TB[InB2] ]
>
>Since TX is a permutation, this implies
>
> 3 TA[InA1] + 2 TB[InB1] = 3 TA[InA2] + 2 TB[InB2]
>or
> 3 TA[InA1] + 2 TB[InB1] - 3 TA[InA2] - 2 TB[InB2] = 0
>
>which is a linear equation with the table entries as variables.
>[...]
>If we can find 32 suitable linearly independent equations (which
>simply requires having enough known or chosen text), we can solve
>for the 32 unknowns TA[0]..TA[15] and TB[0]..TB[15]. Once the TA
>and TB tables are known, it is trivial to find TX and TY.
OK. This is the good stuff! This is what I asked for, and presumably
the desired solution. But I expect to have to work it out in detail
before I gain any deep insight into the problem.
My thanks to David for his help and interest.
---
Terry Ritter ritter@io.com http://www.io.com/~ritter/
The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt
Subject: Re: Break This 8-Bit Block Cipher (long)
Date: Wed, 29 Apr 1998 15:51:54 GMT
Lines: 148
Message-ID: <35474c6f.949708@news.io.com>
References: <353a6292.2214286@news.io.com> <1998042510591374952@zetnet.co.uk>
OK, I've looked at the attack, and I'm having trouble getting it to
work.
On Sat, 25 Apr 1998 10:59:13 +0100, in
<1998042510591374952@zetnet.co.uk> in sci.crypt David Hopwood
<hopwood@zetnet.co.uk> wrote:
>[...]
>the linear BBM is not sufficiently well hidden by the
>tables. Consider
>
> OutX = TX[ 3 TA[InA] + 2 TB[InB] (mod 2)(mod p) ]
>
>Suppose we have two plaintext blocks, (InA1 InB1) and (InA2 InB2),
>that map to the same value for OutX (e.g. 0B => 01 and 1D => 02 in
>the sample table given above).
>
>Then we can write (taking all arithmetic to be implicitly
>(mod 2)(mod p)):
>
> TX[ 3 TA[InA1] + 2 TB[InB1] ] = TX[ 3 TA[InA2] + 2 TB[InB2] ]
Yes.
>Since TX is a permutation, this implies
>
> 3 TA[InA1] + 2 TB[InB1] = 3 TA[InA2] + 2 TB[InB2]
>or
> 3 TA[InA1] + 2 TB[InB1] - 3 TA[InA2] - 2 TB[InB2] = 0
Actually, subtraction and addition are the same thing mod 2, so we
really have no choice but to "add" all terms.
>which is a linear equation with the table entries as variables.
>For the example of 0B => 01 and 1D => 02, we would get
>
> 3 TA[0x0] + 2 TB[0xB] - 3 TA[0x1] - 2 TB[0xD] = 0
Yes.
>Blocks that map to the same value for OutY can also be used; they
>will yield equations of the form
>
> 2 TA[InA1'] + 3 TB[InB1'] - 2 TA[InA1'] - 3 TB[InB2'] = 0
Sure.
>If we can find 32 suitable linearly independent equations (which
>simply requires having enough known or chosen text), we can solve
>for the 32 unknowns TA[0]..TA[15] and TB[0]..TB[15].
OK, this seems to be the problem: The apparently reasonable idea that
32 such equations exist (or that even 2 equations exist with the same
2 unknowns) appears false. To see why in a manageable size, let's go
back to the 4-bit mixing table from the earlier 4-bit block cipher
article:
X = 3A + 2B (mod 2)(mod p), p = 111
Y = 2A + 3B (mod 2)(mod p)
Here A selects a row, B selects a column, and the selected
entry is XY.
0 1 2 3
0 00 23 31 12
1 32 11 03 20
2 13 30 22 01
3 21 02 10 33
Let's assume that we know TA[] and TB[] so we can see inside the
computation and group things appropriately. Without loss of
generality and for analytic convenience only, we assume that TA[] and
TB[] are the identity substitution. Let's start with X, which is 3
TA[] + 2 TB[], and group the equations which produce the same X value:
3 TA[0] + 2 TB[0] = 0
3 TA[1] + 2 TB[2] = 0
3 TA[2] + 2 TB[3] = 0
3 TA[3] + 2 TB[1] = 0
3 TA[0] + 2 TB[3] = 1
3 TA[1] + 2 TB[1] = 1
3 TA[2] + 2 TB[0] = 1
3 TA[3] + 2 TB[2] = 1
3 TA[0] + 2 TB[1] = 2
3 TA[1] + 2 TB[3] = 2
3 TA[2] + 2 TB[2] = 2
3 TA[3] + 2 TB[0] = 2
3 TA[0] + 2 TB[2] = 3
3 TA[1] + 2 TB[0] = 3
3 TA[2] + 2 TB[1] = 3
3 TA[3] + 2 TB[3] = 3
This is every possible combination for the 2-bit input values InA and
InB, grouped by the internal 2-bit X results for all 16 possible 4-bit
"messages." So we have 16 equations, and can similarly do Y to get 16
more. But note that this is *not* 16 different views of 2 unknown
variables similar to what we saw in Linear Algebra problems. Since
each table element is a different unknown, we must collect all 4 of
the equations in each group just to cover the unknowns once. And
since this is mod 2, when we collect an even number of expressions
which produce the same value, they sum to zero:
3TA[0]+2TB[0]+3TA[1]+2TB[2]+3TA[2]+2TB[3]+3TA[3]+2TB[1] = 0
3TA[0]+2TB[3]+3TA[1]+2TB[1]+3TA[2]+2TB[0]+3TA[3]+2TB[2] = 0
3TA[0]+2TB[1]+3TA[1]+2TB[3]+3TA[2]+2TB[2]+3TA[3]+2TB[0] = 0
3TA[0]+2TB[2]+3TA[1]+2TB[0]+3TA[2]+2TB[1]+3TA[3]+2TB[3] = 0
So now we apparently have 4 equations and 8 unknowns.
But if we *look* at these equations and re-arrange the terms, we find
that we *actually* have just *one* equation, expressed 4 times. This
equation is just the sum of all input possibilities in the X mixing
function. And we can do the same thing with Y.
Now, in the 8-bit size, we have 16 unknowns in each 4-bit table, and
256 possible 8-bit "messages." So we start out with 16 groups of 16
equations, and then get 16 equations which each cover all 32 input
variables exactly once. But all of these equations are the same, so
in the end we have just 2 different equations (X and Y), and this is
not going to solve the system.
>Once the TA
>and TB tables are known, it is trivial to find TX and TY.
Yup.
>I haven't implemented code to solve the system of equations (my
>linear algebra is a little rusty), [...]
So far, I don't see that it works, but perhaps someone has a better
idea.
---
Terry Ritter ritter@io.com http://www.io.com/~ritter/
The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: David Hopwood <hopwood@zetnet.co.uk>
Newsgroups: sci.crypt
Subject: Re: Break This 8-Bit Block Cipher (long)
Date: Fri, 15 May 1998 17:47:47 +0100
Message-ID: <1998051517474774952@zetnet.co.uk>
References: <353a6292.2214286@news.io.com> <1998042510591374952@zetnet.co.uk> <35474c6f.949708@news.io.com>
Lines: 256
-----BEGIN PGP SIGNED MESSAGE-----
In message <35474c6f.949708@news.io.com>
ritter@io.com (Terry Ritter) wrote:
> OK, I've looked at the attack, and I'm having trouble getting it to
> work.
Yes, so did I when I looked at it more closely, but I've now fixed it.
There is not enough information to uniquely determine the table
entries; however the key space is divided into classes of equivalent
keys, and it is possible to find which equivalence class was used
(which is all that a cryptanalyst needs). I've written a Java program
to implement this, at
http://www.users.zetnet.co.uk/hopwood/crypto/ritter/kBit.zip
Try "java kBitDemo -known -showtables 8 19", for example (you will
need to install the JDK from www.javasoft.com, if you don't already
have it).
Instances with a block size of up to 20 bits can be solved in less
than a minute on a PC (providing the -lowmemory option is used).
The attack requires more known plaintext than I originally thought
would be needed, though (the number of plaintexts required is a
roughly constant fraction of the number of possible input blocks,
although it may be possible to improve that).
> On Sat, 25 Apr 1998 10:59:13 +0100, in
> <1998042510591374952@zetnet.co.uk> in sci.crypt David Hopwood
> <hopwood@zetnet.co.uk> wrote:
> >[...]
> >the linear BBM is not sufficiently well hidden by the
> >tables. Consider
> >
> > OutX = TX[ 3 TA[InA] + 2 TB[InB] (mod 2)(mod p) ]
> >
> >Suppose we have two plaintext blocks, (InA1 InB1) and (InA2 InB2),
> >that map to the same value for OutX (e.g. 0B => 01 and 1D => 02 in
> >the sample table given above).
> >
> >Then we can write (taking all arithmetic to be implicitly
> >(mod 2)(mod p)):
> >
> > TX[ 3 TA[InA1] + 2 TB[InB1] ] = TX[ 3 TA[InA2] + 2 TB[InB2] ]
> Yes.
It turns out to be easier to handle a single equation for each
plaintext/ciphertext pair, with entries in the inverse tables for
TX and TY (call them ITX and ITY) as additional unknowns:
3 TA[InA] + 2 TB[InB] + ITX[OutX] = 0
2 TA[InA] + 3 TB[InB] + ITY[OutY] = 0
The advantage of doing this is that the full set of these equations
completely characterise the overall permutation, so a key is equivalent
to the original key if-and-only-if it is a solution to the equations.
[...]
> >If we can find 32 suitable linearly independent equations (which
> >simply requires having enough known or chosen text), we can solve
> >for the 32 unknowns TA[0]..TA[15] and TB[0]..TB[15].
> OK, this seems to be the problem: The apparently reasonable idea that
> 32 such equations exist (or that even 2 equations exist with the same
> 2 unknowns) appears false.
Yes, you're right. That's a consequence of the balanced mixing structure;
if no variables are known initially, any linear combination of the
equations will have at least three unknown terms.
However, it turns out that the equations have m*m*(m-1) solutions
(where m is 2^(k/2), i.e. the size of a table, or equivalently the number
of elements in the field). Since we only need one of those solutions,
it's possible to give fixed values to some of the table entries (in
practice, 3 of them), and then solve for the rest.
First, here's an argument for why there are at least (and I think
always exactly) m*m*(m-1) solutions:
Let s, t and u be constant elements in the field, with s != 0
f(x) = sx + t
g(x) = sx + u
u(x) = (x + 3t + 2u)/s
v(x) = (x + 2t + 3u)/s
'.' denotes functional composition.
For all a and b,
TX.u[L0(f.TA[a], g.TB[b])]
= TX.u[3s TA[a] + 3t + 2s TB[b] + 2u]
= TX[((3s TA[a] + 2s TB[b] + 3t + 2u) + 3t + 2u)/s]
= TX[3 TA[a] + 2 TB[b]]
= TX[L0(TA[a], TB[b])]
and
TY.v[L1(f.TA[a], g.TB[b])]
= TY.v[2s TA[a] + 2t + 3s TB[b] + 3u]
= TY[((2s TA[a] + 3s TB[b] + 2t + 3u) + 2t + 3u)/s]
= TY[2 TA[a] + 3 TB[b]]
= TY[L1(TA[a], TB[b])]
I.e. if (TA, TB, TX, TY) is a solution, then so is (f.TA, g.TB, TX.u, TY.v)
for each s != 0, t, and u. These represent equivalent keys (in the usual
sense of representing the same mapping from plaintext to ciphertext).
There are m possibilities for each of t and u, and m-1 possibilities
for s, so this proves that the number of solutions is either zero, or at
least m*m*(m-1). We know that there is at least one solution (the original
key), so there must be at least m*m*(m-1). [I can't immediately see how to
show that there are no more than that, but it's not really critical.]
This means that without loss of generality, we can set
f.TA[i] = 0
f.TA[j] = 1
g.TB[k] = 0
for any indices i, j and k where i != j.
[There will always be an equivalent key that satisfies the above, since
the equations
s TA[i] + u = 0
s TA[j] + u = 1
s TB[k] + t = 0
always have a solution.]
======
Let's try an example by hand with 4-bit blocks:
0 1 2 3
0 00 23 31 12
1 32 11 03 20
2 13 30 22 01
3 21 02 10 33
The original table entries are:
TA[0] = 0, TB[0] = 0, TX[0] = 0, TY[0] = 0
TA[1] = 1, TB[1] = 1, TX[1] = 1, TY[1] = 1
TA[2] = 2, TB[2] = 2, TX[2] = 2, TY[2] = 2
TA[3] = 3, TB[3] = 3, TX[3] = 3, TY[3] = 3
We'll use the names TA', TB', ITX' and ITY' for the tables that will be
found by cryptanalysis (i.e. f.TA, g.TB, (TX.u)^-1 and (TY.v)^-1)).
Arbitrarily pick i = 1, j = 3, k = 2. (If doing a known plaintext attack,
we could choose these values to correspond to the terms of the first
available equation, so that additional variables can be found as quickly
as possible.)
Set TA'[1] = 0, TA'[3] = 1, TB'[2] = 0.
I can't work out GF(2^k) multipliction in my head, so here is a table for
multiplication:
* 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 3 1
3 0 3 1 2
Now repeatedly pick equations for which all but one term is known:
3 TA'[1] + 2 TB'[2] + 1 ITX'[0] = 0
=> ITX'[0] = 0
3 TA'[3] + 2 TB'[1] + 1 ITX'[0] = 0
=> 2 TB'[1] = 3
=> TB'[1] = 2
3 TA'[1] + 2 TB'[1] + 1 ITX'[1] = 0
=> ITX'[1] = 3
2 TA'[3] + 3 TB'[2] + 1 ITY'[0] = 0
=> ITY'[0] = 2
2 TA'[2] + 3 TB'[1] + 1 ITY'[0] = 0
=> 2 TA'[2] = 3
TA'[2] = 2
3 TA'[2] + 2 TB'[3] + 1 ITX'[0] = 0
=> 2 TB'[3] = 1
TB'[3] = 3
3 TA'[0] + 2 TB'[3] + 1 ITX'[1] = 0
=> 3 TA'[0] = 2
=> TA'[0] = 3 (check: TA entries sum to 0)
3 TA'[0] + 2 TB'[0] + 1 ITX'[0] = 0
=> 2 TB'[0] = 2
TB'[0] = 1 (check: TB entries sum to 0)
3 TA'[0] + 2 TB'[1] + 1 ITX'[2] = 0
=> ITX'[2] = 1
3 TA'[0] + 2 TB'[2] + 1 ITX'[3] = 0
=> ITX'[3] = 2 (check: ITX entries sum to 0)
2 TA'[0] + 3 TB'[2] + 1 ITY'[1] = 0
=> ITY'[1] = 1
2 TA'[0] + 3 TB'[3] + 1 ITY'[2] = 0
=> ITY'[2] = 3
2 TA'[0] + 3 TB'[1] + 1 ITY'[3] = 0
=> ITY'[3] = 0 (check: ITY entries sum to 0)
In summary:
TA'[0] = 3, TB'[0] = 1, ITX'[0] = 0, ITY'[0] = 2
TA'[1] = 0, TB'[1] = 2, ITX'[1] = 3, ITY'[1] = 1
TA'[2] = 2, TB'[2] = 0, ITX'[2] = 1, ITY'[2] = 3
TA'[3] = 1, TB'[3] = 3, ITX'[3] = 2, ITY'[3] = 0
Invert ITX' and ITY':
TX'[0] = 0, TY'[0] = 3
TY'[1] = 2, TY'[1] = 1
TY'[2] = 3, TY'[2] = 0
TY'[3] = 1, TY'[3] = 2
which gives the same output table as for the original key:
0 1 2 3
0 00 23 31 12
1 32 11 03 20
2 13 30 22 01
3 21 02 10 33
Voila.
- --
David Hopwood
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
Key fingerprint = 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Key type/length = RSA 2048-bit (always check this as well as the fingerprint)
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBNVs3mTkCAxeYt5gVAQEj7wgA0ExYH2VRhBVruCoVX7tJkIauTWzTkgiH
/OyPrLdf3D2V8/m+gm5sGZI95jVe9aRDFuQ1/kfNJC7s8YcjDRIw68NE5VGUTRBc
z7YAvJa290WnquiBlIcD92KINWD0f3Em3Z1x88ohMd9CJY5xXC3HZnTi+spQIVJ2
SUyrpj+a+KKsWb+/hKEEcEFq/sUul2BbuD0mq7h+SHJ3IiqAVZ8cSRTnYcdljQXt
AAmeOHLkQQ/iXARaJucJAuqoTViIrJRVzR1JnSmhBMcr8Ax6BF0Z4QGTJ0qTvwtZ
8pSFQFBSaGZapHPNLDocrLFEhbSfkgLVIPZcnH+gxzetZojvAv1dhA==
=5Ucy
-----END PGP SIGNATURE-----
Terry Ritter, his current address, and his top page.
Last updated: 1998-05-29