Subject: PGP Keyserver Synchronization Protocol (corrected)

From: "William H. Geiger III" <[email-masked]>
Date: Fri, 18 Jun 1999 10:05:43 -0500

Sorry, I didn't run the spell checker over the previous post.

pgpk-sync-00.txt
PGP Keyserver Synchronization Protocol -- Initial Proposal
William H. Geiger III
Geiger Consulting
[email-masked]
http://www.openpgp.net
01 June 1999

	This protocol is designed to allow the synchronization of 2 PGP Keyserver
Databases with the minimal of overhead and network traffic. It will allow
2 servers to detect exactly which keys in their databases are different or
missing and only exchange those keys. This protocol can also be used by
PGP clients to communicate with the servers to compare keys in their local
keyring with those on the server and receive updates to their keys.

Overview:

	The synchronization process involves several steps:

	Generation of Hash Tables
	Exchange of Hash Tables
	Comparison of Hash Tables
	Exchange of Keys

In this process one database is initiating the synchronization (client)
while the other is the receiver of a synchronization request (server). To
start the process the client will create a hash table of his database then
he will request a hash table from the server. When the client receives the
server's hash table he will compare it with his own and generate 3 lists:

	#1 All Keys that are on the server but not on the client
	#2 All Keys that are on the client but not the server
	#3 All Keys that are on both client & server but have different hashes

The client will then request from the server all the keys in list #1 & #2
and add those keys to it's database. Once this is done the client will
generate a new hash table for his database and compare it to the hash
table he has from the server. He should now only have 2 lists:

	#1 All Keys on the client but not on the server
	#2 All Keys on the client & server but have different hashes

The client should then send the server all keys that are in the 2 lists.

Now both servers should be synchronized.

Exclusion lists:

	It is common practice among some PGP Keyserver operators to exclude some
keys from their databases (a practice I do not agree with). When doing the
key exchange one may want to take into account the exclusion lists of the
server and not send keys that the client has that matches this list.

FTP of Hash Tables:

	A server may wish to periodically create a hash table (once a day) and
store it on his FTP server. This way a client can download the hash table
and do his synchronization without any action on the part of the server. A
more practical approach may be for the servers to maintain a hash table in
"real time" updating it every time keys are added or updated in the
database.

	Another approach would be for the servers to create a hash table once a
week and then create daily hash tables that only contain the keys that
have been added/updated for that day.

	I am rather flexible on this area and some testing in the field should
provide the best mechanism for when the hash tables should be generate.

Hash Table:

	A hash table is a sorted index by keyID of all the keys contained in a
PGP Database. The index contains only 2 fields; the 64bit keyID & 128bit
MD5 hash of the key:

        	0000000000000000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
		0000000000000001 ABABABABABABABABABABABABABABABAB
		0000000000000002 CDCDCDCFCDCDCFCDCDCDCDCFCDCDCFCD
		0000000000000003 EDEDEDEDEDEDFEDEEDEDEDEDEDEDFEDE

Calculating Hashes:

	It is important that when calculating the hash of a key that it be done
in a specific order as to guarantee that the identical key in two
different databases has the same hash. The following order of operation
for calculating the hash is:

	Primary Key
	SubKeys Sorted by KeyID
	Signatures Sorted by Signing KeyID
	UserID's Sorted Alphabetically

PhotoID's & X509 signatures are 2 issues that need to be looked into.
Unfortunately the specs for neither of these packets have been released by
NAI. For right now I recommend that any proprietary packets *not* be used
in the key hash calculations.

-- 
---------------------------------------------------------------
William H. Geiger III  http://www.openpgp.net
Geiger Consulting    Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 5.0 at: http://www.openpgp.net/pgp.html
Talk About PGP on IRC EFNet Channel: #pgp Nick: whgiii

Hi Jeff!! :)
---------------------------------------------------------------