A Variable Size Block Cipher (VSBC) is distinguished by its ability to cipher blocks of dynamically arbitrary size, to the byte, and yet produce good data diffusion across the whole block.

In dramatic contrast to conventional designs, here most
diffusion occurs in simple *linear* BBM operations
**which are not intended to provide strength!**
By itself, linear mixing has no
strength
at all, but it does set the stage for
keyed
substitution tables
which *do* have strength. The BBM's provide a *guaranteed,*
exactly
balanced and reversible mixing
which, in a successful design, prevents individual tables from being
distinguished and solved.

Here we present the ciphering ** core,** the
architecture of tables and mixing which performs actual ciphering.
The tables are initialized or
"keyed"
by a separate process which
shuffles
each table independently, twice.

**SPEED**-- about 985,000 bytes per second in 16-byte blocks and about 1,120,000 bytes per second in 64-byte blocks (on a 100 MHz "686," under Win95, with the Borland 32-bit Delphi 2 compiler). The typical keying overhead is around 64 milliseconds for 64 tables.**STRENGTH**-- greater than 128 bits for a block size of at least 64 bits and at least 64 keyed tables.**BLOCK SIZE**-- dynamically selectable to the byte at ciphering time, but this is a block cipher anda stream cipher. Clearly, a single program can handle "legacy" 64-bit blocks, "modern" 128-bit blocks, "independent" 64-byte blocks and 512-byte disk blocks, and anything in between.*not***KEY SIZE**-- arbitrary, independent of block size.

- Variable Size Block Cipher Attributes
- Background
- Components
- Scalability
- The BBM
- A Variable Size Block
- Dynamic Table Selection
- Data Diffusion
- Deciphering
- Large Blocks
- Primary Keying
- Strength
- Dynamic Keying
- Authentication
- Strength Arguments
- Summary of Advantages
- Also See:

The first known publication of the concept of a Variable Size Block Cipher (VSBC) -- and the first published VSBC design -- was the 1995 Aug 20 sci.crypt announcement by Ritter and the resulting discussion. The general lack of understanding in the responses indicates that the concept was new to those who replied.

A patent has been granted on Variable Size Block Ciphers.

In this Variable Size Block Cipher core we have two main component types:

- keyed, invertible substitution tables, and
- Balanced Block Mixers (BBM's).

`In the figure, each box represents a table, and each hourglass
shape represents a BBM.
Plaintext
data bytes enter at the top, are substituted, mixed right,
substituted, mixed right, substituted, mixed left, substituted,
mixed left and substituted into
ciphertext.
Dynamic table selection is not shown.
`

The essence of the design is an inability to externally isolate or distinguish one table from another. This inability is directly related to the exact balance in the high-quality BBM mixing, as opposed to an exponential increase in complexity from repeated low-quality mixing with confusion.

Tables are widely used in
many designs, and even keyed tables are not that unusual. But in
this design *all* of the inter-element diffusion occurs in
distinct,
one-way diffusion
layers
composed of *linear*
Balanced Block Mixing (BBM) operations, and this *is* new.

This separation between mixing
(diffusion)
and keyed substitution
(confusion)
is beneficial in that the two operations can be seen,
understood, and measured separately. In conventional designs,
confusion and diffusion are often combined, which makes these ciphers
difficult to understand *or* measure. And conventional ciphers
do not scale down to testable size.

A Variable Size Block Cipher is scalable in a way that few designs are:

- First, the block size is dynamically selectable to the byte.
A single unchanged program can handle "legacy" 64-bit blocks,
"modern" 128-bit blocks, "independent" 64-byte (512-bit)
blocks,
*and*everything in between. - Next, we can even scale down the size of the tables and the mixing elements. This means that the same design can deliver either a full-scale real cipher, or a tiny model which can be investigated experimentally for weakness.

This ability to scale a single design between large real ciphers
and small testable models almost cannot be overemphasized.
Cryptography
**does** have better-known structures and designs, but
cryptography simply **does not** have a proven methodology
which -- if only followed -- will guarantee a strong design. This
means that testing is exceedingly important, and real ciphers are
far too large for many types of test.

A Balanced Block Mixer can be considered an orthogonal pair of Latin squares. The two inputs select "row" and "column" and return the value from the selected element of each square. This "mixes" or combines the two input values into the two output values with some useful properties for this design:

- A change to either input will change both outputs.
- No input change can keep both outputs unchanged.
- Any possible value (value balance) from either output can be achieved by changing either input (structural balance), regardless of the value on the other input (independence).

Even a single bit change in one mixing input will produce some
change in both mixing outputs.
And if each output is
substituted through a keyed table, each table will produce a random
result value. So even a single bit change on one input will produce
a new random result on both outputs.

To have a
block cipher
which can be expanded arbitrarily, to the byte,
at ciphering time, we are necessarily limited to operations which
can be applied byte-by-byte. But we are *not* limited to
performing the whole transformation on each byte *separately*
as we would in a
stream cipher.
Instead, we can apply operations
which, though byte-size, produce "carry" information as an input to
the *next* byte operation. When we do this multiple times in
both directions we can approach the desired block cipher goal of
apparent
overall diffusion.
`
`

`In the figure, each plaintext byte enters the top of the
structure and is immediately confused through an invertible
substitution table.
The substituted value then mixes
into a
one way diffusion
path running across the unknown width of the
block. Each of the funny-looking hourglass shapes represents a separate
Balanced Block Mixing
(BBM), a two-input two-output mixing operation which proceeds in the
direction of the arrow.
`

While each substitution in the figures has a particular number
(e.g., S00 for the leftmost top substitution), these are just
*positions* for tables and not particular *tables*
themselves. Considerable strength is added by selecting the
table for each next position based on an exclusive-OR of the data
and substituted data values in the preceding position. This
"dynamic table selection" virtually eliminates the possibility of
having even two blocks ciphered under the same table arrangement.

Dynamic table selection also provides a zero-latency form of
"chaining" which can be used for authentication. (The initial
table values can be explicitly reset before each block if blocks
are to be ciphered independently.)

The intent of the design is to mix every input byte into every output byte in a way which appears to be a huge overall random substitution. Most of this mixing occurs in the four BBM one-way diffusion layers, and some occurs in the dynamic table selection of the confusion layers.

While one might think that two one-way diffusion channels would be sufficient (one each way, or both the same way with an end-around-carry), in practice, random inputs occasionally "cancel" earlier changes, so that -- occasionally -- no propagation occurs. This can be made rare by having a wide diffusion channel. And here we have not only two layers of Balanced Block Mixing in each direction, but also the dynamic table selection to carry diffusion across the block. In this particular design, there are 4 specific 8-bit one-way diffusion layers, plus 5 layers of dynamic table selection. With 64 substitution boxes, we thus have a 62-bit diffusion path between adjacent columns.

The first two right-going BBM layers assure that almost any
left-side data change will be conducted across the block, and so
complicate attempts to isolate the leftmost column. After the first
left-going diffusion layer, we should have a complex function of
*every* input byte across the entire block. The final
left-going BBM layer is used to protect against random cancellation
effects which might otherwise affect the left-going diffusion.

By conducting a
defined plaintext attack,
and running through all
values for the first few columns, it should be possible to detect
cancellations in both carry paths as a lack of ciphertext changes
to the right. These are all evenly distributed, however, and seem
to provide no information about particular values which could be
used in reconstructing the table contents. This issue is discussed in
Defined Plaintext Attack on a Simplified BBM VSBC
on these pages.

Since we use invertible substitution tables, we can "undo" any table translation by sending the resulting value through the corresponding inverse table. The form of Dynamic Table Selection used here takes both the input and output table values and exclusive-OR's them, which selects the same next table whether we have forward or inverse tables. So a right-going Dynamic Table Selection layer is reversed by a right-going Dynamic Table Selection layer using inverse tables.

The inverse of the simple linear BBM component used here is just
another occurrence of that same BBM component. In the one-way
diffusion layers used here, a left-going diffusion (L) is the
inverse of a right-going diffusion (R), and vise versa. In the
current design we have four one-way diffusion layers for
enciphering, in the sequence <R R L L>. When deciphering, to
reverse the bottom "L" layer, we need an "R", and so on. So the
deciphering diffusion layer sequence is *also* <R R L L>.

This means that *exactly the same ciphering routine* can be
used for both enciphering and deciphering. For deciphering we use
inverse tables and take the initial values (IV's) in reverse layer
order. Both of these conditions are easily handled during keying.

DES has a fixed block size and we have somehow managed thus far, so it may seem like overkill for a cipher to have multiple block sizes. But there is almost no cost for this, and it must be admitted that having blocks of various size -- or even dynamically variable size -- sometimes can provide a better fit to the overall system than any single fixed block size. But perhaps the biggest benefit comes from the ability to cipher in very large blocks.

If plaintext really does contain uniqueness at a rate of only
about one bit per character, a legacy 64-bit block covers only
about eight bits of uniqueness. This is the situation encountered
in the classic
codebook attack.
This sort of attack is *not* avoided by having a larger
keyspace, but *can*
be avoided by using a wide, unbiased selection of plaintext blocks.
Normally this is done by using a chained
operating mode
to randomize the plaintext. But increasing the block size to
64 bytes or more can collect enough uniqueness in the plaintext
block so that randomization can be avoided.

By increasing the block size to 64 bytes or more we may be able to operate in "electronic code book" (ECB) mode instead of "cipher block chain" (CBC) mode. This means that we may not need to develop, send or store an initial value (IV), which would otherwise expand the ciphertext. And it also means that blocks can be both enciphered and deciphered independently, even if they are received out-of-sequence, as may happen in packet-switching transmission.

In conventional block cipher designs, the block size is so
small that we can scarcely consider displacing some data with
other information. But when we have a large block, there is
room for other information, at a relatively small overhead.
Typical applications include Dynamic Keying and Authentication.

Primary keying generally consists of shuffling each substitution table with a keyed cryptographic random number generator (RNG), twice. Primary keying can use fairly conventional technology, and is largely independent of the ciphering core itself. One example of a keying system is described in A Keyed Shuffling System on these pages.

Primary keying takes about 1 msec per table on a 100 MHz processor,
which is fast enough on a human scale. Primary keying does take time,
because it is specifically intended to perform as much computation
as possible -- once -- instead of having computation repeated with
every block at ciphering-time.

We assign an 8 bit strength to each table. Although an arbitrary table permutation contains 1684 bits of independence, we reason that if The Opponents can find (that is, absolutely identify and confirm) one value, they can probably find another. Since each table value is 8 bits, we assume a table strength of just 8 bits.

With this sort of five
confusion
layer
and four
one-way diffusion
layer structure, we believe that only three of the layers contribute
independent
strength.
Therefore, for a small 8-byte block, we expect to see

True zero-latency dynamic keying is available by placing keying values in each data block along with data. This will of course expand the ciphertext by the size of the keying field, but even a 64-bit dynamic keying field is only about 12.5 percent of a 64-byte block. This sort of keying can be used in any true (that is, avalanching or data diffusing) block cipher with room for extra data.

Strong block-by-block
authentication
is available similar to dynamic keying. Authentication values are
placed into each data block along with data. Potentially, this can
avoid a higher-level scan across the data with a cryptographic
hash function.
The exact same field can provide both authentication *and*
dynamic keying.

Here we present various
attacks
and comment on their likelihood
of success on this particular cipher. Recall that attacks are not
*algorithms,* but instead just general approaches which must
be reinvented for every new type of cipher.

Try each possible key until the message deciphers properly. Try most-likely keys first.

A keyspace of at least 120 bits should be sufficient to prevent exhaustive search in the foreseeable future. The keying system for the VSBC core has a keyspace substantially beyond this value, mainly because this produces a convenient design.

No cipher can do very much about key search attacks if there are only a relatively small number of possible keys, and if some keys are vastly more probable than others. It is the responsibility of the larger system to prevent this.

Try various keys on known plaintext and compare the resulting ciphertext to the actual ciphertext, to try and build the correct key value.

If a user has the ability to generate specific keys which are
used by the VSBC core on data, it is quite likely that the
external cipher system has already failed. However, even in this
situation, key selection seems unlikely to help The Opponent. Sure,
they can force particular table values by manipulating the key, but
they can do that *without* going through the keying process.
The Opponent's main problem in attacking the cipher is that
the one-way diffusion layers appear to couple the various tables
together so that a single table cannot be isolated and worked on
separately.

The Opponent accumulates a mass of ciphertext material and tries to find relationships within the data.

This is a general class of various specialized attacks which all use only the exposed ciphertext as opposed to particular knowledge of the plaintext or access to the ciphering system itself.

Collect as many ciphertexts as possible and try to understand their contents through usage and relationships; then, when a ciphertext occurs, look it up. This treats the block cipher like acode, and is the classic approach to code-breaking.

Just as some letters are more frequently used than others, words and phrases also have usage frequencies, as do blocks which contain plaintext. If the cipher block size is small (under 64 bytes), and if the plaintext is not randomized, and if dynamic keying is not used, and if the ciphering key is not changed frequently, it may be possible to build a codebook of block values with their intended meanings.

Codebook attacks of any sort are ideally prevented by having a large number of block values, which implies a large block size. Once the block size is at least, say, 64 bytes, we expect the amount of uniqueness in each block to exceed anyone's ability to collect and form a codebook.

Since the complexity of any sort of a codebook attack is related to block size only, doing "triple" anything will not affect increase this complexity. In particular, this means that Triple DES is no stronger that DES itself under this sort of attack, which is based on block size and not transformation complexity.

Somehow "obtain" both the plaintext and the corresponding ciphertext for some large number of encipherings under one key.

First, since the VSBC core described here has an internal
state typically 512 times as large as a 64-byte data block, we
know that a single plaintext and ciphertext pair simply do not
contain sufficient information to reveal the full internal state.
Note that a *single* known plaintext and ciphertext pair
probably *would* identify a DES key.

Larger amounts of known plaintext and ciphertext will of course surpass the required information, but the question is how The Opponent might use it. The problem is a supposed inability to distinguish one table from another and so work on one table at at time.

Collect as many ciphertexts and associated plaintext blocks as possible; then, when a ciphertext occurs, look it up.

Small block ciphers prevent codebook attacks by randomizing the plaintext (often with Cipher Block Chaining) so that the plaintext block values are distributed evenly across all possible block values. But not all block ciphers are always applied properly.

Codebook attacks are ideally prevented by having a large number
of block values, which implies a block size. To prevent this
attack for the future, we need a block size of at least 128 bits,
and even then *still* require the plaintext to be randomized.
If we wish to avoid randomizing with CBC, we need a block which is
large enough so the uniqueness it does contain assures that there
will be too many different blocks to catalog. A reasonable
power-of-2 minimum size to avoid randomization would be at least
64 bytes.

Without knowing the key, arrange to cipher data at will and capture the associated ciphertext. Dynamically modify the data to reveal the key, or keyed values in the cipher.

The point here is not to decipher the associated ciphertext
because The Opponent is *producing* the original plaintext.
If The Opponents have chosen plaintext capabilities, they can
probably also submit arbitrary ciphertext blocks for deciphering.

The weakness to be exploited here depends
upon the ciphering system beyond the core cipher *per se.*
If the primary keying values change with each message, and the
ciphering keys are not under the control of the user (if the system
uses message keys), there simply *is* no fixed internal state
to be exposed.

If the primary key remains the same for all messages, then there will be some keyed state to try and ferret out. But if the ciphering system uses dynamic keying fields (with values again not under the control of the user), there can be no completely-known Chosen Plaintext blocks for use in analysis.

If the ciphering core is used raw, without primary re-keying and also without dynamic keying, the Dynamic Table Selection still uses whatever "uniqueness" exists in the data to change the tables used in the block transformation.

It is not clear that there exist any statistical relationships in the VSBC core which can be exploited better by Chosen Plaintext than by Known Plaintext.

Create as many ciphertexts and associated plaintext blocks as possible; then, when a ciphertext occurs, look it up.

This is much like the previous codebook attacks, now with the
ability to fill the codebook at will and at electronic speeds.
Again, the ability to do this depends upon the cipher having a
relatively small block size and not having a dynamic keying field.
How difficult such an attack would be depends upon the size of the
block, but a VSBC may *have* no particular block size.

With a multi-layered structure, given known-or defined-plaintext, search the top keyspace to find every possible result, and search the bottom keyspace to find every possible value.

With a two-level construct and a small block size, matches can be verified with a few subsequent known-plaintext/ciphertext pairs. Of course, three and more-level constructs can always be partitioned into two sections so a meet-in-the-middle attack can always be applied; this just may be pretty complex.

The Mixing core avoids meet-in-the-middle attacks by using a three-level construction, in which each layer has a huge amount of keyed state or "keyspace."

Through extensive ciphering of fixed plaintext data under a variety of different keys, it may sometimes be possible to associate key bits with the statistical value of some ciphertext bits. This knowledge will break the cipher quickly.

This is a rather unlikely circumstance, albeit one with absolutely deadly results.

Exploit known properties of particular known substitution tables to effectively reduce the number of "rounds" in an iterated block cipher.

The original form of Differential Cryptanalysis mainly applies to iterated block ciphers with known tables, neither of which are present here. However, the general concept is like the expected VSBC attack.

The general idea of trying to relate byte values in adjacent
columns is one of the major possible attacks on VSBC's. This is
made difficult by using Balanced Block Mixing to conduct diffusion,
and by having multiple diffusion layers. Each BBM guarantees that
a change in a data value can "cancel" at most *one* of the
mixed outputs, which leaves the other mixed output to carry the
change across the block.

Another difficulty in applying Differential Cryptanalysis to a VSBC would be in handling the Dynamic Table Selection feature. Each different input value will actually select a different set of tables, and, thus, a completely different transformation. It is hard to attack a transformation which changes its structure whenever it is probed.

- The strength advantage of large blocks, which can hold huge amounts of plaintext uncertainty.
- Large blocks have room for dynamic keying information, which supports zero-latency block-by-block keying.
- Large blocks have room for authentication information, which can avoid the need for a slow higher-level authentication pass over the data
- The strength advantage of massive, keyed, nonlinear, hidden
internal state, which generally means that an attacker must
somehow
*expose*that state. - The strength advantage of dynamic table selection, since there exists no fixed cipher to be attacked, even for an unchanging key.
- The strength advantage of dynamically selectable block size to the byte, which supports the random block-partitioning of data (as opposed to the fixed-size blocks in a standard block cipher).
- The strength advantage of a fundamentally
*scalable*design which supports tiny true models that can be exhaustively tested.

- The flexibility advantage of dynamically selectable block size.
This directly supports "legacy" 64-bit blocks, "modern" 128-bit
blocks, "independent" 64-byte blocks, and 512-byte disk sectors
in
*the exact same unchanged program*. - Large blocks can eliminate the need for plaintext randomization, chaining, and the use of ciphertext-expanding IV's.
- Large blocks support the independent ciphering of blocks, and random-access ciphering.
- The dynamically selectable block size can cipher
*existing*data structures in*existing*systems*without*needing extra data storage and resulting modification of the system. - The dynamically selectable block size to the byte need not
expand data
*at all.* - The flexibility advantage of key processing as a part of the
cipher. This directly supports
*both*textual*and*random binary keys of arbitrary length. - The flexibility advantage of
*the ideal single cipher,*since it efficiently covers ciphering jobs of all block sizes.

*Also see:*

- The Large Block DES Open Development: our search for a new "DES" architecture started over four years ago.
- The original BBM article
- The start of a theoretical basis
- Realized VSBC prototypes
- The current BBM article
- The keying system
- The one-way diffusion layers
- VSBC's on the top page

*Last updated:* 1998-03-21