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