On the time-memory tradeoff between exhaustive key search and table precomputation
Johan Borst, Bart Preneel, Joos P. L. Vandewalle · 1998
In cryptanalysis of block ciphers, there are several attacks that are always feasible and for which the success probability and complexity only depend on key length and/or block size. Exhaustive key search and table precomputation are two of such attacks. In [Hel80] an attack was introduced which provides a tradeoff between the processing complexity of exhaustive key search and the memory complexity of table precomputation. We introduce a variant on the Hellman time-memory tradeoff, which decreases the expected number of memory accesses by a large factor and we demonstrate its advantages in a distributed key search. 1 Introduction In this paper we study an attack on block ciphers that combines the following two attacks. One is exhaustive key search in which an attacker tries all possible keys to encrypt a known plaintext for which he has the corresponding ciphertext. The other is table precomputation in which the attacker precomputes and stores encryptions of a chosen plaintext and co...