Publication: A Parallel Implementation of Rainbowcrack Using MPI

All || By Area || By Year

Title	A Parallel Implementation of Rainbowcrack Using MPI
Authors/Editors*	Edward R. Sykes, Wesley Skoczen
Where published*	Lecture Notes in Computer Science
How published*	Proceedings
Year*	2009
Volume
Number
Pages
Publisher	Springer
Keywords	Rainbow tables, MPI, time-memory trade-off, password cracking, parallel processing, cryptanalysis
Link
Abstract	Nearly three decades ago, Martin Hellman introduced a cryptanalytic time-memory trade-off algorithm which reduced the time of cryptanalysis by using precalculated data. Rivest shortly improved this technique by introducing distinguished points which significantly reduced the frequency of memory lookups during cryptanalysis. In 2003, Philip Oechslin proposed a new and improved algorithm which reduces the number of calculations during cryptanalysis by a factor of two. In this research we present the results of a parallel implementation of Oechslin's faster time-memory trade-off algorithm using MPI on a SHARCNET supercomputer. We use MS-Windows hashes (alphanumeric sequences of length 14 characters or less). We can construct 119GB of data in 6 days and crack 99.9% of all passwords hashes in 6 seconds or less. On a standard desktop machine, the same task requires 2,354 days (6 years!) to construct the data and 3-15 minutes to crack the password