on a Simplified BBM VSBC

Here we consider a ** Defined Plaintext attack** on the
structure of a Variable Size Block Cipher (VSBC) which uses
Balanced Block Mixing (BBM) components. In this attack, The
Opponent can introduce plaintext at will and collect the related
ciphertext, but does not know the key or the structure of any
table.

It is important to understand that the larger cipher system
** can** and

- by using a different starting IV (table-select values) for each message,
- by using a different primary key for each message (classical message keys), or
- by placing different dynamic keying information in each block (modern message keys).

All of these approaches use random values which The Opponent
can neither define nor expose, but these values must be available on
both ends. One possibility is that both ends retain some secret but
progressing cryptographic state which is used for message keys. But
more typically, using message keys implies that random keying
information (enciphered under a main key) must be transported (or
saved) along with the message. The problem is that this *expands*
the ciphertext. Of course, in many or even *most* applications,
that is no problem at all.

But applications do exist for fast ciphering which does *not*
expand ciphertext, and this may eliminate the above possibilities.
A typical application might be the ciphering of variable-size data
fields in a database program. This is exactly this sort of
application which could most benefit from a VSBC, and yet also
best supports a Defined Plaintext attack. We wish to see how
successful such an attack might be.

One reasonable approach to a VSBC design is described in A Variable Size Block Core on these pages. Not shown is the Dynamic Table Selection, where we select each particular table from an array of tables, based on both the data and table in the previous column. The diagram is already visually complicated by the many tables used, and here we wish to simplify that architecture and so better understand the ability to attack it.

Perhaps the best way to simplify the diagram is to eliminate
the tables, and to show a small fixed-size structure for analysis.
We ignore Dynamic Table Selection to see what we have without it.

Here we have the simplified architecture. We hide the tables without loss of generality simply by assuming that each BBM may have any desired structure. Each of these BBM's might be a separate pair of keyed, 65536-byte Latin square tables, for extreme strength and nonlinearity. But in practice, there is a limit on the effort we want to put into main keying, and this probably means using linear BBM's with smaller nonlinear tables. Unfortunately, attacking the system eventually means resolving those tables, and then the diagram is no longer simple anymore.

Still, we can illustrate some issues with a simplified diagram.
Here we have 12 BBM's in 4 rows by 3 columns forming a 4-byte block
cipher. The top two rows represent right-going one-way diffusion
layers. In the simplified system (*without* Dynamic Table
Selection), these are the *only* right-going diffusions, so if
these can be defeated, the block-wide diffusion we expect from a
block cipher can also be defeated.

Suppose we try to "cancel" the right-going diffusion in the
top layer. That is, suppose we *change* the leftmost data
byte and then *also* change the adjacent data byte. In the
figure, each "change," and each "consequence" of those changes,
are highlighted as medium red lines.

Probably the best way to think about these structures is to recall some useful BBM properties:

- The mapping is one-to-one: Every possible input value (across both inputs) produces a different output value (taken across both outputs), and all values are possible.
- Any possible change to a single input will always change both outputs; to change only a single output, it is necessary to change both inputs.
- Stepping any one input through all possible values (while keeping the other input fixed) will step every output through all possible values.

Because of the BBM properties, we can always find some second
byte value which will leave the top right-going diffusion channel
unchanged, despite the data having changed. But there are
*two* right-going diffusion layers, and the second will
pick up the change and carry it across the block. The obvious
next question is whether one can cancel *both* right-going
layers simultaneously.

We have seen that we *can* cancel the first right-going
carry, so now we are interested in cancelling the carry from the
the leftmost BBM in the second layer. For any change in the left
input of that second-layer BBM, we can cancel that change (leave
the carry-channel unchanged), *provided* that we can place
any possible value on the right input. We can do *that* if
we can control both of the inputs to the BBM in the second column
in the top row. We do have direct control of the right input to
the second BBM, but the left input is the carry from the first
BBM in that row.

So the question becomes: If we traverse all possible values of the second and third bytes, can we find a pair which will leave both carry channels unchanged? This is the condition shown in the diagram. And this brings us back to the properties of the BBM.

In the same sense that each BBM is itself invertible, the chained
structure with 3 inputs and 3 outputs is *also* invertible.
This means that one can fix the values on any two output channels,
and still support every possible value on the other. For *any*
two carry values, there are *always* 2^{8} triples
(out of 2^{24} for the 3 inputs) which will leave the carry
channels unchanged, and this is independent of whether the BBM's
are linear or not. Presumably, one could externally detect and
collect such "groups" of related values, and this can be done with
*any* adjacent three columns, not just the start of the block.

So, if we change the leftmost byte, there is exactly one pair
of bytes which will produce the same two right-going carry values
as before. And we can detect that situation because of a lack of
avalanche in the right part of the block.

Of all 2^{24} possible values of the left three bytes,
there are 2^{16} "groups" of 256 triples which each
represent a particular pair of right-going carry values. Within
such a group, S20 can be taken through all possible values
(although the actual values will not be known). Further, the
left-going carry inputs to both the leftmost BBM on the third row,
and the second BBM on the fourth row will be fixed, because all
right-going diffusion has been cancelled.

One can think of solving the bottom-left sub-system, or at least
getting some relationships, because of the linear nature of the
BBM's proper. But as far as is known, the keyed tables S30, S31,
S40, S41, and S42 prevent those computations.

Assuming that we have a input triple that cancels all
right-going diffusion (again, in the absence of Dynamic Table
Selection) we want to know is whether we can *extend* the
relationship for another input value, to produce a related quad.

In the figure, the mid-size red lines are the changed bytes with
a successful cancelling set. The larger green lines represent our
attempt to build upon that situation. To continue to cancel the
right-going diffusion, we have to keep the right outputs fixed for
two changing BBM's in the top two layers. But this is harder than
it looks. If we try to extend the situation by only changing the
third and fourth bytes, there seems to be just no way to do it.

The ability to cancel the right-going diffusions seems to set out a substantial relationship in the cipher, but it is unclear how this can be used. The internal linear relationships are hidden behind layers of keyed tables, so the actual values involved are not known.

In analysis we seek situations in which some values do not occur, or in which some values occur at least twice, for we can use that information to define a value or relationship. But when every value can always occur with the same probability, that particular sort of reasoning does not seem helpful.

In fact, this ability to cancel the right-going diffusions seems
little more than an obvious extension of the property of a single
BBM: Suppose we have just one BBM, with a table on each input and
a table on each output. Even in this minimal case, we can obviously
select input values which change only the leftmost output, so that
no "avalanche" occurs in the rightmost element. Presumably this
gives us information about the system, but does this really help us
expose any table element, or even yield any useful relationship
at all? And if not, can we not reason that the more complex
multi-layer structure must in fact behave similarly?

First we again note that we discuss a *simplified* system
in which Dynamic Table Selection is not part of the structure. The
three layers of right-going Dynamic Table Selection in a practical
design should complicate this sort of attack by up to 24 keying bits
(depending on the number of tables).

Next, with this simplified system, at first it seems as though the ability to cancel layers should give great power to develop powerful relationships between columns. But after having done this, it is not clear where to go from there.

This is not a successful attack, because, at this point, it does not provide insight into any particular table value, or even build relationships between particular tables in different columns.

David Wagner was kind enough to look at the previous version
of these arguments, and to voice concerns about the ability to
cancel the right-going diffusions.

*Last updated:* 1998-03-17