From: ritter@cactus.org (Terry Ritter)
Date: Tue, 1 Feb 94 23:25:29 PST
To: cypherpunks@toad.com
Subject: NxM DES
Message-ID: <9402020724.AA29200@cactus.org>
MIME-Version: 1.0
Content-Type: text





                   Ritter Software Engineering
                       2609 Choctaw Trail
                       Austin, Texas 78745
                (512) 892-0494, ritter@cactus.org



          Strong Block Ciphers from Weak Ones: NxM DES
               A New Class of DES Operating Modes

                          Terry Ritter
                        January 31, 1994


Introduction

Many security vendors are now preparing a new generation of software
and hardware products.  Given the well-known criticism of DES, and the
government's unwillingness to publish their new Skipjack algorithm,
much attention has been focused on triple-DES as a replacement for DES.
But triple-DES requires three times the processing of normal DES, and
retains the same small block size which must be increasingly vulnerable
to improved dictionary attacks.  Thus it is reasonable to seek
alternatives to triple-DES, and compare them with respect to keyspace,
processing requirements, and block size.  Vendors should be cautioned
that triple-DES is not the only, nor necessarily the best, alternative
to DES.  They should consider delaying implementation of alternatives
until a consensus develops on exactly what the replacement should be.

New ciphering algorithms are often challenged to "prove" they are
stronger than DES.  Since it is impossible to measure the "strength"
of a cipher (and there has been no absolute proof of strength for any
practical cipher), new cipher algorithms are often considered
curiosities.  On the other hand, DES itself is well-known and accepted
(despite having no proof of strength), so there seems to be great
interest in the possibility of forming from DES a stronger cipher. 
Triple-DES is one approach at forming that stronger cipher, and is what
we could call a 1x3 DES structure: one DES block wide by three DES
cipherings deep.  Naturally, we expect software for any three-level
ciphering to operate at about one-third the speed of normal DES. 

There is an alternative approach which offers a larger keyspace,
reduced processing, and larger block sizes (which, nevertheless, can
often be used without data-expansion beyond that of normal DES).  I
call that approach "NxM DES," of which 2x2 DES is perhaps the easiest
nontrivial example:


2x2 DES

Instead of repeatedly enciphering a single 8-byte block, consider using
multiple DES cipherings to form a 16-byte block operation and thereby
improve plaintext block statistics.  2x2 DES will be two DES blocks
wide by two DES cipherings deep.  

First, encipher two data blocks with DES, each under a different key. 
Exchange half the data in the first and second blocks.  Then encipher
the resulting blocks again, using two more keys:

Let us denote a DES enciphering by:  

     ciphertext := DESe( plaintext, key ) .  

We want to encipher two DES-size blocks, call them A and B, and end up
with ciphertext blocks G and H:

     C := DESe( A, k1 );          D := DESe( B, k2 );
     E := C[0..3],D[4..7];        F := D[0..3],C[4..7];
     G := DESe( E, k3 );          H := DESe( F, k4 );

The byte-index notation on the second line is intended to convey the
exchange of the rightmost four bytes of the first two DES ciphertexts. 
The exchange is a permutation, costless in hardware, and simple and
cheap in software.  This particular permutation is also a self-inverse,
so that the same permutation can be used for both enciphering and
deciphering.  If we give each two-bytes of data a symbol and denote the
original data as:

     0123  4567

then after the permutation we have:

     0167  4523 .

For example,

     A:    01A1D6D039776742       B:   5CD54CA83DEF57DA
     k1:   7CA110454A1A6E57       k2:  0131D9619DC1376E
     C:    690F5B0D9A26939B       D:   7A389D10354BD271
     E:    690f5b0d354bd271       F:   7a389d109a26939b
     k3:   07A1133E4A0B2686       k4:  3849674C2602319E
     G:    b4de11d10c55c267       H:   64f1a0b723d360a7 .

Deciphering is similar to enciphering, except that the last-stage keys
are used first, and we use DES deciphering instead of enciphering:

     E := DESd( G, k3 );          F := DESd( H, k4 );
     C := E[0..3],F[4..7];        D := E[0..3],F[4..7];
     A := DESd( C, k1 );          B := DESd( D, k2 );

Thus, 2x2 DES enciphers DES blocks A and B to DES blocks G and H in
four DES cipherings.  This is faster than triple DES, because twice as
much data are enciphered in each block:  2x2 DES has a cost similar to
double-DES.  But 2x2 DES is potentially stronger than triple-DES,
because each of the resulting ciphertext bits is a function of 128
plaintext bits (instead of 64), as well as three DES keys.  (Although
four keys are used in 2x2 DES, only three keys affect each output
block, a 168-bit keyspace.) 

2x2 DES does have a larger block size, so, when used alone, last-block
padding overhead increases from four bytes (on average) to eight; a
four-byte data expansion.  Naturally, when used alone in CBC mode, the
initialization vector (IV) will also be larger, 16 bytes instead of 8. 
This 12-byte overall increase in overhead should be weighed against the
stronger 16-byte block size, since strength is the reason for moving
away from normal DES in the first place.  


4x2 DES

In a manner similar to 2x2 DES, we can consider enciphering four DES
blocks of plaintext, sharing data between them, and then enciphering
the resulting four blocks again.  4x2 DES has a larger keyspace than
2x2 DES, yet retains the same ciphering cost.  4x2 DES does have some
additional last-block and IV overhead, in return for a greater keyspace
and larger block-size strength.  Each 4x2 ciphering requires eight DES
keys:  

     E[0..7] := DESe( A, k1 );
     F[0..7] := DESe( B, k2 );
     G[0..7] := DESe( C, k3 );
     H[0..7] := DESe( D, k4 );

     (swap right-hand half of the data in {E,F} and {G,H})
     I := E[0..3],F[4..7]
     J := F[0..3],E[4..7]
     K := G[0..3],H[4..7]
     L := H[0..3],G[4..7]

     (swap the middle half of the data in {I,L} and {J,K})
     M := I[0..1],L[2..5],I[6..7]
     N := J[0..1],K[2..5],J[6..7]
     O := K[0..1],J[2..5],K[6..7]
     P := L[0..1],I[2..5],L[6..7]

     Q := DESe( M, k5 );
     R := DESe( N, k6 );
     S := DESe( O, k7 );
     T := DESe( P, k8 );

The intermediate permutation involves four 32-bit exchange operations,
an expense still trivial compared to the DES ciphering operations.  (In
a hardware implementation, the byte-swaps are the connections always
needed between stages, just connected differently, with no added
expense at all.)  This permutation is also a self-inverse.  If we
denote each two-bytes of the data symbolically:

     0123  4567  89ab cdef

then after the permutation, we have:

     0da7  49e3  852f c16b .


Alternately, if we denote the data prior to permutation as:

     0000  1111  2222 3333

then after the permutation we have:

     0321  1230  2103 3012 ,

showing that each permuted block contains exactly two bytes from each
of the four original DES blocks.  Each 8-byte output block in 4x2 DES
is a function of 32 bytes of input plaintext, as well as five DES keys,
a 280-bit keyspace.

For example,

     A:    01A1D6D039776742       B:   5CD54CA83DEF57DA 
     C:    0248D43806F67172       D:   51454B582DDF440A

     k1:   7CA110454A1A6E57       k2:  0131D9619DC1376E
     k3:   07A1133E4A0B2686       k4:  3849674C2602319E

     E:    690F5B0D9A26939B       F:   7A389D10354BD271
     G:    868EBB51CAB4599A       H:   7178876E01F19B2A

     M:    690f876ecab4d271       N:   7a38bb5101f1939b 
     O:    868e9d109a269b2a       P:   71785b0d354b599a

     k5:   04B915BA43FEB5B6       k6:  0113B970FD34F2CE
     k7:   0170F175468FB5E6       k8:  43297FAD38E373FE

     Q:    89af722f592664c4       R:   012d483a04db300f
     S:    dd60060ad098e3e0       T:   a3832dc4ff5c99ad .


Again, 4x2 DES deciphering is similar, except that we use the last-
stage keys first, and DES deciphering instead of enciphering.  


NxM DES

8x2 DES would have a 64-byte block and 16 DES keys, yet should still
be considerably faster than triple-DES.  Even larger blocks are
possible, but would seem to require exchange operations on non-byte
boundaries (to assure that each permuted block contains bits from each
stage-one ciphertext block), so 16x2 DES and larger structures may have
a larger software permutation cost.  Nevertheless, the Nx2 approach
gives us a way to increase the keyspace while generally retaining
processing costs similar to double-DES.

DES structures with additional ciphering levels, such as 2x3 DES or
4x3 DES, are also available, at a processing cost similar to triple-
DES, but with the increased strength of a larger block size.  A 2x3 DES
structure would have a 280-bit keyspace similar to 4x2 DES, but with
50 percent higher processing costs.  A 4x3 DES structure could be
appropriate for some applications, but would have a huge 504-bit
keyspace which would require us to create, transport and store the
associated 84-byte key set.  


Large Blocks in Existing Systems

It should be possible to adapt many existing systems to use larger
blocks without further data expansion.  Consider an 82-byte message,
which would normally be structured as eleven 8-byte DES blocks, for a
total of 88 bytes:  An NxM DES alternative might use two 4x2 DES
blocks, one 2x2 DES block, and one 1x3 DES block, for 32+32+16+8 or 88
bytes, exactly the same as normal DES.  A 63-byte message (normally 8
DES blocks) would use just two 4x2 DES blocks for a total of 64 bytes,
also the same as normal DES.  If larger blocks are always used until
smaller blocks would be more efficient, there is exactly one way to
structure any given amount of data, and the resulting length is
sufficient to reproduce the multiple-size blocking structure.  The
overhead of these blocking manipulations remains insignificant when
compared to the DES ciphering operations.  We could call this sort of
use of multi-size blocking "NxM+ DES," and 4x2+2x2+1x3 DES (which we
could call "4x2+ DES") would seem to be a very practical system.  

Clearly, in CBC mode, 4x2 DES will require a larger IV than normal DES. 
Perhaps the IV could be transferred as part of the key-exchange; there
is obviously no way to avoid using larger keys if we want a stronger
cipher, whatever approach we use.  Smaller blocks at the end of a data
area could just take the left-most part of the preceding block as their
chain value.  Similarly, a 2x2 DES block might use the left-most two
DES keys at both levels of a 4x2 DES block (k1,k2,k5,k6), while a 1x3
DES block might just use the first three keys of the 2x2 DES block.  

Overall, 4x2+ DES might be a simple firmware upgrade for existing DES
hardware.  


Summary

Because the DES cipher is well known, there is interest in creating a
stronger cipher which builds on normal DES as a base.  By introducing
a larger block width in addition to repeated cipherings, additional
complexity can be obtained with a moderate increase in processing. 
This approach is unusual in that various levels of strength can be
obtained at virtually the same processing cost, a cost comparable to
double-DES and substantially less than triple-DES.  Furthermore, the
larger data blocks can be used even in systems which would not support
data expansion beyond that inherent in normal DES.  Consequently, the
NxM DES approach would seem to have significant practical advantages
over either double-DES or triple-DES as a replacement for DES.  

NxM DES is a product of my own research.  I am not aware that this
approach has been previously published.