Chapter 7

Non-Zero Sum Games and Survivable Malware

Today, computer viruses, Trojans, and worms are summarily removed from computers when found. Even in the case of the One-half virus that is designed to make safe removal difficult, disinfection is still possible without damaging the host system. Antiviral programs seldom attempt to remove a virus unless they believe there are no harmful consequences for doing so. But what if the consequence extends beyond the infected computer in question? Put another way, what if the removal of a virus on one machine will cause damage on another remotely located machine? If harmful consequences result from removing malware then the payoff for removal becomes a negative quantity in game theoretic terms. Of course, leaving the malware on the system may have a payoff that is even more negative. This begs the question as to whether or not there exist malware enforceable games between the host and the malware that have a higher payoff for the host when the malware is allowed to remain after discovery.

The unspoken dream of every virus writer is to design a virus that cannot be safely removed even after discovery.¹

It is this that would constitute a true digital disease. This chapter investigates how various technologies can achieve this end when appropriately combined.

A dedicated attacker may have a rather serious goal in mind. For example, the attacker may want to factor someone's RSA key, or compute a discrete logarithm. Attacks along these lines are presented in this chapter.

An attacker that is simply carrying out a prank may simply want to give people a hard time. Under these circumstances survivability among malware helps to ensure that the attack lasts even after the virus is discovered and antivirus software is deployed. Such attacks hinge on the fact that not everyone is going to apply antiviral solutions on time, and some might not get around to it at all.² By distributing the bargaining chips that the virus has among several machines (for example, sensitive information that is damaging if disclosed), the virus can be made to be more survivable. In this situation, when Alice deletes the virus from her machine, the viruses that still reside on Bob and Carol's machines may exact revenge by anonymously posting stolen data from Alice's machine. The notion of distributing data among viruses and having them coordinate their attack efforts with each other is well known [332].

7.1 Survivable Malware

The ultimate goal of designing a survivable virus has been noted in the literature [332]. This notion was inspired by a creature called the facehugger that appeared in the science fiction movie Alien [265]. The facehugger is a parasitic alien that attacks humanoids for the purposes of perpetuating the alien species. It has the appearance of a small octopus with a long, powerful tail. It wraps its fingerlike legs around the host's head and its long tail around the host's neck, threatening the flow of air to the lungs. Once attached to the face of the victim, it slides a tube through the victim's mouth. The victim falls unconscious and remains in hibernation while retaining the ability to breathe normally.

The lifecycle for the alien species is as follows. The facehugger implants an embryo into the living host that gestates in the victim's abdomen. Eventually the host dies since the embryo grows into a baby drone that breaches the lining of the stomach. When the monstrous drones grow up, they herd together more humanoids for the facehuggers. Once in a blue moon a facehugger implants the embryo of a new queen. The queen in turn lays eggs that hatch into facehuggers.³

The facehugger is a fascinating alien creature. Any attempt to remove it causes it to tighten its tail and suffocate the host. Any attempt to lacerate it will cause it to bleed its acidic blood that will eat through any and all flesh. It even eats through metal. The facehugger maliciously forces a symbiotic relationship with its host.

In fact, there exists an even earlier fictional precedent for a facehugger-like entity.⁴ What's more, it takes the form of rogue software that travels through the network. The following is from the chapter entitled “Collapse of the Stout Party” in Book II of the 1975 novel The Shockwave Rider [43]:

“Remember what you said about a tapeworm?”

“Oh my God. That was a joke. You mean they spat in our eye again?”

“See for yourself, It's kind of—uh—fierce, isn't it?”

“Fierce is only half of it. Well, I guess it better claim its first victim. You found it. You go tell Mr. Hartz to abandon the attack on Hearing Aid.”

“What?”

“You heard me. Carry the good news from Y to X! Tamper with this thing, and—and my God! The data-net would be in chaos in one minute flat or maybe sooner! Hurry!”

Could a digital analog to the facehugger ever be devised? This, of course, is not known, yet various technologies when combined appropriately do suggest that something similar might be possible. A protocol is given in Section 7.3 that is a step in this direction. It was presented at West Point and was published in the proceedings of IEEE Information Assurance '03 [331]. The protocol constitutes a distributed cryptovirus attack in which the virus initiates a two-player game between copies of itself and the victimized machine. Game theory is used to analyze the consequences for ignoring or meeting the demands of the distributed virus.

Game theory grew out of work at RAND Corporation, Stanford University, and the work of John von Neumann. It is a mathematical study of rational decision making, and involves the payoffs received in simplified multiplayer games. Of particular interest in this chapter is a class of games called two-player non-zero sum games. The most celebrated such game is the famous Prisoner's Dilemma in which two players find themselves in a situation in which there is no guaranteed way to win: true collaboration is the only way to guarantee minimal losses by both. However, in a commercial society such collaboration does not exist between competing companies. This suggests that companies are optimal targets for game-theoretic virus and worm payloads.

7.2 Elements of Game Theory

In order to analyze the effectiveness of the attack that is presented, some basic notions in game theory [178] are needed. Table 7.1 is standard notation for a two-player non-zero sum game. In the game there are two players, the column player and the row player. The column player selects either column 1 or column 2 and the row player selects either row 1 or row 2. The selections occur simultaneously and the payoff for each is listed in the entry that results from the two selections. The row player receives the payoff on the left and the column player receives the payoff on the right. For instance, if the column player selects column 2 and the row player selects row 1 then the row player is paid b₁ and the column player is paid b₂. Payoffs can be positive, zero, or even negative, indicating indebtedness on behalf of the player.

A game is a constant sum game if a₁ + a₂ = b₁ + b₂ = c₁ + c₂ = d₁ + d₂. A game is a zero-sum game if it is a constant sum game and a₁ + a₂ = 0. When a game is not a zero-sum game it is a non-zero sum game. There are several famous non-zero sum games including Prisoner's Dilemma [305], Chicken, Battle of the Sexes, and so on. This attack involves a particular type of non-zero sum game that has a trivial solution.

The Prisoner's Dilemma is a well-known non-zero sum game that exemplifies a dichotomy between cooperation and rational decision making that can occur. This classic game theory problem is as follows.

Table 7.1 Payoff matrix for a two-player non-zero sum game

Two suspects A and B are in prison. The police have insufficient evidence for getting a conviction. The two suspects are separated and each one is offered the same deal: confess, and provided the other prisoner remains silent, there is no penalty. In this case the other prisoner will get 10 years to life. If both prisoners remain silent then each gets a 6-month prison term. If both prisoners confess, then each gets 5 years to life.

The payoff matrix for this game is given in Table 7.2. A rational approach to this problem from A's perspective is as follows. Clearly either B confessed or B did not confess. If B confessed and A does not, then A gets 10 years. But, if A confesses, then A only gets 5 years. If B did not confess, then by confessing A goes free. If A does not confess, then in this case A gets 6 months. To avoid heavy losses it is best for A to rat on B and confess. Assuming that they both behave rationally they will each confess and serve 5-year sentences. But, if they cooperate, they each do 6 months.

Merrill Flood and Melvin Dresher of RAND first discovered this paradox in 1950. Albert W. Tucker wrote about it in a Stanford University memo in 1950 that didn't appear until later [305].

7.3 Attacking a Brokerage Firm

The applications of utility theory and probabilistic decision making have been growing recently in secure systems research. For example, in Financial Crypto '03 the utility of a thief who seeks to exploit a single vulnerability to attack multiple installations was investigated [255]. The issue that is addressed here takes utility theory in a slightly different direction. Game theory is used as an integral part of the attack itself that is mounted on the host. The attack in this section builds on the notion of a cryptovirus by adding a novel property: it is possible that the payload of the virus will survive even after the virus is discovered. The payload has a chance to survive since it initiates a two player non-zero sum game between the host system and remote copies of the virus. The host system, which in this case is a brokerage firm, is forced to play the game under the threat that sensitive information on the host system will be disclosed by the malware.

Table 7.2 Payoff matrix in the Prisoner's Dilemma

The attack differs from the extortion attack in the following way. In the extortion attack, the victim is denied access to its own valuable information and has to pay to get it back, whereas in the attack that is presented here the victim retains access to the information but its disclosure is at the discretion of the computer virus. The attack therefore assumes that the critical host data satisfies a different property altogether.

It has been argued that whereas PKI adoption will do much to establish trust between individual people in public networks, it will also do much to establish trust for malware in public networks [331]. PKI paves the way for malware to be able to verify the compliance of remote victims by having the virus verify digital signatures, and public key cryptography allows viruses to send secure messages to other viruses.

7.3.1 Assumptions for the Attack

The victim of this particular attack is a stock market brokerage firm that conducts on-line trading. It is assumed that this firm has its own public key infrastructure and it is also assumed that the Securities and Exchange Commission (SEC) has its own PKI. Also, the clients of the brokerage firm belong to their own PKIs as well. It is necessary that all of these PKIs trust one another (that is, that they be cross-certified).

In this hypothetical scenario, trades occur in a very straightforward fashion. A client sends a signed message to the brokerage firm to request a trade in his or her account. Provided the signature is valid and the funds/shares are available the firm agrees to perform the transaction. At this point the firm signs the buy/sell request and sends the signed request to the trading floor. The SEC, acting as an overseer of all public trades, sends the outcome of the trade to the firm via a signed message. If a buyer/seller was found and the trade was carried out, then the SEC confirms its legitimacy. The brokerage firm forwards this signed response to the client at which point the client verifies it. This way, clients who may not be legally permitted to buy and sell stocks directly can do it securely through the brokerage firm for a small fee.

Another infrastructure that is assumed for this attack is an anonymous mix network (see Subsection 3.10.2). Since the attack amounts to an illegal act it is assumed that the mix network is vast. This may occur through the development and widespread adoption of a de facto mix network industry standard, for instance. To avoid the threat of a subpoena being issued that allows law enforcement to demand the private keys of the mixes, a re-encryption mix net can be used [120]. With such a service, seizing the machines of the mix net administrators would not help in apprehending abusers. The mix network in this attack is used in conjunction with a readable and writable public bulletin board. An example of such a public bulletin board is a Usenet newsgroup. It is assumed that the virus can both read from and write to the bulletin board anonymously. Servers currently exist that take e-mail messages and post them to the Usenet newsgroups and many users employ these servers to post anonymously. The assumptions are as follows:

1. A PKI encompasses the SEC, the brokerage firm, and the clients of the firm (for example, three cross-certified PKIs).
2. Clients send digitally signed buy/sell stock requests through the firm, and the SEC returns to clients, through the firm, signed responses to trade requests.
3. There exists a large anonymous mix network that is not controlled by law enforcement bodies.
4. There exists a public readable/writable bulletin board that accepts posts from the mix network and that is operated in such a way that it cannot be inhibited by law enforcement.
5. There exists a viral grace period in which the distributed viruses can freely post to the board in an inconspicuous and uninterrupted fashion.
6. The infection tree of the virus is difficult to reconstruct. This is necessary to conceal the location of the viral instances. In general a virus does not need to store any information relating to its previous host.

7.3.2 The Distributed Cryptoviral Attack

The attack is carried out by a distributed cryptovirus that tries to find three suitable host machines. The viral attack may be broken down into three phases: replication that leads to the infection of three suitable host machines, preparation for the attack, and then playing the two-player game.

All reading and writing to the bulletin board by the viruses is done through the mix network. For simplicity it is assumed that the messaging system is both timely and reliable. The following are the steps in the cryptovirus attack protocol:

1. Phase I: The cryptovirus is released into the wild. It is designed to do nothing but replicate for a specified period of time. For example, it will do nothing but replicate until a particular date. This allows the virus to secure entry into a large number of potential host systems.
2. When the virus activates on the particular date it analyzes its host to ascertain how well it will support the two-player game. For the machine to be an acceptable host it must fall into one of two categories: it must either be a brokerage machine or a reclusive machine. A brokerage machine is a machine in a brokerage firm that has sensitive information D available to the virus. Information D must have the property that it would be severely damaging to the firm if it were disclosed to the public. A reclusive machine is a machine in a remote area that preferably undergoes little if any scrutiny.
3. Phase II: If the host is a brokerage or reclusive machine then the virus posts a message to the bulletin board. The message indicates whether the host is a brokerage or reclusive machine and contains a randomly chosen identifier for the virus. The identifier can be a randomly chosen 512-bit number, for instance. These identifiers will be unique with overwhelming probability.
4. Each virus on a brokerage machine then goes about selecting two viruses on distinct reclusive machines to carry out the attack. Let V_b denote a virus on a particular brokerage machine. For j ranging from 1 to 2, V_b selects (e.g., at random) a posting of a reclusive virus, takes note of its identifier, and posts a message inviting the reclusive virus to engage in the attack with V_b. The reclusive virus reads the post of V_b and responds with one of two different posts: it accepts the invitation of V_b to act as virus V_r,j, or rejects. It rejects if and only if it accepted a previous invitation. This step amounts to a handshaking protocol in which V_b establishes the IDs for V_r,1 and V_r,2 and vice versa.
5. V_r,1 reads the bulletin board and finds the message in which V_r,2 accepts the invitation of V_b. V_r,2 reads the bulletin board and finds the message in which V_r,1 accepts the invitation of V_b. This way each virus V_b, V_r,1 and V_r,2 knows the IDs of the other two viruses. When V_b posts a message to V_r,1 it includes a from field that includes the ID of V_b and includes a to field containing the ID of V_r,1. This allows the viruses to communicate with each other unambiguously.
6. Each of the three viruses (V_b, V_r,1, and V_r,2) generates a key pair and gives the public key to the other viruses by posting it to the bulletin board. To prevent man-in-the-middle (MITM) attacks it is necessary that all viral activity goes unnoticed before the attack. From then on every viral posting is first signed and then encrypted for the intended recipient, and the signatures on all messages are verified before being accepted as valid. Note that the ciphertext postings need not have identifiers visible on the outside. The viruses can attempt to decrypt any and all ciphertexts to distinguish valid postings from random data.
7. Once all three public keys have been posted, V_b chooses a pad R randomly and then encrypts D using the Vernam cipher, thereby obtaining the ciphertext C. V_b then transmits R securely to V_r,1 and C securely to V_r,2 over the bulletin board.
8. V_b instructs the brokerage firm to establish a new account for the virus (if necessary). Either by making the attack known to the firm, or in secret, the virus allocates an account for itself containing say, $10,000.
9. Phase III: By communicating in a signed and encrypted fashion over the bulletin board, V_r,1 and V_r,2 collectively select a publicly tradable stock to purchase and request that a single share be purchased. This share can be selected uniformly at random from all tradable shares or can be chosen according to a specified algorithm. The collaborative decision-making process can be accomplished by having V_r,1 and V_r,2 conduct fair coin tosses [31, 33] over the bulletin board. This guarantees fair coin tosses even if the coin flips of one of the viruses are compromised. The virus insists that the resulting share be held under the street name of the firm.
10. The desired transaction is conveyed to V_b by V_r,1 and V_r,2 using the bulletin board. V_b either performs the transaction in secret (if it has control over the trading system), or failing that, it informs the brokerage firm of the desired stock transaction by displaying a message to the broker, for example.
11. The brokerage firm's trading system either carries out the purchase or does not. If it does, then either V_b, or the firm acting as V_b, encrypts the signed SEC response under the public keys of V_r,1 and V_r,2 respectively and publishes the two resulting ciphertexts in two different postings.
12. V_r,1 expects to find a posting on the bulletin board from V_b consisting of a signed SEC response. If a valid signed response is not received within time T (e.g., two days) by V_r,1, then V_r,1 posts R in plaintext form to the bulletin board. Similarly, V_r,2 expects to find a posting on the bulletin board from V_b consisting of a signed SEC response within time T. V_r,2 posts C in plaintext form to the bulletin board if the SEC signed response is not received on time. So, if the two encrypted SEC messages are not posted then anyone with access to the bulletin board will be able to bitwise exclusive-or C with R and recover the sensitive data D, thus ending the two-player game in Phase III.
13. If the initial trade request is processed, then eventually another request is made by V_r,1 and V_r,2. By keeping track of the account internally, the virus can issue sale transactions in addition to buy transactions.

The attack is depicted in Figure 7.1. The purpose of using street names is to keep the transactions fluid, as in typical firm/client relationships.⁵ Over time such a virus may make many transaction requests, which may be to either buy or sell shares.

Note that when the virus asks the firm to purchase one share of XYZ, the firm can always obtain a fresh signature as follows. The firm can sell one share of XYZ if it already has one to spare, or failing that, it can sell short on one share. The firm can then buy the share of XYZ back from the open market and obtain the fresh SEC signature that the virus expects. So what can really be gained in this attack? If nothing else, the virus has secured the opportunity to prove its worth as an intelligent investment advisor. The goal in this particular attack is not to give the virus writer direct monetary gain,⁶ but to give the distributed malware purchasing power. The virus will develop a portfolio history based on its transaction requests. The firm must comply with the requests under threat of sensitive information disclosure, and hence the firm must observe the series of requested transactions. Over time the virus may prove its worth as a portfolio manager. In the event that the virus develops a solid track record the firm may actually start purchasing shares at the request of the virus without selling them first. If the account grows, the virus will be in a better position to levy unorthodox demands against its victim.⁷

Figure 7.1 Distributed cryptoviral attack

A computer virus could conceivably steal investment advice as well. This is possible if the virus is in a position to observe the investment decisions of other investors. The virus could eavesdrop on the buy/sell transactions and then mimic the decisions of the best investors. An ideal host for such functionality is a client program that allows users to send transaction requests to an on-line brokerage firm.

Another possibility is for the virus to demand that the firm purchase a CD from a bank. In this case the CD would have to be signed by the bank under the PKI of the bank. This type of investment differs from stocks since a CD cannot be cashed out prematurely without suffering a financial penalty. However, even in this case the firm can try to sell the CD to someone who actually wants it in order to obtain the cash that was spent on the CD.⁸ An interesting question is whether or not there exists a financial investment mechanism that truly locks the buyer in and prevents the transference of the asset in question.

Also, what is to prevent the firm from notifying the SEC that the attack is being carried out? This would certainly foil the malware attack. The firm can certainly do this, but by doing so the firm would likely run the risk of the attack being made public. Hacker attacks can be very embarrassing to large companies and it is not uncommon for companies to cover them up and even suffer losses to do so.

7.3.3 Security of the Attack

On an algorithmic level it is possible to select various primitives for use in this attack that are provably secure by themselves. For example, the Optimal Asymmetric Encryption Padding (OAEP) algorithm used in PKCS #1 can be used to perform encryption, and PKCS #1 can be used for signing the messages that the viruses send each other [249]. Also, a provably secure mix network can be selected. However, it is difficult to analyze the exact security of this hybrid cryptographic protocol, except against specific attacks. This results from the complexity of combining all of the underlying primitives.

To allow confidential and authenticated communications between V_r,1 V_r,2 and V_b it might be tempting at first to include three separate key pairs in the initial virus. However, this is not a secure approach since the key pairs will exist in all future offspring of the virus and will therefore provide no privacy in Phase III of the attack. However, by having the viruses generate key pairs in Phase II the key exchange is subject to a man-in-the-middle attack. For this reason it seems necessary that the viruses operate in secret from when the virus is released up until the beginning of Phase III.

The reason that V_b utilizes the Vernam cipher is to try to protect the privacy of the brokerage firm. Since the One-time pad is information theoretically secure, an administrator that finds R will not learn anything about the plaintext D without the ciphertext C. The same applies for C. This mechanism, combined with the use of mix networks, gives the brokerage firm the assurance that D is stored in a secret-splitting fashion. Other approaches can be used to accomplish this as well. For example, an m-out-of-n secret sharing scheme [21, 22, 40, 42, 59, 101] can be used in which any m out of n viruses can collaborate and reconstruct D.

A corollary of this attack is that V_b can be removed without affecting the overall game that is initiated. Virus V_r,1 and virus V_r,2 expect SEC signed messages in response to their trade initiations. The viruses do not care who actually obtains and sends these signatures. A broker can carry out all of the tasks that V_b performs in Phase III manually. It is a matter of semantics to say that the malware is removed by removing V_b. This will not change the fact that the information needed to reconstruct D will be exposed to the general public if the SEC responses are not received.

7.3.4 Utility of the Attack

Many stock portfolios specialize in particular markets such as pharmaceuticals, computer technology, energy, and so on. For this reason the demand to purchase a tradable stock chosen randomly from all tradable stocks is likely to be perceived negatively. As a result the perceived payoff for making the purchase that the virus selects will likely be negative irrespective of any potential return on investment. If it were known a priori that this two-player game were only going to be played once, a suitable characterization for the game might be the one given in Table 7.3.

The column player is the victimized brokerage firm and the row player is the distributed cryptovirus. Column 1 is the choice to buy the stock that the virus requests. Column 2 is the choice to refuse the transaction. Row 1 is the choice to issue a buy request. Row 2 is the choice to publish sensitive data D.

Table 7.3 Payoff matrix for virus and firm

The game differs from a traditional two-player game since the choice that the virus makes is in fact contingent upon the choice that the firm makes. The payoffs may be reasoned as follows. The firm suffers a −10 penalty if D ends up being published. This happens if the firm denies the buy request or if the virus simply decides to publish D. The virus may as well select row 2 and publish D if the column player chooses column 2. Strictly speaking, due to this conditional move, this matrix is more of a payoff matrix than a two-player game. Also, the salient feature of the payoff matrix is the partial ordering of the payoffs as opposed to the specific values given in Table 7.3.

This “game” is nonetheless not a zero-sum game since 0 + (−10) = −10. It is not a constant sum game since 1 + (−1) = 0 does not equal 0 + (−10) = −10. The game is therefore a non-zero sum game. But it is arguably one of the less interesting non-zero sum games since there is no conflict of interest. When played once the optimal strategy for each player is clear. The solution to the game is row 1, column 1. However, for the firm, winning amounts to cutting the firm's losses whereas for the cryptovirus winning amounts to successfully coaxing the firm to purchase a stock.

It is difficult to speculate on the game when it is repeated multiple times. There are numerous factors to take into account including how often the virus makes requests, how many shares are in each request, and so on. If the firm denies every request and eliminates the virus, then the firm can guarantee a loss of no worse than −10. But, if the firm processes the requests and the virus ultimately publishes D anyway, then the losses could be even more. If the damage that would result from the publication of D far outweighs the purchase of a few stocks, then it may be best to cater to the virus, at least for a time. On the other hand, one should not immediately discount the possibility that the virus will make sound investment decisions. It is not unthinkable that some day a real-time trading engine could be created that would cause the firm to eagerly wait for the valued investment advice of the cryptovirus. Once such a stance is established, the virus could make uncanny demands such as who to hire and fire in the firm.

The utility of this attack from the malware author's perspective is clear. It amounts to an on-line agent that is capable of automatically making and executing the author's investment decisions. The author can communicate with the agent over the same bulletin board using public key cryptography and make manual decisions on behalf of the agent. This allows the author to exercise control over the victim with very minimal real-time interaction, thereby minimizing the author's chances of being apprehended. If the investments are lucrative, the attack amounts to a free lunch for both the firm and the author. If they are not lucrative, then the firm loses money and the author loses nothing.

There are several issues that are left open. For example, are there well-defined and well-studied games in game theory that directly apply to this particular malware attack? Are there ways to improve the attack⁹ so that the victimized firm is certain that D will not be published if the transaction is honored?

7.4 Other Two-Player Game Attacks

There are other two-player games that can be initiated by malware as well. Two such attacks are described in this section. They both utilize the notion of a distributed virus that carries out its payload by having its individual instances communicate with each other securely.

7.4.1 Key Search via Facehuggers

The notion of using viruses to solve computationally difficult problems is well known. For instance, a virus can by brute force try to determine the DES key that was used to produce a particular symmetric encryption [320]. Also, viruses can be used to steal CPU time to try to factor composites, compute discrete logarithms, and so on.

In this subsection a particular cryptovirus attack is detailed that is geared towards solving the discrete logarithm problem in a prime order subgroup. The prime order subgroup discrete-log problem is believed to be intractable and is the basis for many cryptographic algorithms such as DSA. Recall that the DSA private key is x and the DSA public key is (y, g, p) (see Subsection C.2.7). DSA utilizes a public prime q that is 160 bits in length. The order of g modulo p is q and hence q divides p − 1 evenly.

The attack utilizes the approach of Feigenbaum et al to hide information from an oracle [1, 2, 99] (see Section 6.8). The virus writer chooses r < q randomly and computes y_r = yg^r mod p thus randomizing y. It is simple enough to place y_r = yg^r mod p in a virus and let the offspring try to compute the base g discrete log of y_r. If it is found, then it can be posted to a bulletin board so that the virus writer can obtain it. Since the virus writer knows r, the virus writer can recover x from the posting. This allows the virus writer to try to determine someone's DSA private key x in y = g^x mod p by brute force in such a way that the owner of the public key has no way of knowing that the private key has been compromised.

Consider the case that one of these viruses is found. The virus would likely be chewing up a fair amount of CPU time, and would be a nuisance in general, and would simply be removed. So in this straightforward attack a machine is lost whenever the virus on that machine is found, that is, there is one less machine to perform the distributed brute-force computation.

However, if the virus were more like a facehugger then there would be consequences for removing it. The goal then is to devise a mechanism that optimizes the number of machines that are actively trying to solve the discrete logarithm problem instance. The following is a virus attack that seeks to achieve this goal. We call the virus a facehugger and give a very high level description of it.¹⁰

To mount the attack the virus writer chooses r < q randomly and computes y_r = yg^r mod p. The value (y_r, p, g, q) is placed within the virus. It is assumed that the virus is given a grace period in which it can infect many machines and remotely store sensitive data without hindrance, and so on. The virus operates much like the virus in the attack on the brokerage firm. Each virus generates a large random identifier ID, each virus generates a key pair, and they communicate securely¹¹ with each other over a mix network and bulletin board, and so on. The identifiers serve as digital pseudonyms. Each virus searches its host for sensitive host data D that would be damaging if published. This data is encrypted using the Vernam cipher. The resulting ciphertext C and One-time pad R are securely sent to the two other viruses involved in the attack on the host.

So far the attack is almost exactly the same as the attack on the brokerage firm. However, the attack would be on a much larger scale since any host machine that contains sensitive data D is a viable host for the attack. Brokerage firms are not sought after explicitly. Let the total number of viruses be denoted by N and for simplicity assume that all N machines contain sensitive data. The viruses partition the key space into N roughly equal partitions each of which is a contiguous set of numbers. The viruses are each responsible for making their respective hosts search a given partition. Let s₁ denote the starting value for the partition of a given virus V₁.

It is important not to overload a virus in terms of the Vernam ciphertexts and One-time pads that it stores from other virus attacks. To avoid this the viruses carefully arrange the way they store the sensitive data. The arrangement of viruses can be expressed as a bipartite graph (see Figure 7.2). Each virus is represented by two vertices of the same color. The figure shows the case of N = 5, 4, 3 from left to right.

Although it is not shown in the figure, the vertices are labeled using the identifiers of the viruses. The vertex at the top has the highest value for ID, the one below that has the second highest value for ID, and so on. When a virus computes a One-time pad and Vernam ciphertext it sends them to the two viruses indicated by the directed edges.

The bipartite graphs in the figures are all quite similar since each vertex connects to the two vertices directly below it and to the right, except for the bottom two vertices. The bottom vertex always connects to the top two vertices on the right. The vertex second from the bottom always connects to the top and bottom vertices on the right. Also, the arrangement is constructed such that each virus is responsible for storing a Vernam ciphertext from one machine and a One-time pad from another.

Figure 7.2 Bipartite arrangement of the facehugger

When the grace period ends each virus immediately begins searching the keyspace. For example, V₁ immediately starts searching the partition that begins with s₁. Virus V₁ checks to see if y_r = g^s₁, g^s₁ g, g^s₁+1 g, and so on. The partition is exponentially large so the virus, which is polynomially bounded, will not finish the search. If the logarithm of y_r is found, then it is posted to the bulletin board.

Each virus also demands that two other hosts conduct searches. Consider the case that V₁ stores the Vernam ciphertext C₂ and One-time pad R₃ corresponding to the senstive data on two other infected machines M₂ and M₃, respectively. Also, let the viruses on these machines be denoted by V₂ and V₃, respectively. V₁ demands that V₂ and V₃ search the key space as well. This is accomplished by having V₁ send each of these two machines challenge sequences. The following is how the challenge sequences for V₂ are constructed. It is the same for V₃.

At regular intervals (e.g., once every couple of hours or so) V₁ chooses r₁, r₂ < q randomly, chooses j randomly from {0, 1, 2, ..., 2²⁰ −1}, and then flips a coin. If the result is heads then V₁ sets w = r₂ and t = y_rg^r₁ mod p. If the result is tails then V₁ sets w = r₂ and t = g^r₁ mod p. V₁ sends the pair (t, w) to V₂ securely.

If there exists an i contained in {0, 1, 2, ..., 2²⁰ − 1} such that t = g^w+i mod p then V₁ expects V₂ to respond with i. If no such i exists then V₁ expects V₂ to respond with “no exponent found.” Failure to produce a valid answer, that is, i such that 0 ≤ i < 2²⁰ or “no exponent found” after time T elapses always results in the publication of C₂ in retaliation. For concreteness let T = 2 hours. This interval must be chosen to give plenty of elbow room for V₂ to solve two challenge sequences at once.

If the result is heads and V₂ responds with i then V₁ checks to see if g^w+i t = y_rg^r₁ mod p. If this equality does not hold then V₁ publishes C₂ to the bulletin board. If the equality does hold then V₁ publishes w + i − r₁ ≡ x + r mod q to the bulletin board. This allows the virus writer to recover x since the virus writer knows r. If the result is heads and V₂ responds with “no exponent found” then V₁ assumes on faith that there is no i contained in {0, 1, 2, ..., 2²⁰ −1} such that g^w+i = t mod p and so V₂ passes the challenge sequence.

Now consider the case that the result is tails. If V₂ responds with “no exponent found” or a value for i such that j ≠ i then V₁ publishes C₂ to the bulletin board in retaliation. If i = j then V₂ passes the challenge sequence.

So what is really going on here? V₁ is conducting a sting operation of sorts against the host of V₂. With 50 percent probability a sequence is sent to M₂ for which, if V₂ is still running properly on M₂, V₂ will find the discrete logarithm and give it to V₁. With 50 percent probability M₂ is given a portion of the keyspace to search. M₂ has no way of knowing which is the case. So, it can do no better than guess. To be uncooperative the operator of M₂ can refuse to send a discrete logarithm when one is found. However, the operator will be caught with probability 1/2. This interactive protocol is intimately related to the notion of a proof of work. Informally speaking, a proof of work allows a prover to demonstrate to a verifier that the prover has performed a certain amount of computational work in a specified interval of time [136].

The operator of M₂ can decide to ignore V₁'s challenge sequences entirely under the assumption that only C₂ will be published and not the One-time pad R₂. However, this increases the chances that both C₂ and R₂ will become available, thus compromising C₂ ⊕ R₂. M₂ will still receive challenge sequences from the other virus, unless it has been tampered with.

The attack is intriguing since it creates a form of deadlock when the victims do not trust each other. For instance, if the operator of the machine that hosts V₁ decides to be a good samaritan and delete the Vernam ciphertext and One-time pad that V₁ is storing, there is no reason to believe that the operators of the machines that store the ciphertext and One-time pad that V₁ sent out will reciprocate. They might in fact publish them. This can cause the good samaritan to loose the game.

The payload of the facehugger forces victims to perform intensive computations under the threat of sensitive information disclosure. This would clearly be a hassle and a nuisance for the victim. It is related to the use of puzzles to defend against connection depletion attacks [146]. However, it uses puzzles as a malicious payload rather than a defense. Also, the payload is not simply destructive since these intensive computations are geared towards breaking a public key.

There are also other issues to consider. For example, when the viruses are never found this scheme creates needless extra work for the virus. This results from the phoney challenge sequences that must be searched. However, when the viruses are brought to near extinction the virus has a chance to continue the search on machines in which the virus has been discovered. Open issues include ways of improving the attacks as well as identifying new attacks along these lines.

A similar sort of attack can be carried out against composite public keys. Let n = pq be the product of two large primes p and q. This could be a Rabin public key, an RSA public key, and so on. The virus contains n and attempts to discover the factorization of n. Already a complication exists since if the owner of the public key n learns that a virus is trying to break it, the owner will immediately revoke the public key n. However, if the virus writer has a ciphertext c that was computed using n, then breaking n is still useful in trying to decrypt c. The attack will not be described in detail, but the general idea will be sketched out.

In the attack the virus writer tries to obtain two ambivalent roots of a quadratic residue modulo n. The values x and y are ambivalent roots of x² mod n if x² = y² mod n and x ≠ ± y mod n. These two values allow n to be factored since gcd(x + y, n) or gcd(x − y, n) is a non-trivial divisor of n.

The virus writer places a = x² mod n in the virus and hopes that the viruses will find a y that is ambivalent with respect to x. Also, the virus contains a random function H that maps {0, 1}* onto the set . Let H_j(s) = H(J||s) where J is the 20-bit binary representation of j and s is any input string. It may be assumed that H_j(·) is publicly known.

The victim's machine is challenged by the virus as follows. The virus chooses r₁ randomly from , w randomly from , j randomly from {0, 1, 2, ..., 2²⁰ − 1}, and flips a coin. If the result is heads then the virus computes t = ar²₁ mod n. If the result is tails then the virus computes t = H_j(w)² mod n. The virus sends the challenge (t, w) to the victim.

If the victim does not respond with i {0, 1, 2, ..., 2²⁰ −1} or “no root found” on time then the sensitive data is published in retaliation. If the victim responds with i {0, 1, 2, ..., 2²⁰ −1} then the virus checks to see if H_i(w)² mod n t. If this does not hold then the sensitive data (either the Vernam ciphertext or the One-time pad) is published. If this does hold and the coin toss resulted in heads then H_i(w)/r₁ mod n = is asymmetrically encrypted under the public key of the virus writer that is contained in the virus. This ciphertext is published to a bulletin board so that the virus writer can obtain it. If H_i(w)/r₁ is ambivalent with respect to x then the virus writer can factor n using H_i(w)/r₁ and x.

7.4.2 Catalyzing Conflict Among Hosts

An ancient strategy when three warring factions are mutually at odds is to get the two opposing factions to obliterate each other and then take out the one that is left standing, if any. A surviving faction will likely have suffered severe losses in the initial battle. This strategy can be extrapolated to cryptovirus attacks as well. The basic idea is to infect two remote systems that are operated by owners that oppose each other. The viruses securely transfer sensitive host data to each other to initiate a two-player game and then announce that this has been done. The two owners must then complete the two-player game that the virus initiated.

Consider such an attack against two companies. The cryptovirus asymmetrically encrypts sensitive information from company A and transmits it to another copy of the virus located at company B. The virus at B decrypts the ciphertext with its private key. Similarly, the virus at B steals sensitive information from B, asymmetrically encrypts it, and then transmits the ciphertext to the virus at A. The virus at A decrypts it with its private key. When all of the information has been transferred, the distributed cryptoviruses alert their respective victims of the presence of the newfound information on their system.

If the information that was transferred is damaging when disclosed and if A and B are in direct competition, then A and B have entered into an exacerbated state of conflict. A and B are then left to arrive at a solution. In this situation the virus can be removed but its payload may only be considered removed if and when A and B complete the two-person game that the distributed cryptovirus started. Viruses that force their victims to play games with each other are unique since they exploit naturally occurring distrust among victims.

7.5 Future Possibilities

These attacks constitute plausibility results regarding survivable malware. The following are basic ideas that form the basis for such attacks:

1. Implementing the virus as a distributed algorithm. The virus resides on multiple machines that are networked. This gives robustness against the possibility that the virus attack will be terminated since deleting or compromising one or two viruses may not halt the attack (fault-tolerant viruses).
2. Having the viruses utilize a bulletin board. This allows the viruses to communicate to each other by reading and writing to a single location that they are all aware of.
3. Having the viruses utilize a mix net. This allows the viruses to conceal their locations from everyone including each other and therefore helps to keep them from being discovered.
4. Having the virus employ split (or threshold) encryption. This protects the privacy of the victim(s). Without some measure of privacy certain victims may not hesitate to pull the plug on the virus altogether and ignore the viral demands.
5. Having the virus employ asymmetric cryptography. This allows the viruses to exchange public keys, digitally sign data, and encrypt data using a public key. Hence, the viruses can establish authenticated and confidential channels with each other through the mix net and over the bulletin board.
6. Having the viruses generate shared randomness. Cryptographic coin flipping protocols allow the viruses to generate randomness in a way that is robust against a small number of viruses being compromised. In some sense it allows the distributed viruses to perform distributed decision making with the benefit of having an honest random (Turing machine) tape.
7. Having the victims victimize each other. This defers blame and some degree of culpability away from the virus. It provides victims with an alternate means of dealing with the payload; namely, by having the victims reconcile their differences out-of-band. Such conflicts can be instigated by certain non-zero sum games.

Another extension that can be made to this type of distributed malware is secure multiparty computations. These are cryptographic protocols that allow a number of parties to securely evaluate a circuit and they have some very robust security properties with respect to privacy, faults, and so on. By having a distributed virus employ such protocols, they would be able to perform secure distributed computations even when some of the viruses are compromised.

Looking even further ahead, consider the following possibility. Intelligent agents are slowly becoming integrated with our everyday lives. When we call a company that provides some form of service (for example, a bank) we often get connected to electronic helpers. These agents use voice recognition to answer our questions, perform transactions, and even offer advice on achieving problem resolution. A chilling thought is the possibility that the back-end software of such an agent is a victim of an ongoing distributed cryptovirological attack. The virus could directly influence the actions of such an agent. The thing about distributed cryptoviruses that use mix nets is that there is essentially no way to find out where they are on the net. One could argue that the first step in achieving power is the accumulation of wealth. The overall threat is a foreseeable possibility since we are increasingly allowing machines to make decisions for us.

Fears that machines might evolve and subsequently replace people appeared in S. Butler's novel Erewhon. It was published in 1872 [46] and challenged the moral hypocrisy of Victorian England and its ecclesiastical institutions. In Automata, S. F. Wright describes machines that take over all human activities and eventually eliminates the entire species [322]. Also, the Colossus computer from the 1966 novel Colossus [143, 254] and the Skynet computer in the movie The Terminator [51] threaten the extinction of all mankind.

The distributed cryptovirus attacks may appear to be sensational, and for our time they most certainly are. However, they are perhaps no less sensational than how a pair of cell phones would have appeared to the inventor of the telegraph. In today's computing environments these attacks are perhaps most relevant as thought-provoking possibilities rather than realizable threats.