In CRYPTO '94, Langford and Hellman attacked DES reduced to 8-round in the chosen plaintext scenario by their "differential-1inear cryptanalysis," which is a combination of differential cryptanalysis and linear cryptanalysis. In this paper, a historical review of differential-linear cryptanalysis, our formalization of differential-linear cryptanalysis, and the application of differential-linear cryptanalysis to FEAL-8 are presented. As a result, though the previous best method (differential cryptanalysis) required 128 chosen plaintexts, only 12 chosen plaintexts are sufficient, in computer experimentations, to attack FEAL-8.
In 1980, Hellman presented "time-memory trade-off cryptanalysis" for block ciphers, which requires precomputation equivalent to time complexity of exhaustive search, but can drastically reduce both time complexity on intercepted ciphertexts of exhaustive search and space complexity of table lookup. This paper extends his cryptanalysis and optimizes a relation among the breaking cost, time, and success probability. The power of the optimized cryptanalytic method can be demonstrated by the estimates as of January 1995 in the following. For breaking DES in one hour with success probability of 50% or more, the estimated cost of a simple and a highly parallel machine is respectively about 0.26[million dollars] and 0.06[million dollars]. Also it takes about six and two years respectively until each machine costs for breaking FEAL-32 on the same condition decreases to 1[million dollars]. Moreover, it takes about 22.5 and 19[years] respectively until each costs for breaking Skipjack similarly decreases to 1[million dollars], but time complexity of precomputation is huge in case of the former. The cost-time product for this precomputation will decrease to 20[million dollars
Routo TERADA Paulo G. PINHEIRO Kenji KOYAMA
We create a new version of the FEAL-N(X) cryptographic function, called FEAL-N(X)S, by introducing a dynamic swapping function. FEAL-N(X)S is stronger against Differential Cryptanalysis in the sense that any characteristic for FEAL-N(X) is less effective when applied to FEAL-N(X)S. Furthermore, the only iterative characteristics. that may attack the same number of rounds for the two versions are the symmetric ones, which have an average probability bounded above by 2-4 per round, i.e., the FEAL-N(X)S is at least as strong as DES with respect to this type of characteristic. We also show that in general the probability of an iterative characteristic for the FEAL-N(X) that is still valid for FEAL-N(X)S is decreased by 1/2 per round. Some of the best characteristics are shown. Experimental results show that the running time required by FEAL-N(X)S is around 10% greater compared to FEAL-N(X), in software; but this price is small compared to the gained strength against Differential Cryptanalysis.