Article: Vulnerability analysis of certificate graphs Journal: International Journal of Security and Networks (IJSN) 2006 Vol.1 No.1/2 pp.13 - 23 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<SUP align="right"><SMALL>h</SMALL></SUP>. 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. Inderscience Publishers - linking academia, business and industry through research

Title: Vulnerability analysis of certificate graphs

Authors: Eunjin (EJ) Jung, Mohamed G. Gouda

Addresses: Department of Computer Science, University of Iowa, Iowa City, IA 52242, USA. ' Department of Computer Science, University of Texas, Austin, TX 78712, USA

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.

Keywords: certificate systems; certificate graphs; vulnerability analysis; security; authentication; private keys; public keys; networks.

DOI: 10.1504/IJSN.2006.010820

International Journal of Security and Networks, 2006 Vol.1 No.1/2, pp.13 - 23

Published online: 06 Sep 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Vulnerability analysis of certificate graphs

Keep up-to-date