A PGP Public Key Server

Marc Horowitz February 24, 1996

Abstract

Existing key servers for Pretty Good Privacy^{TM} (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.

Contents

1 Background 3 1.1 PGP and the web of trust . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Key servers today . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 A new key server 5

2.1 Functional specifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 Mail server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.3 HTTP server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.4 Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Database format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.3 Main server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Conclusions 13 3.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A Details of the database engine 16 B Sample query form HTML 19

Chapter 1

Background

1.1 PGP and the web of trust

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.

1.2 Key servers today

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

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:

Compatibility The server should behave like the existing servers from the user’s point of view. Especially, no functionality should be lost.

Administration Building and installing the server should be simple. Special privileges on the server should not be required for day-to-day maintenance.

Performance Queries of all sorts should take a reasonable amount of time to complete.

Access The server should be accessible via email and the World Wide Web. It should be able to create files for access by ftp.

2.1 Functional specifications

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.

2.1.1 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.^{1} 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.

2.1.2 Mail server

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.

ADD This command adds or updates keys in the key database. The body of the message should contain a keyring in ASCII-armor format to be merged into the database.

The next three commands search in the key database for userid as described in section 2.1.1 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 userid The response is equivalent to that outputted by pgp -kv on the matching keys.

VERBOSE INDEX userid The response is equivalent to that outputted by pgp -kvv on the matching keys.

GET userid The response is equivalent to that outputted by pgp -kxa on the matching keys.

LAST num This command is like GET, except that keys which have been added or changed in the last num days are returned.

The MGET command 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.

1A week’s worth of statistics taken in early October, 1995, from the mail and HTTP servers running on pgp.ai.mit.edu indicate that this change will only result in a difference in behavior for a very small number of requests (less than 1 in 1000).

2.1.3 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 should be 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, as described in section 2.1.1. 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 as described in section 2.1.1.

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.

For an example of an HTML page which includes forms for making the above queries, see Appendix B.

2.1.4 Replication

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.

INCREMENTAL This command is intended for inter-server communication. It functions identically to ADD, 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.

2.2 Architecture

2.2.1 Overview

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 unix^{TM} 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 eventdriven 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^{2}. 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.

2.2.2 Database format

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 as described in section 2.1.1. 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.

2This is not a problem now, since the servers are only receiving about 350 HTTP requests a day, but it is worth considering.

2.2.3 Main server

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.

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.

Database engine

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

• Add a key to the database.

• Extract an index based on a key ID or user ID. The format of the index will be the same as that generated by the PGP keyring view functions. The exact command equivalent will be determined by flags to the function:

verbose format? include fingerprint? PGP command equivalent

      no  no  pgp -kv
      yes  no  pgp -kvv
      no  yes  pgp -kvc
      yes  yes  pgp -kvcv

• Extract keys based on key ID or user ID.

• Extract keys added to the database since a given time.

• Delete keys based on key ID or user ID.

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 as described in section 2.1.1. 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.

HTTP server

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.

Unix domain socket server

In order to provide a mechanism for controlling the running server, the server listens for connections on a unix domain socket.^{3}

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.

3Unix domain sockets are a mechanism for stream-based IPC in unix.

Conclusions

3.1 Performance

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. Figure 3.1 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

add  get  index
average median average median average median
old server  169  183  38  15  53  29
new server  2.3  2  0.5  †  0.3  †

† The median of get and index requests against the new server was zero seconds, which is an artifact of the one second granularity of the timing samples. This indicates that most of the requests took less than one second to process.

Figure 3.1: Average and Median request times for the old and new PGP key servers, in seconds.

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.

3.2 Future Work

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, as shown in Appendix A. 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.

Appendix A

Details of the database engine

This appendix describes in pseudocode how the basic operations (add, get, index, delete, since) of the key server are implemented. The code itself is more complex, since it has to deal with error checking and the general overhead of C memory management.

add(keyring) ::=

for key in keyring dbkey = read-entry(key-db, keyid(key)) if found then (key, newkeys) = merge-keys(dbkey, key) write-entry(key-db, keyid(key), key) for word in userids(key)

keyid-list = read-entry(word-db, word) add-to-list(keyid-list, keyid(key)) write-entry(word-db, word, keyid-list)

end write-entry(time-db, now, keyid(key)) allnewkeys = allnewkeys + newkeys

end return(allnewkeys)

delete(keyid) ::= keyid-list = search(userid) for keyid in keyid-list

key = read-entry(key-db, keyid(key)) for word in userids(key)

keyid-list = read-entry(word-db, word) delete-from-list(keyid-list, keyid(key)) write-entry(word-db, word, keyid-list)

end delete-entry(key-db, keyid(key))

end

get(userid) ::= keyid-list = search(userid) for keyid in keyid-list

keyring = keyring + read-entry(key-db, keyid) end return(ascii-armor(keyring))

index(userid,verbose,fingerprint) ::= keyid-list = search(userid) for keyid in keyid-list

keyring = keyring + read-entry(key-db, keyid) end return(index(keyring,verbose,fingerprint))

since(time) ::= keyid-list = read-range(time-db, from time to end) for keyid in keyid-list

keyring = keyring + read-entry(key-db, keyid) end return(ascii-armor(keyring))

The above pseudocode uses a few functions whose implementation is not trivial. These are defined here.

merge-keys(key1, key2) ::= output-key.modulus = key2.modulus output-key.exponent = key2.exponent if key1.primary-userid.name eq key2.primary-userid.name then

output-key.primary-userid.name = key2.primary-userid.name output-key.primary-userid.sigs =

merge-sigs(key1.primary-userid.sigs

key2.primary-userid.sigs)

output-key.secondary-userid-list =

merge-userids(key1.secondary-userid-list,

key2.secondary-userid-list)

else

for userid in key1.secondary-userid-list

if userid.name eq key2.primary-userid.name then

temp-userid = userid fi

end

delete-from-list(key1.secondary-userid-list, temp-userid) output-key.primary-userid.name = key2.primary-userid.name output-key.primary-userid.sigs =

merge-sigs(temp-userid.sigs

key2.primary-userid.sigs)

output-key.secondary-userid-list =

merge-userids(key1.primary-userid, key1.secondary-userid-list, key2.secondary-userid-list)

fi return(output-key)

merge-userids(userid-list-1, userid-list-2) ::=

for (userid-1, userid2) in (userid-list-1, userid-list-2)

such that userid-1.name eq userid-2.name

output-userid.name = userid-2.name

output-userid.sigs = merge-sigs(userid-1.sigs, userid-2.sigs) add-to-list(output-list, output-userid)

end for userid-1 in userid-list-1

such that userid-1.name not in userid-list-2 add-to-list(output-list, userid-1)

end for userid-2 in userid-list-2

such that userid-2.name not in userid-list-1 add-to-list(output-list, userid-2)

end return(output-list)

merge-sigs(sigs-list-1, sigs-list-2) ::= return(add-to-list(sigs-list-1, sigs-list-2))

search(userid) ::= if (is-keyid-format(userid)) return(userid) for word in userid

keyid-list = read-entry(word-db, word)

if (output-list is empty)

output-list = keyid-list else

output-list = intersect(keyid-list, output-list) fi

end return(output-list)

Appendix B

Sample query form HTML

<!-- $Id: pks-commands.html,v 1.2 1996/01/30 02:04:02 marc Exp $ -->
<title>Public Key Server Commands</title>
<h1>Public Key Server Commands</h1>
<b>HTML Forms support required!</b><p>
<h2><a href="#extract">Extract a key from the server</a></h2>
<h2><a href="#submit">Submit a key to the server</a></h2>
<hr>
<h2><a name="extract">Extracting a key</a></h2>
Here's how to extract a key:
<ol>
 <li> Select either the ``Index'' or ``Verbose Index'' check box.  The
``Verbose'' option also displays all signatures on displayed keys.
 <li> Type ID you want to search for in the ``Search String'' box.
 <li> Press the ``Do the search!'' key.
 <li> The server will return a (verbose) list of keys on the server
matching the given ID.  (The ID can be any valid argument to a pgp
-kv(v) command. If you want to look up a key by its hexadecimal KeyID,
remember to prefix the ID with <tt>0x</tt>.)
 <li> The returned index will have hypertext links for every KeyID,
and every bracket-delimited identifier (i.e. &lt;<a
href="http://blaster.mit.edu:11371/pks/lookup?op=get&exact=on&search=marc@mit.edu">
<i>marc@mit.edu</i></a>&gt;).  Clicking on the hypertext link will
display an ASCII-armored version of the listed public key.
 </ol>
<hr>

<form action="http://blaster.mit.edu:11371/pks/lookup" method="GET">
Index: <input type="radio" name="op" value="index" checked>
Verbose Index: <input type="radio" name="op" value="vindex">
<p>
Search String: <input name="search" size=40><p>
<input type="checkbox" name="fingerprint"> Show PGP "fingerprints"
for keys <p>
<input type="checkbox" name="exact"> Only return exact matches <p>
<input type="reset" value="Reset">
<input type="submit" value="Do the search!">
</form>
<hr>
<b>Extract caveats:</b>
<ul>
 <li>Currently, hypertext links are only generated for the KeyID and
for text found between matching brackets.  (It's a common convention
to put your e-mail address inside brackets somewhere in the key ID
string.)
 <li>The search engine is not the same as that used by the pgp
program.  It will return information for all keys which contain all
the words in the search string.  A ``word'' in this context is a
string of consecutive alphabetic characters.  For example, in the
string <tt>marc@mit.edu</tt>, the words are <tt>marc</tt>,
<tt>mit</tt>, and <tt>edu</tt>. <p>
 This means that some keys you might not expect will be returned.  If
there was a key in the database for <tt>Marc Edu
&lt;mit.foo.com&gt;</tt>, this would be returned for by the above
query.  If you don't want to see all these extra matches, you can
select ``Only return exact matches'', and only keys containing the
specified search string will be returned.<p>
 This algorithm does <i>not</i> match partial words in any case.  So,
if you are used to specifying only part of a long name, this will no
longer work. <p>
 </ul>
<hr>
<h2><a name="submit">Submitting a new key to the server</a></h2>
Here's how to add a key to the server's keyring:
<ol>
<li> Cut-and-paste an ASCII-armored version of your public key into
the text box.
<li> Press "Submit".
</ol>
That's it!  The keyserver will process your request immediately.  If
you like, you can check that your key exists using the <a

href="#extract">extract</a> procedure above.
<hr>
<form action="http://blaster.mit.edu:11371/pks/add" method="POST">
Enter ASCII-armored PGP key here: <p>
<textarea name="keytext" rows=20 cols=66></textarea><p>
<input type="reset" value="Reset">
<input type="submit" value="Submit this key to the keyserver!"><p>
</form>
<hr>
<address>
(Thanks to <a href="http://www-swiss.ai.mit.edu/~bal">Brian LaMacchia</a>,
from whom much of this page is cribbed)<p>
Marc Horowitz <a href="mailto:marc@mit.edu">&lt;marc@mit.edu&gt;</a> <br>
<a href="http://www.mit.edu:8001/sipb/sipb.html>
Student Information Processing Board</a> <br>
w20-557 <br>
84 Massachusetts Avenue <br>
Cambridge, MA 02139 <br>
+1 617 253 7788
</address>

Acknowledgements

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.

References

Aktins, Derek, et al. PGP Message Exchange Formats. IETF Internet Draft, 1995. Graff, Michael. PGP Keyserver Software, version 2.5. Computer software, 1995. LaMacchia, Brian A. Public Key Server Commands. World Wide Web document, 1995.