David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`Hiding Routing Information
`
`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson
`
`Naval Research Laboratory, Center For High Assurance Computer Systems,
`Washington, D.C.  - , USA, phone: + ..  , fax: + .. ,
`e-mail: flast nameg@itd.nrl.navy.mil.
`
`Abstract. This paper describes an architecture, Onion Routing, that
`limits a network’s vulnerability to trac analysis. The architecture pro-
`vides anonymous socket connections by means of proxy servers. It pro-
`vides real-time, bi-directional, anonymous communication for any proto-
`col that can be adapted to use a proxy service. Specically, the architec-
`ture provides for bi-directional communication even though no-one but
`the initiator’s proxy server knows anything but previous and next hops
`in the communication chain. This implies that neither the respondent
`nor his proxy server nor any external observer need know the identity
`of the initiator or his proxy server. A prototype of Onion Routing has
`been implemented. This prototype works with HTTP World Wide Web
`proxies. In addition, an analogous proxy for TELNET has been imple-
`mented. Proxies for FTP and SMTP are under development.
`
` Introduction
`
`This paper presents an architecture that limits a network’s vulnerability to traf-
`c analysis. We call this approach Onion Routing , because it relies upon a lay-
`ered object to direct the construction of an anonymous, bi-directional, real-time
`virtual circuit between two communicating parties, an initiator and responder .
`Because individual routing nodes in each circuit only know the identities of adja-
`cent nodes as in  , and because the nodes further encrypt multiplexed virtual
`circuits, studying trac patterns does not yield much information about the
`paths of messages. This makes it dicult to use trac analysis to determine
`who is communicating with whom.
`Onion Routing provides an anonymous socket connection through a proxy
`server. Since proxies are a well dened interface at the application layer  , ,
`and many protocols have been adapted to work with proxy servers in order to
`accommodate rewalls, Onion Routing can be easily used by many applications.
`Our prototype works with HTTP World Wide Web proxies. In addition, a
`proxy for TELNET has been implemented.
`Trac analysis can be used to help deduce who is communicating with whom
`by analyzing trac patterns instead of the data that is sent. For example, in
`most networks, it is relatively easy to determine which pairs of machines are
`communicating by watching the routing information that is part of each packet.
`Even if data is encrypted, routing information is still sent in the clear because
`routers need to know packets’ destinations, in order to route them in the right
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 1
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`direction. Trac analysis can also be done by watching particular data move
`through a network, by matching amounts of data, or by examining coincidences,
`such as connections opening and closing at about the same time.
`Onion Routing hides routing information by making a data stream follow a
`path through several nodes en route to its destination. The path is dened by
`the rst node, which is also a proxy for the service being requested e.g., HTTP
`requests. Therefore, this ProxyRouting Node is the most sensitive one, so sites
`that are concerned about trac analysis should also manage a ProxyRouting
`Node. We will see later that it is important that this ProxyRouting Node also
`be used as an intermediate routing node in other virtual circuits. Although the
`compromise of all routing nodes compromises the hiding, one uncompromised
`routing node is sucient to complicate trac analysis. Figure illustrates the
`topology of an Onion Routing network with ve nodes, one of which W  is the
`ProxyRouting node for the initiator’s site.
`
`Secure Site
`
`Internet
`
`W is a Proxy/Routing Node
`controlled by Secure Site
`
`W
`
`X
`
`U
`
`Initiator
`Machine
`
`Y
`
`Z
`
`Responder
`Machine
`
`Link Encrypted Connection Between Routing Nodes
`
`Routing Node
`
`Routing/Proxy Node
`
`Fig. . Routing Topology.
`
`The goal of Onion Routing is not to provide anonymous communication.
`Parties are free to and usually should identify themselves within a message. But
`the use of a public network should not automatically give away the identities and
`locations of the communicating parties. For example, imagine a researcher who
`uses the World Wide Web to collect data from a variety of sources. Although each
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 2
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`piece of information that he retrieves is publicly known, it may be possible for an
`outside observer to determine his sensitive interests by studying the patterns in
`his requests. Onion Routing makes it very dicult to match his HTTP requests
`to his site.
`Anonymous re-mailers ,  attempt to limit the feasibility of trac analysis
`by providing an anonymous store and forward architecture. To prevent replay
`attacks, re-mailers keep a log of sent messages. These two characteristics make
`the anonymous re-mailer approach unsuitable for HTTP applications, as HTTP
`requests would both generate an enormous log and require bi-directional commu-
`nication. Anonymous ISDN  has even more severe real-time and bi-directional
`requirements than HTTP, but, the architecture of an ISDN network is consider-
`ably dierent from the architecture of the Internet .
`Onion Routing provides bi-directional communication, without requiring that
`the responder know the initiator’s identity or location. Individual messages are
`not logged. In addition, Onion Routing is easily adapted to electronic mail.
`Messages can include Reply Onions that permit a later reply to the sender
`without knowing his address and without keeping the original virtual circuit
`open.
`The rest of the paper is organized in the following way: Section  presents
`background information. Section describes the Onion, the object that directs
`the construction of the virtual circuit. Section  describes the construction and
`use of these virtual circuits. Section  describes the vulnerabilities in the Onion
`Routing architecture. Section  presents some concluding remarks.
`
` Background
`
`Chaum   denes a layered object that routes data through intermediate nodes,
`called mixes. These intermediate nodes may reorder, delay, and pad trac to
`complicate trac analysis. Some work has been done using mixes in ATM net-
`works  .
`Anonymous Remailers like ,  use mixes to provide anonymous e-mail
`services and also to invent an address through which mail can be forwarded back
`to the original sender. Remailers work in a store and forward manner at the mail
`application layer, by stripping o headers at each mix, and forwarding the mail
`message to the next mix. These remailers provide conrmation of delivery.
`In , mixes are used to provide untraceable communication in an ISDN
`network. In a phone system, each telephone line is assigned to a particular local
`switch i.e., local exchange, and switches are interconnected by a long distance
`network. Anonymous calls in ISDN rely upon an anonymous connection within
`each switch between the caller and the long distance network, which is obtained
`by routing calls through a predened series of mixes. The long distance endpoints
`of the connection are then mated to complete the call. Notice that observers can
`tell which local switches are connected. This approach relies upon two unique
`features of ISDN switches. Since each phone line has a subset of the switch’s
`total capacity pre-allocated to it, there is no real cost associated with keeping
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 3
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`a phone line active all the time, either by making calls to itself, to other phone
`lines on the same switch, or to the long distance network. Keeping phone lines
`active complicates trac analysis because an observer cannot track coincidences.
`Also, since each phone line has a control circuit connection to the switch,
`the switch can broadcast messages to each line using these control circuits. So,
`within a switch a truly anonymous connection can be established: A phone line
`makes an anonymous connection to some mix. That mix broadcasts a token
`identifying itself and the connection. A recipient of that token can make another
`anonymous connection to the specied mix, which mates the two connections to
`complete the call.
`Our goal of anonymous socket connections over the Internet diers from
`anonymous remailers and anonymous ISDN. The data is dierent, with real-time
`constraints more severe than mail, but somewhat looser than voice. Both HTTP
`and ISDN connections are bidirectional, but, unlike ISDN, HTTP connections
`are likely to be small requests followed by short bursts of returned data. In a
`local switch capacity is pre-allocated to each phone line, and broadcasting is
`ecient. But broadcasting over the Internet is not free, and dening broadcasts
`domains is not trivial. Most importantly, the network topology of the Internet
`is more akin to the network topology of the long distance network between
`switches, where capacity is a shared resource. In anonymous ISDN, the mixes
`hide communication within the local switch, but connections between switches
`are not hidden. This implies that all calls between two businesses, each large
`enough to use an entire switch, reveal which businesses are communicating. In
`Onion Routing, mixing is dispersed throughout the Internet, which improves
`hiding.
`
` Onions
`
`To begin a session between an initiator and a responder, the initiator’s proxy
`identies a series of routing nodes forming a route through the network and
`constructs an onion which encapsulates that route. Figure  illustrates an onion
`constructed by the initiator’s ProxyRouting Node W for an anonymous route
`to the responder’s ProxyRouting Node Z through intermediate routing nodes
`X and Y . The initiator’s proxy then sends the onion along that route to establish
`a virtual circuit between himself and the responder’s proxy.
`The onion data structure is composed of layer upon layer of encryption
`wrapped around a payload. Leaving aside the shape of the payload at the very
`center, the basic structure of the onion is based on the route to the responder
`that is chosen by the initiator’s proxy. Based on this route, the initiator’s proxy
`encrypts rst for the responder’s proxy, then for the preceding node on the route,
`and so on back to the rst routing node to whom he will send the onion. When
`the onion is received, each node knows who sent him the onion and to whom he
`should pass the onion. But, he knows nothing about the other nodes, nor about
`how many there are in the chain or his place in it unless he is last. What a
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 4
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`X
`
`exp_timex,Y,Ffx,Kfx,Fbx,Kbx,
`Y
`
`exp_timey,Z,Ffy,Kfy,Fby,Kby,
`Z
`
`exp_timez,NULL,Ffz,Kfz,Fbz,Kbz,PADDING
`
`Fig. . A Forward Onion.
`
`node Px receives looks like this
`
`fexp time; next hop; Ff ; Kf ; Fb; Kb;p ayloadgP Kx
`
`Here P Kx is a public encryption key for routing node Px, who is assumed
`to have the corresponding decryption key. The decrypted message contains an
`expiration time for the onion, the next routing node to which the payload is to
`be sent, the payload, and two functionkey pairs specifying the cryptographic
`operations and keys to be applied to data that will be sent along the virtual
`circuit. The forward pair Ff ; Kf  is applied to data moving in the forward
`direction along the route that the onion is traveling the backward pair Fb; Kb
`is applied to data moving in the opposite direction along the onion’s reverse
`route. If the receiving node is the responder’s proxy, then the next hop eld
`is null . For any intermediate routing node the payload will be another onion.
`The expiration time is used to detect replays, which pairs of compromised nodes
`could use to try to correlate messages. Each node holds a copy of the onion
`until exp time. If he receives another copy of the same onion within that time
`he simply ignores it. And, if he receives an onion that has expired, he ignores
`that as well.
`Notice that at each hop the onion shrinks as a layer is peeled o. To avoid
`compromised nodes inferring route information from this monotonically dimin-
`ishing size, a random bit string the size of the peeled o layer is appended to the
`end of the payload before forwarding. No proxy except the last will know how
`much of the payload he receives is such padding because he won’t know where
`
` Depending on certain assumptions about the elds in each onion layer, a naive RSA
`implementation of the simple public key encryption implied by our notation could
`be vulnerable to an attack as described in . In our implementation, this potential
`vulnerability is illusory since the public key is only used to encrypt a secret key, and
`that secret key is used to encrypt the remainder of the message using an ecient
`symmetric algorithm. This also makes for a more ecient implementation than the
`simple, straightforward implementation using only public keys.
` Specifying two pairs of functions unies the virtual circuits that are constructed by
`forward and reply onions. See section . .
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 5
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`he is in the chain. He simply ‘decrypts’ the padding along with the rest of the
`onion. Even a constant size onion might be traced unless all onions are the same
`size, so we x the size of the onion. To maintain this constant size to hide the
`length of the chain from the responder’s proxy, the initiator’s proxy will pad the
`central payload according to the size of the onion, i.e., the number of hops. So,
`when any onion arrives at the responder’s proxy it will always have the same
`amount of padding, either added initially or en route.
`
` . Creating the circuit
`
`The goal in sending the onion is to produce virtual circuits within link encrypted
`connections already running between routing nodes. More details will be given
`in section . An onion occurs as the data eld in one of the presently described
`‘messages’. Such messages contain a circuit identier, a command create, de-
`stroy , and data, and data. Any other command is considered an error, and the
`node who receives such a message ignores that message except to return a destroy
`command back through that virtual circuit. The create command accompanies
`an onion. When a node receives a create command along with an onion, he
`chooses a virtual circuit identier and sends another create message containing
`this identier to the next node and the onion padded with his layer peeled
`o. He also stores the virtual circuit identier he received and virtual circuit
`identier he sent as a pair. Until the circuit is destroyed, whenever he receives
`data on the one connection he sends it o on the other. He applies the forward
`cryptographic function and key obtained from the onion to data moving in the
`forward direction along the route the onion traveled and the backward cryp-
`tographic function and key to data moving in the opposite direction along the
`onion’s reverse route. The virtual circuit established by the onion in gure  is
`illustrated in gure :
`Data sent by the initiator over a virtual circuit is pre-crypted" repeatedly
`by his proxy by applying the inverse of all the forward cryptographic operations
`specied in the onion, innermost rst. Therefore, these layers of cryptography
`will be peeled o as the data travels forward through the virtual circuit. Data
`sent by the responder is crypted" once by his proxy and again by each previous
`node in the virtual circuit using the backward cryptographic operation specied
`at the corresponding layer of the onion. The initiator’s proxy applies the inverse
`of the backward cryptographic operations specied in the onion, outermost rst,
`to this stream, to obtain the plaintext.
`
` . Loose Routing
`
`It is not necessary that the entire route be prespecied by the initiator’s proxy.
`He can instruct various nodes along the route to choose their own route to the
`
` Onions could be used to carry data also, but since onions have to be tracked to
`prevent replay, this would introduce a large cost.
` We dene the verb crypt to mean the application of a cryptographic operation, be
`it encryption or decryption, where the two are logically interchangeable.
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 6
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`Secure Site
`
`Internet
`
`W is a Proxy/Routing Node
`controlled by Secure Site
`
`W
`
`Initiator
`Machine
`
`Fb x,Kb x
`
`Ffx,Kfx
`
`Y
`
`U
`
`X
`
`Fb y,Kb y
`
`Fb z,Kb z
`
`Z
`
`Responder
`Machine
`
`Ffy,Kfy
`
`Ff z,Kf z
`
`Data Flow (with Function/Key Pairs if crypted)
`Unsecured Socket Connection
`Virtual Circuit through Link Encrypted Connection Between Routing Nodes
`Link Encrypted Connection Between Routing Nodes
`
`Routing Node
`
`Routing/Proxy Node
`
`Fig. . A Virtual Circuit.
`
`next prespecied node. This can be useful for security, adding more hops to the
`chain. It could also be used if the initiating proxy does not know a complete,
`connected route to the responder but believes that the node where any break
`occurs can construct a route to the next node. Or, loose routing can be used to
`handle connection changes that occur of which the initiator was unaware. Also,
`since onions are all of xed size, there is a xed maximum length to the route
`from the initiator’s proxy to the responder’s proxy. Loose routing allows us to
`increase the size of that maximum for the same xed onion size. Why this is so
`should become clear presently.
`It is also possible to iterate the loose routing process, allowing nodes on the
`added route to themselves add to the chain. Obviously, we need a mechanism to
`prevent the chain from lengthening indenitely. This can be incorporated into
`the onion structure. An onion for a system that allows for loose routing is as
`follows:
`
`fexp time; next hop; max loosecount; Ff ; Kf ; Fb; Kb;p ayloadgP Kx
`
`If the node receiving this onion decides to loose-route the onion, he prepares
`a new onion with up to max loosecount layers. The payload of this onion is
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 7
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`simply the onion he received with P Kx changed for the last innermost node
`he added to the chain. In other words, he behaves as an initiator’s proxy except
`that his payload is itself already an onion. This node behaves like an initiator’s
`proxy with respect to data also, since he must repeatedly pre- and post- crypt
`data that moves along the diverted route. To keep the onion a constant length
`he must truncate the payload by an amount commensurate with the layers he
`has added to the onion. The initiating proxy must anticipate the amount of
`padding both present initially and any added andor truncated en route that
`will be on the central payload at the time loose routing occurs to allow for this
`truncation. Failure to pre-pad correctly or ignoring an onion’s xed size will
`result in a malformed onion later in the route. The total of the max loosecount
`values occurring in the added layers plus the number of added layers must be
`less than or equal to the max loosecount value that the adding node received.
`
` . Reply Onions
`
`There are applications in which it would be useful for a responder to send back
`a reply after the original circuit is broken. This would allow answers like e-mail
`replies to be sent to queries that were not available at the time of the original
`connection. As we shall see presently, this also allows the responder as well as
`the initiator to remain hidden. The way we allow for these delayed replies is by
`sending a reply onion to accompany the reply. Like the forward onion, it reveals
`to each node en route only the next step to be taken. It has the same structure as
`the forward onion and is treated the same way by nodes en route. Intermediate
`nodes processing an onion cannot dierentiate between forward and reply onions.
`Furthermore, the behavior of the original initiator and responder proxies are the
`same, once the circuit is formed.
`The primary dierence between a forward and a reply onion is the innermost
`payload. The payload of the forward onion can be eectively empty containing
`only padding. The reply onion payload contains enough information to enable
`the initiator’s proxy to reach the initiator and all the cryptographic function and
`key pairs that are to crypt data along the virtual circuit. The initiator’s proxy
`retrieves the keys from the onion. Figure  illustrates a reply onion constructed
`by the initiator’s ProxyRouting Node W for an anonymous route back to him
`starting at the responder’s ProxyRouting Node Z through intermediate routing
`nodes Y and X:
`There is no dierence between virtual circuits established by reply onions
`and forward onions, except that in circuits established by reply onions interme-
`diate routing nodes appear to think that forward points toward the initiator’s
`proxy. But since the behavior of intermediate routing nodes is symmetric, this
`dierence is irrelevant. The terminal ProxyRouting nodes, however, have the
`same behavior in circuits established by forward and reply onions. Therefore, a
`gure of the virtual circuit formed by the reply onion illustrated in gure  would
`be identical to the virtual circuit illustrated in gure even though the circuit
`was formed by the reply onion moving from the responder’s proxy node to the
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 8
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`Z
`
`exp_timez,Y,Fbz,Kbz,Ffz,Kfz,
`Y
`
`exp_timey,X,Fby,Kby,Ffy,Kfy,
`X
`
`exp_timex,W,Fbx,Kbx,Ffx,Kfx,
`Wexp_timew,NULL,NULL,NULL,NULL,NULL,
`{IDENTITY,Fbx,Kbx,Ffx,Kfx,Fby,Kby,Ffy,Kfy,
`Fbz,Kbz,Ffz,Kfz,PADDING}
`
`Fig. . A Reply Onion.
`
`initiator’s proxy node. Internally to the intermediate nodes, the forward crypto-
`graphic functions are applied to data moving in the direction that the circuit was
`established, and the backward cryptographic functions are applied to data mov-
`ing in the opposite direction. The location of the terminal ProxyRouting Nodes
`are in this sense reversed, with the initiator’s proxy at the end of the circuit and
`the responder’s proxy at the beginning of the circuit. However, the behavior of
`the initiator and responder proxies is identical to their behavior in the virtual
`circuit formed by a forward onion. This is the reason for having forward and
`backward functionkey pairs at each layer of the onion.
`Like a forward onion, a reply onion can only be used once. When a node
`receives an onion it is kept until it expires, and any onion received is compared
`to detect replay. If a replay is detected, it is treated as an error and ignored.
`Since reply onions can only be used once, if multiple replies are desired, multiple
`reply onions must be sent. Of course, they need not all follow the same return
`route; although they may. If replies are only likely to be forthcoming if they are
`anonymous, one or more reply onions can be broadcast. Anyone can then reply
`with an unused onion. If he can maintain anonymity from or in cooperation with
`the responder’s proxy for that reply onion, then he can do so anonymously.
`
` Implementation
`
`The easiest way to build our system without requiring the complete redesign and
`deployment of new client and server software is to make use of existing proxy
`technologies. Historically, proxy technologies have been used to create tunnels
`through a rewall. The use of proxy technologies requires that the client applica-
`tions be ‘proxy aware’. The widespread deployment of rewalls on the Internet
`has created the demand for such proxy aware applications, which software man-
`ufacturers are rushing to meet.
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 9
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`In the rewall setting, a system administrator will set up a proxy server on
`the rewall machine which will be responsible for forwarding requests from the
`protected domain out onto the open Internet, and maintain a return path for
`the response to the request. A proxy server can be divided into two parts: the
`front end that receives and parses the request, and the back end that processes
`the request and returns the results back to the requester. Classically, the front
`and back ends are the same process running on one machine.
`
`Under our system we will use a traditional proxy front end and back end, but,
`they will be separate processes on separate machines with a tunnel connecting
`them. In this manner, our ProxyRouting Nodes will look no dierent to the
`client and server software than any other proxy server. A couple of assumptions
`will hold for the remainder of this paper:  ProxyRouting Nodes and interme-
`diate routing nodes know about each other in advance of their operation, and 
`public key certicates for each node have been securely distributed to all others
`prior to operation.
`
`All nodes are connected by link encrypted connections which multiplex many
`virtual circuits between initiator and responder proxy nodes. These connections
`are link encrypted in an odd way for eciency. All messages moving through
`these connections are of xed size and have two components, header and payload
`elds. Header elds contain the virtual circuit identier and the command and
`are link encrypted using a stream cipher  . Since all payload elds will be
`encrypted via other mechanisms public keys or onion keys, they need not be
`link encrypted.
`
`There are three commands that nodes understand. The rst is to create a
`virtual circuit. At each node, a virtual circuit has two connections. Data arriv-
`ing on one is passed along on the other. The circuit is dened by the labels
`for these two connections. Creating a virtual circuit is the process of dening
`these labels for each node along the route. For the rst ProxyRouting Node,
`one connection is a link to the initiator, and the other is a link to the next
`routing node. The ProxyRouting Node creates an onion dening the sequence
`of intermediate routing nodes to the responder’s ProxyRouting Node. It breaks
`the onion up into payload sized chunks and transmits these chunks in order to
`the next node with a control eld containing both the label of the connection
`and a create command. Each subsequent node reassembles the onion and peels
`o a layer from the onion which reveals the next node in the route and two cryp-
`tographic functionkey pairs. Before acting on the create command, the node
`checks whether the onion has expired or is a replay. To check for replay, the node
`consults a table of unexpired onions. If the onion is valid, it is inserted into the
`table, and the node then labels a new connection to the next node and passes the
`peeled and padded onion in a similar sequence of messages to the next node. It
`also updates a table containing the labels and cryptographic functionkey pairs
`associated with the new virtual circuit. The appropriate forward or backward
`functionkey pair should be used to crypt data moving along that circuit. The
`responder’s ProxyRouting Node, recognizing that the onion is empty, will par-
`tially update its tables. As with standard proxies the next data message along
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 10
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`this circuit will identify the responder.
`The second command is data. The second role of the initiator’s ProxyRout-
`ing Node is to pass a stream of data from the initiator along the virtual circuit
`together with other control information for the responder’s ProxyRouting Node.
`To do this, he breaks the incoming stream into at most payload sized chunks,
`and repeatedly pre-crypts each chunk using the inverse of the cryptographic
`operations specied in the onion, innermost rst. The functionkey pairs that
`are applied, and the virtual circuit identier of the connection to the next node
`are obtained from a table. The header eld for each payload is the label of
`the connection and a data command. Each subsequent node looks at its table,
`obtaining the cryptographic functionkey pair associated with the circuit for
`the appropriate direction and the virtual circuit identier of the connection to
`the next node. It then peels o a layer of cryptography and forwards the peeled
`payload to the next node. Once the data reaches the responder’s proxy, its nal
`cryption will produce the plaintext that is to be processed or forwarded to the
`responder.
`The data command can also be used to move data from the responder’s
`ProxyRouting Node to the initiator’s ProxyRouting Node. The responder’s
`ProxyRouting Node obtains the cryptographic functionkey pair and the vir-
`tual circuit identier for the next node from its tables, and crypts the stream.
`It breaks the crypted stream into payload sized chunks and forwards them to
`the next node with the appropriate control eld. Each subsequent node further
`stream crypts each payload using the appropriate functionkey associated with
`that virtual circuit. Once a messages arrives at the initiator’s ProxyRouting
`Node he looks at his table and applies the inverse of the backward cryptographic
`operations specied in the onion, outermost rst, to this stream to obtain the
`plaintext. The plaintext is forwarded to the initiator.
`The third command is destroy which is used to tear down a virtual circuit
`when it is no longer needed or in response to certain error conditions. Notice
`that destroy messages can be initiated by any node along a virtual circuit, and it
`is a node’s obligation to forward the destroy messages in the appropriate direc-
`tions. A node initiating a destroy message in an active virtual circuit forwards
`it in both directions. A node that receives a destroy message passes it along
`in the same direction. The payload of a destroy command is empty padding.
`Nonetheless, this payload is still crypted with the appropriate functionkey pair.
`In addition to the destroy command, the control eld contains the virtual cir-
`cuit identier of the recipient of the destroy command. Upon receipt of a destroy
`command a node deletes the table entries associated with that virtual circuit.
`
` Vulnerabilities
`
`Onion Routing is not invulnerable to trac analysis attacks. With enough data,
`it is still possible to analyze usage patterns and make educated guesses about
`the routing of messages. Also, since our application requires real time commu-
`nication, it may be possible to detect the near simultaneous opening of socket
`
`
`
`Petitioner RPX Corporation - Ex. 1054, p. 11
`
`

`

`David M. Goldschlag, Michael G. Reed, and Paul F. Syverson. Hiding Routing Information,"
`Workshop on Information Hiding, Cambridge, UK, May, .
`
`connections on the rst and last proxy servers revealing who is requesting what
`information. However, these sorts of attacks require the collection and analysis
`of huge amounts of data by external observers.
`Other attacks depend upon compromised Proxy Servers and Routing Nodes.
`If the initiator’s proxy is compromised then all information is revealed. In general
`it is sucient for a single routing node to be uncompromised to complicate trac
`analysis. However, a single compromised routing node can destroy connections
`or stop forwarding messages, resulting in denial of service attacks.
`Onion Routing uses expiration times to prevent re