A cryptanalytic time-memory trade-off is a technique introduced by M. Hellman in 1980 to perform brute-force attacks. It consists of a time-consuming precomputation phase performed and stored once and for all, which is then used to reduce the computation time of brute-force attacks. A variant, known as rainbow tables, introduced by Oechslin in 2003 is used by most of today’s off-the-shelf password-guessing tools. Precomputation of such tables is highly inefficient however, because much of the values computed during this task are eventually discarded. This paper revisits rainbow tables precomputation, challenging what has so far been regarded as an immutable foundation. The key idea consists in recycling values discarded during the precomputation phase, and adapting the brute force phase to make use of these recycled values. For a given memory and probability of success, the stepped rainbow tables thus created significantly reduce the workload induced by both the precomputation phase and the attack phase. The speedup obtained by using such tables is provided, and backed up by practical experiments.

Abstract Rainbow tables are techniques commonly used in computer security to invert one-way functions, for instance to crack passwords, when the domain of definition is reasonably sized. This article explores the limit on the problem size that can be treated by rainbow tables when the precomputation and the attack phases are both CPU-driven. We conclude that the bottleneck is no longer the memory as it may have been and the precomputation phase seems to have been underestimated so far. We offer a comparison of what can be done on different environments depending on the needs and available computing power of the users.

Internet users are increasingly concerned about their privacy and are looking for ways to protect their data. Additionally, they may rightly fear that companies extract information about them from their online behavior. The so-called tokenization process allows for the use of trusted third-party managed temporary identities, from which no personal data about the user can be inferred. We consider in this paper tokenization systems allowing a customer to hide their credit card number from a webshop. We present here a method for managing tokens in RAM using a table. We refer to our approach as upcycling as it allows for regenerating used tokens by maintaining a table of currently valid tokens. We compare our approach to existing ones and analyze its security. Contrary to the main existing system (Voltage), our table does not increase in size nor slow down over time. The approach we propose satisfies the common specifications of the domain. It is validated by measurements from an implementation. By reaching 70 thousand tries per timeframe, we almost exhaust the possibilities of the 8-digit model for properly dimensioned systems.