english only
School of Computer and Communication Sciences
LASEC - Security and Cryptography Laboratory
EPFL > IC > LASEC > publications
Banner IC
INDEX
Home
People
Research
Teaching
Publications
Softwares & Events
Intranet
How to reach us

CONTACT

EPFL - I&C - ISC - LASEC
Station 14 - Building INF
CH-1015 Lausanne
Switzerland

Tel. +41 21 693 7603
Fax. +41 21 693 7689

Ref: Oech03


Making a Faster Cryptanalytic Time-Memory Trade-Off
Philippe Oechslin

Published:
To appear in Lecture Notes in Computer Science (Proceedings of Crypto'03)

Abstract:
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 (2 37 ) 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 param-eters used.


Download   [HTTP]

© 2011, EPFL