Method for authenticating a channel in large-scale distributed systems
First Claim
1. A method for authenticating a channel in a large distributed system, comprising the steps of:
- a) determining a set of independent paths, each of length at most a predetermined value, by which the channel could have been authenticated; and
b) using the paths in the set to authenticate the channel.
1 Assignment
0 Petitions
Accused Products
Abstract
Authenticating the source of a message in a large distributed system can be difficult due to the lack of a single authority that can tell for whom a channel speaks. This has led many to propose the use of a path of authorities, each able to authenticate the next, such that the first authority in the path can be authenticated by the message recipient and the last authority in the path can authenticate the message source. The present invention uses multiple ones of such paths, no two of which share a common authority, to provide independent confirmation of the message source. As the problem of finding a maximum set of such paths of bounded length in a graph-theoretic framework can be shown to be NP-hard, the present invention includes approximation algorithms for this problem. The present invention also includes a PathServer for PGP, a service for finding maximum sets of such paths to support authentication in PGP-based applications.
-
Citations
33 Claims
-
1. A method for authenticating a channel in a large distributed system, comprising the steps of:
-
a) determining a set of independent paths, each of length at most a predetermined value, by which the channel could have been authenticated; and b) using the paths in the set to authenticate the channel. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for authenticating a target channel (t) using a source channel (s) in a large distributed system comprising the steps of:
-
a) determining a plurality of bounded disjoint paths from the source channel (s) to the target channel (t) by; (i) selecting a path from the source (s) channel to the target channel (t) of length at most b that intersects a fewest number of other paths from the source channel (s) to the target channel (t) of at length at most b; (ii) adding the selected path to the plurality of bounded disjoint paths being determined; (iii) deleting the selected path along with all incident edges from a graph of the large distributed system to obtain a revised version of the graph; and (iv) repeating steps (i) through (iii) using a revised version of the graph in each iteration until no more paths can be found in step (i); and b) using the plurality of bounded disjoint paths to authenticate the target channel (t). - View Dependent Claims (8, 9, 10)
-
-
11. A web server providing a plurality of bounded disjoint paths for use in authenticating a target channel (t) using a source channel (s) in a large distributed system comprising:
-
a) means for interfacing with a user to accept a source channel (s) and a target channel (t) specified by the user; b) means for determining a plurality of bounded disjoint paths from the source channel (s) to the target channel (t), said means for determining; (i) selecting a path from the source (s) channel to the target channel (t) of length at most b that intersects a fewest number of other paths from the source channel (s) to the target channel (t) of at length at most b; (ii) adding the selected path to the plurality of bounded disjoint paths being determined by the determining means; (iii) deleting the selected path along with all incident edges from a graph of the large distributed system to obtain a revised version of the graph; and (iv) repeating (i) through (iii) using a revised version of the graph in each iteration until no more paths can be found in (i); and c) means for outputting the plurality of disjoint paths from the source channel (s) to the target channel (t) upon request by a user. - View Dependent Claims (12, 13, 14, 15)
-
-
16. An apparatus for determining an owner of a query key using a sequence of certificates from a trusted key to the query key, wherein a key in each certificate in the sequence verifies a signature on a next certificate in the sequence, and a certificate binds a key to a name and email address using a digital signature, said apparatus comprising:
-
a) a processor determining a plurality of bounded independent paths from the trusted key to the query key; b) a database being coupled to the processor and storing a plurality of PGP certificates, wherein said database includes an interface for receiving periodic updates from a plurality of PGP key servers; and c) a graphical user interface accepting input from the user regarding a path length bound, the trusted key, and the query key. - View Dependent Claims (17, 18)
-
-
19. A method for authenticating a target channel comprising the steps of:
-
a) determining a set of disjoint b-bounded paths from a source channel to a target channel; b) augmenting the set of disjoint b-bounded paths from the source channel to the target channel with other b-bounded paths from the source channel to the target channel; c) choosing a path to augment the set of disjoint b-bounded paths in step b) by minimizing a predetermined criteria; and d) terminating the step of augmenting upon a predetermined condition. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A method for assuring authentication for data received comprising the steps of:
-
a) receiving the data; b) requesting assurance over a trusted channel to an authentication authority; c) learning a graph of the received data; d) determining a set of independent paths by which the channel could have been authenticated; e) deleting paths from the set determined in step d) whose length exceeds a predetermined value; and f) using any paths remaining in the set determined in step e) to authenticate the channel. - View Dependent Claims (29, 30, 31, 32, 33)
-
Specification