Anatomy of a Parasitic Computer

In SETI@home, each node of the supercomputer must run a program to participate. In the case of parasitic computing, however, a node only needs to be connected to the Internet to be a potential participant. In this article, I describe how one parasitic computer — the TCP/IP checksum computer (TICC) — is constructed. It uses a specially constructed TCP segment in such a way that when the receiver computes the checksum, it unwittingly performs a computation for a remote node. Using the TCP checksum, a parasite is able to ask the following question: Is a+b equal to c? (hereafter written as a+bc). This operation performs addition followed by a comparison. Given this add-and-compare operation, you can (through a sequence of one or more of these operations) solve any computational problem. Ordinarily, the sender-side TCP stack builds the TCP header, including the checksum. However, TICC bypasses the TCP stack, injecting the message at the IP layer, in a variation on IP spoofing. (For more on IP spoofing, see http://www.fc.net/phrack/files/p48/p48-14.html and http://www.cert.org/advisories/CA-1996-21.html.)

TCP is a transport protocol, whereas the target on the receiver is an application — an end point of communication. Thus, TICC cannot simply target TCP. Instead it uses HTTP because it is built on TCP, it replies to invalid requests, and there are numerous web servers — TICC begins with an IP packet that masquerades as a TCP segment destined for port 80 (default for HTTP).

The next step is to evaluate the add-and-compare operator. When the answer is True for (a+b=c), the checksum test performed by the TCP stack on the receiver side succeeds and the segment is passed up to HTTP. Even though the message is not a valid HTTP request, the web server responds (as required by HTTP), usually with error number 501 (unsupported operation).

On the other hand, when the answer is False (a+bc), the checksum test fails. In this case, the segment is not passed up to HTTP. This is observed by lack of response (that is, the answer is declared false after some timeout).

Implementation

Listing One outlines an implementation of TICC in Linux. There are three steps in the TICC. First, it must setup the connection, then create a segment, and finally, determine the answer. (Actually, I'll discuss an optimization that eliminates connection setup shortly.)

TCP is a connection-oriented protocol and a connection must be established before any communication can take place. Connection setup consists of three messages:

• First, the initiator node sends a SYN message, which is a request to create a connection.
• Next, the destination of the aforementioned message replies with a SYN-ACK (if it wishes to communicate).

• Last, the initiator sends another ACK message. At this point, the connection is established and a conversation can begin.

TICC initially sets up two sockets (see initCommo() in Listing One). One socket is standard TCP, using the SOCK_STREAM protocol. This socket creates a connection between the parasite and the host. The second is a raw socket using the SOCK_RAW protocol that reads/writes raw IP packets. In this context, "raw" means the headers are visible. In Linux, a raw socket sees all IP packets, including those sent to TCP. (This is not necessarily portable to other flavors of UNIX.) A raw socket can only be created by privileged users. The raw socket has two purposes: It snoops the TCP connection messages for critical data, and it injects the add-and-compare operation at the IP layer and looks for the response.

There is a sequence number for each communication direction. The sequence number is essentially the location in the bytestream. In each TCP segment, senders insert the sequence number of the first byte in the message being sent. It also inserts the sequence number of the last byte received from the computer on the other end of the socket. The latter is called the "acknowledgment number." The sequence numbers provide an ordering of the segments, which is necessary because IP is unreliable and can deliver out of order (see TCP/IP Illustrated, by W. Richard Stevens, Addison-Wesley, 1994; and TCP/IP Protocol Suite, by Behrouz A. Forouzan, McGraw-Hill, 2000).

TCP selects a unique initial sequence number (ISN) for each conversation. The ISN of a connection is essentially random — the more random, the harder the guess. Because TICC employs the standard TCP stack to establish the connection, it must capture the ISNs, one for each direction. Figure 1 shows the three messages sent in the connection setup: S and D stand for "source" and "destination," respectively. An acknowledgment number is the sequence number of the last byte successfully received. TICC reads the raw socket during the initial TCP connection setup to acquire the ISNs.

The getIPpacket() procedure extracts the ISNs. Because the raw socket reads every IP packet, the code checks that this is the appropriate packet. If it isn't, the code skips this packet and gets the next one. When the correct packet arrives, the code copies the acknowledgment and sequence number from the packet.

The parasite node begins the conversation (first message following connection setup) with an add-and-compare operation, which is a specially constructed TCP segment. A TCP segment consists of an IP header, TCP header, and data; see Figure 2. TICC constructs the entire TCP segment in a user-level buffer before sending it (done in transmit_TCP(), although omitted from Listing One). The SOCK_RAW protocol always sets some critical fields in the IP header, such as IP checksum and total length. It can optionally set the other fields. If not set by the protocol stack, TICC must set these fields in a user-level buffer before writing it to the socket. In any case, certain fields in the IP header must be set appropriately. In particular, the protocol field must be set to TCP (protocol number 6).

Because TICC bypasses the sender-side TCP stack, it must construct the entire TCP header, which is sent as cargo in the IP packet. The sequence number is the index of the first byte of the message, which is computed by adding the number of bytes already sent to the source's ISN. The acknowledgment number is the index of the last byte received, using the sequence number for the other direction.

The TCP checksum is part of the TCP header. It is the last field computed because it sums the TCP header and cargo. The "correct" TCP checksum, which is computed by the sender, is determined by putting 0 into the checksum field in the header. The message is padded to a 2-byte boundary. Then, using unsigned, 1s-complement arithmetic, the message is summed on 2-byte boundaries. Overflow bits are discarded. This sum is bit-wise complemented (all 0s changed to 1s and 1s to 0s). The complemented sum is inserted into the TCP header.

The receiver performs nearly identical steps, except that after the summation, instead of complementing, it examines sum. If no errors have occurred, the receiver's sum should be all 1s. This is because the fields not including the checksum add up to S, the checksum is , S+ equals all 1s.

In the add-and-compare operation, the checksum is determined a bit differently. Instead of computing the sum over the header and the cargo, it is computed over the header and the answer, c in a+bc.

The add-and-compare is not limited to two add-ends (as in a+bc). The general form of the operator is a_ic, which is limited by the size of a TCP segment. This limit has a default of approximately 250 2-byte words, but depends on the connection. However, because overflow bits are discarded, the practical limit is only a handful of add-ends.

Improvements

Detecting a true answer is trivial — any response to the add-and-compare means the segment passed the TCP checksum. However, because you cannot distinguish between a lost message and a delayed one, false answers are not 100 percent reliable.

Unreliability causes two undesirable consequences. First, a false positive occurs when a bit error changes an invalid result into a valid result. This is statistically rare and all but impossible in practice. Second, a false negative occurs when a packet for a valid solution is dropped due to data corruption or congestion. Although this is also unusual, it is frequent enough that it must be addressed.

There are two ways to handle false negatives. Suppose you can ask a question, Q, and its complement, not Q. Because only one of the questions can be true, one response is expected. If there is no response (or two responses), then the questions should be asked again. Although this way creates a reliable system, not all questions that can be asked with add-and-compare have a complement.

Therefore, a more general approach is to verify negative results by asking the question more than once. This decreases the probability of false negatives. For example, if p is the probability of a false negative, then pn is the probability of n false negatives. Because p<<1, the likelihood of a false negative all but disappears for small values of n.

This implementation sends only one add-and-compare operation per TCP connection. You can try to perform more than one add-and-compare per connection, which will reduce the overhead significantly. If the previous question was true, then TICC received a reply from the destination. Sending another add-and-compare operation will be a normal continuation of the conversation. You need only increment the sequence and acknowledgment numbers appropriately and send the next add-and-compare.

However, if the answer to the previous question was false, the conversation cannot be started "following" the previous message because it did not actually take place. If you use the same sequence and acknowledgment numbers as the previous add-and-compare, there are now two outstanding operations. A response from the destination could be answering either of the outstanding operations. If all outstanding operations have a different length (which can be accomplished by padding with 0s), you can use the acknowledgment number in the reply to identify the operation being answered. Of course, this approach requires that no false positives have occurred on this connection.

Much of the overhead in TICC is due to TCP connection management. In the straightforward approach, the parasite node sends four messages and receives one or two. However, many TCP stacks respond to spurious FIN messages. Thus, TICC can first determine if a targeted TCP stack responds to such FIN messages. Then it can avoid connection setup. This reduces the overhead to one message sent and zero or one received.

Because the FIN improvement does not require an actual connection to be established, it is not limited to targeting HTTP servers. Thus, any computer running TCP is a potential host for parasitic computing. Furthermore, with FIN, many add-and-compare messages can be concurrently sent to the same host, with each using a different port number.

Conclusion

TICC is a proof-of-concept implementation and, at this time, not very efficient. The cost of an add-and-compare is at best the cost of sending a message. The benefit is some addition and a compare. Thus, the overhead of TICC is several hundred times greater than the benefit.

Because TICC does not offload any work, it is not a threat to be used in that way. Additionally, TICC is too computation intensive to be an effective denial of service attack. Furthermore, it is not likely that a different, smarter implementation can extract more work from the host using TCP checksum because the checksum function is too simple. However, many believe that there could be some cost-effective exploit in one of the many Internet protocols. Even though this implementation is not a threat, parasite computing raises important issues.

This project has generated much interest regarding ethical and legal issues. While this is an important and timely discussion, there are some interesting technical issues as well. One is in detection, where we have developed rules that catch checksum parasites. Another is a catalog or taxonomy of exploits of public protocols. Finally, we are investigating other techniques for parasitic computing in order to access viability and threat. The result of this research will be a greater understanding of the fundamental elements of Internet communications, which will lead to a more robust and capable Internet.

DDJ

Listing One

int main (int argc, char *argv[])
{
  int raw;                      // socket that is opened SOCK_RAW
  char *host;                   // targeted machine--the parasite's "host"
  char answer[2];               // value c in 'is a+b equal to c'
  u_short checksum;             // computed checksum
  char *data;                   // data added (a,b in 'is a+b equal to c')
  int datalen;                  // length of data in bytes
  u_long haddr, paddr;          // dotted addr of host and parasite
  int hport, pport;             // IP port of host and parasite
  int ack, seq;                 // acknowledge and sequence numbers

  // ... init code omitted ...
  raw = initCommo(host);
  getIPpacket(raw, haddr, hport, pport, &ack, &seq);
  checksum = computeTCPchecksum((char*)answer, sizeof(u_short)*datalen, paddr,
                       pport, haddr, hport, ackRead, seqRead+1 , ACK|PSH);
  transmit_TCP(raw, (char*)data, sizeof(u_short)*datalen, checksum paddr, 
                       pport, haddr, hport, ackRead, seqRead+1 , ACK|PSH);
  // if there is a response, the query is true
  rc = getIPpacket(raw, haddr, hport, pport, NULL, NULL);
  printf("Answer is %s\n", rc ? "false" : "true");
}
void initCommo(char *host)
{
  // ... omitted locals ...
  /* create raw read socket */
  raw = socket(AF_INET,SOCK_RAW,IPPROTO_TCP);
  if (raw < 0) {
    perror("socket (raw)");
    exit(-1);
  }
  // set mask to make socket async
  val =  fcntl(rd, F_GETFL);
  val |= O_NDELAY;
  if ( fcntl(raw, F_SETFL, val) < 0 ) {
    perror("fcntl");
    exit(1);
  }
  // create and connect to a tcp socket
  // use address family INET and STREAMing sockets (TCP)
  // ... details omitted ...
  s = socket(AF_INET, SOCK_STREAM, 0);
  rc = bind(s, (struct sockaddr *)&sin, sizeof(sin));
  rc = connect(s, (struct sockaddr *)&sin, sizeof(sin));
}
int getIPpacket(int sock, u_long haddr, int hport, int pport, 
                                           int *ack, int *seq)
{
  // ... omitted locals ...
  // raw socket is async and next IP packet may not be from host
  // so may need to read socket several times 
  while (wait < pause) {
    nbytes = recv(sock, buf, 10000, 0);
    if (nbytes < 0) {
      if (errno == EWOULDBLOCK) {       // async: nothing to read, try again
        if (++wait > pause)             
          return -1;
        sigpause(0);
        continue;
      }
      perror("recv");
      exit(-1);
    }
    // check host
    if (buf[12] != host[0] || buf[13] != host[1] ||
        buf[14] != host[2] || buf[15] != host[3]) {
      if (Verbose)
        printf("skipping %u.%u.%u.%u\n",buf[12],buf[13], buf[14], buf[15]);
      continue;
    }
    // check host port
    offset = (buf[0]&0xf)*4;
    tmp = (buf[offset]<<8)+buf[++offset];
    if (hport != tmp) {
      if (Verbose) printf("skipping\n");
      continue;
    }
    // check parasite port
    if (pport != tmp) {
      if (Verbose) printf("skipping\n");
      continue;
    }
    if (proto == 6) {              // buf[9] is proto; TCP is 6
      if (ack && seq) {
        // copy ack and seq numbers out of TCP header
        *ack = LONG(buf+4);
        *seq = LONG(buf+8);
      }
      return 0;
    }
    else
      continue;
  }
  return -1;                     // not reached
}
void transmit_TCP (int fd, char *sp_data, int datalen, u_long paddr, 
            int pport, u_long haddr, int hport, int ack, int seq, int flags)
{
  // ... most locals omitted ...
  char buffer[1500];
  struct sockaddr_in sockaddr;
  // setup IP header fields in buffer
  // set TCP header fields in buffer
  return sendto(fd, buffer, datalen + TCP_BASE + IP_BASE +  ipOptLen, 0,
                                     &sockaddr, sizeof(struct sockaddr));
}

Back to Article