The AltaVista Tunnel:
`Using the Internet to
`Extend Corporate
`Networks
`
`The public Internet has become a low-cost
`connection medium for joining remote employ-
`ees or offices to a private intranet and for per-
`mitting impromptu high-speed connections
`between business partners. This connectivity
`is offset by a significant loss in security. The
`AltaVista Tunnel, a DIGITAL product, offers
`secure network-level routing over Internet
`connections by combining two well-known
`networking technologies: tunneling and secure
`channels. This paper discusses the design and
`implementation of the AltaVista Tunnel and
`describes our experience in deploying the
`product within DIGITAL.
`
`Kenneth F. Alden
`Edward P. Wobber
`
`The public Internet is fast becoming a ubiquitous and
`inexpensive medium for connecting remote employ-
`ees or offices to a private intranet or for permitting
`impromptu high-speed connections between business
`partners. This gain in connectivity is offset by a signifi-
`cant loss in security, however. The Internet is notori-
`ous for electronic break-ins and eavesdropping.
`The AltaVista Tunnel, a DIGITAL product, offers
`network-layer routing over secure Internet connec-
`tions. This allows, for example, a mobile user to con-
`nect securely to his or her corporate network using the
`Internet. Similarly, a corporate network can employ
`the AltaVista Tunnel to securely link remote offices
`with Internet connections. Although our product uses
`the Internet for packet transport, all traffic is encapsu-
`lated within cryptographically secured connections.
`Because the AltaVista Tunnel is a network-layer
`router, client applications can run without modifica-
`tion. Moreover, our product is firewall independent
`and therefore can be used in concert with most com-
`mon firewalls. The AltaVista Tunnel supports both
`static connections to remote offices and intermittent
`connections to single-user machines. Currently, imple-
`mentations exist for the UNIX, Windows 95, and
`Windows NT platforms.
`In this paper, we begin with an overview of the ben-
`efits and pitfalls presented by using the Internet for
`private network connectivity. Next, we describe the
`design of the network protocol used by the AltaVista
`Tunnel, with a particular focus on the security concerns
`that led to this design. We then discuss how we imple-
`mented our design. Finally, we briefly describe our
`experience deploying the tunnel product in a large cor-
`porate network, provide performance data, and discuss
`some of the security risks this technology entails.
`
`Overview
`
`Before the Internet became pervasive, corporate net-
`works were built from leased and dial-in telephone
`lines. Such networks carried substantial costs for both
`communications equipment and telephone service.
`Usually, security relied on the inaccessibility of the
`physical medium, and over the years, the risk of wiretap
`has proved to be slight when compared to password
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`5
`
`Petitioner Apple Inc. - Exhibit 1022, p. 1
`
`

`
`cracking or other higher-level attack. The reason for
`this is that most telephone systems are both proprietary
`and centrally managed, and they are therefore not easy
`to subvert in the large without a substantial budget.
`The Internet brings opportunity and challenge to
`the modern corporate network designer. Global con-
`nectivity makes it possible to replace expensive leased
`lines and communications equipment with Internet
`connections. However, such connections lack the
`physical security of telephone lines. Furthermore,
`direct connection to the Internet poses numerous,
`well-documented security problems. Consequently,
`many organizations find it necessary to isolate their
`private networks behind firewalls—filtering routers
`that place constraints on packets allowed to pass
`between protected and public networks. The policy
`decisions made in configuring firewalls always involve
`a difficult trade-off between security and functionality.
`Cryptography makes it possible to emulate most of
`the properties of physically secure wire using Internet
`connections. When encapsulated at a suitable protocol
`level, cryptographically secured data can be allowed to
`traverse firewalls without substantially weakening
`security policy. However, the encapsulation protocol
`must require no implicit trust in the router nodes and
`links that make up the fabric of the insecure network.
`To solve this problem, the protocol employed by
`the AltaVista Tunnel uses a synthesis of two well-
`understood networking constructs: tunneling proto-
`cols1 and secure channels.2
`
`Protocol Design
`
`In computer networks, tunneling is the act of encapsu-
`lating one communications protocol within another.
`For example, a DECnet-in-IP tunnel might transport
`DECnet datagrams over an Internet Protocol (IP) net-
`work using IP datagrams. In this arrangement, IP
`datagrams act only as a transport mechanism—there is
`no need for the active nodes in the IP network to inter-
`pret or to manipulate the encapsulated DECnet pack-
`ets. A tunnel alone, however, cannot guarantee that an
`
`intermediate node (“man-in-the-middle”) will not
`intentionally read or modify the data portions of tun-
`neled packets. To prevent such unwanted tampering,
`we cryptographically secure encapsulated packets for
`passage over the public network. Abstractly, data
`passed over this secure channel appears once and
`only once at the receiver as sent by the sender.
`Furthermore, an attacker observing the public net-
`work cannot read this data. Thus, tunnel encapsula-
`tion ensures that private-network datagrams cannot
`interact with the routing algorithms of the public net-
`work, whereas secure channels guarantee that the tun-
`neled data arrive intact from an authenticated source
`and that privacy is maintained.
`Figure 1 depicts a secure tunnel in operation. Nodes
`A and B are tunnel endpoints, that is, packet routers
`that forward to and from tunneled routes. Node A
`processes datagrams in private network X and deter-
`mines which, if any, should be routed to private net-
`work Y. Node A then encapsulates all such datagrams
`and sends them securely across its tunnel connection
`to node B. Node B checks the integrity of each trans-
`mission and then decapsulates and forwards the
`datagrams to network Y. The process is symmetric,
`although this is not pictured.
`These methods can be used to connect any sort of
`private network; however, our product is specifically
`designed to connect IP networks by tunneling IP data-
`grams. Given the dominance of IP in the network mar-
`ketplace, the choice of network type is easy. The choice
`of protocol from which to construct tunnel connec-
`tions is more difficult. There are three obvious can-
`didates: IP, User Datagram Protocol (UDP), and
`Transmission Control Protocol (TCP).
`Since IP is a network protocol, there is no notion of
`port-level addressing. This implies that IP-in-IP tun-
`nels must be implemented very close to the operating
`system, and any multiplexing of tunnel connections
`must be explicitly added. Since our goal was for our
`tunneling product to be firewall and operating system
`independent, we rejected IP in favor of a higher-level
`protocol.
`
`NETWORK X
`
`TUNNELED
`IP PACKET
`
`NETWORK Y
`
`NODE B
`
`IP
`PACKET
`
`FIREWALL
`FIREWALL
`
`IP
`PACKET
`
`INTERNET
`
`FIREWALL
`
`IP
`PACKET
`
`NODE A
`
`Figure 1
`A Secure Tunnel in Operation
`
`6
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`Petitioner Apple Inc. - Exhibit 1022, p. 2
`
`

`
`The choice between UDP and TCP depends on
`whether datagrams or byte streams best apply to tun-
`neling. Since our application is inherently connection
`oriented, TCP offers a natural fit, while any UDP
`design must include an explicit means for reliable con-
`nection maintenance. In addition, byte streams elimi-
`nate constraints caused by packet boundaries, so
`fragmentation and maximum size determination pose
`few difficulties. Furthermore, byte streams enable
`forms of cryptography and data compression that
`would be awkward to implement using datagrams. Of
`course this flexibility does not come without cost. TCP
`adds an extra layer of reliable transmission, and per-
`packet headers are large.
`The previous discussion lends no clear advantage to
`either protocol option. We chose to implement the
`AltaVista Tunnel using IP-in-TCP in order to simplify
`firewall security policy. As shown in Figure 2, a tunnel
`connection usually traverses at least one firewall. In
`practice, a tunnel virtual connection is composed of
`several distinct TCP connections laid end-to-end.
`Where TCP connections meet, there is a bidirectional
`relay process that shuffles packets in either direction.
`Such a relay service is included with most firewalls.3
`We also offer an intelligent relay that participates in the
`tunnel connection protocol and therefore allows more
`flexibility in choosing destination endpoints.
`By using TCP connections and relays, we minimize
`the policy changes required to permit tunnel traversal.
`All that is necessary is to enable TCP connections
`between the tunnel endpoint, which is on the private
`network, and the relay, which is just outside the fire-
`wall. (Note that relays are logically outside the firewall,
`although they might be implemented on the firewall
`machine.) Whether a generic or an intelligent relay is
`used, firewall-traversal connections always originate
`on a locally controlled network. Furthermore, TCP
`connection requests are infrequent, and therefore
`TCP traversals are more tractable to log at the firewall
`than are datagrams. Although the firewall industry has
`begun to develop standards for IP-in-IP tunnels,4–6 our
`choice of IP-in-TCP gives us the clear advantage
`
`that tunnel endpoints need not be packaged with
`or dependent on a specific firewall implementation.
`Eventually, the emerging standards will probably pre-
`vail for static tunnels; however, no standards exist for
`transient (mobile) users and our solution remains
`quite viable.
`
`Implementation
`
`As with many tunnel implementations,1 we provide
`tunneling by tricking the operating system’s routing
`layer into forwarding packets to an emulated network
`device. This device does not transmit packets directly,
`but rather it encapsulates them as data within a higher-
`level protocol. The AltaVista Tunnel implementation
`contains three major components: the tunnel applica-
`tion, the protocol handler, and the pseudo-device dri-
`ver. The main function of the tunnel application is to
`interact with the user or system administrator and to
`modify the system routing tables to make tunneled
`routes available. This code also maintains a database of
`acceptable partner endpoints and matching crypto-
`graphic keys. The protocol handler implements the
`tunnel encapsulation protocol and all associated cryp-
`tography. The pseudo-device driver is responsible for
`redirecting packets from the local IP stack to the
`encapsulation protocol handler and vice versa.
`Figure 3 shows how the components of the
`AltaVista Tunnel cooperate to process tunneled IP
`packets. The diagram depicts a single-user client and a
`tunnel server. Although the same basic structure
`applies to all tunnel endpoint software, there are sub-
`stantial differences between single-user and server con-
`figurations, and between the UNIX and Windows
`implementations. For example, the single-user version
`usually runs only while the user is actively connected.
`On the server side, the tunnel application is a daemon
`process that continuously waits for connection requests
`and services existing connections. The following three
`sections discuss the individual system components in
`detail and, where appropriate, point out the differences
`between the various software configurations.
`
`SINGLE-USER
`TUNNEL
`
`RELAY
`
`FIREWALL
`
`TUNNEL
`SERVER
`
`TCP
`
`TCP
`
`INTERNET
`
`LOCALLY
`CONTROLLED
`NETWORK
`
`PRIVATE
`NETWORK
`
`Figure 2
`Tunnel with Intelligent Relay
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`7
`
`Petitioner Apple Inc. - Exhibit 1022, p. 3
`
`

`
`SINGLE-USER TUNNEL
`
`TUNNEL SERVER
`
`TUNNEL APPLICATION
`
`USER
`APPLICATIONS
`
`TUNNEL APPLICATION
`
`PROTOCOL
`HANDLER
`
`IP STACK
`
`PROTOCOL
`HANDLER
`
`PSEUDO-DEVICE
`
`NETWORK
`DEVICE
`
`PSEUDO-DEVICE
`
`IP STACK
`
`NETWORK
`DEVICE
`
`INTERNET
`
`PRIVATE NETWORK
`
`KEY:
`
`ENCRYPTED
`UNENCRYPTED
`
`Figure 3
`System Components and Data Flow
`
`The Tunnel Application
`
`The primary function of the tunnel application is to
`present a user interface (UI). Although each instantia-
`tion of the user interface is slightly different, the func-
`tion of the application remains the same. The
`AltaVista Personal Tunnel ’97, a single-user configura-
`tion, offers a straightforward graphical user interface
`(GUI) (see Figure 4) that allows the user to register a
`set of target tunnel servers, select from this set, and
`then establish and tear down connections. The
`emphasis is on simplicity. A tunnel connection may be
`started from either a command line interface or the
`GUI. If the GUI is used to start a tunnel, the GUI win-
`dow can be minimized and ignored until the end of
`the tunnel session. The application logs all interesting
`events, reflects current state through the user inter-
`face, and notifies the user of exceptional events. In this
`configuration, only traffic from local applications is
`directed over the tunnel, and no inbound tunnel con-
`nection requests are accepted.
`In the server configuration, the tunnel application is
`significantly more complicated. The primary function
`of the server code is to restrict tunnel access to autho-
`rized clients. To achieve this, the server application is
`also responsible for issuing cryptographic credentials
`and maintaining an authorization database. In addi-
`tion to accepting connections, a tunnel server is capa-
`ble of initiating them. In the “workgroup” tunnel
`configuration, two servers cooperate to maintain a
`permanent connection, for example between a corpo-
`rate network and a remote office local area network
`(LAN). A tunnel server is a full-fledged router—its job
`is to forward packets from the protected network into
`the tunnel and vice versa. We offer servers for both the
`UNIX and the Windows NT environments.
`
`8
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`Routing
`As mentioned in the Implementation section, our tun-
`nel works by manipulation of the system routing table.
`In some environments, such as Windows 95, there is
`no fully integrated notion of packet routing (some-
`times called IP forwarding). However, there is support
`for multiple network devices. Each network device has
`a uniquely assigned IP address so that the IP stack can
`determine which device to use when transmitting
`packets. The AltaVista Tunnel pseudo-device appears
`to the operating system as just another network
`device. There is a one-to-one relationship between
`tunnel connections and pseudo-devices. During con-
`nection establishment, the tunnel application activates
`a pseudo-device and modifies the routing table to
`include any newly reachable private network or net-
`works. The application then restores the original state
`upon termination of the connection.
`The tunnel server is implemented in a richer routing
`environment. Each server typically routes an entire IP
`class-C subnetwork (254 addresses) but may support
`partial subnetworks or multiple networks as well. A
`tunnel server can maintain multiple connections, and
`this is accomplished by assigning a different IP address
`to each pseudo-device/tunnel connection. IP pseudo-
`device addresses at both ends of the tunnel are assigned
`dynamically or statically from a pool of IP addresses
`controlled by the server. The operating system, com-
`bined with a routing management program such as
`gated,7 performs all necessary route propagation. As
`discussed in the next section, each tunnel user can be
`restricted to a specific set of IP addresses. This approach
`allows network managers to establish routing policy
`based on user class. To obtain fine-grain control over
`a given tunnel connection, the server can also run a
`packet-filtering program such as screend8 to restrict the
`IP protocols entering and exiting that tunnel.
`
`Petitioner Apple Inc. - Exhibit 1022, p. 4
`
`

`
`Figure 4
`The AltaVista Personal Tunnel ’97 User Interface
`
`Key Management and Access Control
`In practice, a secure channel protocol is only as strong
`as the techniques it employs for naming and key distri-
`bution. In the AltaVista Tunnel system, we must name
`both tunnel servers and human users. (Tunnel users
`must be authenticated by name, not by IP address,
`since many users acquire IP addresses dynamically from
`their Internet service provider.) Because no ubiquitous
`infrastructure exists to support such a namespace, our
`software currently assumes a flat, server-specific nam-
`ing structure, much in the style of PGP.9 We use RSA
`public-key cryptography10 to establish secure connec-
`tions. Each tunnel endpoint maintains a key file that
`contains a sequence of names and matching public
`keys—one (name, key) pair per potential destination.
`Each key file also contains the password-encrypted pri-
`vate key of its maintainer. The key file is signed by this
`private key to prevent tampering. Note that the com-
`promise of any given (nonserver) key file does not
`affect the security of other endpoints. Although we
`
`could have obtained a similar result with symmetric key
`encryption, we believe that the current design will
`allow our system to scale up gracefully through the
`addition of public key certification.
`When a new user is registered, the tunnel server
`generates a new RSA key and key file for that user. The
`user’s public key is inserted into the server’s key file,
`and conversely, the server’s key is inserted into the
`user’s key file. To obtain enough randomness for key
`generation, we carefully measure the elapsed time (in
`machine instructions) to perform each of a sequence
`of disk seeks. These results are then hashed to provide
`a seed for a pseudorandom number generator. There is
`substantial evidence that the air turbulence between
`hard-disk heads and platters contributes sufficient ran-
`domness for such purposes.11
`Both single-user and server tunnel applications use
`key files, and the credentials stored therein, as a mini-
`mum requirement for successful authentication and
`authorization. Our server software places additional
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`9
`
`Petitioner Apple Inc. - Exhibit 1022, p. 5
`
`

`
`constraints on incoming connection requests. In addi-
`tion to recording a new user’s public key, tunnel
`servers maintain a small set of tunnel configuration
`parameters for each user. These parameters define the
`range of IP address pairs that can be assigned to the
`server and client pseudo-device, the set of network
`routing entries that are passed from server to client at
`tunnel formation, and the minimum level of encryp-
`tion strength permitted for a tunnel connection.
`Creating or initiating a tunnel connection can be a
`complex task, considering the network path the tunnel
`connection might traverse. This path can include two
`intelligent relays, any number of generic TCP/IP
`relays, and a final tunnel endpoint. Requiring the user
`to remember such a path would have made the tun-
`nel exceedingly difficult to operate. Therefore, the
`AltaVista Tunnel stores this information in an external
`configuration file. Each new user receives both a con-
`figuration file and a key file to initialize a newly
`installed tunnel application. These files provide all the
`data necessary to run the tunnel application—the user
`need only press the connect button.
`
`The Protocol Handler
`
`n
`
`The AltaVista Tunnel protocol handler is responsible
`for establishing secure virtual connections between tun-
`nel endpoints and for encapsulating and transmitting
`redirected IP packets as data. These connections are vir-
`tual in that they are composed of several distinct TCP
`connections joined by relays. Upon the establishment of
`each new virtual connection, the tunnel endpoints
`engage in a dialog to agree on security parameters for
`that connection. For our purposes, a secure connection
`must have at least the following properties:
`n Authenticity—Data received over the channel orig-
`inates at a known sender.
`Integrity—Data received over the channel cannot
`be modified in transit.
`n Exactly-once delivery—Each datum is received once
`and only once.
`n Privacy—An attacker may not learn the contents of
`transmitted data by observing the network.
`We use cryptography to provide these properties. As
`discussed in the previous section, key files form the
`long-term basis for trust between tunnel endpoints.
`Prior to transmitting data, the parties must perform
`mutual authentication and agree on a key length, a set
`of cryptographic algorithms, and a shared encryption
`key. It is important that keys be negotiated periodi-
`cally, since this minimizes the benefit an attacker can
`gain from breaking a specific key. In the current
`AltaVista Tunnel, we perform the very simple key
`exchange shown in Figure 5.2
`
`1. A sends to B: A, B, {Pab}, Kb-1(Sa)
`
`2. B sends to A: B, A, {Pba}, K a-1(Sb)
`
`
`A and B compute: Pk = Best ({Pab} ^ {Pba})
`A and B compute: S = Sa ⫹ Sb
`⫹
`A and B compute: K = Reduce (Pk, S)
`
`Figure 5
`Tunnel Key Exchange Protocol
`
`Figure 5 describes our key exchange protocol; K-1( )
`signifies encryption with the public component of an
`RSA key pair. Suppose tunnel nodes A and B wish to
`share an encryption key. Both can determine their
`partner’s public key from their local key file. As shown
`in Figure 5, node A invents a random number Sa,
`encrypts it with node B’s public key, and sends it to
`node B’s network address. This message also includes
`{Pab}, a set of proposed cryptographic algorithms and
`key lengths that node A considers acceptable for com-
`municating with node B. Upon receipt of message 1,
`node B similarly constructs and sends response 2.
`Now nodes A and B can choose Pk, a negotiated
`choice of key length and algorithm, by intersecting
`sets {Pab} and {Pba} and then selecting the best available
`option using an a priori ranking. Both parties can also
`compute S, a shared key seed, by decryption and
`exclusive OR. Finally, nodes A and B can produce a
`shared key by reducing the shared seed to a key in a
`manner specific to Pk. For simplicity, this protocol is
`executed for every new connection, and by default, a
`new connection is established every 30 minutes. This
`technique guarantees that the active key is updated
`frequently.
`Our protocol succeeds because only node B can
`decrypt message 1, and only node A can decrypt mes-
`sage 2. As a result, both parties can believe that K is
`known only to each other. An intermediate node can-
`not control the negotiated key by intercepting mes-
`sage 1 and then retransmitting a modified version to
`node B. (Note that this represents a denial-of-service
`attack.) Both node A and node B, however, must take
`some care in choosing their algorithm proposals. An
`intermediate node can force the resultant connection
`parameters P to be the weakest proposal jointly accept-
`able to both parties. This problem would be elimi-
`nated if messages 1 and 2 were cryptographically
`signed at their origin.
`Once the key exchange is complete, it is easy to see
`how to achieve the essential properties of secure con-
`nections. We sign all transmitted data by appending
`the output of a keyed hash function under K, where a
`keyed hash function (such as the one described by
`
`10
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`Petitioner Apple Inc. - Exhibit 1022, p. 6
`
`

`
`Krawcyzk et al.12) is a cryptographic hash of data that
`incorporates a shared secret. This signature guarantees
`the authenticity of the data (more specifically, the
`signer must know K) and ensures that any in-transit
`modification will be detected. Once-only delivery is
`guaranteed by including a monotonically increasing
`sequence number in the keyed hash. Since TCP
`sequence numbers are not secure, an attacker could
`otherwise insert previously sent data into the data
`stream. Finally, privacy is obtained by applying a sym-
`metric cipher, such as the RC4 algorithm,13 to all tun-
`neled datagrams using K to initialize the keying
`material. Note that since our transport is reliable, hav-
`ing no missing data or out-of-order delivery, it is easy
`to use a stream cipher for this purpose. Similarly, com-
`pression state can be maintained over the lifetime of
`a connection. This allows for efficient compression of
`data prior to encryption, although we have yet to
`implement this.
`To implement virtual connection establishment and
`data encapsulation, we segment the data stream into
`typed command frames. Using these command frames,
`we implement a straightforward protocol for relay
`activation, connection establishment, key exchange,
`data transmission, failure detection, and connection
`teardown. Since the data stream is reliable, this proto-
`col is quite simple. Moreover, the data carried by key
`exchange packets is opaque from the point of view of
`the connection protocol, and key exchange can
`encompass multiple round-trips. Therefore, the basic
`mechanism we use to establish tunnel connections
`should support other forms of cryptographic creden-
`tials and negotiation as new standards for naming,
`trust management, and key exchange emerge.
`In the UNIX server, the protocol handler is imple-
`mented as part of the tunnel server daemon, which
`runs in user space. In the Windows environment, we
`found that tunneling could not be implemented in user
`space. Under certain circumstances, the Windows file
`system can perform remote operations while holding
`critical system locks. Since the tunnel application can-
`not run while these locks are held, deadlock ensues.
`Therefore, we implement the Windows protocol han-
`dler in kernel space, alongside the pseudo-device driver.
`This approach also improves performance by eliminat-
`ing the need to copy data to user space.
`
`The Pseudo-Device Driver
`
`In the AltaVista Tunnel, the pseudo-device driver’s
`sole purpose is to redirect outgoing IP packets to the
`tunnel protocol handler and to reintroduce incoming
`packets from the protocol handler to the IP stack.
`Once the tunnel application has set up and authenti-
`cated a tunnel connection, it activates the pseudo-
`device driver to enable redirection of the tunnel
`packets into and out of the connection. During activa-
`
`tion, the IP stack recognizes the new network device
`and updates the routing table to reflect any newly
`available routes.
`Because of differences in networking architectures,
`the implementation of this driver is very simple on the
`UNIX platform and quite complex on the Windows
`95 and Window NT platforms. Our initial attempt to
`implement the Windows pseudo-device emulated an
`Ethernet LAN. This design became overly baroque
`due to the need to emulate LAN services such as the
`Address Resolution Protocol (ARP).14 Recently, the
`pseudo-device in AltaVista Tunnel ’97 was redesigned
`to closely resemble a dial-up network adapter, thereby
`eliminating the need for LAN emulation. We describe
`all these implementations in this section.
`
`UNIX Pseudo-Device
`On the UNIX platform, the pseudo-device driver is a
`straightforward emulation of a network device. The
`back end of this network device communicates with a
`user-level process through a socket interface. The sim-
`plicity of this design comes from the fact that the UNIX
`IP stack delivers packets to network devices without
`additional encapsulation. Since the physical device layer
`takes care of Ethernet Media Access Control (MAC)
`encapsulation, the emulated network device does not
`have to deal with complexities such as ARP14 process-
`ing. The UNIX tunnel application uses the ifconfig
`program to activate the pseudo-device, assign an IP
`address to the device, and insert the address into the
`routing table.
`
`Windows Pseudo-Device
`The first release of the Windows 95 tunnel pseudo-
`device was considerably more complex than its UNIX
`counterpart. Under the Windows operating system,
`most 32-bit network device drivers are implemented
`using the Network Device Interface Specification.15
`This application programming interface (API) is tai-
`lored to handle physical devices, not abstract IP inter-
`faces. In the Windows environment, the network stack
`must have considerable knowledge of the physical net-
`work. For example, the stack must implement the
`MAC protocols necessary to transmit a packet on a
`supported medium. As a result, our initial implemen-
`tation of a network pseudo-device emulated a com-
`plete Ethernet LAN, including a gateway host that
`provides ARP and dynamic addressing services, as
`shown in Figure 6.
`Every Ethernet device has a unique hardware or
`MAC address. When IP packets are sent over the
`Ethernet, they are transmitted using these hardware
`addresses. IP packets with a destination address off the
`local LAN must be sent to a gateway host router
`located on the LAN. The tunnel pseudo-device creates
`an illusion of the complete LAN, including the gate-
`way host, within the device driver and assigns the IP
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`11
`
`Petitioner Apple Inc. - Exhibit 1022, p. 7
`
`

`
`OPERATING SYSTEM
`
`TCP/IP STACK
`
`TCP/IP
`TRANSMIT
`FUNCTION
`
`TCP/IP
`RECEIVE
`FUNCTION
`
`TRANSMITTED
`NETWORK PACKETS
`
`RECEIVED
`NETWORK PACKETS
`
`PSEUDO-DEVICE
`
`ARP EMULATOR
`DHCP EMULATOR
`(VERSION 1.0 ONLY)
`
`TRANSMIT
`PATH
`
`RECEIVE
`PATH
`
`ENCAPSULATION
`
`DECAPSULATION
`
`ENCRYPTION
`
`DECRYPTION
`
`REAL NETWORK ADAPTER
`(SENDS AND RECEIVES
`PACKETS ON THE
`PHYSICAL NETWORK)
`
`Figure 6
`Control Flow in the Windows Pseudo-Device
`
`address of the remote tunnel server pseudo-device to
`this emulated host. The IP stack is fooled into believing
`there are two nodes on the emulated network LAN—
`the tunnel client, which provides the local node, and
`the tunnel server as the gateway host to the real net-
`work or networks on the other side of the tunnel.
`When the IP stack prepares to transmit a packet, it
`must know the MAC address of the destination or the
`gateway host. If the stack does not know the MAC
`address, it transmits an ARP packet to the pseudo-
`device. The pseudo-device responds only to ARP
`requests for the gateway host MAC address. To resolve
`this ARP request, the driver includes the functionality
`of an ARP server. Note that the MAC address must
`be unique to prevent a conflict with the MAC address
`of a real device. Clearly, no Ethernet device will ever
`contain a MAC address of 08-00-2B-00-00-01 or
`08-00-2B-00-00-02, which are the first two Ethernet
`addresses that Digital Equipment Corporation ever
`assigned. In the AltaVista Tunnel, the first of these
`addresses always serves as the pseudo-device MAC
`address; the second serves as the MAC address of the
`gateway host.
`
`12
`
`Digital Technical Journal
`
`Vol. 9 No. 2 1997
`
`The network pseudo-device in AltaVista Tunnel ’97
`is simple by comparison. With help from Microsoft,
`our implementation is now able to emulate a Windows
`dial-up adapter rather than a LAN. Dial-up adapters
`are treated specially by the Windows IP stack. No ARP
`packets are directed at dial-up devices, only one emu-
`lated address must be maintained, and information
`about gateways and dynamic IP addressing can be
`supplied after link establishment. This, of course,
`perfectly matches the tunnel’s operating environment.
`The control flow outlined in Figure 6 correctly
`describes the operation of this new pseudo-device
`implementation; however, as noted, ARP and dynamic
`address emulation is no longer required.
`
`Dynamic IP Address Binding
`Each tunnel is uniquely identified by the IP addresses
`assigned to the pseudo-device at each endpoint. The
`tunnel server uses a separate pseudo-device for each
`active tunnel. The tunnel server implementation could
`have used a single IP address and pseudo-device for
`multiple tunnels, because each client is unaware of any
`other’s existence. However, that would have required
`
`Petitioner Apple Inc. - Exhibit 1022, p. 8
`
`

`
`additional routing complexity at the tunnel server. By
`using unique address pairs, the routing tables on both
`the client and server can be maintained easily without
`platform-specific software. This design also permits
`conventional packet filtering on the tunnel server. The
`tunnel address space can be a valid, externally visible or
`hidden network, thereby supplying an almost unlim-
`ited number of addresses.
`To facilitate a very large number of registered users
`for any given tunnel server, we implement dynamic
`reuse of address pairs. Since dynamic addresses are
`negotiated at connect time, we need to bind IP
`addresses to pseudo-devices after tunnel connection
`establishment. For the Windows platform, we use the
`Transport Driver Interface (TDI)16 from within the
`pseudo-device driver to perform both dynamic
`address assignment and routing table modification.
`
`Performance and Experience
`
`Tunneling does add overhead to data tra