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 should make Defined Plaintext attacks impossible in many applications. This can be done by using random keying specific to each message:
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:
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 28 triples (out of 224 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 224 possible values of the left three bytes, there are 216 "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