Return-Path: <sentto-279987-1619-998049260-fc=all.net@returns.onelist.com> Delivered-To: fc@all.net Received: from 204.181.12.215 by localhost with POP3 (fetchmail-5.1.0) for fc@localhost (single-drop); Fri, 17 Aug 2001 04:55:07 -0700 (PDT) Received: (qmail 15075 invoked by uid 510); 17 Aug 2001 11:54:42 -0000 Received: from n21.groups.yahoo.com (216.115.96.71) by 204.181.12.215 with SMTP; 17 Aug 2001 11:54:42 -0000 X-eGroups-Return: sentto-279987-1619-998049260-fc=all.net@returns.onelist.com Received: from [10.1.4.55] by ci.egroups.com with NNFMP; 17 Aug 2001 11:54:20 -0000 X-Sender: ellisd@cs.ucsb.edu X-Apparently-To: iwar@yahoogroups.com Received: (EGP: mail-7_3_1); 17 Aug 2001 11:54:19 -0000 Received: (qmail 21731 invoked from network); 17 Aug 2001 11:54:19 -0000 Received: from unknown (10.1.10.26) by l9.egroups.com with QMQP; 17 Aug 2001 11:54:19 -0000 Received: from unknown (HELO n27.groups.yahoo.com) (10.1.2.135) by mta1 with SMTP; 17 Aug 2001 11:54:19 -0000 X-eGroups-Return: ellisd@cs.ucsb.edu Received: from [10.1.2.101] by fh.egroups.com with NNFMP; 17 Aug 2001 11:54:19 -0000 To: iwar@yahoogroups.com Message-ID: <9lj0la+37hb@eGroups.com> User-Agent: eGroups-EW/0.82 X-Mailer: eGroups Message Poster X-Originating-IP: 128.29.4.2 From: ellisd@cs.ucsb.edu Mailing-List: list iwar@yahoogroups.com; contact iwar-owner@yahoogroups.com Delivered-To: mailing list iwar@yahoogroups.com Precedence: bulk List-Unsubscribe: <mailto:iwar-unsubscribe@yahoogroups.com> Date: Fri, 17 Aug 2001 11:54:18 -0000 Reply-To: iwar@yahoogroups.com Subject: [iwar] Worm Ideas Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit The following two sites have proposed worms that I find very interesting. I still think the worms that are proposed here are somewhat limited in scope. The text for each follows the link. http://www.cs.berkeley.edu/~nweaver/warhol.html A Warhol Worm: An Internet plague in 15 minutes! by Nicholas C Weaver (nweaver@cs.berkeley.edu) The following is an analysis of a worst case virulence for a computer worm, using existing mechanisms and a modified infection strategy. Such a "Warhol Worm" could infect every vulnerable machine in a 15 minute time period, outpacing human defense. It is important to understand the possible threat, in order to develop better defenses. "In the future, everybody will have 15 minutes of fame" -Andy Warhol The recent outbreak of the Code Red active worm has demonstrated how vulnerable our infrastructure is. But the worm could have been a thousand times worse. It could have contained a malicious payload: corrupting data, reflashing BIOSes, and potentially destroying machines. It could have included attacks for different servers, or a secondary email component, to increase its reach. But although it was fast, the 12 hours it took to reach epidemic levels still allows for an organized response. But by simply changing the infection pattern, it is possible for a malicious programmer to build a "Warhol Worm", able to attack all vulnerable machines, worldwide, in 15 minutes. A reactive, human defense would fail before such an onslaught. It is an important exercise to realize just how vulnerable we are. An active worm such as Code Red or the original Morris worm takes advantage of a security hole in a server. It scans through the Internet, looking for machines running that service. Then it tries to break into that service. If successful, it infects the target machine with another copy of itself. Over a period of several hours, it goes from an initial machine to Internet wide contamination. The difference between an active worm and a Warhol worm is minor, just a different strategy of choosing hosts to infect. There are 4 billion Internet addresses, and let us assume that 1 million machines are vulnerable a particular Warhol Worm. Assume that the worm is under 100k in size and is multithreaded, allowing it to probe and attack many machines simultaneously. Further assume that the targeted servers have good network connections, allowing a running copy of the worm to scan 100 machines per second, probe and infect 10 machines per second, and it takes 1 second to actually transfer over the worm to a new target. Finally, assume that a Warhol Worm author has planned ahead and quietly constructed a list of 50,000 computers with good network connections and a running copy of the targeted server, of which an unknown 25% are actually infectible by the worm. The worm starts out on a single machine, with its list of 50,000 targets. The worm goes through the list in order, and probes and infects the machines. When it successfully takes over another machine, it divides the list in half, sends half over to the newly infected machine and keeps the other half. This quick division of labor allows the worm to infect every vulnerable machine on the list in under a minute. Now roughly 12,000 machines will be infected, and the second stage begins. The worm first attempts to infect all the hosts on its subnet, before beginning to choose new targets in the general Internet. But instead of just picking random machines, or scanning through the net in a linear order, the worms use a pseudo-random order. A Warhol worm contains a generator for a pseudo-random permutation of all 4 billion Internet addresses. Each worm infected during the hitlist phase starts at its address and goes through the permutation, looking for new targets to infect, while each worm infected during the second phase starts at a random location. If it finds another copy of itself running, it picks a new, random address and starts from there. This will have the worm behave with both the features of a random probe (scattering through the net) and a sequential probe (minimizing duplication of effort and guaranteeing that the entire Internet will be efficiently scanned). Even if the worms did not infect any other machines during this phase, they would take about 50-100 hours to scan the entire internet at 100 scans/machine/second. If the computers on the hit list are chosen for speed and connectivity, this would be significantly lower. But with 1 million vulnerable machines, any given scan and probe has a .025% chance of being a vulnerable machine. Thus, with the 1.2 million scans per second the initial worms send out, 300 will reveal new targets. By the second minute after release, the worm will have infected a total of 30,000 machines. After the third minute, there will be over 70,000 infected machines. It becomes quite obvious that complete infection will be achieved within the 15 minute timeframe. Normally, once a worm which uses random probes infects about 1/2 of the available hosts, the rate of new infections slows down considerably. A fully coordinated worm, where the tasks of scanning the internet are perfectly divided, will only slow down once every target is infected. The pseudo random/random combination is a compromise, allowing the worm to do a comprehensive scan of the internet without relying on transmitting information between worms, just the ability to check to see if a potential target is already infected. The Internet will slow down during this process, but not as much as may be expected. With only a few bytes to scan a target to see if a server is running, roughly 5k to infect a target, and 100k to transfer on successful infection, the amount of data involved is surprisingly small: Even at the peak of infection with a million infested machines, this represents only a hundred million scans per second worldwide, a network load not significantly higher than Code Red employed. There is no current defense against a malicious Warhol worm. The author of a Warhol worm could easily cause hundreds of billions in real damage, through corrupted data, destroyed machines, and lost time. By the time the world realizes what is happening, all the damage would be done. Appendix 1: Justification of assumptions 100k worm size: 100 kilobytes of data is a reasonable size for a worm: It is sufficient for the infection code and a small but effective malicious payload. With some patience and cleverness, the size could probably be reduced to 50k or less. 100 scans/second: Scanning a single machine to see if it is running the vulnerable service requires only about a kilobit of data to be sent and received, this only requires about a 100kbps link for each active worm. Since server machines targeted by active worms tend to have good network, this is easily achievable. Many machines should be capable of 1000 scans per second. 10 attacks/second: 10 attacks per second requires transfering the whole worm over. For servers, 1 megabyte/second of data is a little high for some but many machines do have that level of bandwidth. A lower limit of one attack per second would still be sufficient, as it would only slow the initial phase of expansion, perhaps to slightly more than a minute. During the second phase, infection rates are limited by the rate of probing, not the rate of attacking. 1 second to infect a machine: Taking over and infecting a machine requires that the probe be successful, the worm transfered over, and the worm to start running. Since the worm is only 100k, this can easily be accomplished in a second for machines connected through broadband links. Note that a latency of several seconds will not significantly slow down the propagation during the permutation scanning phase, but only slows down the hitlist phase. 1M vulnerable hosts: Code Red I and II seem to have infected somewhere between 500,000 and 1,000,000 machines on the net. A fewer number of potential hosts would slow down the rate of infection slightly, but even with only 500,000 vulnerable machines, the spread would still take roughly 15 minutes: it would double every 2 minutes instead of every minute, until all vulnerable machines are infected. Initial hit list scan: The initial hit-list scan is a slow scan which is done in advance, just to determine a set of potentially vulnerable machines. In the case of a web server, a simple web-crawler could be used. For a different service, another form of scanner. Such scans, since they only are used to detect the program running, not the existence of the vulnerability, can be done weeks in advance and would not attract notice. Much of the information may already be publicly available. In practice, it would be very hard to detect and trace the scan used to create such a hitlist. The Honeynet project has revealed just how many scans occur all the time. A slow, advanced scan just to determine the version of a web-server and its response time would be nearly undetectable amid all the noise generated by script kiddies. Also, the hitlist can be created long before an actual vulnerability is discovered. The attacker simply collects a catalog of machines running potential targeted services, and constructs the worm with the exception of the actual exploitation code. Once an exploit is available is the final worm compiled and released, using the premade hitlist. Pseudo random scanning: The pseudo-random-permutation is easy to construct: Just use a 32 bit block cipher and a key selected in advance. To generate the Nth entry in the permutation, just encrypt N. To get the index of a given machine K, just decrypt K. This does result in some redundancy in scanning, as multiple worms may probe a range in the permutation until an already infected machine is found. However, this is a comparatively minor loss, and the rapid expansion of the worm will cause a loss in efficiency, this is a comparatively minor loss. Complete efficiency of scanning could be accomplished by having the worms communicate with each other. Such communication would make such a worm even more virulent, possibly allowing complete infection in 5 minutes. Normally, a worm like Code Red has its infection rate start to slow as it reaches saturation, as random probing becomes less effective. Because this combines the effects of random and comprehensive probes, the rate stay higher, longer. Coordinated worms, and worms which exploit the structure of the net in dividing the workload, would be even faster. The point of this exercise, however, is to show that even very simple modifications to random infection strategies can produce super virulence. Once you get a worm which propagates in under an hour, what difference is there between 5 minutes and 15? Appendix 2: Possible defenses Unfortunately, Warhol worms are very fast, so human mediated defenses fail. A transition to IPv6 would work wonders, since it eliminates the random probing as a viable means of finding new hosts. Short of that, more variation in applications, so individual flaws would affect fewer hosts would help, since fewer vulnerable machines will slow the spread of such worms. Getting programmers to write their servers in bounds checked languages would help, as this would eliminate roughly half of the security flaws. But it isn't a panacea, there is nothing in a Warhol worm which requires that the exploit used be a buffer overflow. One factor which may slow the spread is the ability for routers to process ARP requests. This will result in the effects of network congestion for the worm, which will slow the spread. I have no current estimates on how much this will affect things. Thanks to Michael Constant for his assistance in helping design the strategies used by such a worm. I am currently writing an abstract simulator to model the virulence of an abstract Warhol Worm for various parameters. I AM NOT, AND WILL NOT, EVER WRITE SUCH A WORM! "I have no need to destroy things, just to prove a point" My math is deliberately sloppy when it comes to evaluating the point where the geometric growth slows down. But the simulator confirms these times. I will be releasing initial code for the simulator in a couple of days, as well as data runs, but initial results say that it takes roughly 7 minutes and 30 seconds for 1M vulnerable hosts, 12 minutes and 45 seconds if there are only 500k potential hosts in the network, as expected. Why I'm keeping this page up! Unfortunately, the results are too simple: Any reasonably intelligent programmer who thinks about the problem will come up with a similar solution, or a coordinated worm which efficiently divides the search space. Coordinated worms are even faster but do require a level of worm to worm communication. The point of this was to just demonstrate that coordinated worms are NOT a prerequisite for truly fast propagation. Secondly, the current worms, taking 12 hours to a day, are still fast enough to foil most human reaction: Look at the continued spread of the code red variants, roughly 3 weeks after initial infection. Changing this to under an hour would only slightly increase the reach in the current environment. Finally, I am a personal believer in the doctrine of full disclosure, especially when the "bad guys" (skilled, malicious programmers) could easily come up with the same results without documentation. It is important for the rest of us to consider and evaluate what the realistic threat is. Saying nothing would help nobody. We have always known, even before the Morris worm, that connected, homogeneous computer networks are vulnerable to fast moving, active worms. This, however, is an important result because it is a reminder of just HOW vulnerable it is. Human mediated defenses can not stop a fast active worm. I will not remove this page. Copyright 2001 by Nicholas C Weaver, nweaver@cs.berkeley.edu. It may be reproduced only in its entirety and with credit to its author. The term "Warhol Worm" is an original term coined by the author. If you mirror this article, please let me know where it is and from where you got it. I am interested in how this article gets spread around. *************************************************************** http://www.silicondefense.com/flash/ Stuart Staniford, Gary Grim, Roelof Jonkman, Silicon Defense, 8/16/2001 In a recent very ingenious analysis, Nick Weaver at UC Berkeley proposed the possibility of a Warhol Worm that could spread across the Internet and infect all vulnerable servers in less than 15 minutes (much faster than the hours or days seen in Worm infections to date, such as Code Red). In this note, we observe that there is a variant of the Warhol strategy that could plausibly be used and that could result in all vulnerable servers on the Internet being infected in less than thirty seconds (possibly significantly less). We refer to this as a Flash Worm, or flash infection. We have run out of hyberbolic adjectives to describe how seriously vulnerable the Internet is to security disruptions, so we won't comment further on the social implications of this. The recent Code Red worm operated by probing random addresses on the Internet in the CRv2 version. The later Code Red II worm used a mixture of random probing of local subnets, and probing the entire Internet randomly. The Warhol worm would first use a list of 50,000 or so sites to start the infection from (this list would be built by scanning in advance), and then use a clever co-ordinated scanning technique to scan and infect the rest of the Internet. In simulations, Weaver estimated such a worm could infect one million vulnerable servers in significantly less than 15 minutes, using plausible estimates of the scan rate a worm could achieve. The nub of our observation is that it is reasonable to think that a determined attacker could have obtained a list of all or almost all servers with the relevant service open to the Internet in advance of the release of the worm. This could be done in a number of ways: Straight scanning from a single site For the well funded three-letter agency with an OC12 connection to the Internet, we believe a scan of the entire Internet address space can be conducted in a little less than two hours (we estimate about 750,000 syn packets per second can be fit down the 622Mbps of an OC12, allowing for ATM/AAL framing of the 40 byte TCP segments. The return traffic will be smaller in size than the outbound. Faster links could scan even faster. Distributed scanning For the hacker community, it will be more feasible to scan the Internet from a platform of a few thousand zombies similar to what they have assembled from time-to-time for DDOS attacks. Distributed scanning has been seen in the wild. 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 scans (but see Spade/Spice). DNS searches Using widely available spam mail lists, a list of domains can be assembled. 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), it would be possible to use web-crawling techniques similar to search engines in order to produce a list of most Internet connected web sites (some sites with no links from other sites would be missed). This would be unlikely to attract serious attention. Given that an attacker has the determination and foresight to assemble a list of all or most Internet connected addresses with the relevant service open, a worm can spread most efficiently by simply attacking addresses on that list. There are about 12 million web servers on the Internet (according to Netcraft), so the size of that particular address list would be 48MB, uncompressed. The initial copy of the worm can be programmed to divide the list into n blocks, and then to find and infect the first address in each block (or an especially chosen high-bandwidth address in that block), and then hand the child worm the list of addresses for that block. That copy of the worm can then re-iterate the process to infect everything in its block. A threaded worm could begin infecting hosts before it had received the full host list from its parent to work on, to maximize the parallelization process, and it could start work on looking for multiple children in parallel. A related design would call for most of the address list to be located in pre-assigned chunks on one or a number of high-bandwidth servers that were well-known to the worm. Each copy of the worm would receive an assignment from its parent, and then fetch the address list from there. This process will result in relatively little wasted effort. For example, if the worm had a list of web servers, and a zero-day IIS vulnerability, about 26% of the list would be vulnerable. No server would be probed twice. If n were 10, then the infection tree for the 3 million vulnerable servers would be just 7 layers deep. The spread rate of such a worm would likely be constrained by one of two things. The worm itself is likely to be small (CRv2 was about 4k, and the hypothetical Warhol worm is 100K to allow for more malicious payload code). Thus the address list is much larger than the worm itself at the start of the list. Thus the propagation of the worm could literally be limited by the time required to transmit the host list out of the initial infection site or servers were it was stored. Since all the children of the infection will have much smaller lists to transmit, they are less likely to limit the worm spread (unless a first generation child has less than 1/n of the initial copy's bandwidth available to it). The exact time required to transmit the list will depend on the bandwidth of the storage sites, and the amount of traffic there. For some examples, however, we point out that the 48MB of address list could be pushed down an otherwise empty T1 line in just over 4 minutes. It could be pushed down an OC12 link in less than a second. Thus starting the worm on a high-bandwidth link is desirable for the attacker, and bandwidth is probably a concern at the next layer also. Compression of the list could make the list delivery much faster. The other possible limitation is simply the latency required to infect each new layer in the tree. Given that probes can be issued in parallel, and substantially more threads can be spawned than n (the number of children), we do not have to add up the time required for a given copy to cycle through its list, but simply take the maximum infection latency. Weaver hypothesizes 1 second for this latency, but with an n=10, it perhaps might take a little longer to get 10 copies of the worm through a given sites link. However, not much longer - if a 5KB worm can get 50% utilization through a 256k DSL uplink, it can transmit ten copies of itself in three seconds. That leads to a sub thirty second limit on the total infection time (given an infection tree seven layers deep and a design were the new worm children go to a server for their addresses). In conclusion, we argue that a small worm that begins with a list including all likely vulnerable addresses, and that has initial knowledge of some vulnerable sites with high-bandwidth links, can infect almost all vulnerable servers on the Internet in less than thirty seconds. Acknowledgements: We thank Nick Weaver at UC Berkeley and Vern Paxson at the AT&T Center for Internet Research for a very helpful discussion of these ideas. ------------------------ Yahoo! Groups Sponsor ---------------------~--> Get VeriSign's FREE GUIDE: "Securing Your Web Site for Business." Learn about using SSL for serious online security. Click Here! http://us.click.yahoo.com/KYe3qC/I56CAA/yigFAA/kgFolB/TM ---------------------------------------------------------------------~-> ------------------ http://all.net/ Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
This archive was generated by hypermail 2.1.2 : 2001-09-29 21:08:39 PDT