Paper 2005/207

Some Thoughts on Time-Memory-Data Tradeoffs

Alex Biryukov

Abstract

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.

Note: It seems that we will have to give up the convenient world in which we assumed a k-bit security for a good k-bit key cipher.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Time-Memory-Data Tradeoff
Contact author(s)
abiryuko @ esat kuleuven be
History
2005-07-01: received
Short URL
https://ia.cr/2005/207
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/207,
      author = {Alex Biryukov},
      title = {Some Thoughts on Time-Memory-Data Tradeoffs},
      howpublished = {Cryptology ePrint Archive, Paper 2005/207},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/207}},
      url = {https://eprint.iacr.org/2005/207}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.