From: Shelby Moore <coolpage(_at_)earthlink(_dot_)net>
...
1. Vernon apparently got offended because I pointed out that he
didn't realize that MD5 checksum on IPv4 was easily breakable via
dictionary attack or that his use of it went his often public stated
condescending policy of "do not implement half-solutions".
Perhaps Mr. Moore should recall my claim to archive mail.
He wrote this:
< 3. Most importantly, is there any reasonable way to extract the
< original IP from the checksum? I suppose the IPv4 address space
< is 4 billion. How long does it take to run 4 billion MD5 hashs?
< If impractical, I might be able to work with your checksums in my
< database instead of storing IP addresses (might not be a such a
< bad idea for privacy reasons). However, why did you use checksum
< on IP any way (seems to me a hacker can get the original IP using
< a brute force attack)?
I responded:
] The DCC databases contain only MD5 hashes. If you know of a way to
] reverse MD5 hashes other than a dictionary attack, you should publish
] it and get famous. I'm not sure, but you may be agreeing with that
] throught.
]
] When the DCC databases contained MD5 hashes of IP addresses, they were
] of IPv6 addresses. Of course, those IPv6 addresses were related in
] the standard way to IPv4 addresses. I've not timed MD5 on 128 bit
] values, but guess 100 usec/hash. If that's right, you could build a
] 16 GByte dictionary in about 100 hours.
(I made an arithmetic error in the figuring the size of the dictionary.)
Mr. Moore came back with:
} http://www.faqs.org/rfcs/rfc1810.html
}
} 1995 RFC claims 87 Mbps rate for MD5 in software. Assuming Moore's
} Law (double speed every 18 months), then we get 9 years (6 x 18
} months) to 2004, thus 6*87Mbps in 2004.
}
} 32 bit = 2 ^ 32 = 4 billion / 6*87 millions = 24 seconds.
}
} So if you had 1% of that space, or 40 million IPs in your databases
} over time, then would take approx. 20 million minutes = 333,000
} hours = 15,000 days < 50 years to convert all MD5 back to IPv4s.
}
} However an inverse table could be built if we had 4 GB * 128 bit
} of storage = 4 * 16 GB = 64 GB. This would drop the time to probably < month.
}
} Assuming I am interpreting the RFC correctly.
}
} Note I read some where that 2 ^ 64 search space is required before
} hitting the duplicate space of MD5.
and later:
| >When the DCC databases contained MD5 hashes of IP addresses, they were
| >of IPv6 addresses. Of course, those IPv6 addresses were related in
| >the standard way to IPv4 addresses. I've not timed MD5 on 128 bit
| >values, but guess 100 usec/hash. If that's right, you could build a
| >16 GByte dictionary in about 100 hours.
|
| Correct 16 GB, not the 64 GB I mistakenly wrote late last night.
Perhaps Mr. Moore's 16 GBytes comes from limiting the dictionary to
1 billion interesting IPv4 addresses. Otherwise 64 GBytes is better.
I never did figure out what Mr. Moore meant by 15,000 days. He
could not have been thinking of doing on average 2 billion MD5 hashes
for each of 4 billion IPv4 addresses, because that would have been
silly and would have take more than 15,000 days.
Ok, I'll stop feeding the troll now.
Vernon Schryver vjs(_at_)rhyolite(_dot_)com