LOCATION PRIVACY THROUGH IP ADDRESS SPACE SCRAMBLING

• US 20070104202A1
• Filed: 01/02/2007
• Published: 05/10/2007
• Est. Priority Date: 10/31/2002
• Status: Active Grant

• Current Assignee: Craig Gentry, James Kempf, Muhammad Tariq, Ravi Jain, Toshiro Kawahara
• Original Assignee: Craig Gentry, James Kempf, Muhammad Tariq, Ravi Jain, Toshiro Kawahara
• Inventors: Jain, Ravi, Kempf, James, Kawahara, Toshiro, Gentry, Craig, Tariq, Muhammad
• Granted Patent: US 8,601,262 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 2101/668 Internet protocol [IP] address subnets
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 61/5014 using dynamic host configuration protocol [DHCP] or bootstrap protocol [BOOTP]
• CPC Class Codes: H04L 63/0407 wherein the identity of one or more communicating identities is hidden cryptographic mechanisms or cryptographic arrangements for anonymous credentials or for identity based cryptographic systems H04L9/00
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/045 wherein the sending and receiving network entities apply hybrid encryption, i.e. combination of symmetric and asymmetric encryption cryptographic mechanisms or cryptographic arrangements using a plurality of keys or algorithms H04L9/14
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity

Abstract

In a network, a router uses some secret information combined with a cryptographic process in determination of a subnet'"'"'s routing prefix. Several methods are disclosed, including using an IP suffix for prefix generation and for decryption, maintaining a pool of pseudo prefixes at the router, using public key encryption and symmetric key encryption.

Claims

1. A network address assignment method for assigning an address to a host for network communications, the method comprising:

computing a pseudo prefix incorporating an encryption of a subnet address associated with a subnet associated with the host; and

communicating the pseudo prefix to the host for use as part of said address assigned to the host, the address being for use by the host as the host'"'"'s address in network communications.

2. The network address assignment method of claim 1 wherein the pseudo prefix is computed in response to the host requesting an address over a network.

3. The network address assignment method of claim 1 wherein the pseudo prefix is communicated to the host over a network.

4. The network address assignment method of claim 1 wherein the pseudo prefix is not equal to a prefix advertised by any router connected to the subnet.

5. The method of claim 1 wherein computing the pseudo prefix comprises logically combining a suffix of the address of the host with a shared secret key.

6. The network address assignment method of claim 5 wherein the computed pseudo prefix is specific to the host and the router.

7. The network address assignment method of claim 1 wherein the pseudo prefix comprises a common prefix shared by all routers in the privacy domain.

8. The network address assignment method of claim 5 wherein logically combining comprises exclusive-OR-ing the suffix with the shared secret key.

9. The method of claim 1 wherein:

the host and the subnet are part of a privacy domain comprising a plurality of subnets and one or more routers;

the pseudo prefix includes an unencrypted portion of the subnet address;

the one or more routers inside the privacy domain are provided with cryptographic information for decrypting the pseudo prefix to obtain the subnet address when routing data to the host, but the privacy domain does not provide the cryptographic information to one or more routers outside the privacy domain, the one or more routers outside the privacy domain being operable to route data to at least one router in the privacy domain using the unencrypted portion of the pseudo prefix.

10. The method of claim 9 wherein the pseudo prefix does not include a prefix portion equal to any prefix advertised by any router of the privacy domain.

52. An apparatus adapted to perform the method of claim 1.

11. A network address assignment method for assigning an address to a host for network communications, the method comprising:

receiving an address request from the host associated with a router in a network;

computing a pseudo prefix including logically combining an actual routing prefix and a message authentication code computed over nonce data and a suffix of the address of the host to produce a result; and

communicating the pseudo prefix to the host for use as part of said address assigned to the host, the address being for use by the host as the host'"'"'s address in network communications.

12. The network address assignment method of claim 11 wherein computing the pseudo prefix comprises:

concatenating the result with the nonce data to form the pseudo prefix.

13. The network address assignment method of claim 11 wherein the pseudo prefix is combined with a common prefix shared by all routers in a subnetwork.

14. The network address assignment method of claim 13 wherein the pseudo prefix is computed in response to the host requesting an address over a network.

15. The network address assignment method of claim 13 wherein the pseudo prefix is communicated to the host over a network.

16. The network address assignment method of claim 13 wherein the pseudo prefix is not equal to a prefix advertised by any router in the subnetwork.

53. An apparatus adapted to perform the method of claim 11.

17. A network address assignment method for assigning an address to a host associated with a router in a network, wherein the host and the router are part of a privacy domain, the method comprising:

receiving an address request from the host;

computing a pseudo prefix, including encrypting an actual routing prefix of the router using an encryption key; and

communicating the pseudo prefix to the host, the host using the pseudo prefix to configure the host'"'"'s address, said address being for use as a destination address both in packets destined to the host and originating inside the privacy domain and in packets destined to the host and originating outside the privacy domain;

wherein each router inside the privacy domain is provided with cryptographic information for decrypting the pseudo prefix to obtain the actual routing prefix when routing data to the host, but the privacy domain does not provide the cryptographic information to one or more routers outside the privacy domain, the one or more routers outside the privacy domain being operable to forward data to at least one router in the privacy domain without decrypting the pseudo prefix.

18. The network address assignment method of claim 17 wherein computing the pseudo prefix comprises:

computing the encryption key as a hash of a suffix of the address of the host and secret information shared with other routers of the network.

54. An apparatus adapted to perform the method of claim 17.

19. A network address assignment method for assigning a network address to a host for network communications, the method comprising:

receiving an address request from the host associated with a router in a network;

computing a network address, the network address including

1) a common routing prefix shared between all routers in the network,

2) a pseudo prefix portion,

3) data including a number generated by the router, referred to as nonce; and

communicating the network address to the host for use by the host as the host'"'"'s network address in network communications.

20. The network address assignment method of claim 19 wherein computing the pseudo prefix portion comprises:

logically combining a routing prefix of the router and a message authentication code.

21. The network address assignment method of claim 20 wherein computing the pseudo prefix portion further comprises:

computing the message authentication code over the nonce data.

22. The network address assignment method of claim 19 wherein computing the pseudo prefix portion comprises:

encryption of the routing prefix of the router.

23. The network address assignment method of claim 22 wherein computing the pseudo prefix portion further comprises:

encryption of the routing prefix of the router using an encryption key based on a hash computed over the nonce and the shared secret information between the routers.

55. An apparatus adapted to perform the method of claim 19.

24. A method for routing a data packet in a network, the method comprising:

receiving the data packet over the network, the data packet comprising a destination address comprising an encryption of a subnet address associated with the data packet'"'"'s destination;

decrypting the destination address to obtain the subnet address; and

forwarding said data packet over a network in accordance with the subnet address to deliver said data packet comprising said destination address comprising said encryption of said subnet address to the data packet'"'"'s destination.

25. The method of claim 24 wherein decrypting the destination address comprises:

logically combining a portion of the destination address with secret information.

26. The method of claim 25 wherein logically combining comprises:

exclusive OR-ing at least a portion of a pseudo prefix and a suffix of the destination address with the secret information.

27. The method of claim 25 wherein decrypting the destination address comprises:

logically combining at least a portion of a pseudo prefix and a suffix of the destination address with secret information at the router to produce the subnet address.

28. The method of claim 24 wherein decrypting the destination address to obtain a subnet address comprises:

computing a message authentication code, and logically combining the message authentication code with at least a portion of a pseudo prefix of the packet address to produce a result.

29. The method of claim 28 further comprising:

computing the message authentication code using nonce data contained in the data packet;

combining the nonce data with the portion of the pseudo prefix in a concatenation process.

30. The method of claim 28 wherein the message authentication code is keyed with some secret information shared between routers of the network and computed over nonce data contained in the destination address and a suffix of the destination address.

31. The method of claim 24 wherein decrypting the destination address to obtain a subnet address comprises:

generating a decryption key using a portion of the destination address, and

decrypting a pseudo prefix of the destination address to produce the routing prefix.

32. The method of claim 31 wherein generating the decryption key comprises:

generating the decryption key using a hash of secret information of the router and a suffix of the destination address.

33. The method of claim 24 wherein decrypting the destination address to obtain a subnet address comprises decrypting a pseudo prefix of the destination address to produce an actual routing prefix.

34. The method of claim 24, further comprising:

sharing a public key with routers and hosts;

sharing a private key with only the routers in a privacy domain;

wherein decrypting the destination address comprises;

decrypting a pseudo prefix of the destination address using the private key and a suffix of the destination address to obtain a routing prefix, and

determining an actual routing prefix from the routing prefix.

35. The method of claim 24, further comprising:

each host having a private key;

sharing a master key among the routers;

wherein decrypting the destination address comprises;

decrypting a pseudo routing prefix of the destination address using the master key to produce the routing prefix; and

determining an actual routing prefix from the routing prefix.

36. The method of claim 35 wherein any information encrypted using the private key may be decrypted using the master key shared among the routers.

37. The method of claim 24 wherein decrypting the destination address to obtain a subnet address comprises:

generating a key using a hash of shared secret information and nonce data of the destination address, and

decrypting the destination address using the key to produce the subnet address.

38. The method of claim 24 wherein decrypting the packet address to obtain a subnet address comprises:

computing a message authentication code over nonce data contained in the destination address;

logically combining the message authentication code with a pseudo prefix contained in the destination address; and

decrypting the destination address using the key to produce the subnet address.

56. An apparatus adapted to perform the method of claim 24.

39. A method for configuring a new internet protocol (IP) address, the method comprising:

at a network host, requesting an address prefix;

receiving a pseudo prefix computed using an encryption of a routing prefix of a router associated with the host; and

the host combining the pseudo prefix with a suffix of the host to form the new IP address, and using the new IP address as the host'"'"'s address in network communications.

40. The method of claim 39 wherein receiving the pseudo prefix comprises receiving a prefix computed using a cryptographic process and a secret key at the router.

57. An apparatus adapted to perform the method of claim 39.

41. A method for operating a router in a communication network, the method comprising:

receiving a packet;

reading a destination address from the packet;

determining a network routing prefix from the destination address, wherein determining the network routing prefix comprises using secret information and a cryptographic process;

caching the network routing prefix determined above for later use; and

forwarding the packet in accordance with the network routing prefix to deliver the packet comprising said destination address to the packet'"'"'s destination specified by the destination address.

42. The method of claim 41 further comprising:

receiving a subsequent packet;

retrieving the cached network routing prefix; and

forwarding the subsequent packet over a network to a network address corresponding to the cached network routing prefix.

43. The method of claim 41 further comprising:

sharing the secret information with other routers of a defined privacy domain.

44. The method of claim 41 further comprising:

updating the cached network routing prefix if the secret information changes.

58. An apparatus adapted to perform the method of claim 41.

45. A method for network communication in a network comprising a privacy domain comprising a plurality of networked devices comprising one or more routers, the network domain comprising a plurality of subnets, wherein each of said devices is associated with at least one of said subnets, and each of said subnets is associated with at least one subnet address corresponding to a prefix of an address of a networked device, the method comprising the one or more routers of the privacy domain advertising prefixes associated with the subnet addresses, but at least one of the networked devices in the privacy domain having an address whose prefix does not coincide with any of the advertised prefixes.

46. The method of claim 45 wherein the one or more routers of the privacy domain are provided with a key for decrypting the prefix of the address of said at least one of the networked devices.

47. The method of claim 45 wherein the prefix of the address of said at least one of the networked devices comprises a portion common to the advertised prefixes, to allow a router outside the privacy domain to route a packet with the address of said at least one of the networked devices to the privacy domain.

59. An apparatus adapted to perform the method of claim 45.

48. A method for network communications, the method comprising a host receiving a data packet in a subnet with which the host is associated, the data packet comprising a destination address identifying the host, the destination address comprising an encryption of a subnet address of the subnet.

49. The method of claim 48 wherein the data packet does not comprise the subnet address in unencrypted form.

50. The method of claim 48 wherein the packet originated in a privacy domain comprising one or more routers decrypting the subnet address to route the packet to the host, and the packet has never left the privacy domain to reach a router not operable to decrypt the subnet address.

60. An apparatus adapted to perform the method of claim 48.

51. A method for delivering a data packet over a network to a host in a privacy domain, the data packet having a destination address comprising an encrypted portion of a subnet address of a subnet associated with a host and an encrypted portion of the subnet address, the method comprising:

routing the packet by one or more routers outside the privacy domain to a router in the privacy domain using the unencrypted portion without decrypting the encrypted portion; and

routing the packet by one or more routers inside the privacy domain by decrypting the decrypted portion.

61. An apparatus adapted to perform the method of claim 51.