MD5 hashes are no longer safe as a hash for signing applications or fingerprinting documents

Short summary of the paper:

It is possible (in a ‘chosen prefix attack scenario) to generate identical MD5 hash values for two functional different binaries.

This has been done before (in 2004) but the main difference here is that the altered binary is fully functional and can contain malicious code while in 2004 the modified file needed to contain the same binary code as the original one. In this attack scenario, the attacker only needs to calculate a few kbytes to prefix both executables which results in both files having the same MD5 hashing value. The only problem for the attacker is that the original file needs to be changed as well. It is still not possible to generate a binary for a given MD5 hash.

What does this mean?
Security software which checks the MD5 signature of an application/document to verify its integrity is no longer to be trusted to provide the correct results.

What about VPNs?
This does not mean that it is now possible to alter the integrity of a VPN connection. Simple reason for this is that in a VPN scenario, data flows continuously over the network and an MD5 hash is only valid for a matter of milliseconds (time the data needs to go from point A->B). It is currently not (yet) possible to alter data, calculate and update identical hashes on the fly. The researchers used a PlayStation 3 with its advanced cell processor to calculate collision hashes as fast as a 30 PC cluster but still it took hours or even days to perform the calculation. Time based security is what effectively protects a VPN in this scenario.

What integrity algorithm to use then?
SHA-1, SHA-224, SHA-256, SHA-384 and SHA-512 are still considered pretty safe and are mandatory in US federal organizations.However, SHA-1 has been reported broken back in 2005 and it was advised to move away from SHA-1 then as well.
Currently the NSA is considering candidates for the next generation hashing algorithm.

Will these kind of attacks actually be seen in the wild?
Most likely not. Simple things still work for the average attacker so there is no need for them in investing in this attack scenario. Especially not for infecting the general public and expanding current botnets.
For targeted attacks and corporate/international espionage scenarios, the story is different. There the attacker might go through the difficulties of this attack because the stakes are higher.