From: mrr@scss3.cl.msu.edu (Mark Riordan)
Newsgroups: sci.crypt

Subject: Re: Ladder DES
Date: 1 Mar 1994 02:40:12 GMT
Organization: Michigan State University
Lines: 123
Message-ID: <2ku9uc$sr8@msuinfo.cl.msu.edu>
References: <1994Feb22.083353.26012@cactus.org> <2kejt8$1384@msuinfo.cl.msu.edu>
 <1994Feb25.175256.1510@cactus.org> <2km7dv$jf2@msuinfo.cl.msu.edu>
NNTP-Posting-Host: scss3.cl.msu.edu
X-Newsreader: TIN [version 1.2 PL1]

Mark Riordan (mrr@scss3.cl.msu.edu) wrote:
: I will prepare a description of the algorithm and have
: someone who has not seen RSA DSI's code reimplement it 
: in C.  (RSA's implementation is about 150 lines of C,
: so it shouldn't be too hard.)  Then we'll have a public
: domain implementation of a stronger-than-DES cipher
: designed by recognized experts.

So, here it is:

DESX is an encryption algorithm that extends the famous DES
(Data Encryption Standard) algorithm to a keysize of 120 bits.
It does this by simply XORing the input block with a bit pattern
(pre-Whitening), encrypting with standard DES, and then XORing 
the result with another bit pattern (post-Whitening).

DESX was designed by RSA Data Security, and has been in use
in its MailSafe and BSafe encryption products since 1986/87.
RSA DSI says:
  "We claim no intellectual property ownership of DESX except for a
  copyright on our own implementation and a trademark on DESX.  If
  someone wanted to use our spec for DESX, they could call it DESX if it
  were an accurate implementation. In any case, no money is involved."

The algorithm is quite simple, and is described below.  Nearly all
of the steps in the algorithm are at key setup time.

DESX encrypts 64 bits (8 bytes) at a time, just like DES.

DESX takes two keys:  a DES key (represented as 8 bytes, but 
of course only 56 bits are used, as per DES specs), and a
"Whitening" key of length 8 bytes, of which all 64 bits are significant.

The Whitening key is expanded into two 64-bit bit patterns, the
pre-Whitening pattern, and the post-Whitening pattern.

Because DESX uses absolutely off-the-shelf DES as one of its
pieces, a particular DES implementation is not included as part
of the specification of DESX.  It is assumed that you have your
own favorite DES implementation with its own peculiarities in
terms of procedure calling sequences, key data structures, and
so on.

Let's assume the following data structures and procedures.
(I am deliberately using something other than pseudo-C
to help demonstrate that I am not simply publishing RSA's C
source code.  I admit that the result is not completely clear,
but I am trying to avoid writing actual code, for various reasons.)

TypDESXKey has members:
   DESKey64        -- 8-byte DES key supplied by user
   Whitening64     -- 8-byte secondary key supplied by user

TypDESXContext has members:
   DESContext      -- Processed version of DESKey64.  Length and
                      other details depend upon which DES implementation
                      you use.
   PreWhitening64  -- 8-byte XOR pattern computed by key setup
   PostWhitening64 -- Another 8-byte XOR pattern computed by key setup
    
Assume the following functions:

DESXKeySetup(output: TypDESXContext, input: TypDESXKey)
DESXEncryptBlock(input: DESXContext, output: OutData64, input: InData64)
DESXDecryptBlock(input: DESXContext, output: OutData64, input: InData64)

Assume the following lookup table, based in the digits of PI:

DESXSubstTable[0:255] =
  189, 86,234,242,162,241,172, 42,176,147,209,156, 27, 51,253,208,
   48,  4,182,220,125,223, 50, 75,247,203, 69,155, 49,187, 33, 90, 
   65,159,225,217, 74, 77,158,218,160,104, 44,195, 39, 95,128, 54, 
   62,238,251,149, 26,254,206,168, 52,169, 19,240,166, 63,216, 12,
  120, 36,175, 35, 82,193,103, 23,245,102,144,231,232,  7,184, 96,
   72,230, 30, 83,243,146,164,114,140,  8, 21,110,134,  0,132,250,
  244,127,138, 66, 25,246,219,205, 20,141, 80, 18,186, 60,  6, 78, 
  236,179, 53, 17,161,136,142, 43,148,153,183,113,116,211,228,191,
   58,222,150, 14,188, 10,237,119,252, 55,107,  3,121,137, 98,198,
  215,192,210,124,106,139, 34,163, 91,  5, 93,  2,117,213, 97,227,
   24,143, 85, 81,173, 31, 11, 94,133,229,194, 87, 99,202, 61,108,
  180,197,204,112,178,145, 89, 13, 71, 32,200, 79, 88,224,  1,226,
   22, 56,196,111, 59, 15,101, 70,190,126, 45,123,130,249, 64,181, 
   29,115,248,235, 38,199,135,151, 37, 84,177, 40,170,152,157,165,
  100,109,122,212, 16,129, 68,239, 73,214,174, 46,221,118, 92, 47, 
  167, 28,201,  9,105,154,131,207, 41, 57,185,233, 76,255, 67,171


==> DESXKeySetup works as follows:

Compute DESContext from DESKey64 using the key setup procedures
that come with whatever DES implementation you are using.

Set PreWhitening64 to the input key Whitening64.

Compute PostWhitening64 as:
 
  PostWhitening64 := 0
  Run Hash procedure with Input := DESKey64
  Run Hash procedure with Input := Whitening64

Hash procedure:
    For each Ibyte of the 8 bytes of Input, left to right:
      tableindex := left 8 bits of PostWhitening64 XOR
                    next 8 bits (just to right of above) of PostWhitening64
      lastbyte := DESXSubstTable[tableindex]
      Shift PostWhitening64 left 8 bits 
      last (right) 8 bits of PostWhitening64 := lastbyte XOR Ibyte
       

==> DESXEncryptBlock does this:

   OutData64 := InData64 XOR PreWhitening64
   OutData64 := DESEncrypt(DESContext,OutData64)
   OutData64 := OutData64 XOR PostWhitening64

==> DESXDecryptBlock does this:

   OutData64 := InData64 XOR PostWhitening64
   OutData64 := DESDecrypt(DESContext,OutData64)
   OutData64 := OutData64 XOR PreWhitening64


Mark Riordan   28 February 1994   mrr@ripem.msu.edu