HashClash (BOINC平台)---英文---狀態不明

包含 BURP、Cels@Home、Chess960@Home、ESEA@home、Gerasim@Home、NCSSM Grid Computing、Pirates@Home、Project Neuron、RND@home 這些專案
文章: 639
註冊時間: 2006-03-17 23:42

HashClash (BOINC平台)---英文---狀態不明

文章 BOINC » 2007-05-18 21:24



HashClash explanation

MD5 is a hash-function which maps any message to a fixed number of 128 bits called the hash. This is done in such a manner that the following two problems are hard:

* finding a collision: two messages with the same hash
* finding a pre-image: for a given hash find a message that maps to that hash

Because of these properties MD5 is used commonly for the following purposes:

* Integrity checking: to verify that a file did not change or was transmitted correctly
* Digital signatures: a message is signed by signing its hash

MD5 was designed by Ron Rivest in 1991. It breaks each message into 512-bits blocks, and processes them seperately in a iterative way by using a function md5compress.

* iv0 is a fixed value in MD5
* iv1 = md5compress(iv0, block1)
* iv2 = md5compress(iv1, block2)
* ....

The hash of a message is now the iv value calculated using the last block.
MD5 collisions
MD5 has been broken in August 2004 by a chinese research team consisting of Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu. They showed how to create a collision of two messages with the same hash. However these messages have a special form:

* First blocks are equal, e.g. block1,...,block41.
Therefore both messages have the same value in iv1,...,iv41.
* Two blocks that are generated completely random: block42 and block43. They depend on the specific value in iv41.
The messages differ in these two blocks, however these blocks are such that both have the same value iv43.
* Last blocks are also equal, therefore all the values from iv43 till the last iv value, the hash, are equal.

Their attack creates collisions that are not easily to abuse. In real life you have to put the two colliding blocks, which are totally random nonsense, to some use. There are two examples where it has been done:

* In digital certificates: the random blocks are put inside the public key.
However these certificates still have the same Name, Address, etc., so you can't fool anyone with it.
* In digital documents: the random blocks are put inside a if-then-else construction.
In this construction each file contains both documents, however using the if-then-else either the first or the second is shown.

The first attack was done in about one hour on a high-performance IBM p690 cluster. Later reports show that attacks on a desktop pc with a Pentium4 1.7Ghz can be done in approx. 4 hours. Currently Marc has gained a substantial speedup of this attack. A report is in preparation.
Project HashClash
Using techniques from the attack from Wang et al., we are trying to find collisions which are more flexible. More concretely, we will allow the first blocks of two messages to be chosen at will. This attack is in ongoing research, however it is already clear that it requires large scale computational power. Therefore project HashClash was started. Currently you can join HashClash to help us in the first phase of this research, called 'MD5 Birthdaying'. It consists of finding a block with very specific properties, that will help us in later phases. Finding that block on a single Pentium4 3Ghz would take approx. 800 days of 24/7 continous running. We hope by combining the computational powers of many pc's to find this block much faster.

This project is intended as cryptographic research only. We intend to clarify the nature of the vulnerabilities in applications of MD5 that have been opened up by the collision finding methods of Wang et al. At a later stage we also intend to work on collision-finding for SHA-1.


請參考:[教學]BOINC基本名詞與安裝 - ㈣添加專案

文章: 356
註冊時間: 2006-04-20 16:27
中央處理器 CPU: Intel CORE i3-3120M
顯示卡 GPU: AMD Radeon HD 7670M
主記憶體 RAM: 4G
CPU 主力專案: Collatz Conjecture
GPU 主力專案: Moo! Wrapper
來自: 後山

文章 kaoh » 2007-09-05 21:47





正在瀏覽這個版面的使用者:沒有註冊會員 和 1 位訪客