When a public key is needed for use, it must be made available to PGP. The program itself looks for it on a special file called pubring.pgp in a standard place. This keyring is a simple collection of public keys. If the required key cannot be found, the user is asked for the name of an alternative keyring file. If the user does not possess the required key at all they must either acquire a copy or accept that they cannot process the information in question, whether that is encrypting for privacy or checking a signature to test for integrity and authenticity.
At the moment, there are a number of ad hoc means of acquiring someone's public key, and a couple of semi-automated methods. The former include asking the person concerned for a copy by email; on a diskette sent by conventional post; by using the finger utility (a number of PGP users make their keys available by this means), looking in a web page and so on. The key is then added, by an interactive run of PGP or by a front-end program, to the personal public keyring.
The semi-automated methods use the first-generation key server network. A number of machines around the world each maintain a large pubring.pgp containing over twenty-five thousand public keys (as of May 1996). The servers communicate with each other by mail or ftp in an attempt to ensure that all machines hold the same keys. It must be acknowledged that the attempts are not completely successful and different servers hold slightly different sets of keys. These servers are also available to PGP users. By sending appropriate electronic mail, or by accessing a Web page, the servers will respond with email (or whatever) containing the required key or keys. A few utilities, especially the Emacs RMAIL add-on mentioned earlier, are capable of interrogating the servers for required keys and adding the reply to the user's keyring. Most MUAs are not so obliging. Keys may be added, of course, by submitting them to a keyserver by email; similarly help (in any of several European languages) and an index may be obtained
The first-generation keyservers have a number of flaws, some of which are visible to the end-user. For instance, it is not possible at present to remove signatures and complete keys from the database. There are also problems with the size of the monolithic ring, which is almost beyond PGP version 2. x's capabilities. The more important one is that they use PGP itself to maintain the keyrings, and PGP was not designed to handle large keyrings. This problem is not directly visible to the clients, but rather it is the consequences that they notice. Responses to queries can take hours or days, though ten to fifteen minutes is more typical. The email servers generally queue requests as they arrive and run a batch job to clear the queue every fifteen minutes or so. The Web servers are better in this respect, giving almost instant responses, but some contain read-only copies of the email servers' keyrings and arrange that updates are sent to a suitable read-write server. Although next-day delivery may be acceptable to people wishing to send important information securely but not necessarily instantly, it does not permit MUAs to acquire needed keys invisibly between the user clicking the Send button and dispatch of the mail. If PGP is to become truly easy to use by non-specialists, rapid key provision will be essential. Rapid means a few seconds delay at most.
The present keyserver network is in serious trouble. There are over 25,000 keys on the keyrings, and PGP takes several minutes to add a new key to the ring when running on a mid-range workstation. When PGP was designed, expectations were that a user would have a dozen or two keys on their keyring. Adding a key, and checking its signatures, is done with an inefficient algorithm which takes time proportional to the square of the number of keys on the ring multiplied by the number of signatures on the key. The rate of growth in the key servers' keyrings is such that the present mechanism will be unusable within a year, even on fast machines.
There are two possible ways out of this situation. It has been stated that the next version of PGP to be released will have a vastly improved keyring maintenance mechanism. It should be able to handle rings with many thousands of keys in seconds, rather than minutes, and it should exhibit a much slower rate of increase in processing time as the rings become larger. It is not yet clear whether PGP version 3.0 will become available within the next few months. The other solution is a second generation key server, which distributes the data in a manner similar to the DNS, and which does not use PGP to manipulate the keys.
As PGP becomes more popular it will become ever more inappropriate for the servers to attempt to maintain copies of the global keyring. It will be essential that a distributed database be set up and managed. Compare the situation with internet name resolution: a single file, /etc/hosts, is adequate for a network of a few dozen machines, unwieldy for a few hundred and totally unusable when there are a million. The Domain Name Service was invented to solve this problem. The design of the analogue to the DNS for PGP keys is presently underway. The DNS as it currently exists cannot be used for a number of reasons, one of which is that keyIDs do not heirarchically parallel the key management structure. A group (of which both authors are members) is investigating these matters and, at the time of writing, believes that most of the problems in producing a service capable of handling keys by the million have been identified. We hope that the first implementations will become available towards the end of 1996.