Newsgroups: sci.crypt Path: cactus.org!ritter From: ritter@cactus.org (Terry Ritter) Subject: Re: Ladder DES Message-ID: <1994Feb25.175146.1205@cactus.org> Keywords: DES replacement, large blocks Organization: Capital Area Central Texas UNIX Society, Austin, Tx References: <1994Feb22.083353.26012@cactus.org>Date: Fri, 25 Feb 1994 17:51:46 GMT In dbarber@crash.cts.com (David C. Barber) writes: >An interesting post, but begs a question on why don't we want to >use IDEA to replace DES? Speaking for myself, I have trouble *believing* that IDEA (or PES or IPES) is strong. I am of course aware that my intuition of strength has little to do with reality. However, since we cannot *test* or *prove* strength, the mere *feeling* of weakness is what every formal attack must be before it is born. As I reported on sci.crypt, I have performed some experiments on automatically attacking complex combining mechanisms. I found that some apparently complex mechanisms are attackable *provided* their internal operations are linear. For example, it is fairly easy to break PKZIP encryption which has had the output nonlinear operation removed. I have yet to find a way around that section. Occasionally I issue a call for any literature anyone has seen on the solution of large systems of Boolean equations. Surely, with sufficient information, even a system with nonlinear elements must be directly solvable. When I look at IDEA I see a structure which seems complex, but every operation is linear (with the possible exception of multiplication mod 2^16+1). There is no substitution. There is no selection. The innermost four-operation transformation is the same (albeit with different keys) for each round, and it is the rounds which appear to build strength. Thus, my intuition is to not trust IDEA. I don't know what the current results are (I think IDEA became PES, and weakness in PES resulted in IPES), but I have read the comments in: Lai, X. and J. Massey. 1991. Markov Ciphers and Differential Cryptanalysis. Advances in Cryptology--Eurocrypt '91. 17-38. In the conclusions (p. 38) we find: ". . . the true strength of the standard PES algorithm is of the order of 2^64 encryptions, a considerable reduction from the work that a cryptanalyst would expected (sic) in an exhaustive key search for the 128-bit key." I note that this is comparable to realizing that double-DES, with a putative 112-bit key, actually has a strength similar to a 57-bit key. Since double-DES has twice the expense of normal 56-bit DES, this was sufficient to make double-DES essentially useless. The improved IPES apparently does not fall to the same (differential) attack, so maybe it is better. But maybe we can fix up double-DES without changing the internals of the proven cipher. If we believe that strong ciphers are possible, then we already recognize the ability to build a strong large cipher out of less- strong components. If we can limit the intellectual distance in a cipher (from the base exclusive-OR and the final result), we might understand ciphers better, even at their lowest levels. If we can take a structure of known strength that we do believe in, and use it as a building-block in a relatively-simple construct which we can build a belief in, we can hope to avoid the need for the terrible depth of analysis required to certify an entire cipher. We have no public institutions set up to fund or organize such a certification. If it eventually comes down to the need for the banking industry to set up and fund a cipher certification facility, we may get to see just how badly the banks want to avoid government-designed secret cipher systems. Terry