Actually you would expect to on average test 1/2 of the keyspace to find a match - since the space is 128 bits, or 2^128 combinations, half of it is 2^127 (or 1.7 * 10^38). That's a lot longer than a few years even if you do parallellize it.
Added to that, each attempt is more expensive computationally (you are trying to create a several mb file that has an md5 collision and hash it) than something simple like RC4/RC5. IIRC, MD5 takes about 80 cycles for every 64 bytes - that's about 5 million cycles per mp3 to be conservative, never mind generating a file. So expected time for a match would be 1.7 * 10^38 * 5 * 10^6 CPU cycles = 8.5 * 10^44 cycles.
Assume a 1ghz cpu that has a single ALU with ideal pipeline for this and no memory overhead - 10^9 cycles/sec. 3.1*10^7 seconds/year. So 2.7*10^37 CPU years.
In other words, a very conservative estimate of a billion PCs taking 10^28 (ten billion billion billion) years to find an mp3 file whose MD5 hash collides with another. If you have a set of N files and you are looking for a collision with just one, divide above number by N.
Depending on the cell phone you have, and the service, you may be able to make data calls via your cell phone. Data cables are avalilable for Motorola Startacs (pretty much any startac), Motorola i500/1000/2000, and most Nokia's. Some have Palm data cables available. For others, just get the Palm travel kit, and make a cable to connect the travel kit's DB9 to the data cable's DB9 (email me if you want the data cable specs, I need to dig them up).
I used to use a Nokia data cable, a palm V travel kit, and the abovementioned converter. I have since switched to a Motorola i1000, which has pre-made palm data cables available.
The nice thing about using the palm instead of some device like the Blackberry is the flexibility. I have an SSH1 client, a pop3 reader, a web browser, and an IRC client on there. I even have a VNC client, though it's a major pain to use. However, VNC and SSH come in very useful in emergencies, when you absolutely, positively must get that server back up:)
Also, if you have an analog phone, chances are you won't have to pay extra to make data calls. I have a GSM phone, so it's $15/mo for the data calls, and the minutes come out of the normal free minutes each month.
Slashdot Mirror
Actually you would expect to on average test 1/2 of the keyspace to find a match - since the space is 128 bits, or 2^128 combinations, half of it is 2^127 (or 1.7 * 10^38). That's a lot longer than a few years even if you do parallellize it.
Added to that, each attempt is more expensive computationally (you are trying to create a several mb file that has an md5 collision and hash it) than something simple like RC4/RC5.
IIRC, MD5 takes about 80 cycles for every 64 bytes - that's about 5 million cycles per mp3 to be conservative, never mind generating a file. So expected time for a match would be 1.7 * 10^38 * 5 * 10^6 CPU cycles = 8.5 * 10^44 cycles.
Assume a 1ghz cpu that has a single ALU with ideal pipeline for this and no memory overhead - 10^9 cycles/sec. 3.1*10^7 seconds/year. So 2.7*10^37 CPU years.
In other words, a very conservative estimate of a billion PCs taking 10^28 (ten billion billion billion) years to find an mp3 file whose MD5 hash collides with another. If you have a set of N files and you are looking for a collision with just one, divide above number by N.
Depending on the cell phone you have, and the service, you may be able to make data calls via your cell phone. Data cables are avalilable for Motorola Startacs (pretty much any startac), Motorola i500/1000/2000, and most Nokia's. Some have Palm data cables available. For others, just get the Palm travel kit, and make a cable to connect the travel kit's DB9 to the data cable's DB9 (email me if you want the data cable specs, I need to dig them up).
:)
I used to use a Nokia data cable, a palm V travel kit, and the abovementioned converter. I have since switched to a Motorola i1000, which has pre-made palm data cables available.
The nice thing about using the palm instead of some device like the Blackberry is the flexibility. I have an SSH1 client, a pop3 reader, a web browser, and an IRC client on there. I even have a VNC client, though it's a major pain to use. However, VNC and SSH come in very useful in emergencies, when you absolutely, positively must get that server back up
Also, if you have an analog phone, chances are you won't have to pay extra to make data calls. I have a GSM phone, so it's $15/mo for the data calls, and the minutes come out of the normal free minutes each month.