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