Message-ID: <3E3C0DAB.5060106@thievco.com>
From: BlueBoar at thievco.com (Blue Boar)
Subject: interesting?

batz wrote:
> According to the analysis posted to NANOG by a number of
> researchers (http://www.caida.org/analysis/security/sapphire/), 
> It infected the majority of hosts within the first 10 minutes. 
>>From the introduction:
> "The Sapphire Worm was the fastest computer worm in history. 
> As it began spreading throughout the Internet, it doubled in 
> size every 8.5 seconds. It infected more than 90 percent of 
> vulnerable hosts within 10 minutes. " 

I read one report somewhere that there were around 120,000 hosts infected. 
  That's about 2^17, which means it would only have had to double 17 times. 
  At 8.5 seconds per doubling, that's only 144.5 seconds, or 2.4 minutes. 
It can't have been an exponential curve the whole time.

> 
> The paper goes on a few paragraphs down to talk about how both Code Red
> and Sapphire used a strategy based upon "random scanning", a feature
> of which is that they spread exponentially rapidly.  

I don't think I've ever seen a worm that didn't have an exponential curve 
for at least part of it's early lifetime.

> So let me get this straight. You release a peice of _randomly_ self 
> propagating code into a networked system, and despite its randomness
> (or limited randomness in the case of sapphire) it still manages
> to cover %90 of possible targets in its first 10 minutes of existence. 

Well, let's look at some theoretical numbers and see how impressive it is 
(I'm still impressed.)

According to:
http://www.isc.org/ds/WWW-200207/index.html
There were around 162,128,493 IP addresses on the Internet.  This isn't 
totally accurate of course, but lets assume it's within an order of 
magnitude.  Also assume that the 120,000 infected hosts is about right. 
That means that 1 in 1,351 was infected (give or take an order of 
magnitude, unfortunately.)

Pick an average wire speed, say 1mbps.  The worm is 418 bytes on the wire 
with typical MAC, IP and UDP headers, or 4433 bits.  That comes out to 300 
worms/second leaving an infected box.

So, here's a perfect infection rate, with every copy of the worm hitting a 
vulnerable box, no processing delays, etc...

At beat 1, the box 1 infects box 2 (2 boxes infected).  At beat 2, box 1 & 
2 infect 3 and 4 (4 boxes infected), at beat 3 boxes 1, 2, 3, & 4 infect 5, 
6, 7, & 8 (8 boxes infected), i.e. a base 2 exponential growth.  It takes 
17 beats to get all hosts.  At 1/300 seconds per beat, That's obviously a 
very short period of time.  If you want to assume some delays, say 1 second 
per infection, then call it 17 seconds.

Alternately, lets give the worm normal chances, which would be 1 in 1,351 
(if it had a way to only hit live hosts).  So at 300 worms/s it takes 4.5 
seconds to get a hit (or half that time, on average.)  Times 17 is about 
76.5 seconds.

More realisticly, and matching closer to what Sapphire actually does, Let's 
take the entire IP address range, 2^32, and divide by 2^17, which comes out 
to 2^15, or 32,768.  That's 109 seconds per beat at 32,758 * 1/300s.  17 
beats comes out to 1853 seconds, or about 30.8 minutes.

A better algorithm is to leave out known-bad parts of address space, 
including the RFC1918 address, and especially the multicast address space. 
    His will knock a couple of bits off.  Some worms do exactly that, 
sapphire does not.  Some worms even have a list of first octets to use.  It 
wouldn't be terribly difficult to take the BGP tables, do a little 
supernetting, and use that.

So, if this worm did better than 30 minutes, it's beating the worst case. 
The average case is 15 minutes, which is about what happened, yes?

Ideal case is only seconds, though.

Interestingly, I think it would have worked to send Sapphire to broadcast 
addresses.  I wonder how often that happened at random?  I.e. hit 
192.168.1.255, and get a hundred hosts in one shot.

> 
> I can't be the only one who saw this and wondered whether it 
> was a feature of networks, as logical entities, that allowed 
> for something that randomly picked targets to cover so much
> ground so quickly. 

There are optimizations, but it's not a bad strategy.

> 
> This seems important is because it shows that a high rate
> of saturation can be achieved among network nodes as
> effectively (if not more so) using random distribution, as by 
> using a structured or hierarchical distribution strategy. 
> 
> An example of a structured strategy would be, choosing 
> aggregation points and going ISP by ISP, subnet by subnet, 
> or contiguously host by host. 

I think your conclusion could be wrong, but I'd have to think up some way 
to factor in communications overhead for coordination to be able to tell.

The REAL reason this thing spread so fast is because it fits in a tiny UDP 
packet, is fire-and-forget, and does absoltely nothing but send copies of 
itself.

Nimda is positively massive by comparison, so I'll look at CodeRed for 
comparison.  Assume some average Internet latency, say 100ms, and no 
processing time.  TCP has to handshake, so that's 200ms right there. 
CodeRed I is about 4100 bytes on the wire, so it will take several packets. 
  I believe Windows has a default recv window of two packets.  So there 
will be another couple of round-trips for ACKs.  You talking around half a 
second to deliver CodeRed I, compare to close to 0 for Sapphire.  CodeRed 
has a bunch more logic and limiters as well, so it's just slower (if memory 
serves, it was only willing to have 200-600 requests outstanding at any 
given time.)

					BB

P.S. A security mailing list or lists is probably the closest thing to a 
list of "infectable hosts" for security advisories.

Powered by blists - more mailing lists