What is a Time-Memory Tradeoff (TMTO), and how does it balance computation time and storage?
A TMTO combines key search and table lookup — instead of spending all effort on time or all on storage, it uses $k^{2/3}$ of each, dramatically reducing both compared to pure approaches.
* For a 64-bit key: key search and table lookup sit at the extremes; TMTO buys back both time and storage. *
The spectrum of brute-force attacks:
| Attack | Time | Storage |
|---|---|---|
| Exhaustive key search | $k$ | 1 |
| Table lookup | 1 | $k$ |
| TMTO | $k^{2/3}$ | $k^{2/3}$ |
| Theoretical TMTO | $k^{1/3}$ | $k^{1/3}$ |
Example for 64-bit key ($k = 2^{64}$):
| Storage | Time | |
|---|---|---|
| Table lookup | $2^{70} \approx 10^{21}$ | 1 |
| Key search | 1 | $2^{64} \approx 10^{19}$ |
| TMTO ($k^{2/3}$) | $\approx 10^{14}$ | $\approx 10^{12}$ |
| Theoretical ($k^{1/3}$) | $\approx 10^{7}$ | $\approx 10^{6}$ |
The TMTO effectively reduces the security of a cipher — for a 64-bit key, the practical effort drops to that of a ~43-bit key (or even ~21-bit in the theoretical case).
Important: "Meet-in-the-middle" is a specific TMTO technique — don't confuse it with "man-in-the-middle" (a completely different network attack)!
Go deeper:
Meet-in-the-middle attack (Wikipedia) — the best-known TMTO, applied to multiple encryption.