Making a Faster Cryptanalytic Time-Memory Trade-Off

By Philippe Oechslin. Annual International Cryptology Conference, 2003

593 citations recorded by the source corpus.

In 1980 Martin Hellman described a cryptanalytic time-memory trade-off which reduces the time of cryptanalysis by using precalculated data stored in memory. This technique was improved by Rivest before 1982 with the introduction of distinguished points which drastically reduces the number of memory lookups during cryptanalysis. This improved technique has been studied extensively but no new optimisations have been published ever since. We propose a new way of precalculating the data which reduces by two the number of calculations needed during cryptanalysis. Moreover, since the method does not make use of distinguished points, it reduces the overhead due to the variable chain length, which again significantly reduces the number of calculations. As an example we have implemented an attack on MS-Windows password hashes. Using 1.4GB of data (two CD-ROMs) we can crack 99.9% of all alphanumerical passwords hashes (237) in 13.6 seconds whereas it takes 101 seconds with the current approach using distinguished points. We show that the gain could be even much higher depending on the parameters used.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/eebde39b0f6258421699c0f21d639364be0aca24

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Cracking Classifiers for Evasion: A Case Study on the Google's Phishing Pages Filter (2016, methodology): “The rainbow table attack [45] is a more sophisticated hash cracking method.”
Reverse-Engineering a Cryptographic RFID Tag (2008, background): “Rainbow tables store just enough information from a key space for finding any key with high probability, but require much less space than a table for all keys [9, 15].”
Password Strength: An Empirical Analysis (2010, background): “Attacks based on pre-computing the hashed version of the most likely passwords [8], [15] are defeated with “salting”: appending a random number to the password before hashing it,”
Defining Strong Privacy for RFID (2007, background): “(They in fact propose use of a variant called rainbow chains put forth by Oechslin [22].”
Graphical passwords: Learning from the first twelve years (2012, methodology): “Exhaustive-search optimizations such as Oechslin’s rainbow tables [80], which trade pre-computation time for storage, are relevant for password cracking.”
Password Cracking Using Probabilistic Context-Free Grammars (2009, methodology): “If no salting is used, brute-force attacks can be dramatically improved through the use of precomputation and powerful time-memory trade-off techniques [7, 8].”
Guessing human-chosen secrets (2012, unknown): “Oechslin introduced a refinement of this approach in 2003 called rainbow tables [225] which again greatly improve efficiency.”
Introduction to Modern Cryptography, Second Edition (2014, unknown): “Time/space tradeoffs for function inversion were introduced by Hellman [87], with practical improvements—not discussed here—given by Rivest (unpublished) and by Oechslin [134].”
A scalable and provably secure hash-based RFID protocol (2005, background): “Given forward privacy and given the fact that the encryption keys are erased and that one knowledge of one key do not allow one to recover the previous ones, forward secrecy is straightforward.”