Onset of nimda ing, if it receives the right trigger, or a prearranged time rolls around. We return to this point in Section 7 4“ Better” worms-theor g 8 There are several techniques which, although not yet em- ployed, could further significantly increase the virulence of a worm. Beyond the obvious factors of discover- ing more widespread security holes and increasing the canning rate, some additional strategies a worm author could employ are:() hit-list scanning, (ii)permutation scanning,(iii)topologically aware worms, and (iv)In- ternet scale hit-lists. The goal is very rapid infection-in particular, considerably faster than any possible human- 06.5 A worm's scanner can obviously be made significantly Time(PDt)18 September, 2001 faster than the ones seen today by careful use of thread- ing and an understanding of the protocols. By having Figure 5: Http connections per second seen at the many requests outstanding a worm should be capable Lawrence Berkeley National Laboratory rising due to the on- of scanning targets at a rate proportional to its access set of Nimda, September 18 bandwidth. Since it only takes 40 bytes for a TCP SYN packet to determine if a service is accessible, and often only a few hundred bytes to attempt an exploit, the po- Figure 5 illustrates how rapidly the worm tried to in- tential scans per second can easily exceed 100 for even fect one site, the Lawrence Berkeley National Labora- poor Internet connections. This increases K by allow- tory. The T-axis plots hours past midnight, PDT, while ing a worm to search for a greater number of targets in a the y-axis plots Http connection attempts per second given period of time Only connections from hosts confirmed to have harbored Nimda are counted, to avoid possible confusion with Similarly, the more widespread the vulnerable software concurrent Code Red connection attempts. After the on- is, the faster a worm using that vulnerability can sprea set of the infection, the total rate of probing was about because each random scan of the network is more likely 3 times that from the hosts subsequently confirmed to to pick up a target, also increasing K. We should there- harbor nimda fore expect that worm authors will devote considerable scrutiny to highly homogeneous, highly deployed ser Clearly, onset was quite rapid, rising in just half an hour vices, both for the faster spreading and for the greater from essentially no probing to a sustained rate of nearly number of machines that could be compromised in a sin- 100 probes/sec There is an additional synergy in Nimda's use of mul- tiple infection vectors: many firewalls allow mail to 4.1 Hit-list Scanning pass untouched, relying on the mail servers to re- move pathogens. Yet since many mail servers remove pathogens based on signatures, they arent effective dur- One of the biggest problems a worm faces in achieving ing the first few minutes to hours of an outbreak, giving a very rapid rate of infection is"getting off the ground Nimda a reasonably effective means of crossing firewalls Although a worm spreads exponentially during the early to invade internal networks stages of infection, the time needed to infect say the first 10.000 hosts dominates the infection time. as can be seen Finally, we note that Nimda's full functionality is still in Figure 3 not known: all that is known is how it spreads, but not what it might be capable of doing in addition to spre There is a simple way for an active worm to overcome
Onset of NIMDA Time (PDT) 18 September, 2001 C onn / Sec 6.0 6.5 7.0 7.5 8.0 0 20 4 0 6 0 80 10 0 120 14 0 C o n n e ctio ns/S e c o n d Figure 5: HTTP connections per second seen at the Lawrence Berkeley National Laboratory, rising due to the onset of Nimda, September 18. Figure 5 illustrates how rapidly the worm tried to infect one site, the Lawrence Berkeley National Laboratory. The x-axis plots hours past midnight, PDT, while the y-axis plots HTTP connection attempts per second. Only connections from hosts confirmed to have harbored Nimda are counted, to avoid possible confusion with concurrent Code Red connection attempts. After the onset of the infection, the total rate of probing was about 3 times that from the hosts subsequently confirmed to harbor Nimda. Clearly, onset was quite rapid, rising in just half an hour from essentially no probing to a sustained rate of nearly 100 probes/sec. There is an additional synergy in Nimda’s use of multiple infection vectors: many firewalls allow mail to pass untouched, relying on the mail servers to remove pathogens. Yet since many mail servers remove pathogens based on signatures, they aren’t effective during the first few minutes to hours of an outbreak, giving Nimda a reasonably effective means of crossing firewalls to invade internal networks. Finally, we note that Nimda’s full functionality is still not known: all that is known is how it spreads, but not what it might be capable of doing in addition to spreading, if it receives the right trigger, or a prearranged time rolls around. We return to this point in Section 7. 4 “Better” worms—theory There are several techniques which, although not yet employed, could further significantly increase the virulence of a worm. Beyond the obvious factors of discovering more widespread security holes and increasing the scanning rate, some additional strategies a worm author could employ are: (i) hit-list scanning, (ii) permutation scanning, (iii) topologically aware worms, and (iv) Internet scale hit-lists. The goal is very rapid infection—in particular, considerably faster than any possible humanmediated response. A worm’s scanner can obviously be made significantly faster than the ones seen today, by careful use of threading and an understanding of the protocols. By having many requests outstanding, a worm should be capable of scanning targets at a rate proportional to its access bandwidth. Since it only takes 40 bytes for a TCP SYN packet to determine if a service is accessible, and often only a few hundred bytes to attempt an exploit, the potential scans per second can easily exceed 100 for even poor Internet connections. This increases K by allowing a worm to search for a greater number of targets in a given period of time. Similarly, the more widespread the vulnerable software is, the faster a worm using that vulnerability can spread, because each random scan of the network is more likely to pick up a target, also increasing K. We should therefore expect that worm authors will devote considerable scrutiny to highly homogeneous, highly deployed services, both for the faster spreading and for the greater number of machines that could be compromised in a single attack. 4.1 Hit-list Scanning One of the biggest problems a worm faces in achieving a very rapid rate of infection is “getting off the ground.” Although a worm spreads exponentially during the early stages of infection, the time needed to infect say the first 10,000 hosts dominates the infection time, as can be seen in Figure 3. There is a simple way for an active worm to overcome
this obstacle, which we term hit-list scanning. Before gines in order to produce a list of most Internet the worm is released the worm author collects a list of connected Web sites. This would be unlikely to at say 10,000 to 50,000 potentially vulnerable machines tract serious attention ideally ones with good network connections. The worm, when released onto an initial machine on this hit-list be-. Public For many potential targets there gins scanning down the list. When it infects a machine, available listing them, such as the it divides the hit-list in half, communicating half to the Ne02] recipient worm, keeping the other half. Just listen. Some applications, such as peer-to- This quick division ensures that even if only 10-20%of peer networks, wind up advertising many of their the machines on the hit-list are actually vulnerable, an servers. Similarly, many previous worms effec- active worm will quickly go through the hit-list and tively broadcast that the infected machine is vul tablish itself on all vulnerable machines in only a few nerable to further attack. For example, because of seconds. Although the hit-list may start at 200 kilo- its widespread scanning, during the Code Red I in- bytes, it quickly shrinks to nothing during the partition fection it was easy to pick up the addresses of up- ing. This provides a great benefit in constructing a fast wards of 300.000 vulnerable IIs servers-because worm by speeding the initial infection. each one came knocking on everyones door Indeed, some individuals produced active counter The hit-list neednt be perfect: a simple list of machines measures to Code red ll by exploiting this obser- running a particular server type may suffice, although vation. when combined with the backdoor which greater accuracy will improve the spread. The hit-list Code red ll installs [ DAol. However, it is not a itself can be generated using one or several of the fol- given that future worms will broadcast their pres- lowing techniques, prepared well in advance, generally ence, and we also note that worms could readily fix with little fear of detection the very security holes they exploit(such as is often already observed for attackers performing break Stealthy scans. Portscans are so common and ins manually ) which undermines the superficially widely ignored that even a fast scan of the entire ppealing countermeasure of using the worms vec- Internet would be unlikely to attract law enforce- tor as a means by which to disable it ment attention or more than mild comment in the incident response community. However, for attack ers wishing to be especially careful, a randomized 4.2 Permutation Scanning ealthy scan taking several months would be ver unlikely to attract much attention, as most intrusion detection systems are not currently capable of de- Another limitation to very fast infection is the general tecting such low-profile scans. Some portion of the inefficiency of random scanning: many addresses scan would be out of date by the time it was used probed multiple times. Similarly there is no means for a but much of it would not randomly scanning worm to effectively determine when all vulnerable machines are infected Permutation scan- Distributed scanning. An attacker could scan the ning solves these problems by assuming that a worm can Internet using a few dozen to a few thousand detect that a particular target is already infected Iready-compromised"zombies, similar to what DDOS attackers assemble in a fairly routine fash- In a permutation scan, all worms share a common ion. Such distributed scanning has already been pseudo random permutation of the IP address space seen in the wild-Lawrence Berkeley National Such a permutation can be efficiently generate aboratory received 10 during the past year a 32-bit block cipher and a preselected key: simply en- DNS searches. Assemble a list of domains(for ex- crypt an index to get the corresponding address in the mple, by using widely available spam mail lists, or permutation, and decrypt an address to get its index. trolling the address registries). The DNS can then be searched for the IP addresses of mail-servers Any machines infected during the hit-list phase(or lo- ia MX records) or Web servers(by looking for cal subnet scanning) start scanning just after their point in the permutation, working their way through the per mutation, looking for vulnerable machines. Whenever Spiders. For Web server worms(like Code red), the worm sees an already infected machine, it chooses a use Web-crawling techniques similar to search en- new, random start point and proceeds from there. Worn
this obstacle, which we term hit-list scanning. Before the worm is released, the worm author collects a list of say 10,000 to 50,000 potentially vulnerable machines, ideally ones with good network connections. The worm, when released onto an initial machine on this hit-list, begins scanning down the list. When it infects a machine, it divides the hit-list in half, communicating half to the recipient worm, keeping the other half. This quick division ensures that even if only 10–20% of the machines on the hit-list are actually vulnerable, an active worm will quickly go through the hit-list and establish itself on all vulnerable machines in only a few seconds. Although the hit-list may start at 200 kilobytes, it quickly shrinks to nothing during the partitioning. This provides a great benefit in constructing a fast worm by speeding the initial infection. The hit-list needn’t be perfect: a simple list of machines running a particular server type may suffice, although greater accuracy will improve the spread. The hit-list itself can be generated using one or several of the following techniques, prepared well in advance, generally with little fear of detection. • Stealthy scans. Portscans are so common and so widely ignored that even a fast scan of the entire Internet would be unlikely to attract law enforcement attention or more than mild comment in the incident response community. However, for attackers wishing to be especially careful, a randomized stealthy scan taking several months would be very unlikely to attract much attention, as most intrusion detection systems are not currently capable of detecting such low-profile scans. Some portion of the scan would be out of date by the time it was used, but much of it would not. • Distributed scanning. An attacker could scan the Internet using a few dozen to a few thousand already-compromised “zombies,” similar to what DDOS attackers assemble in a fairly routine fashion. Such distributed scanning has already been seen in the wild—Lawrence Berkeley National Laboratory received 10 during the past year. • DNS searches. Assemble a list of domains (for example, by using widely available spam mail lists, or trolling the address registries). The DNS can then be searched for the IP addresses of mail-servers (via MX records) or Web servers (by looking for www.domain.com). • Spiders. For Web server worms (like Code Red), use Web-crawling techniques similar to search engines in order to produce a list of most Internetconnected Web sites. This would be unlikely to attract serious attention. • Public surveys. For many potential targets there may be surveys available listing them, such as the Netcraft survey [Ne02]. • Just listen. Some applications, such as peer-topeer networks, wind up advertising many of their servers. Similarly, many previous worms effectively broadcast that the infected machine is vulnerable to further attack. For example, because of its widespread scanning, during the Code Red I infection it was easy to pick up the addresses of upwards of 300,000 vulnerable IIS servers—because each one came knocking on everyone’s door! Indeed, some individuals produced active countermeasures to Code Red II by exploiting this observation, when combined with the backdoor which Code Red II installs [DA01]. However, it is not a given that future worms will broadcast their presence, and we also note that worms could readily fix the very security holes they exploit (such as is often already observed for attackers performing breakins manually), which undermines the superficially appealing countermeasure of using the worm’s vector as a means by which to disable it. 4.2 Permutation Scanning Another limitation to very fast infection is the general inefficiency of random scanning: many addresses are probed multiple times. Similarly there is no means for a randomly scanning worm to effectively determine when all vulnerable machines are infected. Permutation scanning solves these problems by assuming that a worm can detect that a particular target is already infected. In a permutation scan, all worms share a common pseudo random permutation of the IP address space. Such a permutation can be efficiently generated using a 32-bit block cipher and a preselected key: simply encrypt an index to get the corresponding address in the permutation, and decrypt an address to get its index. Any machines infected during the hit-list phase (or local subnet scanning) start scanning just after their point in the permutation, working their way through the permutation, looking for vulnerable machines. Whenever the worm sees an already infected machine, it chooses a new, random start point and proceeds from there. Worms