Method and system for authenticating messages

A method and system for authenticating a message is described, in which the message contains a network address, at least a portion of which is a digital fingerprint. Embedded in the message is data, such as a code, that indicates the size of the digital fingerprint. A device receiving the message uses the size data and, for example, the public key of the sender to attempt to reproduce the digital fingerprint. If successful, the device receiving the message verifies the identity of the sender.

TECHNICAL FIELD OF THE INVENTION

The invention relates generally to message authentication and, more particularly, to techniques that involve creating all or part of a network address in such a way that a device sending the network address can be authenticated.

BACKGROUND

Security is an important part of many computer networks. One aspect of network security is the ability to verify the identity of computers and/or their users. For example, in wireless networking, it is common for a client computer to be moved out of the operating range of one wireless base station and into the range of another wireless base station. When this occurs, it is often the case that the client computer receives a new network address from the new base station. To ensure that the client computer is still able to receive messages from other computers, the client computer informs a so-called “home agent” of its new address. A home agent is a computer (such as a server) that maintains a publicly known “home address” for the client computer and keeps track of the actual or “care-of” address of the client computer. When other computers wish to send messages to the client computer, they use the client computer's home address. The home agent then forwards the message to the client's “care-of” address. If a malicious entity such as a hacker wishes to intercept messages intended for the client computer, the malicious entity could simply pretend that it is the client computer and “inform” the home agent of its new care-of address. The home agent, if it was successfully tricked, would then forward the client computer's message to the malicious entity.

The above example illustrates the importance of being able to verify the identity of a computer in a wireless context. However, it is also important to be able to verify the identity of users and/or computers in wired scenarios as well.

SUMMARY

In accordance with the foregoing, a method and system for authenticating a message is provided. According to the invention, a sending device uses a network address that has a digital fingerprint. The sending device creates a message containing both the network address and data representing the size of the digital fingerprint. A receiving device using the size data and, for example, the public key of the sending device, verifies the identity of the sending device. According to various embodiments of the invention, the size data is embedded in the network address itself.

The network address may be created in a variety of ways. According to one embodiment, a first portion of the network address is made up of a cryptographic hash of the public key and the private key of the sending device or its user. The network address also includes a code that indicates how many bits of the network address constitute the first portion.

Additional aspects of the invention will be made apparent from the following detailed description of illustrative embodiments that proceeds with reference to the accompanying figures.

DETAILED DESCRIPTION

The invention is generally directed to a method and system for authenticating a message, in which the message contains a network address, at least a portion of which is a digital fingerprint of the device sending the message. Embedded in the message is data, such as a code, that indicates the size of the digital fingerprint. A device receiving the message uses the size data and, for example, the public key of the sending device to attempt to reproduce the digital fingerprint. If successful, the receiving device verifies the identity of the sender.

Prior to proceeding with a description of the various embodiments of the invention, a description of the computer and networking environment in which the various embodiments of the invention may be practiced will now be provided. Although it is not required, the present invention may be implemented by program modules that are executed by a computer. Generally, program modules include routines, objects, components, data structures and the like that perform particular tasks or implement particular abstract data types. The term “program” as used herein may connote a single program module or multiple program modules acting in concert. The invention may be implemented on a variety of types of computers. Accordingly, the terms “device,” “computing device” and “computer” as used herein include personal computers (PCs), hand-held devices, multi-processor systems, microprocessor-based programmable consumer electronics, network PCs, minicomputers, mainframe computers and the like. The invention may also be employed in distributed computing environments, where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, modules may be located in both local and remote memory storage devices.

An example of a networked environment in which the invention may be used will now be described with reference toFIG. 1. The example network includes several computers10communicating with one another over a network11, represented by a cloud. Network11may include many well-known components, such as routers, gateways, hubs, etc. and may allow the computers10to communicate via wired and/or wireless media. When interacting with one another of the network11, one or more of the computers may act as clients, servers or peers with respect to other computers. Accordingly, the various embodiments of the invention may be practiced on clients, servers, peers or combinations thereof, even though specific examples contained herein don't refer to all of these types of computers.

Referring toFIG. 2, an example of a basic configuration for a computer on which all or parts of the invention described herein may be implemented is shown. In its most basic configuration, the computer10typically includes at least one processing unit14and memory16. Depending on the exact configuration and type of the computer10, the memory16may be volatile (such as RAM), non-volatile (such as ROM or flash memory) or some combination of the two. This most basic configuration is illustrated inFIG. 2by dashed line18. Additionally, the computer may also have additional features/functionality. For example, computer10may also include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information, including computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory, CD-ROM, digital versatile disk (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to stored the desired information and which can be accessed by the computer10. Any such computer storage media may be part of computer10.

Computer10may also contain communications connections that allow the device to communicate with other devices. A communication connection is an example of a communication medium. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. The term computer readable media as used herein includes both storage media and communication media.

Computer10may also have input devices such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output devices such as a display20, speakers, a printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here.

Referring toFIG. 3, an example of how data flows from a first computing device30to a second computing device32according to an embodiment of the invention will now be described. The first computing device30, has a network address34. A portion36of the network address34acts as a digital fingerprint that identifies the first computing device30. That portion36of the network address34is created based on a private key of the first computing device30or the private key of a user of the first device30. The first computing device30transmits the network address34, including the digital fingerprint portion36, as part of a message35to the second computing device32. The type of network address used by the first computing device may be any of a variety of types, including an IP address, a URL or a MAC address. The network address34of the first computing device30may be completely or partially generated by the first computing device30itself, or by another computer such as a router or gateway that serves the first computing device30. The first computing device30also transmits data representing the size of the digital fingerprint portion36of the network address34to the second computing device32. This size data is generally labeled38, and can be expressed in a variety of ways. According to one implementation, the size data38is expressed in terms of the number of bits in the digital fingerprint portion36of the network address34. The public key of the first computing device30may be sent to the second computing device32prior to, or during the transmissions depicted inFIG. 3. In some implementations, the second computing device32obtains the public key of the first computing device30from a third party source, such as a public key registry.

When the second computing device32receives the message35, it uses the size data38to determine what portion of the network address34is represents the digital fingerprint. It also executes an algorithm using the public key of the first computing device30. If the result of the algorithm is equal to the digital fingerprint portion36of the network address34, then the second computing device32deems the first computing device30to be successfully authenticated. If the result of the algorithm is not equal to the digital fingerprint portion36of the network address34, then the second computing device32deems the first computing device30to be unauthenticated.

According to an embodiment of the invention, the network address that the first computing device30(FIG. 3) uses is an Internet Protocol Version 6 (IPv6) address. IPv6 addresses are 128 bits long. An example of an IPv6 address is shown inFIG. 4. It includes a 64-bit route prefix, labeled40, and a 64-bit interface ID, labeled42. The interface ID is also referred to herein as the “node selectable portion.” When an IPv6 address is used in the header of an IPv6 packet that is sent through a network, routers generally use the route prefix40to get the packet to the proper destination subnet, while the subnet uses the interface ID42to get the packet to the appropriate computer on the subnet. The interface ID42is, by convention, formatted as an IEEE EUI-64 identifier. The two least significant bits of the first byte (labeled44inFIG. 4) of the interface ID44are the “U” bit and the “G” bit. The “U” bit indicates whether or not the interface ID44is universal or local, and the “G” bit indicates whether the interface ID represents a group or an individual entity.

In an embodiment of the invention, the first computing device30(FIG. 3) creates an IPv6 address, such as that shown inFIG. 4, chooses a certain number of bits of the IPv6 address such that they represent a digital fingerprint, and indicates in the first byte44(FIG. 4) how many bits of the IPv6 address represent the digital fingerprint. It is to be understood that, in other embodiments, other portions of the network address besides the first byte may be used to convey this information. For example, the last byte of the interface ID may be used. This specially-formatted address becomes the network address34(FIG. 3) that the first computing device30transmits to the second computing device32. This network address is valid and routable in the network of which the first computing device30is a part, and is otherwise usable by the first computing device30in the same manner as any other IPv6 address. When the second computing device32receives the network address34, it examines the first byte44to determine how many bits of it needs to match in the network address34, and executes an algorithm on the first computing device's public key. The second computing device32extracts, from the result of the algorithm, the number of bits indicated by the first byte44, and compares those bits with the bits of digital fingerprint contained in the network address34. For example, if the first byte44indicates that 62 bits of the network address34represent the digital fingerprint, the second computing device32extracts 62 bits from the result of the algorithm performed on the first computing device's public key and compares those 62 bits with the appropriate 62 bits of the network address34. If the two 62-bit sets match, then the second computing device32recognizes the first computing device30as the proper sender.

There are many ways in which the first computing device30(FIG. 3) can use the IPv6 interface ID42(FIG. 4) to express how many bits of the IPv6 address constitute the digital fingerprint. In one embodiment, the first computing device30and the second computing device32each have a look-up table that maps the value of the first byte44to the number of encrypted bits. An example of such a table is shown below as Table 1, in which “c” represents “don't care” digits. It is to be understood that the scheme represented by Table 1 is usable regardless of which byte of the network address is used to express many bits are in the digital fingerprint.

TABLE 1First Byte ofWhere An ExampleInterface IDMeaningIs Shownccccccc00No digital fingerprint is usedccccccc01No digital fingerprint is usedccccccc1062 bits represent a digital fingerprintcccccc01167 bits represent a digital fingerprintccccc011175 bits represent a digital fingerprintcccc0111183 bits represent a digital fingerprintcc01111191 bits represent a digital fingerprintc011111198 bits represent a digital fingerprint01111111104 bits represent a digitalfingerprint11111111120 bits represent a digitalfingerprint

Exactly which bits in the IPv6 address represent the digital fingerprint can be established before the communication between the first computing device30and the second computing device32occurs. An example of one way in which the bits that represent the digital fingerprint are selected is shown inFIGS. 5aand5b, which in ten different 128-bit IPv6 addresses are shown and labeled70-88. In the addresses70and72, there is no digital fingerprint. The U and G bits of the address70are set to 0, while in the address72, that U and G bits are set to 0 and 1 respectively. In the address74, the digital fingerprint is represented by 62 bits of the Interface ID, including 6 bits of the first byte.

In the addresses78through88, portions of the route prefix represent the digital fingerprint. The portion of the route prefix that represents the digital fingerprint is the smallest in the address78and the largest in the address88. In the address88, all of the route prefix is part of the digital fingerprint. Referring back toFIG. 3, when the first computing device30sends its address to the second computing device32using one of the schemes of Table 1 andFIGS. 5a-5b, the second computing device32determines how many bits of the address constitute the digital fingerprint (and, consequently how many bits need to be matched) based on the contents of the first byte of Interface ID. Additionally, the second computing device32knows which bits represent the digital fingerprint based on a common understanding with the first computing device30. For example, if the first computing device30sends its address to the second computing device32in the form of the address84shown inFIG. 5b, then the second computing device would see the pattern 0111111 in the first byte of the Interface ID and would realize that the digital fingerprint is 98 bits long. Based on its common understanding with the first computing device30, the second computing device32would know that the 98 bits of the digital fingerprint (the 98 bits that the second computing device needs to match) includes the 56 bits of bytes2-8of the Interface ID, the most significant bit of byte1of the Interface ID, and the 41 least significant bits of the route prefix.

Referring toFIG. 6aan example of a scenario in which the invention may be used will now be provided. In this example, there is a first wireless network102and a second wireless network104. The first and second wireless networks each have access to an internetwork106. The internetwork106may comprise one or more land networks, including the Internet. When a mobile computer100moves to the second wireless network104, the address of the mobile computer100changes. A home agent114keeps track of the current address of the mobile computer100and acts as base station for the mobile computer100. Third parties can send messages to the home agent114that the home agent114then forwards to the mobile computer100.

In this example, another computer, which will be referred to as a correspondent108, wishes to send messages to the mobile computer100. To get a message to the mobile computer100, the correspondent108sends the message, labeled110, to the mobile computer's “home address.” Following a first message path112, the message is received by the home agent114. By reading the home address in the message110, the home agent114determines that the message110is intended for the mobile computer100. The home agent214translates the mobile computer's home address into the mobile computer's current or care-of address and forwards the message along a second message path116to the mobile computer100.

As shown inFIG. 6b, the mobile computer100moves to the second wireless network104. It then obtains a new “care-of” network address. To update the home agent114regarding its new care-of address, the mobile computer100prepares a binding message124, which if formatted as shown inFIG. 7. The binding message124travels along a message path120to the home agent114. Upon receipt of the binding message124, the home agent114changes an entry in a message forwarding translation table that it maintains. Future messages addressed to the mobile computer's home address are now forwarded to the new address contained in the binding message. For example, the correspondent108, oblivious to the change in the mobile computer's care-of address, sends another message110via a first message path112to the mobile computer's home address. The home agent114translates the home address into the new address and forwards the message110over a second message path122to the mobile computer100. Thus, the correspondent108is able to stay in communication with the mobile computer100even though the correspondent is unaware of the change in the mobile computer's care-of address.

To ensure that an attacker does not trick the home agent114by generating a fraudulent binding message, the mobile computer100uses its public key and its private key to create a hash value, uses at least some of the bits of the hash value as a digital fingerprint, populates its “care-of” address with the digital fingerprint and populates another portion of the care-of address with a code indicating how many bits of the care-of address constitute the digital fingerprint. The home agent114, upon receiving the binding message, calculates a hash of the mobile computer's public key, and compares at least part of the results of the hash with the digital fingerprint contained in the care-of address. If the two values match, then the home agent114updates its binding table to reflect the new care-of address. If the two values do not match, then the home agent114ignores the binding message.

An example of how the binding message is created will now be described in conjunction withFIGS. 7 and 8. In this example, it is assumed that the mobile computer100is using the 98-bit matching scheme shown inFIG. 5b, so that it will try to format its care-of address like the address84. The mobile computer100first obtains a 64-bit node prefix from the second wireless network104. The mobile computer100then creates a digital fingerprint such that at least 41 bits of the digital fingerprint match the least significant 41 bits (reference numeral142) of the route prefix received from the second wireless network104(FIG. 6b). To generate the digital fingerprint, the mobile computer100takes its private key, labeled130(FIG. 7), its public key, labeled132, and, optionally, a modifier134, and performs a mathematical operation on these values using a hash function136. The modifier134may be a value derived from a variety of sources. It may, for example, be a randomly-generated two bit number. The result of the operation is a hash value, labeled137.

There are many ways in which the mobile computer100can ensure that the care-of address ends up containing the digital fingerprint and the code that indicates the size of the digital fingerprint. In an embodiment of the invention, the mobile computer100chooses the private key130and/or the public key132in such a way as to ensure that 41 bits of the resulting hash value137equal the least significant 41 bits of the router prefix (reference numeral142). The mobile computer100then populates the least significant 56 bits of its care-of address, labeled138, with the corresponding bits of the hash value137. The mobile computer100also substitutes the most significant bit of the Interface ID with the corresponding bit of the hash value137. The mobile computer100then substitutes the least significant seven bits of the first byte of the Interface ID (labeled140) with the code 0111111 to indicate that 98 bits of the care-of address are encrypted. Finally, the mobile computer100substitutes the least significant 41 bits of the route prefix with the corresponding 41 bits of the hash value137.

There are many alternative ways in which the mobile computer100may generate the network address. For example, the mobile computer100may generate the entire care-of address using a hash function. In such a case, the mobile computer may chose the private key and/or the public key so that the resulting hash value includes the route prefix obtained from the second wireless network104(FIG. 6b), the interface ID (including those portions that are a part of the digital fingerprint) and the code indicating the size of the digital fingerprint.

There are a variety of ways in which the hash function136may be implemented. For example, when the public key is based on the well-known RSA algorithm, one of the following two functions may be used:

If the fingerprint is the hash of an RSA-based public key and another component, such as a free form name, an algorithm that simply iterates over the several versions of the free form name can be used. An example of such an algorithm is as follows:

The mobile computer100then creates a binding message, as shown inFIG. 8. The binding message includes the current care-of address for the mobile computer100, the modified home address of the mobile computer100, the public key of the mobile computer100, the modifier, a timestamp, and the address of the intended recipient. The binding message also includes a signature, which, in this example, is a hash of the care-of address, the home address, the public key, the modifier, the timestamp; and the address of the intended recipient. The mobile computer100then transmits the binding message144to the home agent114.

When the home agent114receives the binding message144, it attempts to verify the identity of the sender by performing the same hashing operation that the mobile computer100performed (which was shown inFIG. 7). The home agent114extracts the care-of address from the binding message, and locates the code140. The home agent114then refers to a look-up table to determine, based on the code140, how many bits of the care-of constitute the digital fingerprint.

The home agent114then calculates a cryptographic hash of the private key and public key of the mobile computer and if used in the hashing operation of the mobile computer100, the modifier. The home agent114then takes the number of bits specified by the code140from the hash results and compares them to the digital fingerprint portion of the care-of address. For example, if, as shown inFIG. 7, the code140is 0111111 then, using Table 1 as the look-up table, the home agent114will conclude that 98 bits of the care-of address are encrypted. The home agent114will therefore take 98 bits of the hash that it calculated and compare them to the 98 bits of the digital fingerprint. The choice of which 98 bits of the hash to compare will be made according to a common scheme shared by the mobile computer100and the home agent214. In this example, the digital fingerprint portion of the care-of address is the 56 least significant bits of the Interface ID, plus the least significant 41 bits of the routing prefix, plus the most significant bit of the Interface ID. If, based on the comparison, the two sets of bits match, then the home agent114will process the binding message and update the forwarding translation table. If the two sets of bits do not match, then the home agent114disregards the binding message.