I'm not worried about it. Just use AES256 and your fine. In 50 years, there will be another better algo to use.

The MD5 Timeline

1995 - Hans Dobbertin announces a weakness in a component of MD5.

1996 - Publication of Dobbertin's paper.

2004 - Wang, Feng, Lai, and Yu announce the construction of collisions in the full MD5 hash.

2005 - Lenstra and Wang construct X.509 certificates with the same hash for 2 different public keys - a capability that could plainly be put to (nefarious) practical use.

2006 - Klima publishes an algorithm claimed to be capable of finding collisions within one minute using a standard PC.

Thus, we see it took about 10 years between the publication of a weakness in MD5, and the first publicly announced practical attack.

My intuition is that it will take years to develop attacks that can approach a practical level, and the "security life" of cryptosystems using AES may expire before AES can be broken.

These are enourmous key spaces:

2^119= 6.64613997892458e+35
2^110.5=1.83575415930179e+33

I agree with MarkH: AES will have been retired by the time this become computationally possible in a reasonable amount of time.

An attacker's time would be better spent working on a better attack.

Every known mathimatical cryptosystem will eventually be broken when computing power grows enough to break it. It all about how long you want the data to be secret

While I agree with the overall idea that 'attacks only get better', I don't see how comparing a symmetric cipher to a message digest is relevant in the slightest, or how it is somehow a measure for how long AES has left to live.

A message digest like MD5 is only as good as its collision resistance. If you're converting any file on the planet into a 128-bit number, you're already completely certain there are innumerable collisions, but the algorithm is still useful as long as no one can figure out how to *construct* such collisions (which is what eventually happened with MD5, it stopped being a one-way transformation).

Constructing collisions is essentially a shortcut that breaks the usefulness of the message digest without breaking the mathematical constructs behind it.
However, there is no such shortcut with AES since it is meaningless to talk of collisions with a symmetric cipher. The two are used for entirely different purposes and AES is not meant to be a one-way transformation.

Even if you did find collisions in AES (two identical cryptotexts from the same input), nobody who wants their data to be secure uses AES in its 'raw mode' (ECB), you have to chain together or modify your output anyway in order to resist replay attacks.

"...nobody who wants their data to be secure uses AES in its 'raw mode' (ECB), you have to chain together or modify your output anyway in order to resist replay attacks."

Huh?

If I use AES256 for my encrypted home or data partitions in Linux, or use it for emailing (pgp/gpg), or other similar applications, do I have to worry about the above paragraph?

Are there settings when setting up a mail client or partitioning and formatting a partition for encryption with AES that I need to set, or is this (above paragraph) something to worry about only for use of AES for some exotic uses that don't pertain to desktop or server linux users?

Are my nuclear secrets safe or not?

@TG: Absolutely, hash algorithms and symmetric ciphers are different kinds of animal.

I believe Sean's post compares them, because MD5 and AES made similar arguments for security: 1. There is no better attack than exhaustive search; 2. We know the cost of exhaustive search; 3. Therefore break is infeasible using X amount of computational resources.

For applications requiring second preimage (collision) resistance, MD5 must be considered dead because the cost of finding them is too low. MD5 is still probably has quite strong first preimage resistance, and may for years to come.

If I understand the new paper correctly, it describes a VERY SPECIALIZED ATTACK whose purpose is recovery of an unknown secret key (cryptanalysis). It can do so at much lower computational cost than would be expected from an ideal 256-bit cipher.

The "local collisions" described in the paper aren't hash-algorithm style collisions: they are collisions in the internal state of the cipher computation, that help to reduce the cost of the attack. As TG wrote, it makes no sense to look for two plaintexts producing the same ciphertext under the same key: a valid block cipher can never do this!

Because the new AES attack is so specialized, it could only lead to a practical attack under unusual (but not impossible) conditions, even if it didn't require a completely impractical amount of computation.

But it DOES seem to show that AES lacks a property that would be expected of an ideal cipher, and in this way is something like the original weakness found in MD5 back in 1995.