Existing key servers for Pretty Good PrivacyTM (PGP) use the PGP program for key management. PGP was not designed to handle large keyrings, and as a result, performance of the existing key server suffers badly. In this paper, I describe the specification and design of a new key server which does not depend on PGP for any of its functions. This new key server is a ``drop-in'' replacement for the old key server, providing almost all of the same functionality via both the e-mail and HTTP interfaces, with much improved performance. Early testing of this server under simulated production conditions demonstrates a performance increase of about two orders of magnitude compared to the old server. This increase is directly attributable to storing the key database in hash tables and balanced trees instead of a PGP format keyring.
PGP, short for Pretty Good Privacy, is a widely used program for performing public key authentication and encryption functions. Unlike most similar systems, which establish trust in terms of strict certification hierarchies, PGP uses a concept known as a ``web of trust'', in which any party can certify the identity of any other party (in PGP parlance, ``sign their key''). A signature on a key or document can be trusted if, and only if, there is a path of signatures between the verifier's key and the key used to make the signature in question. The number, shortness, and quality of such paths determine how well the key, and therefore the signature, can be trusted.
While most public key heirarchies are based on formal, sometimes legally binding notions of identity, the web of trust has no such restrictions. This generality is part of what makes PGP popular. PGP keys exist for individuals, groups, organizations, network services, and even pseudonyms and anonymous addresses. Unfortunately, this generality has its cost. It is not always possible to verify a signature made by an arbitrary key, or even to find the key. Although it is possible to advertise a key via traditional Internet mechanisms such as .plan files and World Wide Web home pages, this is not always practical, since the key space does not map cleanly onto traditional Internet naming. There is no appropriate place for a pseudonym operated through an anonymous remailer, for example.
To solve this problem, repositories of PGP public keys have been established. These PGP public key servers allow anyone to submit any public keys and signatures, and to query this database. The first public key server was a simple email server which used the PGP program to provide basic PGP functionality on a centrally stored keyring. This server evolved and added features, including more advanced searching and incremental updates between servers. Interactive World Wide Web interfaces followed.
However, all these systems have a substantial problem. Today's key servers manage over twenty thousand public keys, including over 28,000 associated signatures. The PGP implementation was not designed to manage extremely large databases of keys such as this. As a result, key server performance suffers badly. Merging a large keyring into a public key server database takes hours or even days. The most common operations takes between thirty and sixty seconds using the old PGP-based key server.
A new key server would solve many of the problems of the first-generation key server. Any new design should strive to meet the following general requirements:
Since the old server uses the PGP program for keyring maintenance,
the old server's commands can be described in terms of the PGP
commands which are used to implement them. This generates familiar
output, which is useful, but the keyring search and modify algorithms
are quite inefficient. The functional specifications are intended to
describe a system with behavior similar to that of the old system,
with a few restrictions which allow for a more efficient
implementation.
Searching
The most user-visible change is that searches are no longer simple string or regular expression matches against the user ID, because this makes it impossible to search efficiently. Instead, each user ID and each search is divided up into ``words'', where a ``word'' is defined as a run of consecutive alphanumeric characters of length greater than one. For a given search, all keys with a user ID which contains all the words in the search are returned. This means that searches for part of a word, which would have succeeded before, will fail now, but these kind of searches are very rare. Optionally, the list of user ID's returned can be limited to those which contain the search string exactly, not just the words which make up the search string. All searches are case-insensitive. Searches by key ID will remain unchanged.
The mail server accepts requests submitted via email, and delivers replies to the originator of the message. The subject header of the message contains a command, and the body of the message contains data if the command requires it.
ADDThe next three commands search in the
key database for userid as described in section and email
a response back to the user based on the keys which match. The option
for exact matching is used so that the new server behaves more like
the old server.
INDEX useridpgp -kv on the matching keys.
VERBOSE INDEX useridpgp -kvv on the matching keys.
GET useridpgp -kxa on the matching keys.
LAST numGET, except
that keys which have been added or changed in the last
num days are returned.
The MGET command (of the old server) is no longer
supported. In a week's worth of mail server logs, this command was
only used 28 times, and all but four of these were constant strings,
which means that MGET had no special effect. Those which were not
constant strings only used the alternation (``|'')
regular expression operator. In other words, all of these queries
could have been made with a few separate GET requests.
HTTP server
The new HTTP server accepts the same query parameters as the old HTTP server; however, the semantics are slightly different, as described here. Two URI's are implemented.
The first URI, /pks/lookup, is for performing
searches. It understands four different properties in its property
list. The op property can have three values. If this
value is index or vindex, then the returned
page is equivalent to that outputted by pgp -kv or
pgp -kvv, respectively, on the keys matched by the
value of the search
property. In addition, if the fingerprint property
has the value on, then output is equivalent to that
outputted by pgp -kvc or
pgp -kvcv, respectively. If the op
property has the value get, then the returned page is
equivalent to that outputted by pgp -kxa on the keys
matched by the value of the search property. If the
exact property has the value on, then the
search is restricted to exact matches.
The second URI, /pks/add, is for adding or changing
keys in the database. It understands one property. The
keytext property contains the ASCII-armored PGP keyring
to be merged into the database.
See the key server page for an example of an HTML page which includes forms for making the above queries.
It is desirable to have multiple key servers for performance and reliability. In order to avoid the latency associated with the slower lines between countries and continents, key servers have been established all over the world. Some organizations separated from the Internet by a firewall or a slow connection run their own key servers. If the nearest server to a user becomes temporarily unavailable, the user can use another key server to look up keys.
In order to have multiple key servers provide access to the same keys, either users must send updates to all key servers, or the key servers must share updates among themselves. Since it is not reasonable to expect users to know all the key servers which exist and are operational, an incremental mechanism is available to propagate updates between servers. A user needs to send updates to just one server, and the update will be spread to all the other key servers.
Each key server keeps a list of other key servers with which it shares updates. Whenever a key is added or changed by a user or by an incremental from another key server, this change is propagated to all the key servers in this list. To keep the message from propagating forever, each key server adds a header to the message to indicate that it has seen the update, and should not be sent it again. Incrementals are implemented using one additional command in the mail server. Users should never need to use this command.
INCREMENTALADD, except that the mail headers will be parsed for
headers of the form X-Keyserver-Sent: email-address.
The servers whose email addresses are listed will be assumed to have
seen the record already, and will not be sent additional copies. When
a server sends an INCREMENTAL to another server, it
should list all the servers which were named when it received the
message, and add itself.
The design of the several programs which make up the new key server is complicated by the very different access methods of email and HTTP. Mail is by nature batched and non-interactive. A mail request should be relatively immune to system failures, network failures, etc. HTTP requests are by nature interactive. If the host or network goes down, it is acceptable to terminate the transaction in progress.
Unfortunately, the traditional means of handling batch and interactive requests in a unixTM environment are very different. Batch requests are usually accumulated in a queue, and the queue is run periodically. Interactive requests usually result in a new process which handles the request, then exits. Multithreaded servers exist which use one thread per interactive request instead of one process, but the principle is the same.
The server must also deal with shared (read) and exclusive (write) locks on the database. Since none of the freely available database libraries provide record locking facilities, the system must insure that while the database is being updated, no other accesses are made to the database, or corruption may occur.
Two solutions seem possible. The first, more traditional system would use several different programs to handle different kinds of access. Whenever mail is received for the mail server, a short program would insert the request in a queue. Periodically, a program would run to handle all the jobs in the queue. A second program would run out of inetd or as a CGI script run by a HTTP server to process HTTP requests. These latter two programs would both access the database files directly to perform queries and updates, and perform locking between them. This is the approach which is used by existing key servers.
The second, more sophisticated solution involves a more complex server which is persistent and handles multiple mail and HTTP requests at the same time, via a threaded or event-driven architecture.
My experience with network servers has shown that the first solution is simpler and easier to implement, but suffers from reduced performance. Mail server users are at a disadvantage, since their requests are not processed immediately upon receipt. The potential exists for many processes to be running at the same time, since there would be one process for each concurrent HTTP request. (This is not a problem now, since the servers are only receiving about 350 HTTP requests a day, but it is worth considering.) Since each request starts a new process, caching information to make future queries faster is difficult.
The second solution is harder to implement correctly, but is more scalable. Because resource consumption does not increase linearly with the number of requests, many more requests can be handled. No interprocess locking is needed, because only one process will ever be manipulating the database. Also, the server can cache frequently-used information to increase performance. Since this solution has more advantages (and is more interesting), I have used this approach.
The Berkeley db database library is used for all the databases. This library is freely available and portable, and is more versatile than the dbm libraries which most vendors ship with their operating systems. In particular, it allows arbitrary sized keys and data, and supports balanced trees in addition to hash tables.
The primary database is a hash table which indexes PGP key IDs into PGP keys. The key is a 32-bit integer corresponding to the key ID. As used here, the key ID is the 32-bit ID which is used by the PGP user interface, not the 64-bit ID which is used by the internal structures. The data is in the same format as a PGP keyring, containing the public key for all keys with that key ID, and all associated user ID's, signatures, and revocations.
Two secondary indexes into the primary database are kept. The first index is a hash table containing words as keys and a list of PGP key IDs and key creation times as values. The creation time is used to disambiguate different keys with the same key ID. This index is used to to implement searches over the database. The list in the data of each entry in this database is sorted by key creation time, with the most recent time first.
The second index is a balanced tree containing times as keys and PGP key IDs and creation times as values. The value of each entry in the database describes all the keys which were added or changed at the time represented by the key. This index is used to generate lists of keys based on recency, such as a keyring consisting of all keys changed in the last day.
Since all the information in the secondary indices is derived from information in the primary database, if the secondary databases are damaged or somehow become out of sync, they can be destroyed and recreated.
The main server consists of four major parts. The first part is the multiplexor, which handles most of the input and output for the server. It deals with the multiple input and output streams of the server, and ensures that no I/O request ever blocks.
The second part of the server is the database engine. It manages the underlying database which stores all the PGP keys, and the various indexes which enable efficient searching.
The third part is the HTTP server. This part receives HTTP requests read from the client by the multiplexor, and converts them into calls to the database engine. The database engine's response is converted into a HTTP reply, which is delivered to the client by the multiplexor.
The last part is the unix domain socket server. This is a more controlled mechanism than HTTP for submitting commands to the key server. The most important task of this part is to handle email messages. Mail requests are parsed and converted into calls to the database engine. The database engine's response is converted into a mail reply, which is delivered to a mail delivery agent by the multiplexor.
To support multiple input sources and output sinks, some sort of multiplexing is necessary. The server implements multiplexing with a queue of inputs (file descriptors opened for reading) and a queue of outputs (file descriptors opened for writing). Using the select() system call, the server can determine which members of the input queue can be read without blocking, and which members of the output queue can be written without blocking.
When new data is available for any of the input file descriptors, it is passed to a function which processes the data. When a full request has been read, this function handles the request, creates a reply, and queues it for output. When any of the output file descriptors becomes writeable, as much data as possible is written to it. When all the data which has been queued is written, a function is called to clean up from the request, freeing memory or other resources. The multiplexor also handles errors, timeouts, and other exception conditions.
The architecture of the server would be much simpler (this component would be basically unnecessary) if multiple threads of execution were used, but since threads are not widely available, using them is not a good idea at this time. The implementation uses abstractions which should permit the event-driven architecture to be replaced with a threaded architecture when a robust thread implementation is available. The logic of the server would still be event-based, but it would then be possible to perform multiple computational tasks, such as database searches, at the same time.
The database engine manages all of the data in the PGP key server. It implements a small number of high-level operations on the database. Functions implementing these operations are called by the mail and HTTP servers.
Functions are provided to
| verbose format? | include fingerprint? | PGP command equivalent | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
Functions are also provided to create an empty database, open and close the database, and write cached elements of the database to disk.
The functions which operate on a key ID or user ID accept a search
string. If the string begins with 0x, then the string
will be interpreted as a hexadecimal key ID. Otherwise, the string
will be interpreted as a user ID search
string. The functions which accept keys can be passed a binary
file, in the format PGP uses for keyring files, or an ASCII-armored
PGP key block, as produced by pgp -kxa. Functions
which return keys return an ASCII-armored PGP key block. When more
than one key or index entry is returned, the keys referred to are
sorted by time, with the most recently created keys first. This
behavior differs from PGP, which lists the keys most recently added to
a keyring first.
The HTTP server listens for connections on a TCP port. As connections are accepted and data is passed in from the multiplexor, the server interprets the data as HTTP requests. The URI, query string, and body from each request are parsed and converted to arguments for the database engine. The database engine performs the actual query, and returns a textual reply. This reply is marked up with HTML, and HTTP headers are added. The result is passed to the multiplexing code for transmission back to the client.
In order to provide a mechanism for controlling the running server, the server listens for connections on a unix domain socket.
When a connection is received on the socket, lines containing
commands for the key server are read and parsed. The first word of
the line describes the type of request. The most frequently used type
of request is a mail request, indicated by the word mail.
The rest of the line gives a filename which contains a mail message
for the PGP mail server. This file is opened and the headers are
parsed to construct a query for the database engine, and reply
information for the mail reply. The database engine performs the
actual query, and returns a textual reply. A short descriptive
message is prepended to the reply, and MIME headers are added for
structure. Finally, a mail transfer agent (usually sendmail) is
executed as a child process, and the reply mail message is passed to
the multiplexing code for output to the mailer. Once the output is
complete, the input mail request file is deleted. If there is any
error, the file is left in place so an administrator can examine it.
The only other type of request is indicated by the word
backup. This request causes the server to write any
cached information to disk, and make a copy of the database files.
This can be run periodically to protect against catastrophic failures.
The new server was tested in a beta production environment for about one week. During this time, it has received about 32 mail requests per day and 220 web requests per day on average. Almost all of the mail requests were add or incremental requests. Of the HTTP requests, 6% were add requests, 33% were get requests, and 61% were index or vindex requests. The requests to this server came from volunteers who heard about the test server from announcements to mailing lists or word-of-mouth.
During a one week sample period, the old server received about 97 mail requests a day and 358 HTTP requests per day on average. Of the mail requests, 83% were add or incremental requests, 14% were get requests, and the remaining 3% were index or last requests. Of the HTTP requests, 8% were add requests, 35% were get requests, and 57% were index or vindex requests.
The new server's load in testing was almost half the old server's load in production, with ratios of add requests, get requests, and index requests about the same. This makes the new server's statistics a good basis for comparison to the old server's statistics. The most interesting basis for comparison of the two servers is performance. Although there is no timing information available for the old HTTP server, there is timing information available for the old mail server, and since the database operations were performed by the same PGP program, it is reasonable to assume that similar HTTP and mail queries take about the same amount of time. This table shows average and median times for the old and new servers for different kinds of requests. For all kinds of requests, the new server is about two orders of magnitude faster than the old server.
As the key database grows, this performance difference can be expected to increase. The PGP keyring format and search algorithms require that all operations scan the database linearly until matches are found, resulting in operations which are O(number of keys). The new key server database format allows all operations to be more efficient. Operations by key ID require only a single hash table lookup, which is O(1) in the number of keys in the database. Operations by user ID, which include add and delete, are currently O(number of keys containing the words in the user ID). This can be extremely small if searches are chosen carefully. Even if inefficient searches are used, both the order of the operation and the associated constant factor are smaller in the new key server than the old server.
The most common words appear in user ID's of about one third of all the keys. For each key with a user ID containinf a word, the new server must read and process about 12 bytes, compared to the old server, which must read and process about 400 bytes. Multiplying these two numbers together gives a constant factor for the new server which is about 0.01 the constant factor of the old server. This factor corresponds to the two orders of magnitude observed performance difference between the two servers.
It is reasonable to expect the viable lifetime of the new server to continue until the performance drops to the performance levels of the old server today. Based on the observations above, I would expect the old key server's performance at twenty thousand keys to equal the new key server's performance at about two million keys. This is a conservative estimate not accounting for other increases in performance, due to faster hardware or other changes. Due to the extra overhead of the database formats and the extra indices, the new key server does use about twice as much disk space as the old server. This proportion should remain constant.
The increases in performance are a direct result of structuring the database for efficient access to the common operations, rather than simplicity of management as with the PGP implementation. Of all the aspects of the design, this is the single most important. As long as the PGP keyring format remains the same, efficient operation on large keyrings will be impossible.
The next level of performance increases can easily be obtained by moving to a relational database model. Well-designed relational databases can perform the operations which are currently O(n) in O(log n) or O(1) time. With a database engine based on a good relational database, the key server could be viable for any conceivable number of keys. With a relational database, it might also become reasonable to store an index of word fragments to allow efficient searches by parts of words.
As more people use PGP, the key servers will receive more requests, and these requests will return more data. The current key server design multiplexes I/O with select(), but handles database requests serially. A single long request will cause all other requests to block until the long request completes. Replacing the event-driven model with a threaded execution model will allow multiple database requests to proceed in parallel, reducing the apparent latency when the server load increases. This change will require locking inside the server in the form of mutexes, since the underlying database is neither thread-safe nor does it support transactions.
Another useful change will come in the next version of the berkeley db library, when transactions are supported. Transaction support will enable the server to recover from system crashes and other failures which require a recovery from backup in the current design. Using transactions for operations requiring multiple database accesses will prevent the secondary indexes from becoming inaccurate with respect to the primary key database.
Finally, there are a number of issues in the key server which are related to PGP itself. PGP allows a key to have multiple user ID's associated with it. One of these keys is the primary user ID, which is treated as a special case by PGP. This special case adds substantial complexity to the key server merge functions. If PGP did not make this user ID special, the server could be substantially simplified. The other problem with PGP which the key server implementation must address is the non-uniqueness of key ID's. PGP uses the least significant 64 bits of the modulus as the key ID of a public key. When a key is referred to, such as in a signature, this key ID is what is stored. There is enough uniqueness in 63 bits (the least bit is always one) to have a reasonable expectation that there will never be collisions. However, the user interface of PGP only exposes the least significant 32 bits of the key ID. The expectation of collisions is high enough at the end of the expected life of the key server that it is prudent to have code which can handle potential collisions. There seems to be little reason for PGP to make less than the entire key ID visible to the user, since the potential collision problems seem to outweigh the small inconvenience of larger key ID's.
I would like to thank Brian LaMacchia for his help at the beginning
of my project, when he provided me with logs from
pgp.ai.mit.edu, and at the end, when he installed my
server for testing. His feedback on the software and on the paper was
invaluable. I would like to thank Phil Zimmerman for making privacy
available to the masses and creating the need for a public key server.
Aktins, Derek, et al. PGP Message Exchange Formats. IETF Internet Draft (expired), 1995.
Graff, Michael. PGP Keyserver Software, version 2.5. Computer software, 1995.
LaMacchia, Brian A. Public Key Server Commands. World Wide Web document, 1995.