North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: IOS Rookit: the sky isn't falling (yet)

  • From: Valdis . Kletnieks
  • Date: Tue May 27 16:43:52 2008

On Tue, 27 May 2008 20:45:11 BST, [email protected] 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...)


Attachment: pgp00008.pgp
Description: PGP signature