[Resource Topic] 2005/207: Some Thoughts on Time-Memory-Data Tradeoffs

Welcome to the resource topic for 2005/207

Some Thoughts on Time-Memory-Data Tradeoffs

Authors: Alex Biryukov


In this paper we show that Time-Memory tradeoff
by Hellman may be extended to Time-Memory-Key tradeoff thus
allowing attacks much faster than exhaustive search for ciphers
for which typically it is stated that no such attack exists. For example,
as a result AES with 128-bit key has only 85-bit security if 2^{43}
encryptions of an arbitrary fixed text under different keys are available to the attacker.
Such attacks are generic and are more practical than some recent high complexity chosen
related-key attacks on round-reduced versions of AES. They constitute a practical threat
for any cipher with 80-bit or shorter keys and are marginally practical for 128-bit key ciphers.
We also show that UNIX password scheme even with carefully generated passwords is vulnerable to
practical tradeoff attacks. Finally we also demonstrate a combination of rainbow tables with
the time-memory-data tradeoff which results in a new tradeoff curve.

ePrint: https://eprint.iacr.org/2005/207

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .