Optimization of Time-Memory Trade-Off Cryptanalysis and Its Application to DES, FEAL-32, and Skipjack (Special Section on Cryptography and Information Security)

概要

論文の詳細を見る
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・years] in about 30 [years].
一般社団法人電子情報通信学会の論文
1996-01-25