sci.crypt #46705 (9 more)
Path: news.io.com!io.com!not-for-mail
From: ritter@io.com (ritter)
Newsgroups: sci.crypt
Subject: Fencing and Mixing Ciphers
Date: 16 Jan 1996 19:31:11 -0600
Organization: Illuminati Online
Lines: 242
Message-ID: <4dhjgv$rn5@pentagon.io.com>
NNTP-Posting-Host: pentagon.io.com
From my previous work on fencing and mixing ciphers I have realized
a family of five interesting block cipher architectures in 64-bit,
128-bit, and 256-bit widths.
You won't find this sort of cipher in the crypto texts.
These working prototypes are intended to explore a range of
"Fencing" and "Balanced Block Mixing" designs, and provide some
crude performance comparisons. This is patent-pending technology.
My Technical Terms
* By "fencing" I mean an array of typically byte-width
substitutions. Each 256-byte table corresponds to a
keyspace of 1684 bits (provided, of course, that the rest
of the cipher will hide the arrangement of the table).
* By "balanced block mixing" I mean a structure which generally
takes two input sub-blocks to two output sub-blocks and
provably propagates a change in *either* input sub-block to
*both* output sub-blocks. (This is sufficient to provide
provable avalanche in a block cipher.)
I show the structure for the "4x" or "256-bit block" versions.
The large block is used for most ciphering; one each 2x and 1x
block may be used at the end of the file to reduce ciphertext
expansion to that of a 64-bit block.
Performance measurements occurred for RAM-drive ciphering of a
750K file on a P90 under DOS 6.22, with single-pass shuffles.
Fenced DES (init = 31ms, ciphering = 181 KB/sec)
INPUT
<------------------------- 256 bits -------------------------->
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
-------------------------------x------------------------------- mixing
---------------x--------------- ---------------x--------------- mixing
------DES------ ------DES------ ------DES------ ------DES------ DES
---------------x--------------- ---------------x--------------- mixing
-------------------------------x------------------------------- mixing
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
<------------------------- 256 bits -------------------------->
OUTPUT
Here we have 32 input and 32 output byte-substitutions (S)
across a 256-bit block. We also mix (---x---) 128-bit and 64-bit
sub-blocks using linear Balanced Block Mixing. Because all data
flows through DES, the cipher cannot be weaker than DES. Each
substitution layer is protected by DES and so apparently cannot be
exposed without breaking DES and the other substitution layer.
Each 256-byte substitution table is keyed by shuffling under a
cryptographic RNG initialized from a User Key. That RNG also
produces 4 separate random DES keys. Normally, the keyspace of
this sort of cipher is limited by the size of the RNG used to key
the substitutions, and it is easy to have a true keyspace of
thousands of bits.
The ability to attack the keying RNG depends upon developing
the state in one or more of the substitutions, then inferring
the RNG sequence. But inferring the RNG sequence can be made
difficult or impossible by double-shuffling each substitution.
It is not at all clear how an attacker could develop the correct
state of any substitution in the first place. Even a single bit
error in any input table is guaranteed to produce avalanche, so
the extent of solution of these tables cannot be distinguished.
(The Fenced DES cipher was described on sci.crypt almost two
years ago, in a post I have archived as
http://www.io.com/~ritter/NEWS/94042901.HTM
).
Fenced Tree (init = 45ms, ciphering = 113 KB/sec)
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
-------------------------------x------------------------------- mixing
---------------x--------------- ---------------x--------------- mixing
-------x------- -------x------- -------x------- -------x------- mixing
---x--- ---x--- ---x--- ---x--- ---x--- ---x--- ---x--- ---x--- mixing
-x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- mixing
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
-x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- -x- mixing
---x--- ---x--- ---x--- ---x--- ---x--- ---x--- ---x--- ---x--- mixing
-------x------- -------x------- -------x------- -------x------- mixing
---------------x--------------- ---------------x--------------- mixing
-------------------------------x------------------------------- mixing
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
This is similar to Fenced DES, but with three more Balanced Block
Mixing layers (for a total of five) and another fencing layer
instead of the DES layer.
Fenced Quad (init = 45ms, ciphering = 398 KB/sec)
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
=============================================================== lin-FFT
======= ======= ======= ======= ======= ======= ======= ======= lin-FFT
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
======= ======= ======= ======= ======= ======= ======= ======= lin-FFT
=============================================================== lin-FFT
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
Here we have two full linear "FFT" operations between three
fencing layers. Note that many different mixing arrangements
will produce equally acceptable mixing.
Each "FFT" "butterfly" operation is a Balanced Block Mixer of
appropriate width. Basically, this design assumes that mixing
with 32-bit sub-blocks is likely to be faster than mixing with
8-bit sub-blocks. Consequently, the mixing is broken down into
32-bit "FFT" layers and 8-bit "FFT" layers.
Fenced FFT (init = 45ms, ciphering = 413 KB/sec)
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
=============================================================== lin-FFT
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
=============================================================== lin-FFT
S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S fencing
Here we also have linear "FFT-like" mixing between three fencing
layers. But here, every "FFT" "butterfly" operation is a byte
width Balanced Block Mixer.
Fenced OLS (init = 76ms, ciphering = 372 KB/sec)
INPUT
<------------------------- 256 bits -------------------------->
=============================================================== nl-FFT
<------------------------- 256 bits -------------------------->
OUTPUT
Here we have non-linear FFT-style mixing, and no fencing layers
at all. Each "FFT" "butterfly" is a byte-width Balanced Block
Mixer composed of a keyed pair of orthogonal Latin squares of
order 256.
This prototype uses a single 128K randomized table, with a
keyspace of 3368 bits. But only memory space and initialization
time prevents us from using a different table at every mixing
node, thus producing an astronomical keyspace.
Avalanche
It is interesting to contrast the avalanche characteristics in
this class of mixing cipher with that of the ideal block cipher,
which is a huge keyed Simple Substitution. In the ideal case,
a one-bit change in the input block has the potential to change
just a single bit in the output block. But in these mixing ciphers,
a one-bit change in the input block will change at least one bit
*in every mixing output*.
However, this particular case is so rare that we could probably
never find such a value in the ideal cipher (even though such
values must exist!). Nor could we expect to see the difference
in practical statistical tests. So here we seem to have designs
whose known deviations from the ideal occur in areas which we
cannot measure.
Complexity
These ciphers are simultaneously more simple and also more complex
than conventional ciphers: These ciphers have far simpler
structures than, say, "round" based Feistel ciphers, and rely on
simple, *provable* mixing characteristics. (See, for example,
http://www.io.com/~ritter/FENCED.HTM (24K)
). But these ciphers have far more "state" than conventional
(mainly "algorithmic") ciphers. These ciphers also *key* the
internal state (as opposed to using the same state for all users).
I expect that the large-state approach is generally more secure
than the algorithmic approach in that a large keyed state
*demands* a large amount of investigation to define that state.
In contrast, a mainly algorithmic approach seems perhaps more
vulnerable to unknown algorithmic attack.
Having a clean, simple structure should mean that any attacks
based on that structure should also be fairly clean and apparent.
It *should* be easier to have confidence in these ciphers than
in complex architectures which have plenty of opportunity to
hide attack techniques.
There is an additional storage cost for the large-state approach,
but, for these sizes, it seems almost irrelevant. This state does
require a keyed initialization which takes longer than the usual
algorithmic cipher. Normally, keyed initialization is arranged
to occur infrequently.
Dynamic Keying
Zero-overhead block-by-block dynamic keying is available by XORing
the input block with a like-size key. I would not expect this to
increase native strength, but I would expect it to defeat attacks
which rely upon knowing the input to the cipher over many blocks.
As long as the cipher itself remains unbroken, this sort of dynamic
key would seem to be well hidden.
Some moderate-overhead dynamic keying is also available in Fenced
DES by changing one or more of the DES keys.
At this time I would resist adding internal XOR keying layers, with
the thought that such layers might expose otherwise hidden internal
operations.
Your Comments Wanted
All comments on these designs, positive or negative, will be
appreciated. Serious financial support is also needed. Companies
interested in custom ciphers based on these or other technologies
should contact me directly.
References
http://www.io.com/~ritter/NEWS/LBDNEWS.HTM#LBDBBM
http://www.io.com/~ritter/BBM.HTM (13K)
http://www.io.com/~ritter/NEWS/LBDNEWS.HTM#LBDFD
http://www.io.com/~ritter/FENCED.HTM (24K)
---
Terry Ritter Ciphers By Ritter http://www.io.com/~ritter/