A Cryptanalytic Time-Memory Tradeoff

Many searching problems allow time-memory tradeoffs. That is, if there are K possible solutions to search over, the time-memory tradeoff allows the solution to be found in T operations (time) withM words of memory, provided the time-memory product T ×M equals K. Cryptanalytic attacks based on exhaustive key search are the typical context where time-memory tradeoffs are applicable. Due to large key sizes, exhaustive key search usually needs unrealistic computing pow-ers and corresponds to a situation where T = K and M = 1. However, if the same attack has to be carried out numerous times, it may be possible to execute the exhaus-tive search in advance and store all the results in a memory. Once this precomputation is done, the attack could be performed almost instantaneously, although in practice, the method is not realistic because of the huge amount of memory needed: T = 1, M = K. The aim of a time-memory tradeoff is to mount an attack that has a lower online processing complexity than exhaustive key search and lower memory complexity than a table lookup. The method can be used to invert any one-way function and was originally presented by Hellman in [1]. 1 The original method Let EK(X) : 2n × 2k → 2n denote an encryption function of a n-bit plaintext X under a k-bit secret key K. The time-memory tradeoff method needs to define function g that maps ciphertexts to keys: g: 2n → 2k. If n> k, g it is a simple reduction function that drops some bits from the ciphertexts (e.g. in the DES, n = 64, k = 56). If n < k, g adds some constant bits. Then we define f(K) = g(EK(P)) (1) Where P is a fixed chosen plaintext. Computing f(K) is almost as simple as enci-phering, but computing K from f(K) is equivalent to cryptanalysis. The time-memory tradeoff method is composed of a precomputation task and an online attack that we describe as follows. Precomputation task: The cryptanalyst first chooses m different start points: SP1, SP2,..., SPm from the key space. Then he computes encryption chains whereXi,0 = SPi and Xi,j+1 = f(Xi,j), for 1 ≤ j ≤ t: X0,0 f → X0,1 f → X0,2 f →....... f → X0,