Re: Time-Memory-Key tradeoff attacks?

2005-07-06 Thread D. J. Bernstein
My paper ``Understanding brute force'' explains an attack with a much
better price-performance ratio than the attack described by Biryukov:

   http://cr.yp.to/talks.html#2005.05.27
   http://cr.yp.to/papers.html#bruteforce

Biryukov's central point regarding key amortization was made earlier
(and, I think, more clearly) in my paper. My paper also analyzes the
merits of various defenses against the attack.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Time-Memory-Key tradeoff attacks?

2005-07-05 Thread Perry E. Metzger

The following has appeared in the IACR preprint archive. I would
appreciate comments. The author certainly has reasonable credentials,
but the document is low on detail:

http://eprint.iacr.org/2005/207

  Some Thoughts on Time-Memory-Data Tradeoffs

  Author: 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.

By the way, much thanks to Eric Rescorla for pointing this out to me.

Perry
-- 
Perry E. Metzger[EMAIL PROTECTED]

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]