Orthogonal Latin Squares
Balanced Block Mixing
Questions, Comments or HTML Problems? Contact
Terry Ritter (About the Author), at
ritter@ciphersbyritter.com.
Last Update:
Search engines often find older articles and miss the newer
summaries in the
Glossary.
For the latest information,
We own and control novel cryptographic technologies:
Our novel ciphering technologies provide unique system-level advantages, including:
Also see our patent policy document.
- massive bandwidth (in BBM Mixing Cipher hardware with huge blocks),
- reduced strength requirements from other parts of the system (e.g., the RNG in Dynamic Substitution type stream ciphers),
- reduced system requirements in general (e.g., avoiding operating modes in Mixing Ciphers and Variable Size Block Ciphers with huge blocks),
- unusual features supporting system operations (e.g., independent ciphering of blocks, per-block authentication, and other advantages based on huge blocks).
Available for license within The United States.
The figure shows at the top a left data input and a right
confusion or "running key" input. A plaintext data byte is
transformed through the invertible substitution table into
ciphertext and output to the right. Then the changes controller
re-arranges the table.
Dynamic Substitution can replace the exclusive-OR (XOR) combiner in stream ciphers. Under known-plaintext conditions, XOR combining has absolutely no strength at all. Good ciphers are expected to defeat known-plaintext.
Typically, Dynamic Substitution tables are initialized by keying, and are very nonlinear. Several strength opportunities not available with XOR combiners can be exploited with DynSub:
The improved strength of multiple DynSub combiner systems acts to protect the confusion sequence generator (RNG) at the system level. Since most technical attacks on stream ciphers involve exposing the state of the RNG, complicating or eliminating such attacks is a significant strength advantage.
The figure shows at the top a left input block with a value of 1 selecting row 1 (of 0..3) in both squares, and a right input value of 3 selecting column 3 in both squares. Each selected element, here 2 and 0, becomes an output value at the bottom. Practical BBM components typically mix two input bytes into two output bytes. FFT-like networks of BBM's essentially become BBM's with some power-of-2 inputs and outputs.
A BBM component has strong guarantees of balance and equal distribution. It performs an arguably "perfect" mixing of n elements using log n mixing sublevels of n operations each.
There are three classes of realization:
A BBM can be seen as a way of emulating larger tables using small ones. This is interesting because a conventional block cipher merely emulates a table far too large to build. A construction based on small keyable tables makes sense. Currently, the table-only realization seems most desirable, because that avoids the linear transformations of the other models. Tables hold the maximum amount of keyed and nonlinear state, and that state is what an opponent must unravel to break the cipher. The cipher is keyed by constructing a particular orthogonal Latin square pair for each mixing element, which is fairly easy to do.
Here we have a typical hybrid realization:
The figure shows connections from a
block of 8 input
bytes at the top, which are each substituted through keyed "8-bit"
invertible tables or
Each yellow diamond represents half of a linear BBM component. Each mixing takes two bytes in, and produces a 2-byte result. The mixings are arranged in an FFT-style pattern which mixes every byte across the entire block using only byte mixings.
We have a top row of substitutions, then a complete mixing.
Then we have another row of substitutions and another complete
mixing.
Then we have a final substitution row, which produces 8 bytes of
ciphertext out the bottom.
FFT-style mixing patterns can be computed at ciphering time, so blocks of dynamically arbitrary power-of-2 size can be ciphered. Extremely large blocks can be ciphered almost as fast (per byte) as smaller blocks, thus possibly avoiding CBC chaining, and providing room for authentication and dynamic keying fields.
Here we have a typical hardware table-only realization:
This is again an 8-byte block, but the 16 input lines are
There are four sublayers, each consisting of eight BBM tables,
that mix every input bit to every output bit.
Each table holds an order-16 oLs in 256 bytes.
Thus, each sublayer needs
In hardware, mixing ciphers can be much faster than most other block cipher approaches because all mixings can operate simultaneously. Table mixings are just table look-ups with a single RAM read each. Chip layout consists almost entirely of RAM and data bus.
Hardware bandwidth typically is a full block per clock cycle, with a different block being processed in each mixing sublayer. With a 450MHz clock, 8-byte block designs do 3,600 megabytes/sec. Doubling the block size doubles the processing bandwidth, but also doubles the number of tables, plus adding another mixing sublayer.
It is possible to save RAM by using order-4
oLs
mixings, which need only 8 bytes of store (16 entries of 4 bits each).
Since they mix only
At the
The figure shows at the top connections from 5 plaintext bytes
(of a presumably larger block) which are each substituted, and
then participate in a right-going one-way diffusion. The hourglass
shapes are
BBM
components, which mix in the direction of the arrow two input values
into two output values. Subsequent substitutions and diffusions
eventually produce 5 ciphertext bytes on the bottom connections.
The use of large blocks can avoid the need for CBC chaining, and provide room for authentication and dynamic keying fields. The ability to cipher blocks of odd size supports the ciphering of existing data structures without re-design of the existing system. The use of random-size blocks in file ciphering provides an unexpected new level of strength, since the bytes composing any particular block are unknown to an attacker.
Attempts at attacking, solving and explaining some aspects of cryptographic design.
Technical articles which actually function.
Various interesting discussions from Usenet, typically from the sci.crypt newsgroup.
Most modern cryptography exists somewhere amidst thousands of published academic articles. No current texts do justice to this huge body of work, and there are too many references for an individual to know where to start. Here I select some of my favorite research stories, outline the coverage of the most important articles, and occasionally suggest directions for the future. Obviously, this will be totally non-controversial.
Send any and all suggestions by e-mail, but to contribute to the discussion, start or join a thread in the sci.crypt Newsgroup. Articles with particularly incisive comments will be archived here as alternate views of reality.
This work was privately conducted without governmental, educational or commercial support.