Location privacy through ip address space scrambling

BACKGROUND

0001The present invention relates generally to network communication. More particularly, the present invention relates to maintenance of location privacy during network access using IP address space scrambling.

0002Internet Protocol (IP) allows any hosts on an IP network to have end-to-end communication between them if they know each other's IP address. An IP network generally includes one or more switches or routers and two or more hosts. The hosts communicate over a wire line or wireless link with a router. Routers similarly communicate with other routers and hosts. Generally, all communication is by internet protocol.

0003Each IP message consists of one or more IP packets. Header information in the IP packets identifies the sender, the recipient and allows the entire IP message to be reconstructed from the IP packets. The IP packets are independent and discrete and may not be routed from sender to receiver over the same path in the network. In an IP network, a sender can send IP packets to a receiver by setting a destination IP address in the IP packet header to the IP address of the intended receiver. Once the packet is injected in the IP network, routing mechanisms try to deliver the packet to the destination host.

0004The information contained in the Destination IP Address field of an IP packet is what enables the routing mechanism of the network to deliver the IP packet to its intended recipient. An IP address is structured in a Prefix-Suffix format. The prefix part of the IP address contains the subnet-prefix of the destination subnet, indicating where the packet ought to go. Routers make routing decisions, such as selection of the link on which the packet needs to be sent, by looking at the destination subnet prefix contained in the IP address and matching it against a routing table maintained at each router. There are a large number of routing protocols in use in different parts of the Internet such as RIP, OSPF, and BGP etc, which are used for communication among routers and for building valid and up to date routing tables.

0005Currently, matching the destination subnet prefix from the destination IP address against the routing table is a very simple process. A router applies a mask function on the IP address to obtain the prefix and then searches in the routing table for the entry with longest match to this prefix. Once the entry is found, the packet is routed or sent out on the link described in that routing table entry.

0006While the inherent simplicity of this process allows the routers to process packets very quickly, and enables them to handle large amounts of traffic, it also creates some potential problems. These problems ere becoming more and more important and significant as networks including the Internet become a primary means of communication.

0007One such problem is location privacy. This problem sterns from the fact that most of the subnets, especially stub-subnets, usually have a fixed association with a fairly small geographical area. Due to the fixed nature of this association, a fairly accurate database of subnet-prefix-to-location mappings may be built. Thus, the user loses a substantial portion of the user's location privacy. It is possible to identify the geographic location of the user, even when that location is changing over time because the user is geogaphically mobile.

0008As noted, internet protocol requires hosts to know each others's IP addresses for true end-to-end communication in the network. In other words, a host cannot communicate with other hosts in end-to-end fashion without actually revealing its location. This is because inferring a subnet-prefix from a given IP address is extremely easy, and subnet-prefixes correspond to geographical locations.

0009<nplcit id="ncit0001" npl-type="b"><text>Dynamic Host Configuration Protocol, IETF Standard, Internet Engineering Task Force, R. Droms, Pucknell University, 01 March 1997</text></nplcit> specifies an Internet standards track protocol for the Internet community. The Dynamic Host Configuration Protocol (DHCP) provides a framework for passing configuration information to hosts on a TCPIP network. DHCP is based on the Bootstrap Protocol (BOOTP), adding the capability of automatic allocation of reusable network addresses and additional configuration options. DHCP captures the behaviour of BOOTP relay agents, and DHCP participants can interoperate with BOOTP participants.

0010Accordingly, a need exists to solve the above mentioned location privacy problem.

SUMMARY

0011The invention is defined as a computer-implemented pseudo-prefix computation method according to claim 1, a corresponding computer system according to independent claim 21, and a corresponding computer program product according to independent claim 23. The invention is also defined as a routing method according to independent claim 20, a corresponding router according to independent claim 22, and a corresponding computer program product according to independent claim 24.

0012By way of introduction only, one current limitation on location privacy for a network user is that a network address such as an IP address includes the destination subnet information in plain and easily inferable form. Location information may be extracted by applying a very simple mask function to determine the corresponding subnet.

0013In one embodiment, then, the simple mask function applied to an IP address is replaced with a cryptographic function. In this embodiment, the IP address is formed in a way that its corresponding destination subnet cannot be determined using a simple mask function. Instead, the router uses some secret information or key combined with a cryptographic process to determine the routing prefix for the corresponding subnet Using this scheme, any entity that does not know the secret information cannot determine the corresponding subnet prefix for a given IP address. This scheme can also be used to reduce correlation between the IP addresses of hosts within a subnet.

0014The foregoing summary has been provided only by way of introduction. Nothing in this section should be taken as a limitation on the following claims, which define the scope of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

0015<figref idref="f0001">FIG. 1A</figref> is a block diagram illustrating a network;

0016<figref idref="f0002">FIG. 1B</figref> is a block diagram illustrating one type of router that may be used in the network of <figref idref="f0001">FIG. 1A</figref>;

0017<figref idref="f0003">FIG. 2</figref> illustrates an internet protocol (IP) address format;

0018<figref idref="f0004">FIG. 3</figref> is a flow diagram illustrating operation of the network of <figref idref="f0001">FIG. 1A</figref> in accordance with a first embodiment;

0019<figref idref="f0003">FIG. 4</figref> illustrates an IP address configured by a host using a pseudo prefix provided by a router in response to a request by the host;

0020<figref idref="f0005">FIG. 5</figref> illustrates calculation of a routing prefix in accordance with a first embodiment;

0021<figref idref="f0003">FIG. 6</figref> illustrates an assigned IP address 600 in accordance with a second embodiment;

0022<figref idref="f0006">FIG. 7</figref> illustrates calculation of a routing prefix in accordance with a second embodiment;

0023<figref idref="f0007">FIG. 8</figref> illustrates calculation of a routing prefix in accordance with a third embodiment;

0024<figref idref="f0008">FIG. 9</figref> is a flow diagram illustrating operation of the network of <figref idref="f0001">FIG. 1A</figref> in accordance with a second embodiment;

0025<figref idref="f0009">FIG. 10</figref> illustrates a method for computing a set of pseudo prefixes;

0026<figref idref="f0003">FIG. 11</figref> illustrates an IP address configured by a host according to the method of <figref idref="f0009">FIG. 10</figref>;

0027<figref idref="f0010">FIG. 12</figref> illustrates a method for generating prefixes using public key cryptography;

0028<figref idref="f0011">FIG. 13</figref> illustrates a method for generating prefixes using symmetric key cryptography;

0029<figref idref="f0003">FIG. 14</figref> illustrates an exemplary IP address in accordance with one embodiment; and

0030<figref idref="f0012">FIG. 15</figref> is a flow diagram illustrating operation of the network of <figref idref="f0001">FIG. 1A</figref>.

DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENTS

0031Referring now to the drawing, <figref idref="f0001">FIG. 1A</figref> is a block diagram illustrating a network 100. The network 100 includes a plurality of switches or routers, including router 102, router 104, router 106, router 108, router 110, router 112, and two or more hosts including host 114 and host 116. The network 100 may be any public or private network for data communication. In the exemplary embodiment, the network 100 communicates packets of data in accordance with transmission control protocol/internet protocol (TCP/IP). Other data formats and communication protocols may be substituted, or exist in addition to TCP and IP.

0032Moreover, the configuration of the network 100 is exemplary only. The number of routers and hosts in the network and the individual interconnections of these devices are arbitrary and may change over time. Individual connections among the network devices use any appropriate technology, such as Ethernet, T1 or integrated services digital network (ISDN). The network 100 may have access to the Internet. Networks may include sub-networks or subnets. Subnets themselves may include one or more smaller subnets. The terms network or sub-network or subnet may be used interchangeably. A subnet which does not include smaller or nested subnets or does not serve as a transient network (inter-connecting network) between two or more subnets is usually called a stub-subnet.

0033The routers 102, 104, 106, 108, 110, 112 are devices or software that determine the next network point to which a received data packet should be forwarded toward its destination. Each router is connected to at least two branches of the network 100 and decides which way to send each information packet based on the router's current information about the state of the network. A router is generally located at any gateway, where one network meets another. A router may be included as part of a network switch.

0034. A router may create or maintain a table of available routes and their conditions, and use this information along with distance and cost algorithms to determine the best route for a given packet. A packet is the unit of data that is routed between an origin and a destination of the network. In one exemplary embodiment, when any file is sent from an origin network location to a destination network location, the transmission control protocol layer of TCP/IP divides the file into packets for routing. Each of these packets is separately numbered and includes the network address of the destination. For unicast transmission, a network address or IP address is a unique location on the network. The address may be expressed as a unique string of numbers and/or as an associated domain name.

0035Each subnet on the network has one or more identifiers or network numbers. These numbers are referred to as the subnet prefix or simply prefix. Any subnets within a larger subnet also have their unique prefixes. Usually, the prefixes of the smaller (or nested) subnets are equal to or longer in length than the prefix of their lager subnet. Moreover, in general practice, prefixes of all the smaller subnets contain one of the prefixes of the larger subnet in its entirety. Thus, the prefix of a smaller subnet is usually a combination of the prefix of the larger subnet (within which the smaller subnet is nested) and some other number.

0036A host, such as the host 114 and the host 116, is connected to other hosts on the network 100. Each host is associated with a sub-network or subnet. The host 114 is associated with the subnet 118 and the host 116 is associated with the subnet 120. Each host has a specific local or host number (usually referred to as a suffix) that, combined together with the network or subnet number (usually referred to as a subnet prefix, or just prefix), forms the host's unique IP address.

0037As noted above, hosts and their subnet generally have a common geographic location. As noted, the location of a host and a subnet may be inferred by applying a mask function. A mask function is conventionally used by a router to separate the suffix from the prefix and route a packet by comparing to entries in a routing table. A similar mask function may be used to obtain the location of the destination subnet

0038In the network 100, to provide location privacy, the simple mask function is replaced by a cryptographic function on some of the routers. Each of these routers uses secret information or data combined with a cryptographic process to determine a corresponding subnet's routing prefix. Any entity that does not know the secret information cannot determine the corresponding subnet prefix.

0039For a router to decrypt the subnet routing prefix from a given IP address, the subnet routing prefix must first be encrypted in the IP address. Thus, IP addresses must be assigned carefully to ensure that when a router applies the decryption on the IP address, the result is the correct or desired routing prefix.

0040In the example of <figref idref="f0001">FIG. 1A</figref>, a privacy domain 122 is defined. A privacy domain is a sufficiently large set of interconnected routers or a large subnet. In <figref idref="f0001">FIG. 1A</figref>, the privacy domain 122 includes router 102, router 104 and router 106. In other embodiments, and in other privacy domains that may be defined on the network 100, more or fewer routers may be designated as members of the privacy domain.

0041It is assumed that all routers in a privacy domain 122 can be keyed and periodically re-keyed with some shared secret. The secret may be data having a particular format or content. Keying and re-keying may be done automatically or manually.

0042<figref idref="f0002">FIG. 1B</figref> shows an example of a router 150 that may be used in the privacy domain 122 to decrypt subnet routing prefixes. As shown, decryption keys are provided to decryption unit and header assembly unit 152. Packets being transmitted through the router 150 pass through a packet destination address extractor 154, which provides the packet destination address to the unit 152. The unit 152 and routing table 156 provide inputs to routing table searcher 158, which in turn (along with unit 152) provides output to the correct interface dispatcher 160. The decrypted subnet routing prefix then may be provided from router 150 over the network 100. Within a privacy domain 122, decryption of subnet prefixes enables proper routing of packets within the privacy domain without revealing the particular geographic location of the destination identified by the address.

0043The router 150 in <figref idref="f0002">FIG. 1B</figref> similarly may encrypt subnet routing prefixes. Not all of the routers in the network 100 shown in <figref idref="f0001">FIG. 1A</figref> need to be able to encrypt or decrypt subnet routing prefixes. Thus, for example, router 102 may have the functionality of router 150, but router 108 may not. In one embodiment, the present invention handles this situation in a manner that will be described in greater detail later on.

0044<figref idref="f0003">FIG. 2</figref> illustrates an internet protocol (IP) address format 200. The address 200 includes a prefix 202 and a suffix 204. The prefix 202 includes a privacy domain prefix portion 206, labeled <i>P₀</i>, and a routing prefix portion 208, labeled <i>P_R</i>. The privacy domain prefix portion <i>P₀</i> 206 is associated with the privacy domain. All hosts and all subnets within a privacy domain share a common privacy domain prefix portion <i>P₀</i> 206. In some embodiments, <i>P₀</i> is 16 bits long, but any length may be assigned and the length may be changed dynamically. All hosts in the privacy domain preferably share <i>P₀</i> as the first prefix, so that any packets that originate outside of the privacy domain can be routed to the privacy domain. Every router inside the privacy domain has a unique routing prefix portion <i>P_R</i> 208. The prefix <i>P_R</i> is conventionally 48 bits long, but any length may be used. Every host, indexed as host_i, is allowed to configure the suffix 204 for its IP address 200. The configured suffix 210 is labeled <i>M_i</i>. The suffix is conventionally 64 bits in length, but any length may be chosen.

0045In the exemplary embodiment, the network cannot exercise any control on how the 64 bit suffix portion of the IP address 200 is configured by a host. A host can use any value for the suffix 210 so long as the value is unique within a subnet, i.e. not used by any other host on the subnet. Any conventional method of ensuring uniqueness may be used, such as Duplicate Address Detection and a Host/Neighbor Table.

0046<figref idref="f0004">FIG. 3</figref> is a flow diagram illustrating operation of the network of <figref idref="f0001">FIG. 1A</figref>. In this embodiment, a host <i>i</i> needs to configure a new IP address. This may happen when a host moves to a new subnet or detects availability of a new router, or upon expiration of a previously assigned IP address, or for any other reason. The host <i>i</i> will reconfigure the prefix to <i>M_i</i>. Instead of using the prefix advertised by the router in Router Advertisement Messages, to complete its IP address, the host solicits a prefix from the router, or from a DHCP server or any other suitable address management entity, block 302. As used herein, "router" indicates a router, DHCP server, data switch, server or any other address management entity and their equivalents. The request is received at the router at block 304.

0047At block 306, the router computes a pseudo prefix. The router has an assigned routing prefix <i>P_R.</i> The router computes the pseudo prefix <i>P₀P`</i><sub>(<i>R,i</i>)</sub> and, at block 308, cummunicates it to the host. The subscript (R, i) signifies that the prefix P` is separately computed for each host with a router, and every router for a host. That is to say that it is likely to be different for every combination of router and host. Different ways of computing <i>P`</i><sub>(<i>R,i</i>)</sub> will be described below. The host uses <i>P<sub>0</sub></i>, <i>P`</i>_(<i>R,i</i>) and its suffix <i>M_i</i> to configure its complete IP address.

0048<figref idref="f0003">FIG. 4</figref> illustrates an IP address 400 configured by the hoat using the pseudo prefix from the router. The IP address 400 includes a prefix 402 and a suffix 404. The prefix includes the concatenation of the privacy domain subnet prefix portion P₀ and the pseudo prefix portion P'_(R,i). The suffix M, 404 is combined with the prefix to form the IF address 400.

0049<figref idref="f0005">FIG. 5</figref>, <figref idref="f0003">FIG. 6</figref> and <figref idref="f0006">FIG. 7</figref> illustrate exemplary embodiments by which the router may compute the pseudo prefix <i>P`</i>_(<i>R,i</i>). Preferably, all routers in a common privacy domain use the same prefix computation method.

0050In a first exemplary embodiment, the assigned prefix is obtained by logically combining the host's suffix <i>M_i</i> with the routing prefix <i>P_R</i> for the router or subnet and a shared secret key. This key is shared among all the routers in the privacy domain. Any appropriate logical combination may be used. In the exemplary embodiment, an exclusive OR (XOR) function is used. Thus, the pseudo prefix <i>P`</i>_(<i>R,i</i>) is computed as

0051<i>P`</i>_(<i>R,i</i>)<i>= (Secret</i> ⊕ <i>P_R</i> ⊕ <i>M_i)</i>

0052The full IP address is then configured by the host <i>i</i> by concatenating the suffix <i>M_i</i> selected by the host with the pseudo prefix <i>P`</i><sub>(<i>R,i</i>)</sub><i>.</i> The host <i>i</i> can use the IP address <i>(P<sub>0</sub>, P`</i>_(<i>R,i</i>)<i>M_i)</i> for communication with any other host within or outside the privacy domain. When an ordinary router outside the privacy domain encounters a packet destined for IP address (<i>P₀ P`</i><sub>(<i>R,i</i>)</sub><i>M<sub>i</sub>),</i> it applies the traditional Mask function. The longest possible prefix match in routing table of any router outside the privacy domain can be <i>P<sub>0</sub></i>. So the router routes the packet to a link going to prefix <i>P</i><sub>0</sub>. Eventually the packet arrives at a router inside the privacy domain. If a packet destined for a host in privacy domain, originated inside the privacy domain it may never actually go to a <b>router</b> outside that privacy domain. When a router inside the privacy domain encounters this packet, it can compute the actual routing prefix <i>P<sub>0</sub> P<sub>R</sub></i> for this packet by XOR-ing the <i>P`</i>_(<i>R,i</i>) and <i>M_i</i>, which are already contained in the IP address, with the shared secret key. Once the actual prefix is determined, the router uses conventional routing table lookup to make the actual routing decision.

0053The routers in the privacy domain may cache the results of the prefix computation for a given IP address, to avoid re-computing the routing prefix for every packet and speed up the routing process. The cached values must be invalidated if the secret used for the computation is changed, for example, during a re-keying, Routers may have limited caching capacity. In that case, they may not be able to persistently cache the results. Instead they may erase some previously cached entries to make room for new ones. Which entries to keep and which ones to erase may be dictated by a cache replacement algorithm. Several cache-replacement algorithms have been studied over the years.

0054<figref idref="f0005">FIG. 5</figref> illustrates this process. The method begins at block 500. At block 502, a packet is received at a router of the privacy domain. At block 504, the router determines if the actual routing prefix corresponding to the pseudo prefix <i>P₀ P`</i>_(<i>R,i</i>) has been calculated and stored in cache memory. If so, control proceeds to block 510. If not, at block 506, the routing prefix is computed. At block 508, a routing table lookup is performed to decide the actual address for routing the packet. The packet is routed at block 510. Subsequently, at block 512, the router is determined if the prefix has been stored in the cache. If so, control returns to block 502 for receipt of a next packet. If the prefix has not already been cached, at block 514 the prefix is stored in memory and control returns to block 502. Storing the prefix in memory may include communicating the prefix to other routers of the privacy domain.

0055In a second embodiment for computing the assigned prefix, it is assumed that there are extra or spare bits available in the second, routing prefix portion <i>P_R.</i> This portion is usually 48 bits long, but this length may vary from implementation to implementation. Further, it is assumed that the actual routing prefix is only y bits long where <i>y ≤48.</i> In that case, there are <i>48-y</i> spare bits. If <i>48-y</i> is sufficiently large, on the order of 10 to 30 bits in one example, these bits can be used to carry a nonce for a message authentication code (MAC). A message authentication code is a bit string that is a function of both data (either plaintext or cipher-text) and a secret key, and that is attached to the data in order to allow data authentication. The function used to generate the message authentication code must be a one-way function. Data associated with an authenticated message allows a receiver to verify the integrity of the message. In this embodiment, then, only valid routers or other entities can compute the right prefix for the IP address. The router can compute the assigned prefix as follows.

0056<i>P*</i>_(<i>R,i</i>)=<i>P_R</i> ⊕ <i>MAC_k (Nonce_i, M_i)</i>

0057The MAC can take a number of forms in accordance with the invention. In one embodiments, the MAC is a hash function, such as Advanced Encryption Standard (AES) or Secure Hash Algorithm (SHA-1).

0058The assigned prefix <i>P`</i>_(<i>R,i</i>) is a concatenation of (a) the result of an exclusive OR operation or other logical combination of they bit actual prefix and <i>y</i> bit message authentication code MAC computed over the nonce and the host configured suffix, using a shared key <i>k</i> among the routers, and (b) the <i>48-y</i> bit nonce.

0059<figref idref="f0003">FIG. 6</figref> illustrates an assigned IP address 600 in accordance with this embodiment. The address 600 includes a prefix 602 and a suffix 604. The prefix is determined as described above and includes a privacy domain subnet prefix portion <i>P₀</i> 606, the assigned prefix <i>P*</i>_(<i>R,i</i>) 608 and the nonce <i>Nonce_i</i> 610. In one exemplary embodiment, the actual prefix <i>P_R</i> 608 would require only 18 bits, leaving 30 bits for the nonce 610.

0060A host <i>i</i> can use the IP address (<i>P₀</i>, <i>P*_(R,I) Nonce_i M_i)</i> for communication with any other host within or outside the privacy domain. When a router outside the privacy domain encounters a packet destined for IP address <i>(P₀, P*</i>_(<i>R,i</i>)<i>Nonce_i M_i).</i> the router routes the packet to the link going to a subnet associated with addresses having the prefix <i>P₀</i>. When a router inside the privacy domain encounters this packet, it can compute the actual routing prefix (<i>P₀P_R)</i> for this packet by computing the message authentication code using key K over <i>Nonce_i</i> and <i>M_i</i> contained in the IP header, XOR-ing the message authentication code with <i>P*</i>_(<i>R,i</i>) which is also contained in the IP address, and then concatenating the result with <i>Nonce_i.</i>

0061A key is information such as a sequence of random or pseudorandom binary digits used initially to set up and periodically change the operations performed in crypto-equipment for the purpose of encrypting or decrypting electronic signals. A nonce is defined in cryptography as a time-variant parameter, such as a counter or a time stamp that is used in key management protocols to prevent message replay and other types of attacks. In the present context, the nonce <i>Nonce_i</i> is a random number picked by the router at the time of pseudo prefix generation. The router may ensure that it picks a different random number for every host in the subnet, but that is not mandatory. The described system and the method will work, albeit with lower security, if the router does not use random or varying nonces.

0062<figref idref="f0006">FIG. 7</figref> illustrates calculation of a routing prefix in accordance with this embodiment. <figref idref="f0006">FIG. 7</figref> shows one detailed implementation of block 506 of <figref idref="f0005">FIG. 5</figref>. After determining that the routing prefix corresponding to the pseudo prefix is not stored in memory, block 504 of <figref idref="f0005">FIG. 5</figref>, at block 702 of <figref idref="f0006">FIG. 7</figref>, a router computing the routing prefix for an IP address first computes the message authentication code. At block 704, the resulting message authentication code is logically combined with the assigned prefix <i>P</i>_{*<i>(R,i)</i>}. In one embodiment, the logical combination is an exclusive OR operation. Finally, at block 706, the result from block 704 is concatenated with the nonce to produce the actual routing prefix <i>P</i>'<i>_(R,i)</i>.

0063From <figref idref="f0006">FIG. 7</figref>, control proceeds to block 508, <figref idref="f0005">FIG. 5</figref>. Once the actual prefix is determined, a conventional simple routing table lookup may be used by the router to make the actual routing decision. The routers may cache the results of above computation for a given IP address, to avoid re-computing the routing prefix for every packet and speed up the routing process.

0064In a third embodiment, the assigned prefix is an encryption of the actual prefix <i>P_R</i>. The key used for encryption is computed as a hash of the configured suffix <i>M_i</i> of the host and a shared secret among the routers.

0065<i>P`_(R,i) =Encrypt _Ki (P_R)</i>

0066<i>Ki = hash (Secret, M_i)</i>

0067Hash functions for computing the key can include the AES and SHA-1 hash functions mentioned above, among others. The encryption function also could be a hash function such as one of the just-mentioned hash functions.

0068As with the other embodiments above, a host <i>i</i> can use an IP address (<i>P₀</i>, <i>P`</i><sub>(<i>R,i</i>)</sub><i>M<sub>i</sub>)</i> for communication with any other host within or outsize the privacy domain. When a router outside the privacy domain encounters a packet destined for IP address (<i>P<sub>0</sub></i>, <i>P`</i>_(<i>R,i</i>)<i>M_i),</i> the router routes the packet to a link going to a subnet addressed with the prefix P<i>₀</i>. When a router inside the privacy domain encounters this packet, the router can compute the actual routing prefix (<i>P₀P_R</i>) for this packet by first generating a key <i>K</i> using a hash of shared secret and the suffix <i>M_i</i> in the IP address. Once the key has been generated, the router can easily decrypt <i>P`</i>_(<i>R,i</i>) to obtain <i>P_R</i>.

0069<figref idref="f0007">FIG. 8</figref> illustrates operation of a router to obtain a prefix in accordance with this third embodiment. <figref idref="f0007">FIG. 8</figref> shows one detailed implementation of block 506 of <figref idref="f0005">FIG. 5</figref>. After determining that the required prefix is not stored in memory, block 504 of <figref idref="f0005">FIG. 5</figref>, at block 802 of <figref idref="f0007">FIG. 8</figref>, a router computing the routing prefix for an IP address first generates a decryption key <i>k</i>. In one embodiment, this is done by using a hash of the secret shared among the routers of the privacy domain and the suffix <i>M_i</i> for the host contained in the address as shown above. At block 804, the key k is used to decrypt <i>P`</i>_(<i>R,i</i>).

0070As described above, in one exemplary embodiment, an IP suffix is used for prefix generation. In a second embodiment, a router maintains a pool of pseudo prefixes which are used by a host associated with that router to configure a new IP address. <figref idref="f0008">FIG. 9</figref> is a flow diagram illustrating one example of this embodiment

0071In accordance with this second embodiment, a host in the network may need to configure a new network or IP address. This may happen when the host moves to a new subnet or detects the availability of new router or upon the expiration of a previously assigned IP address or for any other reason. The host must obtain a prefix from a Router Advertisement (RA) message containing available prefixes. RA messages are usually broadcast or multicast periodically. The time period between successive advertisements may vary with time and implementation.

0072Further in accordance with this embodiment, a router R maintains a large set of pseudo-routing prefixes <i>S_R</i> = {<i>P`</i><sub>(<i>R,1</i>)</sub>, <i>P`</i>_(<i>R,2</i>)<i>, P`</i><sub>(<i>R,3</i>)</sub><i>, ..... P`</i>_(<i>R,n</i>)}. At block 902, the router chooses a small subset of pseudo routing prefixes from <i>S_R</i>. The router prefixes each of the chosen pseudo routing prefixes with a privacy domain prefix <i>P₀</i>.

0073In one embodiment, the router determines if any of the chosen pseudo routing prefixes has expired, block 904. In this embodiment, there is a lifetime associated with each of the pseudo prefixes maintained by the router. Upon expiration of that lifetime, that pseudo prefix may no longer be included in the advertisement messages sent by the router. However, the router may re-introduce the same pseudo prefix at a later time. The router may delete an expired pseudo prefix or replace an expired pseudo prefix by a new one out of the set <i>S_R</i><b>.</b> The router may explicitly indicate the remaining lifetime or an expiration time of the pseudo prefixes in the router advertising message. Alterntatively, the router may periodically keep changing the order of pseudo prefixes in the router advertising messages, moving the older ones to the end of the list, until they gradually 'fall off' the list in the router advertising message. Or, the host may implicitly guess the remaining lifetime of a pseudo prefix by looking at its position in the list. If a host configures its IP address using a pseudo-prefix from the subset of pseudo-prefixes advertised by the router, and later that pseudo-prefix disappears from the subset advertised by the router, then the host takes this event as expiration of that pseudo-prefix and chooses a new one from the latest advertised subset of prefixes.

0074At block 906, the router advertisement message is sent by the router and at block 908, the router advertisement message is received by the host which needs to configure a new IP address.

0075The host can select any one of the pseudo prefixes advertised by the router and configure its IP address. At block 910, the host selects a pseudo prefix and configures its IP address.

0076In one embodiment, at block 912 the host determines if the selected pseudo prefix has expired or is in any way invalid. Expiration of a pseudo-prefix may be assumed if the pseudo prefix disappears or 'falls off' the RA message sent periodically by the router. Alternatively there may be an explicit message indicating expiration of a pseudo-prefix or same other mean. If so, control returns to block 910 to select another pseudo prefix. Any hosts that were using the expired pseudo prefix must select a new one out of the advertised prefixes. Otherwise, at block 914, the host configures its IP address. Further details will be provided on this process below. Subsequently, at block 916, the host receives a router advertising message. At block 918, the host tests to see it the pseudo prefix it selected at block 910 is still in the list, and therefore still valid. If so, the host waits for receipt of a next router advertising message to verify the validity of the selected prefix, block 916. If the selected pseudo prefix is no longer in the list transmitted from the router, or if the selected pseudo prefix becomes invalid or expired for any other reason, control proceeds to block 910 where the host selects another pseudo prefix.

0077<figref idref="f0009">FIG. 10</figref> illustrates one method for computing the set <b><i>S_H</i></b> of pseudo prefixes. A router may compute the set of routing prefixes <b><i>S_R</i></b> using any suitable method. One exemplary method is described here. Other methods may be substituted.

0078In the example, a pseudo-routing prefix <i>P`<sub>(R,k)</sub></i> belongs to set <b><i>S<sub>R</sub></i></b> if <b><i>P<sub>R</sub></i></b> can be inferred from <i><b>Decryption</b> (P`_(R,k))</i>, for example if <i>P_R<b>= Decryption (P`_(R,k)).</b></i> This can be achieved in several ways, one of which is described here. If it is assumed that the actual routing prefix <b><i>P_R</i></b> is only <i>y</i> bits long, where <i>y&lt;48,</i> then there are <i>m</i> = <i>(48-y)</i> spare bits, and we can have a set <b><i>S_R</i></b> with <i>n = 2^m</i> possible pseudo routing prefixes. Again hero we consider 48 bits because this is the length conventionally dedicated for the prefix. However, this value may vary with implementation. The set of pseudo-prefixes may be computed as follows:

0079<i>for k = 1 to n,</i>

0080<b><i>P`_{(R, k)} =Encryption (Combination of y-bit long P_R and m-bit long k).</i></b>

0081This is illustrated in <figref idref="f0009">FIG. 10</figref>. The method of <figref idref="f0009">FIG. 10</figref> begins at block 1002, where the indexing variable <i>k</i> is initialized to 1. At block 1004, the indexing variable is tested. If <i>k =</i> n, processing stops. Until <i>k =</i> n, at block 1006 pseudo routing prefixes are calculated according to the relation above. At block 1008. the indexing variable <i>k</i> is incremented and control returns to block 1004. In other embodiments, the set of pseudo-prefixes may bo populated in any suitable manner, For example, the entire set of pseudo-prefixes (i.e all 'n' prefixes) may not be generated in advance. Rather, in some embodiments, the router (or any entity aiding the router) may generate and use pseudo-prefixes on per need basis, particularly since the router only uses a small subset out of the n-element long set S_R at a time.

0082Decryption of <i><b>P</b>`_{(R, k)}</i> will result in a number which is the concatenation of the <i>y-bit</i> long <b><i>P_R</i></b> and the <i>m</i>-bit long <b><i>k</i>.</b> The process can obtain the routing prefix P_R by truncation or removal of the m-bits which were combined with P_R before applying encryption as noted above. It is noted that currently, no conveniently available cryptographic process can operate on 48 bit long blocks. Any suitable cryptographic process or device that is available or may be subsequently developed may be used to perform this function.

0083<figref idref="f0003">FIG. 11</figref> illustrates an IP address 1100 configured by a host according to the method of <figref idref="f0009">FIG. 10</figref>. The IP address 1100 includes a prefix 1102 and a suffix 1104. The prefix 1102 includes a privacy domain subnet prefix portion <b><i>P₀</i></b> 1106 and one of pseudo- routing prefix <b><i>P`_{(R, k)}</i></b> 1108 as computed at block 1006. These portions 1106, 1108 are concatenated with the host suffix <i>M_i 1104</i> to form the IP address 1100.

0084A host <i>i</i> can use IP address <b><i>(P₀, P`<sub>(R,k)</sub> M<sub>i</sub>)</i></b> 1100 for communication with any other host within or outside the privacy domain. When a router outside the privacy domain encounters a packet destined for IP address <b><i>(P<sub>0</sub>, P`_(R,k) M_i),</i></b> the router routes the packet to the link going to the router having an address including prefix <i>P₀.</i> When a router inside the privacy domain encounters this packet, it can compute the actual routing prefix <b><i>(Po P_R)</i></b> for the packet by decrypting <b><i>P`_{(R, k)}</i></b> and truncating <b><i>m-bits</i></b> from the result to obtain the routing prefix <b><i>P_R.</i></b> Since only the routers in the privacy domain have the key to decrypt the pseudo-prefixes, the actual prefix remains hidden.

0085Similar to the embodiments described above, routers may cache or otherwise store the results of the above computation for any given pseudo prefix to avoid re-computing the routing prefix for every packet and thereby speed up the routing process. The cached values must be invalidated if the secret used for the computation is changed, for example by re-keying.

0086In a second embodiment, a host can configure not just its own suffix but also its prefix. This method has two variants, as will be described in greater detail below. The first variant uses public key cryptography. The second variant uses more symmetric cryptography to generate the suffix. These two variants can be supplemented and other variants may be substituted as well.

0087In the first variant, the privacy domain has a public key <i><b>K</b>_(Public)</i> and a corresponding private key <b><i>K</i></b>_(Private). All the hosts in the privacy domain know the public key <b><i>K</i></b><i>_(Public).</i> In contrast, the private key <i>K_(Private)</i> is only known to all the routers in a privacy domain.

0088<figref idref="f0010">FIG. 12</figref> illustrates a method for generating prefixes using public key cryptography. At block 1202, the router sends a router advertising message. The router advertises a routing prefix <i><b>P</b>*_R</i> that is a function of its actual routing prefix <i><b>P_R</b>, <b>P*_R = f(P_R)</b></i> and there exists an inverse function <i>f^-1</i> such that <i><b>P_R</b> = f^-1 (P*_R).</i> Application of function <b><i>f</i></b> is optional. It may increase security if only all the routers in the privacy domain know the inverse function <i><b>f</b>^-1</i>.

0089At block 1204, the host receives the router advertising message. At block 1206, the host encrypts the prefix <b><i>P*_R</i></b> and uses the public key <b><i>K</i></b><i>_(Public)</i> and its desired suffix <b><i>M_i</i></b> to obtain a pseudo prefix <b><i>P`<sub>(R,i)</sub>.</i></b> At block 1208, the pseudo prefix <i><b>P`</b>_<b>(R,i</b>)</i> and the suffix <b><i>M_i</i></b> are concatenated to form the IP address of the host.

0090A host <i>i</i> can use the IP address <b><i>(P₀, P`<sub>(R,i)</sub> M<sub>i</sub>)</i></b> for communication with any other host within or outside the privacy domain. When a router outside the privacy domain encounters a packet destined for the IP address <b><i>(P<sub>0</sub>, P`_(R,i) M_i),</i></b> the router routes the packet to a link going to a subnet addressed by the prefix <b><i>P₀.</i></b> When a router inside the privacy domain encounters this packet, the router can compute the actual routing prefix <b><i>(P₀₁ P_R)</i></b> for this packet by first decrypting the pseudo prefix <b><i>P`_(R,i)</i></b> using <b><i>K_(Private)</i></b> and <b><i>M_i</i></b> to obtain <b><i>P*_R.</i></b> Next, the router applies the inverse function <b><i>f^-1</i></b> to obtain the routing prefix <b><i>P_R.</i></b> With the routing prefix <b><i>P_R</i></b> and the suffix <b><i>M_i</i></b> the router can route the packet to the intended host.

0091In the second variant, every host <i>i</i> in the privacy domain has a private key <i>K_i.</i> Also, every router in the privacy domain has a master key <b><i>K_m</i></b> such that any information encrypted using any private key <b><i>K_i</i></b> can be decrypted by the common master key <b><i>K_m.</i></b>

0092<figref idref="f0011">FIG. 13</figref> illustrates a method for generating prefixes using symmetric key cryptography. At block 1302, the router generates a routing prefix <i>P*_R</i> that is a function of its actual routing prefix <b><i>P_R,</i></b> where <b><i>P*_R = f (P_R),</i></b> and there exists a function, <i><b>f</b>^-1</i> such that <b><i>P_R</i> = <i>f^-1 (P*_R)</i>.</b> Application of function <b><i>f</i></b> is optional It may increase the security if only all the routers in the privacy domain know the <i>f^-1.</i> At block 1304, the router transmits a router advertising message with the routing prefix <i>P*_R.</i> The router advertising message is received at the host at block 1306. The host proceeds to encrypt <b><i>P*_R</i></b> using its private key <b><i>K_i</i></b> and its selected suffix <b><i>M_i,</i></b> block 1308. The result is the pseudo prefix <b><i>P`<sub>(R,i)</sub></i>.</b> The pseudo routing prefix <b><i>P`_(R,i)</i></b> and the suffix are concatenated at block 1310 to form the IP address for the host.

0093A host i can use the IP address <b><i>(P₀, P`<sub>(R,i)</sub> M<sub>i</sub>)</i></b> for communication with any other host within or outside the privacy domain. When a router outside the privacy domain encounters a packet destined for IP address <b><i>(P<sub>0</sub>, P`_(R,i) M_i),</i></b> the router routes the packet to a link going to a subnet addressed with the prefix <b><i>P₀.</i></b> When a router inside the privacy domain encounters this packet, it can compute the actual routing prefix <b><i>(P₀ P_R)</i></b> for this packet by first decrypting <b><i>P`_(R,i)</i></b> using the master key <b><i>K_m</i></b> and <b><i>M_i</i></b> to obtain <i>P*_R</i>. Next it applies the inverse functio <i>f^-1</i> to obtain the routing prefix <b><i>P_R.</i></b>

0094As above, the routers in the privacy domain may cache or otherwise store the results of the above computation for a given IP address in order to avoid re-computing the routing prefix for every packet and speed up the routing process. The stored value for the IP address of a host must be deleted if that host is assigned a new private key. Similarly, all the cached values must be deleted if the master key is changed, referred to as re-Keying.

0095Above, a constraint was introduced that every host <i>i</i> is allowed to configure a usually 64 bit suffix for its IP address. This suffix is denoted as <b><i>M_i.</i></b> In some applications, this constraint is not in effect. Examples include scenarios in which a router or a DHCP server assigns the entire address to the host instead of allowing the host to auto-configure the IP address.

0096The next exemplary embodiment describes a method in which a pseudo IP address or other network address is embedded with a decryption parameter or key. In this example, a host <i>i</i> needs to configure or otherwise obtain a new IP address. This may happen when a host moves into a new subnet or detects availability of a new router, or upon the expiration of the validity of a previously assigned IP address. The new router or DHCP server will assign the complete address to the host.

0097The host solicits a prefix from the router or DHCP server or any other address assignment entity. The router has a routing prefix <b><i>P_R.</i></b> The router or DHCP server computes a pseudo IP address <b><i>P₀P`<sub>(R,i)</sub>Nonce<sub>i</sub></i></b> and sends it back to the host. In one embodiment, <b><i>Nonce<sub>i</sub></i></b> is a unique random number for each host with the router. Other methods for determining <b><i>Nonce<sub>i</sub></i></b> could be substituted. Possible embodiments of a method for computing <b><i>P`_(R,i)</i></b> are given below. The host uses address <b><i>P₀P`_(R,i) Nonce_i</i></b> as its complete IP address.

0098<figref idref="f0003">FIG. 14</figref> illustrates an exemplary IP address 1400 in accordance with this embodiment. The IP address 1400 includes a prefix 1402 and a nonce portion <b><i>Nonce_i</i></b> 1404. The prefix 1402 includes a privacy domain subnet prefix portion <b><i>P₀</i></b> 1406 and a pseudo routing prefix portion <b><i>P`_{(R, k)}</i></b> 1408. These portions 1406, 1408 are concatenated with the nonce portion <b><i>Nonce_i</i></b> 1404 to form the IP address 1400.

0099<figref idref="f0012">FIG. 15</figref> is a flow diagram illustrating operation of the network of <figref idref="f0001 f0002">FIG. 1</figref> in accordance with this embodiment. Here, a host seeks to reconfigure its IP addrese. The host solicits a prefix from the router, or from a DHCP server or any other suitable address management entity, block 1502. The request is received at the router at block 1504.

0100At block 1506, the routeur computes a pseudo IP address. The router has an assigned routing prefix <b><i>P_R.</i></b> The router computes the pseudo IP addrese <b><i>P₀P`<sub>(R,i)</sub> Nonce<sub>i</sub></i></b> and, at block 1508, returns the pseudo IP address to the host. The host receives the pseudo IP address <b><i>P<sub>0</sub>P`_(R,i) Nonce_i</i></b> at block 1510 and uses it in subsequent communications in the network.

0101The router may compute the routing prefix <b><i>P`_(R,i)</i></b> using any of the following methods, or any equivalent method. In a first method, assume that only y bits are used for routing the prefix, where y <i>≤112.</i> In that case, there are <i>112 -</i> y spare bits. If <i>112 - y</i> is sufficiently large, for example, in the range 48 to 64 bits, these spare bits can be used to carry a nonce for a Message Authentication Code (MAC), so that only valid routers or other entities can compute the right prefix. The router can compute the assigned prefix as follows.

0102P`_(R,i) = P_R ⊕ MAC _k (Nonce_i).

0103Other calculations may be substituted. It is expected that the actual prefix <b><i>P_R</i></b> would require only 18 bits, leaving space for a 94-bit nonce.

0104A host <i>i</i> can use the IP address <b><i>(P₀, P`<sub>(R,i)</sub>Nonce<sub>i</sub>)</i></b> for communication with any other host within or outside the privacy domain. When a router outside the privacy domain encounters a packet destined for IP address <b><i>(P<sub>0</sub>, P`_(R,i) Nonce_i),</i></b> the router routes the packet to a link going to a subnet addressed with the prefix <b><i>P₀.</i></b> When a router inside the privacy domain encounters this packet, the router can compute the actual routing prefix <b>(<i>P₀ P_R</i>)</b> for this packet by computing the message authentication code using Key <b><i>K</i></b> over <b><i>Nonce_i</i></b> contained in the IP header, and XOR-ing the computed message authentication code with <b><i>P`_(R,i)</i></b> which is also contained in the IP address. Once the actual prefix is determined, a conventional simple routing table lookup is used for making the actual routing decision.

0105In a second method, the assigned prefix is an encryption of the actual prefix <b><i>P_R.</i></b> The key used for encryption is computed as a hash of a nonce <b><i>Nonce_i</i></b> which is selected by the router or DHCP server and is guaranteed to be unique for every host in the subnet. The prefix and key may be calculated as shown below.

0106<maths id="math0001"><math display="block"><msub><mi mathvariant="italic">Pʹ</mi><mfenced><mi mathvariant="italic">R</mi><mi mathvariant="italic">i</mi></mfenced></msub><mo>=</mo><msub><mi mathvariant="italic">Encrypt</mi><mi mathvariant="italic">Ki</mi></msub><mfenced><msub><mi mathvariant="italic">P</mi><mi mathvariant="italic">R</mi></msub></mfenced></math><img file="EP1563642B1_D0001.tif" /></maths>

0107<maths id="math0002"><math display="block"><msub><mi mathvariant="italic">K</mi><mi mathvariant="italic">i</mi></msub><mo>=</mo><mi mathvariant="italic">hash</mi><mfenced><mi mathvariant="italic">Secret</mi><msub><mi mathvariant="italic">Nonce</mi><mi mathvariant="italic">i</mi></msub></mfenced></math><img file="EP1563642B1_D0002.tif" /></maths>

0108Encryption and hashing may be used as described earlier with respect to the second and third embodiments. If the DES Data Encryption Standard is used for encryption, the prefixes <b><i>P</i></b> and <b><i>P`</i></b> are expected to be 64 bits long. Some of these may be stuffed bits.

0109A host <i>i</i> can use IP address <b><i>(P₀, P`<sub>(R,i)</sub> Nonce<sub>i</sub>)</i></b> for communication with any other host within or outside the privacy domain. When a router outside privacy domain encounters a packet destined for IP address <b><i>(P<sub>0</sub>, P`_(R,i) Nonce_i),</i></b> the router routes the packet to a link going to a subnet addressed with the prefix <b><i>P₀.</i></b> When a router inside the privacy domain encounters this packet, the router can compute the actual routing prefix <b><i>(P₀ P_R)</i></b> for this packet by first generating a key <b><i>K</i></b> using a hash of shared secret and the nonce <b><i>Nonce_i</i></b> in the IP address. Once the key has been generated, the router can easily decrypt <b><i>P`_(R,i)</i></b> to obtain <b><i>P_R.</i></b>

0110Finally, in discussing a variant of the present invention above with reference to <figref idref="f0002">FIG. 1B</figref>, it was mentioned that not all routers in the privacy domain may have the capability to decrypt the addresses. To operate in such scenarios, in one embodiment, the invention operates as follows.

0111Certain bits in the IP address are dedicated to determining whether the rest of the address is a scrambled-address. Due to traditional longest match based routing used in today's routers, in one embodiment these identifier bits are the 'n' most significant bits after the privacy domain's shared routing prefix P₀. Thus these bits form a second level prefix. These are referred to as P_SAS for Prefix(es) for scrambled address space. This is essentially an extension to the domain's prefix P₀. Any non-scrambling enabled routers route the packets bearing any of the scrambling prefixes P_SAS to scrambling enabled routers for appropriate routing. When a scrambling enabled router receives a packet, it decrypts the prefix as explained in preceding sections and forwards the packet to another scrambling enabled router.

0112In rare events of packet loops, i.e. when a router sees a packet it has already forwarded, or when there are no outgoing paths to scrambling enabled routers except the path along which the packet came, a scrambling enabled router may opt to tunnel the packet directly to the ultimate destination scrambling enabled router. The packet is tunneled to the address P₀P_R::00, where P_R is the decrypted routing prefix of the destination router. Suffix 00 indicates a tunnel endpoint Every edge router reserves this suffix for tunnel endpoints. It is worth noting here that the payload of the tunneled packet contains P`<sub>R</sub>. Thus, if the packet must traverse some non-secure routers or links, then it may be possible to learn P`_R to P_R mapping. Accordingly, for increased security all the payloads must be encrypted using the shared key of the privacy domain. Of course the scrambling enabled routers can act both as specialized and regular routers to route the regular packets which do not have a scrambled destination prefix.

0113While a particular embodiment of the present invention has been shown and described, modifications may be made. It is therefore intended in the appended claims to cover such changes and modifications which follow in the true scope of the invention.