Vulnerability analysis of certificate graphs
by Eunjin (EJ) Jung, Mohamed G. Gouda
International Journal of Security and Networks (IJSN), Vol. 1, No. 1/2, 2006

Abstract: A certificate system can be represented by a directed graph, called a certificate graph, where each node represents a user that has a public key and a private key and each edge (u, v) represents a certificate that is signed by the private key of u and contains the public key of v. Two types of damage can be done in a certificate graph when the private key of a node u in the graph is revealed to an adversary: explicit and implicit. The explicit damage is that the adversary can impersonate node u to other nodes in the graph (until it is known to other nodes that the private key of u is revealed). The implicit damage is that the adversary can impersonate nodes other than u to other nodes in the graph. In this paper, we define a metric called vulnerability that measures the scope of explicit and implicit damage that may occur in a certificate graph when the private key of a node in the graph is revealed to an adversary. Using this metric, we analyse the vulnerability of different classes of certificate graphs. For example, in the case of (m, k)-star certificate graphs, the vulnerability is 1−(k−1)/2mk, whereas in the case of (d, h)-tree certificate graphs, the vulnerability is approximately 1−h/d^h. For the same number of nodes, (m, k)-star certificate graphs can be made less vulnerable than (d, h)-tree certificate graphs. We present three algorithms that compute the vulnerability of an arbitrary certificate graph, and use these algorithms to show that certificate dispersal and stricter acceptance criteria reduce the vulnerability of certificate graphs.

Online publication date: Wed, 06-Sep-2006

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Security and Networks (IJSN):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com