On Tue, 27 May 2008 20:45:11 BST, michael.dillon@bt.com said:
1) The brute-force attack which will require hundreds of thousands of CPU-years.
Millions. Not thousands. See below.
In this case an attacker would definitely go with this option. Since they can't change most of the IOS bytes because they contain IOS and the exploit, they would definitely run a brute force attack on the remaining bytes. Granted, the chances of success are slim, but these are people who are used to playing the odds even if they lose most of the time.
I think you're thinking of the known collision attack against MD5, where you start off with two plaintexts of your choice, and by suitable manipulation of a smallish (on the order of 256 bytes) section of each, you can get the two files to have the same MD5sum. Unfortunately, you have zero control over what the output MD5sum is. There's a known method for doing this that will do it in about 8 hours on a 1.6Ghz computer: http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf In contrast, a "pre-image" attack (finding a plaintext that will hash to a given MD5 hash) is still a bunch of work - this 2004 paper by Kelsey and Schneier (http://eprint.iacr.org/2004/304.pdf) shows how to, for a 128-bit hash and (for instance) a 1 gigabyte file, to compute a second-preimage attack in (roughly) 2**105 rather than the expected 2**128 (n=128 and k=24, for those of you playing along at home). So let's see - if you had a billion CPUs in your botnet, and each one could go at a billion to the second, you still need 2**69 seconds or 449,235,776,528,695 years. Not bad - only 10,000 times the amount of time this planet has been around, so yeah, that's the way they'll attack all right. (If somebody knows a *better* pre-image attack, please fill me in. I know there's a few other crypto-heads out there...)