CS5430 Homework 4: Certification Authorities
You are expected to work alone on this assignment.
Due: March 5, 2020 at 11:59pm.
No late assignments will be accepted.
Submit your solution using CMS.
Prepare your solution as .pdf, as follows:
Use 10 point or larger font.
Put each problem into a separate file and submit it to the correct CMS
submission box for that problem.
Use at most 1 page per problem.
Your employer --- PKI Enterprises --- has decided to develop and market PKIkit,
which allows an enterprise to design and configure a
distributed certification authority service that stores public keys for some
set PrinNames of names.
The basic building block of PKIkit is a CA-server
that PKI Enterprises will sell.
It is a stand-along computer that connects to a network.
A CA-server named (say) CredServ_i is provisioned with
- a database DB_i (say) pre-loaded with digitally signed certificates.
to denote a certificate where CA-server P
digitally signed an attestation that K_nme is the public key
that corresponds to a private key believed known only to nme.
- a private key that allows CredServ_i to create signed certificates.
A distributed certification authority service named DCAS that handles
key bindings from principal names in PrinNames
is configured by defining a set AllNames of names and defining a directed graph
DCAS = ( Servers , Links ) satisfying:
- PrinNames is a subset of AllNames
- every element of Servers is a CA-server and is included in
- for every name n in AllNames,
some database DB_P contains a certificate
P-cert(n,K_n) where P is in Servers.
Execution of a CA-server CredServ_i is a loop.
Each iteration reads a look-up request message and
generates a look-up response message.
- A look-up request message includes one field:
a name from AllNames.
This is the name of a principal for which a key binding is sought.
- Upon receipt of a look-up request specifying a name A,
CA-server CredServ_i replies with a look-up response message that has two fields:
(i) C(A), which is a signed certificate or null, and
(ii) S(A), which is the name of another CA-server or null.
There are two cases.
If DB_i contains a certificate P-cert(A,K_A) for
some public key K_A then:
- P-cert(A,K_A) is the value returned for C(A)
- null is returned for the value of S(A)
If DB_i does not contain such a certificate then:
- CredServ_k is the value returned for S(A), where
CredServ_k is the name of a CA-server having a shorter path in
DCAS to some CA-server CredServ_j
having a database DB_j that stores a certificate giving a public key for A.
- CredServ_i-cert(CredServ_k ,K_(CredServ_k) ) is the value
returned for C(A).
Suppose we make the following assumptions:
(a) Give the protocol that a client cl_0 would use when starting from
CA server CredServ_n to obtain a candidate
certificate for a given principal A.
Assume CredServ_n is an element of Servers.
Graph DCAS = ( Servers , Links ) is connected and,
therefore, it contains a path from every node to every other node.
Each database DB_i contains a certificate
CredServ_i-cert(CredServ_k ,K_(CredServ_k) ) if Links contains a directed edge
from CredServ_i to CredServ_k.
Not all CA-servers are trusted by all clients, but each client cl_i has a set
trusted_i of CA-servers the client does trust.
(b) Describe how that client can decide whether it should trust a
candidate certificate that it obtains from running the protocol given
The PKI Enterprises marketing team has decided to support a restricted
form of hierarchical names like what is found in the Internet.
Specifically, names that must be supported are
variable-length finite lists /N1/N2/.../Ni
(i) the length of the list is at most 5 and
(ii) elements used to build the list come from some set LocalNames.
The marketing team has further requested that no changes be made
to the client-side protocol you gave above for 1(a).
You may, however, choose names for the CA-servers,
the contents of set PrinsNames,
the contents of set AllNames
and graph DCAS.
(Hint: Don't feel restricted to using names like CredServ_i
(a) Give the set of names that PrinNames will include.
(b) Give any additional names that AllNames will include.
(c) Describe the structure of graph DCAS.
Explain the rule you used for having an edge from one
CA-server to another.
(d) What contents is required for the database stored by each CA-server.