[104816] in North American Network Operators' Group
Re: IOS Rookit: the sky isn't falling (yet)
daemon@ATHENA.MIT.EDU (Valdis.Kletnieks@vt.edu)
Tue May 27 16:43:56 2008
To: michael.dillon@bt.com
In-Reply-To: Your message of "Tue, 27 May 2008 20:45:11 BST."
<D03E4899F2FB3D4C8464E8C76B3B68B00295E64E@E03MVC4-UKBR.domain1.systemhost.net>
From: Valdis.Kletnieks@vt.edu
Date: Tue, 27 May 2008 16:43:11 -0400
Cc: nanog@merit.edu
Errors-To: nanog-bounces@nanog.org
--==_Exmh_1211920991_3133P
Content-Type: text/plain; charset=us-ascii
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...)
--==_Exmh_1211920991_3133P
Content-Type: application/pgp-signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Exmh version 2.5 07/13/2001
iD8DBQFIPHJfcC3lWbTT17ARApdhAKChPbRY8MV+V/hxqjPAlrC0mdkwYwCfVIJk
XDaBc/+VNWiy2HWyIrbL0oY=
=m+oa
-----END PGP SIGNATURE-----
--==_Exmh_1211920991_3133P--
