Many cryptanalytic problems can be solved in theory using an exhaustive search in the key space, but are still hard to solve in practice because each new instance of the problem requires to restart the process from scratch. The basic idea of a time-memory trade-off is to carry out an exhaustive search once for all such that following instances of the problem become easier to solve. Thus, if there are N possible solutions to a given problem, a time-memory trade-off can solve it with T units of time and M units of memory. In the methods we are looking at, T is proportional to N2/M2 and a typical setting is T=M=N2/3.
Cryptanalytic time-memory trade-offs have been introduced in 1980 by Hellman and applied to DES. Given a plaintext D and a ciphertext C, the problem consists in recovering the key K such that C=EK(D) where E is an encryption function assumed to follow the behavior of a random function. Encrypting D under all possible keys and storing each corresponding ciphertext allows for immediate cryptanalysis but needs N elements of memory. The idea of a time-memory trade-off is to find a trade-off between the exhaustive search and the exhaustive storage. For that, an exhaustive search is carried out once (precomputation) and only a subset of generated values is kept.
In 2003, Oechslin introduced the trade-off based on rainbow tables and demonstrated the efficiency of his technique by recovering Windows passwords. In collaboration with Philippe Oechslin (Objectif Sécurité) and Pascal Junod (HEIG-Vd), we provided a formal analysis of rainbow tables and improved them using a new concept called checkpoints. We still work on the improvement of the time-memory trade-off using new approaches.
