PEER-TO-PEER NAME RESOLUTION PROTOCOL (PNRP) SECURITY INFRASTRUCTURE AND METHOD
FIELD OF THE INVENTION
[0001] The present invention relates generally to peer-to-peer protocols, and more particularly to security framework infrastructures for to peer-to-peer protocols.
BACKGROUND OF THE INVENTION
[0002] Peer-to-peer communication, and in fact all types of communication, depend on the possibility of establishing valid connections between selected entities. However, entities may have one or several addresses that may vary because the entities move in the network, because the topology changes, or because an address lease cannot be renewed A classic architectural solution to this addressing problem is thus to assign to each entity a stable name, and to "resolve" this name to a current address when a connection is needed. This name to address translation must be very robust, and it must also allow for easy and fast updates.
[0003] To increase the likelihood that an entity's address may be found by those seeking to connect to it, many peer-to-peer protocols allow entities to publish their address through various mechanisms Some protocols also allow a client to acquire knowledge of other entities'

addresses through the processing of requests from others in the network. Indeed, it is this acquisition of address knowledge that enables successful operation of these peer-to-peer networks. That is, the better the information about other peers in the network, the greater the likelihood that a search for a particular resource will converge.
[0004] However, without a robust security infrastructure underlying the peer-to-peer protocol, malicious entities can easily disrupt the ability for such peer-to-peer systems to converge. Such disruptions may be caused, for example, by an entity that engages in identity theft. In such an identity theft attack on the peer-to-peer network, a malicious node publishes address information for IDs with which it does not have an authorized relationship, i.e. it is neither the owner nor a group member, etc. A malicious entity could also intercept and/or respond first before the good node responds, thus appearing to be the good node.
[0005] A malicious entity could also hamper PNRP resolution by flooding the network with bad information so that other entities in the network would tend to forward requests to nonexistent nodes (which would adversely affect the convergence of searches), or to nodes controlled by the attacker. This could also be accomplished by modifying the RESOLVE packet used to discover resources before forwarding it along, or by sending an invalid RESPONSE to back to the requestor which generated the RESOLVE packet. A malicious entity could also attempt to disrupt the operation of the peer-to-peer network by trying to ensure that searches will not converge by, for example, instead of forwarding the search to a node in its cache that is closer to the ID to aid in the convergence of the search, forwarding the search to a node that is

further away from the requested ID. Alternatively, the malicious entity could simply not respond to the search request at all. The PNRP resolution could be further hampered by a malicious node sending an invalid BYE message on behalf of a valid ID. As a result, other nodes in the cloud will remove this valid ID from their cache, decreasing the number of valid nodes stored therein.
[0006] While validation of an address certificate may prevent the identity theft problem, such is ineffective against this second type of attack that hampers PNRP resolution. An attacker can continue to generate verifiable address certificates (or have them pre-generated) and flood the corresponding IDs in the peer-to-peer cloud. If any of the nodes attempts to verify ownership of the ID, the attacker would be able to verify that it is the owner for the flooded IDs because, in fact, it is. However, if the attacker manages to generate enough IDs it can bring most of the peer-to-peer searches to one of the nodes controlled by him. At this point the attacker can fairly well control and direct the operation of the network.
[0007] If the peer-to-peer protocol requires that all new address information first be verified to prevent the identity theft problem discussed above, a third type of attack becomes available to malicious entities This attack to which these types of peer-to-peer networks are susceptible is a form of a denial of service (DoS) attack. If all the nodes that learn about new records try to perform the ID ownership check, a storm of network activity against the advertised ID owner will occur Exploiting this weakness, an attacker could mount an IP DoS attack against a certain target by making that target very popular. For example, if a malicious entity advertises Microsoft's Web IP address as the IDs IP, all the nodes in the peer-to-peer network that receive

this advertised IP will try to connect to that IP (Microsoft's Web server's IP) to verify the authenticity of the record. Of course Microsoft's server will not be able to verify ownership of the ID because the attacker generated this information. However, the damage has already been done. That is, the attacker just managed to convince a good part of the peer-to-peer community to attack Microsoft.
[0008] Another type of DoS attack that overwhelms a node or a cloud by exhausting one or more resources is perpetrated by a malicious node that sends a large volume of invalid/valid PACs to a single node, e.g. by using FLOOD/RESOLVE/SOLICIT packets). The node that receives these PACs will consume all its CPU trying to verify all of the PACs. Similarly, by sending invalid FLOOD/RESOLVE packets, a malicious node will achieve packet multiplication within the cloud. That is, the malicious node can consume network bandwidth for a PNRP cloud using a small number of such packets because the node to which these packets are sent will respond by sending additional packets. Network bandwidth multiplication can also be achieved by a malicious node by sending bogus REQUEST messages to which good nodes will respond by FLOODing the PACs, which are of a larger size than the REQUEST.
[0009] A malicious node can also perpetrate an attack in the PNRP cloud by hampering the initial node synch up. That is, to join the PNRP cloud a node tries to connect to one of the nodes already present in the PNRP cloud. If the node tries to connect to the malicious node, it can totally be controlled by that malicious node. Further, a malicious node can send invalid REQUEST packets when two good nodes are involved in the synchronization process. This is a

type of DoS attack that will hamper the synch up because the invalid REQUEST packets will initiate the generation of FLOOD messages in response
[0010] There exists a need in the art, therefore, for security mechanisms that will ensure the integrity of the P2P cloud by preventing or mitigating the effect of such attacks.
BRIEF SUMMARY OF THE INVENTION
[0011] The inventive concepts disclosed in this application involve a new and improved method for inhibiting a malicious node's ability to disrupt normal operation of a peer-to-peer network. Specifically, the present invention presents methods to address various types of attacks that may be launched by a malicious node, including identity theft attacks, denial of service attacks, attacks that merely attempt to hamper the address resolution in the peer-to-peer network, as well as attacks that attempt to hamper a new node's ability to join and participate in the peer-to-peer network.
[0012] The security infrastructure and methods presented allow both secure and insecure identities to be used by nodes by making them self-verifying. When necessary or opportunistic, ID ownership is validated by piggybacking the validation on existing messages or, if necessary, by sending a small inquire message. The probability of connecting initially to a malicious node is reduced by randomly selecting to which node to connect. Further, information from malicious nodes is identified and can be disregarded by maintaining information about prior

communications that will require a future response. Denial of service attacks are inhibited by allowing the node to disregard requests when its resource utilization exceeds a predetermined limit The ability for a malicious node to remove a valid node is reduced by requiring that revocation certificates be signed by the node to be removed.
[0013] In accordance with one embodiment of the present invention, a method of generating a self-verifiable insecure peer address certificate (PAC) that will prevent a malicious node from publishing another node's secure identification in an insecure PAC in the peer-to-peer network is presented. This method comprises the steps of generating an insecure PAC for a resource discoverable in the peer-to-peer network. The resource has a peer-to-peer identification (ID). The method further includes the step of including an uniform resource identifier (URI) in the insecure PAC from which the peer-to-peer ID is derived. Preferably, the URI is in the format "p2p:/AJRI". The peer-to-peer ID may also be insecure
[0014] In a further embodiment, a method of opportunistically validating a peer address certificate at a first node in a peer-to-peer network is presented. This first node utilizes a multilevel cache for storage of peer address certificates, and the method comprises the steps of receiving a peer address certificate (PAC) purportedly from a second node and determining in which level of the multilevel cache the PAC is to be stored. When the PAC is to be stored in one of two lowest cache levels, the method places the PAC in a set aside list, generates an INQUIRE message containing an ID of the PAC to be validated, and transmits the INQUIRE message to the second node. When the PAC is to be stored in an upper cache level other than one of the two

lowest cache levels, the method stores the PAC in the upper cache level marked as 'not validated'. In this case, the PAC will be validated the first time it is used. The method may also request a certificate chain for the PAC.
[0015] In a preferred embodiment, generation of the INQUIRE message comprises the step of generating a transaction ID to be included in the INQUIRE message. When an AUTHORITY message is received from the second node in response to the INQUIRE message, the PAC is removed from the set aside list and is stored in the one of the two lowest cache levels. If a certificate chain was requested, the AUTHORITY message is examined to determine if the certificate chain is present and valid. If it is, the PAC is stored in the one of the two lowest cache levels, and if not it is deleted. A transaction ID may also be used in an embodiment of the invention to ensure that the AUTHORITY message is in response to a prior communication.
[0016J In a further embodiment of the present invention, a method of discovering a node in a peer-to-peer network in a manner that reduces the probability of connecting to a malicious node is presented This method comprises the steps of broadcasting a discovery message in the peer-to-peer network without including any IDs locally registered, receiving a response from a node in the peer-to-peer network, and establishing a peering relationship with the node. In one embodiment, the step of receiving a response from a node comprises the step of receiving a response from at least two nodes in the peer-to-peer network. In this situation, the step of establishing a peering relationship with the node comprises the steps of randomly selecting one

of the at least two nodes and establishing a peering relationship with the randomly selected one of the at least two nodes.
[0017] In yet a further embodiment of the present invention, a method of inhibiting a denial of service attack based on a synchronization process in a peer-to-peer network is presented. This method comprises the steps of receiving a SOLICIT message requesting cache synchronization from a first node containing a peer address certificate (PAC), examining the PAC to determine its validity, and dropping the SOLICIT packet when the step of examining the PAC determines that the PAC is not valid. Preferably, when the step of examining the PAC determines that the PAC is valid, the method further comprises the steps of generating a nonce, encrypting the nonce with a public key of the first node, generating an ADVERTISE message including the encrypted nonce, and sending the ADVERTISE message to the first node When a REQUEST message is received from the first node, the method examines the REQUEST message to determine if the first node was able to decrypt the encrypted nonce, and processes the REQUEST message when the first node was able to decrypt the encrypted nonce
[0018] Preferably, this method further comprises the steps of maintaining connection information specifically identifying the communication with the first node, examining the REQUEST message to ensure that it is specifically related to the ADVERTISE message, and rejecting the REQUEST message when it is not specifically related to the ADVERTISE message. In one embodiment the step of maintaining connection information specifically identifying the communication with the first node comprises the steps of calculating a first bitpos

as the hash of the nonce and the first node's identity, and setting a bit at the first bitpos in a bit vector. When this is done, the step of examining the REQUEST message comprises the steps of extracting the nonce and the first node's identity from the REQUEST message, calculating a second bitpos as the hash of the nonce and the first node's identity, examining the bit vector to determine if it has a bit set corresponding to the second bitpos, and indicating that the REQUEST is not specifically related to the ADVERTISE message when the step of examining the bit vector does not find a bit set corresponding to the second bitpos. Alternatively, the nonce may be used directly as the bitpos. In this case, when the REQUEST is received, the bitpos corresponding to the enclosed nonce is checked. If it is set, this is a valid REQUEST and the bitpos is cleared. Omerwise, this is an invalid REQUEST or replay attack, and the REQUEST is discarded
[0019] In yet a further embodiment of the present invention, a method of inhibiting a denial of service attack based on a synchronization process in a peer-to-peer network comprises the steps of receiving a REQUEST message purportedly from a first node, determining if the REQUEST message is in response to prior communication with the first node, and rejecting the REQUEST message when the REQUEST message is not in response to prior communication with the first node. Preferably, the step of determining if the REQUEST message is in response to prior communication comprises the steps of extracting a nonce and an identity purportedly of the first node from the REQUEST message, calculating a bitpos as the hash of the nonce and the identity, examining a bit vector to determine if it has a bit set corresponding to the bitpos, and

indicating that the REQUEST is not in response to prior communication with the first node when there is no bit set corresponding to the bitpos.
[0020] A method of inhibiting denial of service attacks based on node resource consumption in a peer-to-peer network is also presented. This method comprises the steps of receiving a message from a node in the peer-to-peer network, examining current resource utilization, and rejecting processing of the message when the current resource utilization is above a predetermined level. When a RESOLVE message is received, the step of rejecting processing of the message comprises the step of sending an AUTHORITY message to the first node. This AUTHORITY message contains an indication that the RESOLVE message will not be processed because the current resource utilization too high. When a FLOOD message is received containing a peer address certificate (PAC) and the method determines that the PAC should be stored in one of two lowest cache levels, the step of rejecting processing of the message comprises the step of placing the PAC in a set aside list for later processing. If the method determines that the PAC should be stored in a cache level higher than two lowest cache levels, the step of rejecting processing of the message comprises the step of rejecting the FLOOD message
[0021] In another embodiment of the present invention, a method of inhibiting denial of service attacks based on node bandwidth consumption in a peer-to-peer network is presented This method comprises the steps of receiving a request for cache synchronization from a node in the peer-to-peer network, examining a metric indicating a number of cache synchronizations

performed in the past, and rejecting processing of the request for cache synchronization when the number of cache synchronization performed in the past exceed a predetermined maximum. In a further embodiment, the method examines the metric to determine the number of cache synchronizations performed during a predetermined preceding period of time. In this embodiment the step of rejecting processing of the request comprises the step of rejecting processing of the request for cache synchronization when the number of cache synchronizations performed in the preceding period of time exceeds a predetermined maximum.
[0022] In another embodiment of the present invention, a method of inhibiting a search based denial of service attack in a peer-to-peer network comprises the steps of examining cache entries of known peer address certificates to determine appropriate nodes to which to send a resolution request, randomly selecting one of the appropriate nodes, and sending the resolution request to the randomly selected node. In one embodiment the step of randomly selecting one of the appropriate nodes comprises the step of calculating a weighted probability for each of the appropriate nodes based on the distance of the PNRP ID from the target ID. The probability of choosing a specific next hop is then determined as an inverse proportionality to the ID distance between that node and the target node.
[0023] In a further embodiment of the present invention, a method of inhibiting a search based denial of service attack in a peer-to-peer network comprises the steps of receiving a RESPONSE message, determining if the RESPONSE message is in response to a prior RESOLVE message, and rejecting the RESPONSE message when the RESPONSE message is

not in response to the prior RESOLVE message. Preferably, the step of determining if the RESPONSE message is in response to a prior RESOLVE message comprises the steps of calculating a bitpos as a hash of information in the RESPONSE message, and examining a bit vector to determine if a bit corresponding to the bitpos is set therein.
[0024] In one embodiment wherein the RESPONSE message contains an address list, the method further comprises the steps of determining if the RESPONSE message has been modified in an attempt to hamper resolution, and rejecting the RESPONSE message when the RESPONSE message has been modified in an attempt to hamper resolution. Preferably the step of determining if the RESPONSE message has been modified in an attempt to hamper resolution comprises the steps of calculating a bitpos as a hash of the address list in the RESPONSE message, and examining a bit vector to determine if a bit corresponding to the bitpos is set therein.
[0025] In another embodiment of the present invention, a method of inhibiting a malicious node from removing a valid node from the peer-to-peer network comprises the steps of receiving a revocation certificate purportedly from the valid node having a peer address certificate (PAC) stored in cache, and verifying that the revocation certificate is signed by the valid node.

BRIEF DESCRIPTION OF THE DRAWINGS
[0026] The accompanying drawings incorporated in and forming a part of the specification illustrate several aspects of the present invention, and together with the description serve to explain the principles of the invention. In the drawings:
[0027] FIG. 1 is a block diagram generally illustrating an exemplary computer system on
which the present invention resides;
[0028] FIG. 2 is a simplified flow diagram illustrating security aspects of AUTHORITY
packet processing in accordance with an embodiment of the present invention;
[0029] FIG. 3 is a simplified communications processing flow diagram illustrating secunty
aspects of a synchronization phase of P2P discovery in accordance with an embodiment of the
present invention;
[0030] FIG. 4 is a simplified flow diagram illustrating secunty aspects of RESOLVE packet
processing in accordance with an embodiment of the present invention;
[0031] FIG. 5 is a simplified flow diagram illustrating security aspects of FLOOD packet
processing in accordance with an embodiment of the present invention; and
[0032] FIG 6 is a simplified flow diagram illustrating security aspects of RESPONSE packet
processing in accordance with an embodiment of the present invention.
[0033] While the invention will be descnbed in connection with certain preferred embodiments, there is no intent to limit it to those embodiments. On the contrary, the intent is to

cover all alternatives, modifications and equivalents as included within the spirit and scope of the invention as defined by the appended claims.
DETAILED DESCRIPTION OF THE INVENTION
[0034] Turning to the drawings, wherein like reference numerals refer to like elements, the invention is illustrated as being implemented in a suitable computing environment. Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by a personal computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Moreover, those skilled in the art will appreciate that the invention may be practiced with other computer system configurations, including hand-held devices, multi-processor systems, microprocessor based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.
[0035] Figure 1 illustrates an example of a suitable computing system environment 100 on which the invention may be implemented. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to

the scope of use or functionality of the invention. Neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100.
[0036] The mvention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.
[0037] The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices

[0038] With reference to Figure 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a computer 110. Components of computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The system bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Associate (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus
[0039] Computer 110 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can

be accessed by computer 110. 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. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. 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. Combinations of the any of the above should also be included within the scope of computer readable media
[0040] The system memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS), containing the basic routines that help to transfer information between elements within computer 110. such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120 By way of example, and not limitation, Figure 1 illustrates operating system 134, application programs 135, other program modules 136, and program data 137.
[0041] The computer 310 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, Figure 1 illustrates a hard disk drive 141 that reads from or writes to non-removable, nonvolatile magnetic media, a

magnetic disk drive 151 that reads from or writes to a removable, nonvolatile magnetic disk 152, and an optical disk drive 155 that reads from or writes to a removable, nonvolatile optical disk 156 such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive 141 is typically connected to the system bus 121 through a non-removable memory interface such as interface 140, and magnetic disk drive 151 and optical disk drive 155 are typically connected to the system bus 121 by a removable memory interface, such as interface 150.
[0042] The drives and their associated computer storage media discussed above and illustrated in Figure 1, provide storage of computer readable instructions, data structures, program modules and other data for the computer 110. In Figure 1, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146, and program data 147. Note that these components can either be the same as or different from operating system 134, application programs 135, other program modules 136, and program data 137. Operating system 144, application programs 145, other program modules 146, and program data 147 are given different numbers hereto illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer 110 through input devices such as a keyboard 162 and pointing device 161, commonly referred to as a mouse, trackball or touch pad. Other input devices (not shown) may include a microphone, joystick,

game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 120 through a user input interface 160 that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor 191 or other type of display device is also connected to the system bus 121 via an interface, such as a video interface 190. In addition to the monitor, computers may also include other peripheral output devices such as speakers 197 and printer 196, which may be connected through a output peripheral interface 195.
[0043] The computer 110 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. The remote computer 180 may be another personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the personal computer 110, although only a memory storage device 181 has been illustrated in Figure 1. The logical connections depicted in Figure 1 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.
[0044] When used in a LAN networking environment, the personal computer 110 is connected to the LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet The modem 172, which

may be internal or external, may be connected to the system bus 121 via the user input interface 160, or other appropriate mechanism. In a networked environment, program modules depicted relative to the personal computer 110, or portions thereof, may be stored in the remote memory storage device By way of example, and not limitation, Figure 1 illustrates remote application programs 185 as residing on memory device 181. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.
[0045] In the description that follows, the invention will be described with reference to acts and symbolic representations of operations that are performed by one or more computer, unless indicated otherwise. As such, it will be understood that such acts and operations, which are at times referred to as being computer-executed, include the manipulation by the processing unit of the computer of electrical signals representing data in a structured form This manipulation transforms the data or maintains it at locations in the memory system of the computer, which reconfigures or otherwise alters the operation of the computer in a manner well understood by those skilled in the art. The data structures where data is maintained are physical locations of the memory that have particular properties defined by the format of the data However, while the invention is being described in the foregoing context, it is not meant to be limiting as those of skill in the art will appreciate that various of the acts and operation described hereinafter may also be implemented in hardware.

[0046] As introduced above, the success of a peer-to-peer (P2P) protocol depends on the protocol's ability to establish valid connections between selected entities. Because a particular user may connect to the network in various ways at various locations having different addresses, a preferred approach is to assign a unique identity to the user, and then resolve that identity to a particular address through the protocol. Such a peer-to-peer name resolution protocol (PNRP) to which the security infrastructure of the instant invention finds particular applicability is described in co-pending Application No. 09/942,164, entitled Peer-To-Peer Name Resolution Protocol (PNRP) And Multilevel Cache For Use Therewith, filed on August 29, 2001, the teachings and disclosure of which are hereby incorporated in their entireties by reference thereto. However, one skilled in the art will recognize from the following teachings that the security infrastructure and methods of the present invention are not limited to the particular peer-to-peer protocol of this co-pending application, but may be applied to other protocols with equal force.
[0047] As discussed in the above-incorporated co-pending application, the peer name resolution protocol (PNRP) is a peer-based name-to-address resolution protocol. Names are 256-bit numbers called PNRP IDs. Addresses consist of an IPv4 or IPv6 address, a port, and a protocol number. When a PNRP ID is resolved into an address, a peer address certificate (PAC) is returned. This certificate includes the target's PNRP ID, current IP address, public key, and many other fields. An instance of the PNRP protocol is called a node. A node may have one or more PNRP IDs registered locally. A node makes an ID-to-address mapping discoverable in PNRP via registration. Each registration includes a locally constructed peer certificate, and requires an appropriate view of the PNRP cache. Hosts which are not PNRP nodes may resolve

PNRP IDs into IP addresses via a PNRP DNS gateway A PNRP DNS gateway accepts DNS 'A' and 'AAAA' queries, performs a PNRP search for a subset of the hostname specified, and returns the results as a DNS query answer.
[0048] As indicated above, PNRP provides a peer-based mechanism associating P2P and PNRP IDs with peer address certificates (PACs). A P2P ID is a persistent 128-bit identifier P2P IDs are created by hashing a correctly formatted P2P name. There are two types of P2P IDs, secure and insecure. A secure P2P ID is an ID with a verifiable relationship to a public key An insecure P2P ID is any ID which is not secure A given P2P ID may be published by many different nodes PNRP uses a 'service location' suffix to ensure each published instance has a unique PNRP ID. A 'service location' is a 128-bit number corresponding to a unique network service endpoint Service locations have some recognizable elements, but should be considered opaque by PNRP clients A service location has two important properties. At any moment, only one socket in the cloud corresponds to a given service location. When two service locations are compared, the length of the common prefix for each is a reasonable measure of network proximity. Two service locations which start with the same four bits are no further apart than two which start with the same three bits.
[0049] A P2P ID is uniquely identified by its catenation with the service location. The resulting 256-bit (32 byte) identifier is called a PNRP ID. PNRP nodes register a PNRP ID by invoking PNRP services with a P2P name, authority, and several other parameters. PNRP services then creates and maintains a Peer Address Certificate (PAC) containing the submitted

data. PACs include at a minimum a PNRP ID, certificate validity interval, service and PNRP address, public key, and a cryptographic signature generated over select PAC contents.
[0050] Creation and registration of PNRP IDs is only one part of the PNRP service. The PNRP service execution can be divided into four phases. The first is PNRP cloud discovery. During this phase a new node must find an existing node in the cloud it wishes to join. The cloud may be the global PNRP cloud, a site local (enterprise) cloud, or a link local cloud Once found, the second phase of joining a PNRP cloud is entered. Once the new node has found an existing node, it performs a SYNCHRONIZE procedure to obtain a copy of the existing nodes top cache level. A single cache level provides enough basis for a new node to start participating in the cloud. Once the SYNCHRONIZATION has been achieved, the next phase, active participation in the cloud, may be begun. After initialization has completed, the node may participate in PNRP ID registration and resolution. During this phase, the peer also performs regular cache maintenance. When the node is done, it enters the fourth phase, leaving the cloud. The node un-registers any locally registered PNRP IDs, then terminates.
[0051] The PNRP protocol consists of nine different types of packets, some of which have been introduced above It should be noted, however, that in this application the names of the packets are used merely to facilitate an understanding of their functionality, and should not be taken as limiting the form or format of the packet or message itself. The RESOLVE packet requests resolution of a target PNRP ID into a PAC. A RESPONSE packet is the result of a completed RESOLVE request. The FLOOD packet contains a PAC intended for the PNRP

cache of the recipient. A SOLICIT packet is used to ask a PNRP node to ADVERTISE its top level cache. The requested ADVERTISE packet contains a list of PNRP IDs for PACs in a node's top level cache. A REQUEST packet is used to ask a node to flood a subset of ADVERTISE'd PACs. An INQUIRE packet is used to insecurely ask a node whether a specific PNRP ID is registered at that node. To confirm local registration of a PNRP ID, an AUTHORITY packet is used. This packet optionally provides a certification chain to help validate the PAC for that ID. An ACK packet acknowledges receipt and/or successful processing of certain messages. Finally, the REPAIR packet is used to try to merge clouds that may be split.
[0052] Once a node is fully initialized, it may participate in the PNRP cloud by performing five types of activities. First, a node may register and un-register PNRP IDs. When a PNRP ID is registered, the PNRP service creates a peer address certificate (PAC) associating the PNRP ID, service address port and protocol, PNRP address port and protocol, and a public key. This PAC is entered into the local cache, and a RESOLVE is initiated using the new PAC as the source, and [PNRP ID + I] as the target This RESOLVE is processed by a number of nodes with PNRP IDs very similar to the registered ID Each recipient of the RESOLVE adds the new node's PAC to their cache, thereby advertising the new PNRP ID in the cloud. When a PNRP ID is unregistered, an updated PAC is created with a 'revoke' flag set The updated PAC is flooded to all entries in the lowest level of the local cache. Each recipient of the FLOOD checks its cache for an older version of the PAC If one is found, the recipient removes the PAC from its cache If

the PAC is removed from the lowest cache level, the recipient in turn FLOODs the revocation to the PNRP nodes represented by all other PACs in its lowest cache level
[0053] The PNRP node may also participate in PNRP ID resolution. As discussed in the above incorporated application, PNRP IDs are resolved into PACs by routing RESOLVE messages successively closer to the target PNRP ID. When a node receives a RESOLVE, it may reject the RESOLVE back to the previous hop, respond to the previous hop with a RESPONSE, or forward the RESOLVE to a node whose PNRP ID is closer to the target ID than the node's own The node also receives and forwards RESPONSE packets as part of resolution. The PNRP node may also initiate RESOLVEs on behalf of a local client. The PNRP service provides an API to allow asynchronous resolution requests. The local node originates RESOLVE packets, and eventually receives a corresponding RESPONSE
[0054] The PNRP node also honors cache synchronization requests Upon receiving a SOLICIT packet, the node responds with an ADVERTISE packet, listing the PNRP IDs in its highest cache level. The solicitor node then sends a REQUEST listing the PNRP IDs for any ADVERTISED PACs it wants. Each REQUESTed cache entry is then FLOODed to the REQUESTor Finally, and as will be discussed more fully below, the PNRP also performs identity validation. Identity validation is a threat mitigation device used to validate PACs. Identity validation basically has two purposes First, identity validation ensures that the PNRP node specified in a PAC has the PNRP ID from that PAC locally registered. Second, for secure

PNRP IDs (discussed below), identity validation ensures that the PAC was signed using a key with a cryptographically provable relationship to the authority m the PNRP ID.
[0055] Having now provided a working knowledge of the PNRP system for which an embodiment of the security infrastructure of the present invention finds particular relevance, attention is now turned to the security mechanisms provided by the security infrastructure of the present invention. These mechanisms are provided by the system of the present invention to eliminate, or at a minimum mitigate, the effect of the various attacks that may be posed by a malicious node in a P2P cloud as discussed above. The PNRP protocol does not have any mechanism to prevent these attacks, nor is there a single solution to address all of these threats. The secunty infrastructure of the present invention, however, minimizes the disruption that may be caused by a malicious node, and may be incorporated into the PNRP protocol.
[0056] As with many successful P2P protocols, entities can be published for easy discovery. To provide security and integrity to the P2P protocol, however, each identity preferably includes an attached identity certificate. However, a robust security architecture will be able to handle both secure and insecure entities. In accordance with an embodiment of the present invention, this robustness is provided through the use of self-verifying PACs.
[0057] A secure PAC is made self-verifying by providing a mapping between the ID and a public key. This will prevent anyone from publishing a secure PAC without having the private key to sign that PAC, and thus will prevent a large number of identity theft attacks. The keeper

of the ID private key uses the certificate to attach additional information to the ID, such as the IP address, friendly name, etc. Preferably, each node generates its own pair of private-public keys, although such may be provided by a trusted supplier. The public key is then included as part of the node identifier. Only the node that created the pair of keys has the private key with which it can prove that it is the creator of the node identity. In this way, identity theft may be discovered, and is, therefore, deterred.
[0058] A generic format for such certificates may be represented as [Version, ID, , Validity, Algorithms, PIssuer]Kissuer. Indeed, P2P name / URL is part of the basic certificate format, regardless of whether it is a secure or insecure ID. As used in this certificate representation, Version is me certificate version, ID is die identifier to be published, represents information to be associated with the ID, Validity represents the period of validity expressed in a pair of From-To dates expressed as Universal Date Time (aka GMT), Algorithms refers to the algorithms used for generating the key pairs, and for signing, and PIssuer is the public key of the certificate issuer If the certificate issuer is the same as the ID owner then this is PID the public key of the ID owner. The term Kissuer is the private key corresponding to Pissuer- If the certificate issuer is the ID owner then this is KID, the private key of the ID owner.
[0059] In a preferred embodiment, the comprises the address tuple where this ID can be found, and the address tuple for the PNRP service of the issuer. In this embodiment, the address certificate becomes [Version, ID,