A 4-bit-wide block cipher model is presented. Given all 16 possible messages and their ciphertexts, the goal is to develop the table arrangements which are the cipher key. The tiny size is intended to support a deep understanding of strength, something which to date has been impossible in any full-size cipher. Related 6-bit and 8-bit versions are also mentioned, should the 4-bit version be in some way a special case.
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt
Subject: Break This 4-Bit Block Cipher!
Date: Mon, 30 Mar 1998 04:02:40 GMT
Message-ID: <351f18af.418844@news.io.com>
BREAK THIS 4-BIT BLOCK CIPHER!
Terry Ritter ritter@io.com
Ritter Software Engineering
http://www.io.com/~ritter/
1998-03-29
ABSTRACT
A 4-bit-wide block cipher model is presented. Given all 16 possible
messages and their ciphertexts, the goal is to develop the table
arrangements which are the cipher key. The tiny size is intended
to support a deep understanding of strength, something which to date
has been impossible in any full-size cipher. Related 6-bit and 8-bit
versions are also mentioned, should the 4-bit version be in some way
a special case.
THE PROBLEM
We have a 4-bit block cipher. It is composed of four keyed 2-bit
invertible substitution tables (4 entries of 2 bits each), and a
linear Balanced Block Mixer. That's it. This is an extremely
reduced *model* specifically intended for analysis.
We assume that we know every possible plaintext and ciphertext pair:
this is the ultimate known-plaintext and defined-plaintext attack.
The goal is to develop the table permutations -- the key -- with
some sort of scalable algorithm.
| 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 STARTING ANALYSIS
Since InA and InB are known, we can write equations for unknown
table entries TA[InA] and TB[InB] in terms of known input values:
A = TA[ InA ]
B = TB[ InB ]
On the other hand, although the output values are also known, it
might seem that we have to define those values in terms of unknown
table positions, as well as unknown values:
OutX = TX[ X ]
OutY = TY[ Y ]
But since we know that the tables are invertible, without loss of
generality we can introduce inverse tables IX and IY and write:
X = IX[ OutX ]
Y = IY[ OutY ]
(If we succeed in defining the inverse tables, we can easily develop
their inverses, which are the values we want.)
So now we have 4 known external values which select 4 unknown values
which have a linear BBM relationship to each other. The orthogonal
Latin squares in the BBM are developed algorithmically as follows:
X = 3A + 2B (mod 2)(mod p), p = 111
Y = 2A + 3B (mod 2)(mod p)
The BBM equations may seem unusual, and this can make it awkward to
think about the system. So, instead of the equations, we can use a
table. Here A selects a row, B selects a column, and the selected
entry is XY. Remember, there are only 4 different values in each
2-bit half-block.
0 1 2 3
0 00 23 31 12
1 32 11 03 20
2 13 30 22 01
3 21 02 10 33
Suppose we concentrate on the case where A = 0: This is the top
row of the table. Note that both X and Y take on each of their
4 possible values exactly once. But this happens in *every* row,
so any of these give the same results, as long as we do not know
the TA keying.
Suppose we hope to identify 00 by the fact that X = Y: But if we
look at the table, we find that this *also* happens exactly 4
times, once for each possible value. Again, a suitable keying of
TA and TB can produce this same effect for any input.
These simple tests appear to have gotten nowhere. Can other tests
improve upon the situation? Can we *prove* that this simple system
is, or is not, solvable?
AVOIDING BRUTE FORCE
Since each 2-bit table has 4 elements (with 8 unknown bits), there
are 4! or 24 different tables (for about 4.6 bits of keying per
selection). We know all 16 of the 4-bit "messages" for a known
information total of 64 bits, against the unknown apparent keyspace
of about 18 bits. This is brute-force territory, but the intent
here is to find an attack which will scale up with the model.
If we are simply unable to resist the pull of brute-force, we should
instead consider the similar 6-bit block cipher which uses 3-bit
tables (at about 15.3 bits each). Here we know all 64 6-bit messages
for a known total of 384 bits, against an unknown apparent keyspace
of about 61 bits.
Or we might consider the 8-bit block cipher which uses 4-bit tables
(about 44 bits each), and has 256 8-bit messages for a known
information total of 2048 bits, against an unknown apparent keyspace
of about 177 bits.
Under the given conditions, there is always substantially more known
information than the internal state we are trying to define.
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 16-element codebook
would be small enough to either break by hand, or 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. But
http://www.io.com/~ritter/JAVASCRP/ACTIVBBM.HTM
has an new introduction to BBM computation, and implements a couple
of functional model-size BBM's in JavaScript.
---
Terry Ritter ritter@io.com http://www.io.com/~ritter/
The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
Terry Ritter, his current address, and his top page.
Last updated: 1998-03-31