OPTIMIZATION OF TIME-MEMORY TRADE-OFF CRYPTANALYSIS AND ITS APPLICATION TO DES, FEAL-32, AND SKIPJACK

In 1980, Hellman presented ''time-memory trade-off cryptanalysis'' for block ciphers, which requires precomputation equivalent to time compl exity of exhaustive search, but can drastically reduce both time compl exity on intercepted ciphertexts of exhaustive search and space comple xity of table lookup. This paper extends his cryptanalysis and optimiz es 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 i n 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, i t takes about 22.5 and 19 [years] respectively until each costs for br eaking Skipjack similarly decreases to 1 [million dollars], but time c omplexity of precomputation is huge in case of the former. The cost-ti me product for this precomputation will decrease to 20 [million dollar s years] in about 30 [years].