sci.crypt #47999
Path: news.io.com!io.com!not-for-mail
From: ritter@io.com (ritter)
Newsgroups: sci.crypt
Subject: Variable Size Block Cipher Designs
Date: 11 Feb 1996 16:23:09 -0600
Organization: Illuminati Online
Lines: 294
Message-ID: <4flq8d$gf4@pentagon.io.com>
NNTP-Posting-Host: pentagon.io.com
From my previous work on Variable Size Block Ciphers (VSBC) I have
realized a family of five very interesting cipher architectures.
This is another set of ciphers you won't find in the crypto books.
These working prototypes are intended to explore a range of
"Variable Size Block Cipher" designs, and provide some crude
performance comparisons. This is patent-pending work.
VARIABLE SIZE BLOCK CIPHERS
The usual block cipher has a small fixed width (often 64 bits).
But if plaintext really does contain uniqueness at a rate of
about one bit per character, the usual block cipher covers only
about eight bits of uniqueness, a searchable quantity. (This
sort of attack, of course, would require a deep knowledge of
language structure, but doing "Triple" anything would not affect
it.) By increasing block size dramatically, we can have a cipher
which is not vulnerable to this sort of attack.
The usual stream cipher can cipher sections of arbitrary size,
but can only propagate uniqueness to *later* ciphertext.
In contrast, a block cipher -- including all of these VSBC
designs -- will propagate plaintext uniqueness to *all* bits of
ciphertext in the same block.
The VSBC concept is a new paradigm, and can be used in ways far
different than fixed size block ciphers. For example, in a VSBC
there is no need to use fixed-size blocks: A message can be
ciphered in blocks of *pseudo-random* size. This means that an
Opponent cannot even know what data belongs to a single block.
THE PROTOTYPE PROGRAM
The VSBC prototype program uses any of these VSBC designs and
ciphers data in random-size blocks of from 10 to 4105 bytes (the
average data block is about 2 KB). Random length "pre" and "post"
blocks (an average of 1/2 K each) which do not contain message data
are used to hide the first and last data block boundaries.
A VSBC CIPHERTEXT FILE
+-----+----------------------+----/ /----+-----+
| Pre | Data Block | | Post|
+-----+----------------------+----/ /----+-----+
The size of each block is generated by the crypto RNG operating
under some key. (In an actual cipher product, the User Key would
decipher an Alias file, in which a public alias would be matched
to recover a corresponding Alias Key. That Alias Key would be used
to decipher only the Message Key from a particular message from a
particular correspondent. The Message Key -- which might be very
long -- would only then initialize the RNG for deciphering data.
This same process is actually implemented in my Penknife and
Cloak2 commercial ciphers.)
A typical VSBC file may not even *have* two blocks of the same
size, and there would seem to be no way to determine the start or
end of any block. This would seem to be a significant strength
advantage, *beyond* the strength of the cipher design, flowing
directly from the new concept of a dynamically-variable block size.
A VSBC CIPHERTEXT DATA BLOCK
+---------------+-------+----------/ /---------+
| VCF | Len | |
+---------------+-------+----------/ /---------+
|<--- 4 By ---->| 2 By |<--- 10..4105 By ---->|
Four pseudo-random validation / error-check bytes are added to each
block when enciphering. When deciphering, the recovered Validation
Check Field (VCF) is compared to the pseudo-random value from the
crypto RNG, and any error indicated. This avoids an additional pass
over the data to compute a CRC for error-detection, creates a
validation field which is not easily spoofed, and provides a form
of dynamic block-by-block keying. Clearly, the VCF could be of any
desired size.
Two bytes are used to specify the amount of data in the *next*
block. This value is needed to specify the length of the last
data block, which is usually short by some unknown amount.
Typically six "iv" or Initialization Value bytes (again developed
from the crypto RNG) are used by some of these VSBC designs, and
the resulting carry values are used as iv's for the next block.
This provides an automatic form of block chaining and randomization
for the leftmost and rightmost column inputs. Those designs which
use substitution tables step through an array of 64 such tables.
The starting table value is also initialized from the crypto RNG
and the "next up" table is also chained from block to block.
THE DESIGNS
Here I show the structure for typically three adjacent bytes, but
each of these designs is used in a file cipher which dynamically
selects block size to the byte with an average size of about 2 KB.
These VSBC designs have a very similar structure for both
enciphering and deciphering. Data flows down for enciphering,
and up for deciphering. The tables (or Latin square rows) used
for deciphering are the inverse of those used for enciphering.
In the SBBM and OLs designs, the diffusion direction also changes.
In the two designs which use substitution tables, the tables are
numbered to remind us that each is generally different. Nor is
the table for any particular position fixed: Tables are used as
needed from an array of 64 such tables. Each table is separately
shuffled by the cryptographic RNG and each table represents a
potential 1648-bit key. Normally, the keyspace of this sort of
cipher is limited by the size of the RNG used to key the tables
or squares, and it is easy to have an efficient true keyspace of
many thousands of bits.
In marked contrast to other cipher designs, additional confusion
and diffusion layers are easily and modularly added to produce a
cipher of any desired working strength.
Performance measurements occurred for RAM-drive ciphering of a
750K file on a P90 under DOS 6.22, with single-pass shuffles.
SubX (init = 15 ms, ciphering = 461 KB/sec)
INPUT or OUTPUT
d[0] d[1] d[2] . . .
| | |
iv0 -> XOR +----> XOR +----> XOR
| | | | |
S00 | S10 | S20
*-- | -+ *-- | -+ *--> c1
iv1 -> XOR | +-> XOR | +-> XOR
*---* *---* *--> c0
iv2 -> XOR | +-> XOR | +-> XOR
*-- | -+ *-- | -+ *--> c2
S01 | S11 | S21
| | | | |
iv0 -> XOR +----> XOR +----> XOR
| | |
XOR <----+ XOR <----+ XOR <- iv4
| | | | |
S03 | S13 | S13
c5 <--* +- | --* +- | --*
XOR <-+ | XOR <-+ | XOR <- iv5
c4 <--* *---* *---*
XOR <-+ | XOR <-+ | XOR <- iv6
c6 <--* +- | --* +- | --*
S04 | S14 | S14
| | | | |
XOR <----+ XOR <----+ XOR <- iv4
| | |
d[0] d[1] d[2] . . .
OUTPUT or INPUT
The SubX VSBC design uses exclusive-OR combining in diffusion
layers, and byte-wide 256-entry substitution tables in confusion
layers. The particular table used in each position is the "next"
table in sequence from an array of keyed tables. (Even if two
blocks do end up having the same size, they probably will not have
the same tables in the same positions.)
The SubX design uses the most primitive components, and so is
graphically more complex than the other designs.
Ls4 (init = 55 ms, ciphering = 236 KB/sec)
d[0] d[1] d[2] . . .
| | |
iv0 -> Lsc +----> Lsc +----> Lsc
*-- | -+ *-- | -+ *--> c1
iv1 -> Lsc | +-> Lsc | +-> Lsc
*---* *---* *--> c0
iv2 -> Lsc | +-> Lsc | +-> Lsc
*-- | -+ *-- | -+ *--> c2
iv0 -> Lsc +----> Lsc +----> Lsc
| | |
Lsc <----+ Lsc <----+ Lsc <- iv4
c5 <--* +- | --* +- | --*
Lsc <-+ | Lsc <-+ | Lsc <- iv5
c4 <--* *---* *---*
Lsc <-+ | Lsc <-+ | Lsc <- iv6
c6 <--* +- | --* +- | --*
Lsc <----+ Lsc <----+ Lsc <- iv4
| | |
d[0] d[1] d[2] . . .
The Ls4 (four Ls's per data element per diffusion direction) VSBC
design uses Latin square combining, which simultaneously provides
both diffusion and confusion in the same layer. A single Latin
square of order 256 is used, requiring 64K of store and
representing a 3296-bit key. (The prototype RNG is a jitterized
Additive RNG with 496 bits of initial state.)
The overall structure is quite like the SubX design, but differs
in that the "table" (actually, the Ls row) used at each node is
here selected by diffusion *data*, instead of some value related
to node position. Since The Opponent does not see the diffusion
data, it is going to be tough to isolate a particular "table" to
be attacked separately.
VSBC LsX (init = 55 ms, ciphering = 372 KB/sec)
d[0] d[1] d[2] . . .
| | |
iv0 -> XOR +-------> XOR +-------> XOR
*-- | ----+ *-- | ----+ *--> c2
iv1 -> Lsc | +----> Lsc | +----> Lsc
*---* | | *---* | | *--> c0
iv2 -> Lsc | | +-> Lsc | | +-> Lsc
*-- | -+ *--- | -+ *--> c1
iv0 -> XOR +-------> XOR +-------> XOR
| | |
XOR <-------+ XOR <-------+ XOR <- iv4
c6 <--* +---- | --* +---- | --*
Lsc <----+ | Lsc <----+ | Lsc <- iv5
c4 <--* | | *---* | | *---*
Lsc <-+ | | Lsc <-+ | | Lsc <- iv6
c5 <--* +- | --* +- | --*
XOR <-------+ XOR <-------+ XOR <- iv4
| | |
d[0] d[1] d[2] . . .
The LsX design uses Latin square layers for both diffusion and
confusion, and exclusive-OR combining for other diffusion layers.
This design also demonstrates a somewhat different feedback
architecture.
SBBM (init = 15 ms, ciphering = 439 KB/sec)
d[0] d[1] d[2] d[3] . . .
| | | |
S00 S10 S20 S30
| | | |
+----> BBM --> BBM --> BBM --> -----+
| | | |
S01 S11 S21 Sy1
| | | |
+----> BBM --> BBM --> --> BBM -----+
| | | |
S02 S12 Sx2 Sy2
| | | |
+----- BBM <-- BBM <-- <-- BBM <----+
| | | |
S03 S13 S23 Sy3
| | | |
+----- BBM <-- BBM <-- BBM <-- <----+
| | | |
S04 S14 S24 S34
| | | |
d[0] d[1] d[2] d[3] . . .
The SBBM VSBC design uses the fast and simple Balanced Block Mixing
component in the diffusion layers, and byte-wide substitution
tables in the diffusion layers. Again, these tables are used in
cyclic sequence from an array of keyed tables, so the same tables
may or may not occur in the same positions in some other block.
OLs (init = 76 ms, ciphering = 369 KB/sec)
d[0] d[1] d[2] d[3] . . .
| | | |
+----> OLs --> OLs --> OLs --> -----+
| | | |
+----> OLs --> OLs --> --> OLs -----+
| | | |
+----- OLs <-- OLs <-- <-- OLs <----+
| | | |
+----- OLs <-- OLs <-- OLs <-- <----+
| | | |
d[0] d[1] d[2] d[3] . . .
This OLs VSBC design uses a keyed orthogonal pair of Latin squares
which realize a keyed Balanced Block Mixer at each node. The OLs
structure fills 128K and also represents 3296 bits of key.
Your Comments Wanted
All comments on these designs, positive or negative, will be
appreciated. Serious financial support is needed, but no personal
donations, please. Companies interested in these or other future
ciphering technologies could do worse than to establish a
continuing relationship through contractual development.
---
Terry Ritter Ciphers By Ritter http://www.io.com/~ritter/