Mesh networks with end device recognition

• US 7,489,645 B2
• Filed: 12/17/2003
• Issued: 02/10/2009
• Est. Priority Date: 12/17/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Simon, Daniel R., Wang, Helen Jiahe
• Primary Examiner(s): Chan; Wing F
• Assistant Examiner(s): Sol; Anthony
• Application Number:
  US10/738,802
• Publication Number:
  US 20050135268A1
• Time in Patent Office: 1,882 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 63/064 Hierarchical key distribution, e.g. by multi-tier trusted parties
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 9/006 involving public key infrastructure [PKI] trust models network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04W 12/069 using certificates or pre-shared keys
• CPC Class Codes: H04W 12/122 Counter-measures against attacks; Protection against rogue devices
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 88/14 Backbone network devices

Abstract

An exemplary router performs actions including: receiving at least one certificate from an end device, the at least one certificate issued by another router; ascertaining if the other router is a member of a predetermined neighborhood; determining if the at least one certificate is valid; and if the other router is ascertained to be a member of the predetermined neighborhood and the at least one certificate is determined to be valid, recognizing the end device as privileged. An exemplary mesh router is capable of establishing a wireless mesh network with other mesh routers, the mesh router is further capable of designating a neighborhood administrator mesh router; and the mesh router is adapted to grant privileged status to a particular end device associated with a particular certificate issued by a particular mesh router when the particular mesh router is a member of a neighborhood of the designated neighborhood administrator mesh router.

Claims

1. A router comprising:

a certificate associated with the router and defined by a producing entity of the router and including a name and a signature, the signature created by performing an operation on the name using a private signing key of the producing entity of the router;

a list stored in the router, the list;

enumerating one or more routers each being a member of a predetermined neighborhood of which the router is also a member, the one or more routers each authenticating itself with the router; and

mapping, for each of the one or more routers in the predetermined neighborhood, a copy of a certificate to a corresponding router;

at least one processor; and

one or more media including processor-executable instructions that are capable of being executed by the at least one processor, the processor-executable instructions adapted to direct the router to perform actions comprising;

receiving, from an end device with which the router has not established trust relationship, a request comprising a first and a second certificate, wherein;

the first certificate is a certificate of a first router that authenticates the end device, the first certificate comprising a public key of a public-private key pair associated with the first router; and

the second certificate is a certificate associated with the end device, the second certificate having a signature signed by the first router using a private key of the public-private key pair associated with the first router;

ascertaining the first router is an authenticated member of the predetermined neighborhood by looking up the first router in the list stored in the router;

determining the first certificate is valid by comparing the first certificate with a copy in the list of the certificate mapped to the first router;

determining the second certificated is valid without routing the second certificate to the first router for its validation, the determining comprising performing, at the router, a signature verification procedure on the signature of the second certificate to verify, based on the pubic key in the first certificate, that the signature is signed by the first router; and

in an event the first router is ascertained to be a member of the predetermined neighborhood and the first and second certificates are determined to be valid, recognizing the end device as having a privileged status;

the privileged status relating to level of service.

2. The router as recited in claim 1, wherein the router further comprises:

a wireless transceiver that enables wireless communication with end devices and/or other routers.

3. The router as recited in claim 1, wherein the receiving action comprises:

receiving an identification of the first router from the end device.

4. The router as recited in claim 1, wherein the receiving action comprises receiving, from the end device:

a membership certificate indicating that the first router is a member of the predetermined neighborhood; and

a certificate of a neighborhood administrator of the predetermined neighborhood, wherein the certificate of the neighborhood administrator signed the membership certificate.

5. The router as recited in claim 1, wherein the list further comprises a secret key shared exclusively between the router and each of the one or more routers in the predetermined neighborhood when the router and each of the one or more routers are mutually authenticated.

6. The router as recited in claim 1, wherein the ascertaining action comprises:

ascertaining if the first router is a member of the predetermined neighborhood, wherein the predetermined neighborhood comprises a neighborhood to which the router is also a member.

7. The router as recited in claim 1, wherein the ascertaining action comprises:

ascertaining if the first router is a member of the predetermined neighborhood, wherein the predetermined neighborhood comprises a neighborhood having a neighborhood administrator that is trusted by a neighborhood administrator of a neighborhood to which the router is a member.

8. The router as recited in claim 1, wherein the recognizing action comprises:

recognizing the end device as being affiliated with the first router wherein the first router is a neighborhood member.

9. The router as recited in claim 1, wherein the recognizing action comprises:

recognizing the end device as being affiliated with the first router wherein the first router is a member of a neighborhood having reciprocity recognition with a neighborhood to which the router is a member.

10. The router as recited in claim 1, wherein the recognizing action comprises:

granting the end device preferred access to a wireless mesh network.

11. The router as recited in claim 1, wherein the processor-executable instructions are adapted to cause the router to perform a further action comprising:

in an event the other router is not ascertained to be a member of the predetermined neighborhood or the at least one of the first and second certificate is not determined to be valid, granting the end device standard access to a wireless mesh network.

12. The router as recited in claim 1, wherein the processor-executable instructions are adapted to cause the router to perform a further action comprising:

issuing a different certificate to a different end device, the different certificate capable of being recognized by the first router;

wherein the router and the first router are peers within a wireless mesh network.

13. One or more processor-accessible storage media having processor-executable instructions stored thereon that, when executed by a first router, configure the first router to implement an arrangement module, the arrangement module comprising:

receiver means for receiving a request form an end device with which the first router has not established trust relationship, the request comprising a first and a second certificate, wherein;

the first certificate is a certificate of a second router to which the end device is affiliated; and

the second certificate is a certificate associated with the end device and signed by the second router;

ascertaining means for ascertaining if the second router is a member of a predetermined neighborhood, the ascertaining comprising looking up the second router in a list locally stored in the first router;

determination means for determining the first and second certificate are valid, the determination means including operation means for performing a public key operation on the second certificate using a public key from the first certificate that is associated with the second router to which the end device is affiliated, the first certificate defined by a producing entity and including a signature created using a private signing key of the producing entity, wherein the determining is performed at the arrangement module without routing the first and second certificate to the second router for its validation; and

recognition means for recognizing the end device as having a privileged status responsive to the ascertaining means and the determination means.

14. One or more processor-accessible storage media as recited in claim 13, wherein the recognition means is adapted to recognize the end device as having the privileged status if the ascertainment means ascertains that:

the second router is a member of the predetermined neighborhood; and

the first and second certificate are valid.

15. One or more processor-accessible storage media as recited in claim 13, wherein the recognition means comprises means for granting preferred access to the end device responsive to the ascertainment means and the determination means.

16. One or more processor-accessible storage media as recited in claim 13, wherein the ascertainment means comprises:

data structure means for storing identifications of neighborhood members; and

access means for checking if the second router is enumerated in the data structure means.

17. One or more processor-accessible storage media as recited in claim 13, wherein the ascertainment means comprises:

data structure means for storing identifications of one or more trusted neighborhood administrators; and

access means for checking if one of the one or more neighborhood administrators of the router, as indicated by a membership certificate, is enumerated in the data structure means.

18. One or more processor-accessible storage media as recited in claim 13, wherein the determination means comprises:

verification means for performing a signature verification procedure on a signature of the second certificate.

19. One or more processor-accessible storage media as recited in claim 13, wherein the router is a mesh router.

20. A mesh router including an associated certificate defined by a producing entity of the mesh router, the associated certificate including a signature created by performing an operation on a name of the mesh router using a private signing key of the producing entity of the mesh router, the mesh router configured to perform action s comprising:

establishing a connection with an end device over a wireless link in a multi-hop wireless network;

receiving a request from the end device with which the mesh router has not established trust relationship, the request comprising a certificate associated with the end device, the certificate having a signature from a second mesh router to which the end device is affiliated;

performing a signature verification procedure on the signature of the certificate without routing the request to the second mesh router for validation by the second mesh router, the signature verification procedure comprising verifying the signature based on available public key of the second mesh router;

in and event the signature verification procedure is successful, granting the end device preferred access.

21. The mesh router as recited in claim 20, wherein the mesh router is configured to perform further actions comprising:

receiving an identifier of the second mesh router that issued the certificate to the end device; and

ascertaining, with regard to the identifier, if the second mesh router is a member of a neighborhood to which the mesh router is also a member.

22. The mesh router as recited in claim 20, wherein the action of receiving comprises:

receiving a second certificate;

wherein the second certificate is associated with the second mesh router.

23. The mesh router as recited in claim 20, wherein the signature is a result of a private key operation using a private key that is associated with the second mesh router.

24. A mesh router that is capable of establishing a wireless mesh network with other mesh routers, the mesh router further capable of designating a neighborhood administrator mesh router;

the mesh router adapted to grant privileged status to a particular end device with which the mesh router has not established trust relationship, the particular end device being associated with a particular certificate issued by a particular mesh router other than the mesh router when the particular mesh router is a member of a neighborhood of the designated neighborhood administrator mesh router, the mesh router including an associated certificate defined by a producing entity of the mesh router, the associated certificate including a name and a signature, the signature created by performing an operation on the name using a private signing key of the producing entity of the mesh router, wherein;

the particular certificate associated with the end device comprises a signature signed by a private key of a public-private key pair associated with the particular mesh router;

a signature verification procedure is performed at the mesh router to verify if the particular certificate is signed by the particular mesh router through an available public key of the public-private key pair associated with the particular mesh router without sending the particular certificate to the particular mesh router for its validation.

25. The mesh router as recited in claim 24, wherein the particular certificate associated with the particular en device includes:

a name of the particular end device, and

a public key of a public-private key pair that is associated with the particular end device.

26. The mesh router as recited in claim 24, wherein the mesh router is further adapted to grant preferred access to the particular end device with regard to the wireless mesh network of which the mesh router forms a node.

27. The mesh router as recited in claim 24, wherein the mesh router is further adapted to recognize certificates that have been hierarchically issued to end device by the other mesh routers that are peers to the mesh router and members of a predetermined neighborhood.

28. The mesh router as recited in claim 27, wherein the predetermined neighborhood comprises at least one of:

the neighborhood of the designated neighborhood administrator mesh router and

a neighborhood having a trusted neighborhood administrator mesh router.

29. The mesh router as recited in claim 24, wherein the mesh router is further adapted to grant privileged status to a given end device associated with a given certificate issued by a given mesh router when the given mesh router is a member of a neighborhood having a trusted neighborhood administrator mesh router.

30. A method of enabling end device recognition at a first router, the method comprising:

receiving, at the first router, a request from an end device with which the first router has not established trust relationship, the request comprising a first and a second certificate, wherein;

the first certificate is a certificate of a second router to which the end device is affiliated, the first certificate comprising a public key of a public-private key pair associated with the second router; and

the second certificate is a certificate associated with the end device and having a signature signed by the second router using a private key of the public-private key pair associated with the second router;

ascertaining the second router is a member of a predetermined neighborhood by looking up the second router in a list, wherein the list enumerates all members of the predetermined neighborhood and the list is stored in the first router;

determining the second certificate is valid without routing the second certificate to the second router for its validation, the determining comprising performing, at the first router, a signature verification procedure on the signature of the second certificate to verify, based on the public key in the first certificate, that the signature is signed by the second router; and

recognizing the end device as having a privileged status in an event the second router is a member of the predetermined neighborhood and the second certificate passes the signature verification procedure.

31. The method as recited in claim 30, further comprising:

signing, by the second router, the second certificate using a private key of the second router; and

issuing, by the second router, the second certificate to the end device.

32. The method as recited in claim 30, further comprising:

connecting, by the end device, to a neighborhood router; and

providing, by the end device, the second certificate and the first certificate of the second router to the neighborhood router;

wherein the neighborhood router performs the receiving, the ascertaining, the determining, and the recognizing.

33. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct a router to perform the method as recited in claim 30.

34. The method as recited in claim 30, wherein the ascertaining comprises:

accessing a list that enumerates at least one of;

routers that are members of a same neighborhood and

trusted neighborhood administrators.

35. The method as recited in claim 30, wherein the ascertaining comprises:

accessing the list that enumerates trusted neighborhood administrators with reference to a membership certificate representing that the second router is a member of a neighborhood having a given neighborhood administrator.