Some Thoughts on Time-Memory-Data Tradeoffs.
Alex Biryukov · 2005
In this paper we show that Time-Memory tradeo# by Hellman may be extended to Time-Memory-Key tradeo# 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 encryptions of an arbitrary fixed text under di#erent 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 tradeo# attacks. Finally we also demonstrate a combination of rainbow tables with the time-memory-data tradeo# which results in a new tradeo# curve.