Paper 2012/683

Fingerprint Tables: A Generalization of Rainbow Tables

Gildas Avoine, Adrien Bourgeois, and Xavier Carpent

Abstract

Cryptanalytic time-memory trade-offs were introduced by Hellman in 1980 in order to perform key-recovery attacks on cryptosystems. A major advance was presented at Crypto 2003 by Oechslin, with the rainbow table variant that outperforms Hellman's seminal work. This paper introduces the fingerprint tables, which drastically reduce the number of false alarms during the attack compared to the rainbow tables. The key point of our technique consists in storing in the tables the fingerprints of the chains instead of their endpoints. The fingerprint tables provide a time-memory trade-off that is about two times faster than the rainbow tables on usual problem sizes. We experimentally illustrate the performance of our technique, and demonstrate that it is faster than Ophcrack, a Windows LM Hash password cracker considered so far to be the fastest one ever implemented.

Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. Unknown status
Keywords
TMTO
Contact author(s)
gildas avoine @ uclouvain be
xavier carpent @ uclouvain be
History
2014-06-24: withdrawn
2012-12-10: received
See all versions
Short URL
https://ia.cr/2012/683
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.