From: aph@cam-orl.co.uk (Andrew Haley) |-( )--( )--( )+-(1) [1] Re: Ladder DES | \-(1) Organization: Olivetti Research Ltd, Cambridge, \-(1) + England. X-Newsreader: TIN [version 1.2 PL2] Date: Tue Mar 01 13:15:23 CST 1994 Lines: 82 Terry Ritter (ritter@cactus.org) wrote: : Ritter Software Engineering : 2609 Choctaw Trail : Austin, Texas 78745 : (512) 892-0494, ritter@cactus.org : Ladder-DES: A Proposed Candidate to Replace DES : Terry Ritter : February 22, 1994 [ ...deleted... ] : A B : | k1 | : v v | : XOR <- DES1 ----| : | | : | k2 | : | v v : |---- DES2 -> XOR : | | : v v : C D It's worth pointing out that when used this way DES is always carried out in the "forward" direction, even during decryption. Because of this, the "scrambling" function used in the "ladder" only needs to be a pseudorandom function; it does not have to be a pseudorandom permutation like DES. A hash function with a 128-bit input and a 64 bit output could be used for this purpose. [ ...deleted... ] : Conclusion : DES operations can be arranged into a "ladder-DES" constructs which : are especially-clean and familiar and seem to resist known attacks. : These constructs seem potentially stronger than normal DES and are : demonstrably faster than triple-DES. Thus, ladder-DES could be a : reasonable candidate to replace DES. These schemes have been the subject of much research in recent years. The classic paper is [1], in which it is shown that three rounds in the structure above are sufficient to prove perfectness (polynomial time indistinguishability from a truly random permutation), provided that the random functions are themselves perfect. There have been many papers on schemes to reduce the key space by using one of the pseudorandom functions more than once; a few examples are given here. Andrew. [1] M. Luby and C. Rackoff, "How to construct pseudorandom permutations from pseudorandom functions," SIAM J. Comput. vol 17, pp. 373-386, 1988. [2] Ulei M. Maurer, "A Simplified and Generalized Treatment of Luby-Rackoff Pseudorandom Permutation Generators," Proc. EUROCRYPT '92, pp. 239-255, 1993. [3] Jacques Patarin, "How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function," Proc. EUROCRYPT '92, pp. 256-266, 1993. [4] Jacques Patarin, "New results on pseudorandom permutation generators based on the DES scheme," Proc. CRYPTO '91, pp. 301-312, 1992. [5] Josef Pieprzyk,, "How to construct Pseudorandom Permutations from Single Pseudorandom Functions," Proc. EUROCRYPT '90, pp. 140-150, 1991. -- "Always keep an open mind, but not so open that your brain falls out."