K. Kusuda et T. Matsumoto, OPTIMIZATION OF TIME-MEMORY TRADE-OFF CRYPTANALYSIS AND ITS APPLICATION TO DES, FEAL-32, AND SKIPJACK, IEICE transactions on fundamentals of electronics, communications and computer science, E79A(1), 1996, pp. 35-48
Citations number
19
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
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].