土产品的土产品

Again from CWI website：

PlayStation 3 used to predict next US president

Can scientists correctly predict the outcome of the 2008 US presidential elections? That is the big question of the new Nostradamus website, launched on November 30, 2007 by researchers Marc Stevens (CWI, Amsterdam), Arjen Lenstra (EPFL, Lausanne), and Benne de Weger (Technical University Eindhoven). To avoid influencing the public debate on the elections, the researchers will keep their prediction secret in a pdf file until the day after the elections. Until that time, they only reveal the MD5 hash function of this file.

Such a hash function or ‘checksum’ can be compared to a digital fingerprint or signature of a document. Many people use the MD5 hash to check if downloaded software is exactly the same as the original. “But MD5 is not safe anymore,” Benne de Weger says. “In 2004, it was already proven that two equal hash codes could be constructed for files that differed 128 bytes in a row.” But by now, the three researchers can even construct equal hash values for files that are different in an unlimited amount of bytes - in less than two days! “We did this with a PlayStation 3 because of its computing power,” Marc Stevens explains. “Using a normal PC, it would take about 30 times longer.”

At the end, constructing equal hash codes turns out to be the secret behind the new Nostradamus website. “Actually, we made 12 different predictions with the same hash functions,” Marc Stevens smiles. “After the elections we can pick the right one. Although this is a kind of a trick, we have a serious message: People really should change their hash procedures from MD5 to safer techniques, like SHA2!”

More information can be found on PNA5’s website or the Nostradamus website

( December 7, 2007 )

BTW MD5的collision是中国人先找出来的。简单的说hash function（比如MD5）是把任何长度信息变成固定长度的字串，所以一个东西的hash值可以作为这个东西的精练”摘要”用来检查文件的完整性。不过因为hash function输出的只是固定长度的字串，所以理论上讲一定有很多很多的原始信息hash后会得到一样值，关键是有没有好的算法计算这些collisions了。。当然hash function还有其他用途，比如这种操作通常需要保证one wayness：知道原始信息算hash值容易，但从hash值算原始信息在实际上基本不可能，可以用来加密信息，作为commitment之类的。