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

["Fred Reimer" <freimer () ctiusa com>]

The conversation shifted to breaking MD5 because it was mentioned that one
way to prevent the installation of cracked IOS images was to include some
sort of DRM or trusted computing chip in new hardware, and have Cisco sign
their IOS images (supposedly even the boot EEPROM).  This wouldn't be DRM in
the sense of DVD's, where they don't want everyone to be able to decode the
disk, so must come up with some scheme where they provide the decryption key
that is itself decrypted with a private key which all of the DVD players
have the public key for, hence could be relatively easily broken (just
extract the public key from the player, which was what was done for HD-DVD.
In other words, attacking the crypto scheme instead of the algorithm.  Cisco
would presumably want everyone to be able to read the file, just sign it
with their private key.  So how do you sign an IOS image?  Most crypto
schemes work by generating a MD5 hash of the data, and then signing the MD5
hash, not signing the whole IOS image, which would be encrypting the whole
thing.  Decrypting an IOS image sized data block with the RSA algorithm
would presumably take too long, so just the hash is signed.  If the signed
hash matches the hash you compute when loading the image it's a good image,
so the boot ROM would load the code.  Once loaded, it would check the
signature (of the hash) on any new boot ROM loaded so that attackers could
not use that vector.

For what it's worth, encrypting the whole file is still not normally done by
encrypting with the RSA public key of the destination.  Rather, another
symmetric protocol is used, such as 3DES or IDEA or something, and they key
for that protocol is encrypted with RSA.  The private key in this case would
be located... on the new Cisco hardware.  So, much like breaking HD-DVD
crypto scheme this could be broken also.  However, I don't think it is the
goal to encrypt the IOS code, just ensure that it is valid code from Cisco,
so an appropriate hash should do just fine.

So the only easy way to attack this is the MD5 hash.  We have a know
plaintext (the IOS code) and the hash.  It is not trivial to be able to make
changes in the code and maintain the same hash value, but there has been at
least limited success in doing so.  If they can change the code and fiddle
with the help text in some obscure feature no one regularly uses and
generate the same hash then viola, access.

That's how we got onto breaking MD5.

However, if there is a known vulnerability, to however few people, in IOS
where there is a buffer overflow or something else where remote code can be
executed, this presumably could overwrite the IOS code running on the box
and bypass the code-checking hardware.  It may not be possible to replace
the boot ROM, because presumably the new hardware would check the ROM code
hash before loading it and also presumably the ROM code does not have quite
as much text messages that can be changed to generate the same hash value,
thereby bypassing the security checks.  So in this scenario rooted IOS would
only exist transiently; a reboot would load the known good code again (or
brick the box if "bad" ROMMON were burned).


Fred Reimer, CISSP, CCNP, CQS-VPN, CQS-ISS
Senior Network Engineer
Coleman Technologies, Inc.
954-298-1697

> -----Original Message-----
> From: Gadi Evron [mailto:ge () linuxbox org]
> Sent: Thursday, May 29, 2008 12:21 AM
> To: Steven M. Bellovin
> Cc: nanog () nanog org
> Subject: Re: IOS Rookit: the sky isn't falling (yet)
>
> On Thu, 29 May 2008, Steven M. Bellovin wrote:
> > On Wed, 28 May 2008 10:37:05 +0100
> > <michael.dillon () bt com> wrote:
> >
> > > > 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.
> > >
> > > I didn't say that. I said that they are starting with an IOS image
> > > in which there are some small number of bytes which they can
> possibly
> > > change and still have a functional image. So it is likely that they
> > > will brute force that by computing an MD5 hash on all variations of
> > > those few bytes. It's like winning the lottery, you only *NEED* to
> > > buy one ticket. No matter how slim the chances are of bad guys
> winning
> > > that lottery, it is no excuse for ignoring the possibility that an
> > > MD5 hash check may not be proof that you have an original image.
> > Did you even look at Valdis' arithmetic?  It *won't work*.  It isn't
> > "likely" that they'll try anything with that low a chance of success.
> > As for "no matter how slim the chances" -- if you want to have even a
> > vague chance of succeeding before Sol turns into a red giant, you're
> > going to have to devote enormous resources to the project.
> (Actually,
> > I don't think you can succeed even then, not by brute force -- there
> > aren't a "small number of bytes" that can be changed, you can
> introduce
> > "random" "typographical" errors in error messages for the SNA stack
> or
> > some such, and if you're doing a brute force pre-image attack on MD5
> any
> > bit is as good as any other.)  Let's put it purely in economic terms:
> > which is a better way to invest your effort, building a machine (or
> > botnet) with many billions of processors and still having no
> plausible
> > chance of winning, or -- as you yourself suggest -- getting the HVAC
> > contract for the data center.  Or putting back doors in the chips.
> Or
> > bribing or blackmailing coders.  Or breaking into the vault where
> Cisco
> > keeps its master RSA key.  Or funding a vast research effort on
> > cracking MD5 before it's replaced by SHA-512.  Or *something* even
> > vaguely sane, because brute-forcing MD5 isn't physically possible.
>
> I don't understand how this disucssion got to breaking MD5 to begin
> with?
> The whole point was that the results will be manipulated due to the
> rootkit messing with the test, no?
>
>       Gadi.
>
> >             --Steve Bellovin, http://www.cs.columbia.edu/~smb

Attachment: smime.p7s
Description: