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/