Linux administrators see log files full of failed attack attempts when some other platform is subject to a worm attack. Dumb worms might be a nuisance and a waste of bandwidth. But what if worms were a little smarter about which hosts to attack, when to attack and with what exploit? What if a worm developer could update all the running worms, on the fly, with a new exploit?

At South By Southwest, we talked with Brandon Wiley, coordinator of the Tristero project, about the threat of such a "superworm" and what might be done to defend against it. For those of you who didn't make it to South By Southwest, we asked him again.

Would a superworm be significantly harder to build than today's dumb worms, or is a superworm just a regular worm plus a pseudo-random number generator?

Building a superworm would not take much more craft than building a normal worm. The difference is in the cleverness of the design. Normal worms are designed without strategy in mind. Each worm pursues the limited strategy of attempting to reproduce itself immediately as much as possible, with no other considerations. The superworm, on the other hand, is designed to take strategies into account that will allow for the maximum propagation globally even if it means limiting propagation locally. This is similar to the different economic models promoted by Adam Smith vs. John Nash. Coding a worm with intelligence about game theory and a global perspective on achieving an optimal outcome is not much harder in terms of the code, but requires a more carefully thought-out design.

Randomization is one way to handle the division of labor among many worm instances. If you flip a coin to determine whether to propagate or sleep for a turn then worms will at least not be propagating at full throttle. However, randomization does not scale well. Ideally you want to have the probability of propagation for each worm be inversely proportional to the number of worms considering the attack of a particular machine. As the network becomes saturated with worms, the number of contending worms increases. So, ideally, you want to decrease the probability of attack. Unfortunately, this requires that you know the number of contending worms, which means that the worms need to coordinate with each other.

An alternative method to randomization is to divide and conquer the network according to principles similar to distributed hash table (DHT) systems. For instance, if the worms form an Achord network, each worm only has to know about approximately log2 (253^4) other worms and each worm has a portion of the network that it is dedicated to compromising. As new worms join the network, the responsibility is redivided. This way only one worm is ever attacking a particular machine and yet there is a minimal amount of coordination between the worms.

Are propagation strategies that a superworm could use already in the open literature?

Techniques for maintaining DHTs are widely published. There proceedings from the 1st International Peer-to-Peer Symposium (IPTPS) at MIT are about to be published and contain a wealth of information about DHTs. I have a paper on a DHT-based superworm called Curious Yellow that will be available at http://blanu.net/curious_yellow.html within a couple of days. Some very good optimizations for superworms have also been published as thought experiments.

The Warhol worm design suggests pre-scanning the network for vulnerable hosts and compiling a large hitlist. The hitlist is the carried by the initial worm and partitioned as the worms divide and conquer the network. This precompiled hitlist allows for the worm to achieve an initial critical mass of propagation that can then be used as a platform from which to launch large-scale attacks.

The Flash worm design optimizes further on Warhol by compiling a nearly complete list of vulnerable servers rather than just a seed list and hosting the host list on a fast, well-connected server rather than transmitting it along with the worm.

What are the best predictions for how long a superworm would take to make the Internet unusable? Days? Hours?

The estimate mentioned in the Warhol paper was 15 minutes and the estimate in the Flash paper was approximately 30 seconds to infect all known vulnerable hosts. In my estimation, though, this is just for the initial seeding of the network. There are a plethora of hosts that might be unreachable during the initial infection either because they are disconnected, they are behind firewalls, or they are not vulnerable to the attacks that the worm has at its disposal during the initial infection period. A truly advanced worm would use this initial infection as a springboard to reach previously unreachable hosts and wait for code updates that would allow infection of previously invulnerable systems. This second stage of infection could go on indefinitely until all hosts in the world are infected. How long this would take depends on how frequently usable exploits are found for various platforms.

Many Linux users say that the diversity of software and configuration on Linux systems makes them relatively safe from worm attacks even when exploits are discovered. Can a superworm's propagation be smart enough to find rare vulnerable configurations or daemons?

While the overall diversity of hosts helps protect against worms, the diversity found in individual Linux systems will not generally be helpful in protecting against worms. While Linux systems are highly customized, exploits used by worms are generally in a widely used package with a homogeneous codebase, such as sshd, fingerd, or ftpd. While there are a few versions of finger and ftp daemons available now, one daemon implementation generally has the largest market share and thus acts as a propagation vector for the majority of Linux systems. For instance, few people are running customized implementations of the GNOME or KDE daemons. All that is required for a system to be vulnerable is for it to be running a single service which has a published exploit.

Are superworms a threat to well-administered Linux systems? Can a superworm outrace news of the exploit it uses?

The most effective superworm would use drop-in 0 day exploits for propagation. A network could already be in place using a Warhol/Flash-style prescanned hitlist for seeding. When a new exploit is found it could then be sent to the worms already in place. This means that the window in which the administrator can harden his system from the worm is between when the vulnerability is discovered and when the worm author writes the code to exploit it. The distribution network for patches to fix the vulnerability will generally be slower than the worm exploit distribution network, which can propagate patches to all worms in 30 seconds. Hence the only way to be fully protected against the worm is to install software very similar to the worm itself that does quick distribution of security patches. At that point it becomes a race between the authors or exploit code and the authors of security patches.

Since a superworm could help perpetuate itself by DoSing sites that provide worm-fighting software and patches, what can sites that want to help people fight worms, but might be silenced by a worm, do to help their users when the attack comes? Should we be applying superworm math to an emergency superworm warning system?

Since the worm network already moves faster than the patch distribution and warning system, there it would not be worth it to DoS patch sites. It would in fact be a liability as the security site would be able to record the IPs of infected nodes. However, if a threat was ever posed to the worm network, the author would be able to coordinate all of the worms within 30 seconds to take arbitrary action as encoded in patches sent to the entire network. While this could be used to DoS the Pentagon or CNN.com, it would most likely be used primarily for shutting down Slashdot and EFnet.

The only effective attack against a well-designed superworm is to have a decentralized network for security patch propagation that can distribute patches before exploits can be distributed. This would be a useful service in general as it would keep all participating systems patched up to the minute with the latest security fixes, thus making them invulnerable not only to superworms, but also to lesser worms and to hacking attempts based on published exploits. The network of nodes could also act as a distributed intrusion detection system, monitoring the progress and acting as an early warning system against hacking attempts, worm infections, and denial of service attacks. This project would be an excellent public service endeavor if funding could be found for its development and deployment. The only project I know of in this area is Austin-based company Invisisoft, whom I spoke to after my superworms panel at SXSW. I don't know what the status of that project is, however.