Subject: Multicast Keyserver Synchronization

From: Marcel Waldvogel <[email-masked]>
Date: Thu, 24 Jun 1999 18:11:32 +0200

Last summer, Michael Baumer has been working out and implementing a
protocol for efficient key server synchronization (with input from
Nathalie Weiler, Patrick Feisthammel, and myself). The semester thesis
report can be found at
http://www.tik.ee.ethz.ch/tik/education/sadas/SASS1998-33/thesis.ps.gz
Unfortunately, lack of time have prevented us from developing this
further than a prototype implementation based on pks-0.9.3.

In the following, I'll present the main goals.

1. Reduce the load for basic keyserver synchronization
2. Insure synchronization with very little network traffic
3. Allow the operation of cache/partial keyservers

Status:

Currently, each keyserver has a list of neighbors (syncsites), which
it sends new keys and signatures ("incrementals") to by mail. This
results in flooding each message along the keyserver network. Each of
the hosts receives the message potentionally from each of its
syncsites. To achieve high reliability, the degree of the syncsite
graph has to be relatively high, resulting in many redundant mails for
a single incremental.

The flooding approach is not well-suited for the mail system, which
results in regular overloads at sites (too many processes), and lost
incrementals. Although, if a destination is down for some time, the
mail queue at its syncsites quickly grows without bound, requiring
manual intervention.

Solution:

Instead of using the "push" semantics using mail, our proposal is to
use a combined "push-pull" semantics using IP multicast (and
designated unicast tunnels for sites not connected to the MBone).
Whenever a keyserver learns of a new packet to any key from an
"old-style" source, the following steps are performed:

* Sender:
- it tags that packet with a world-wide unique sequence number,
  consisting of its host ID to make everything unique, and the
  next number of its private sequence number space
- it multicasts the tuple (host ID, sequence number, OpenPGP packet)
  to the multicast group (together with an identification of the
  enclosing UID and public key packet.

* Receivers:
- add the packet together with its sequence number to their database
- make sure that the sequence number from this host is exactly one
  higher than the previous number. If not, they ask for retransmission
  of missing packets

On a regular basis, keyservers heartbeat the list of their known (host
ID, highest sequence number) pairs, to tell the others what their
belief of maximum sequence number is. This packet's size is
proportional to the number of sequence-number creating keyservers, and
not influenced by the number of "listening" keyservers or the number
of keys in the database. When any host thus learns of a higher
sequence number, it starts requesting the missing packets from either
a closeby host or the originator.

In our experiments, the network traffic generated was much less than
it is with the current e-mail-based synchronization. Also, the load
was lower. To insure against malicious sending of packets, it is
possible to get (possibly signed) *incremental* digests from the
originator. We also believe, that this is better than sending out
hashes of all keys.

-Marcel

---

From: Albert Levi <[email-masked]>
Date: Fri, 25 Jun 1999 16:51:55 +0300

> originator. We also believe, that this is better than sending out

where does a server get its worldwide unique sequence number? don't we
need a central authority here? If so, I believe that this is incongruous
to the soul of PGP.

Albert

---

From: Nathalie Weiler <[email-masked]>
Date: Fri, 25 Jun 1999 16:40:23 +0200 (MET DST)

-----BEGIN PGP SIGNED MESSAGE-----

>need a central authority here? If so, I believe that this is incongruous

No, we do not need a central authority, since we can pretty well
coordinate this "getting" of this unique sequence number by a distributed
approach.

Nathalie 
- ---
PGP-KeyID: 52D1CAB1 <[email-masked]>
PGP encrypted mail welcome

---

From: Paul Koning <[email-masked]>
Date: Fri, 25 Jun 1999 10:42:21 -0400

>>>>> "Albert" == Albert Levi <[email-masked]> writes:

 Albert> Marcel Waldvogel wrote:

 >> Instead of using the "push" semantics using mail, our proposal is
 >> to use a combined "push-pull" semantics using IP multicast (and

Hm, this sounds like IS-IS or OSPF or similar routing update
distribution protocols.  Given that this is a long-studied area in
layer 3, it's probably a good idea to examine that literature.  There
are plenty of pitfalls to be avoided, and at this point it is known
how to do so.

 >> * Sender: - it tags that packet with a world-wide unique sequence
 >> number, consisting of its host ID to make everything unique, and
 >> the next number of its private sequence number space - it
 >> multicasts the tuple (host ID, sequence number, OpenPGP packet) to
 >> the multicast group (together with an identification of the

For example, sequence numbers raise the issue of how you deal with the 
bounded number of bits.  There's an obvious way to do this which is
wrong (see paper by Eric Rosen et al. from around 1980) and a right
way which is now used in routing protocols.

 Albert> where does a server get its worldwide unique sequence number?
 Albert> don't we need a central authority here?

No...  Marcel said "consisting of its host ID... and the next number
of its private sequence number space".  That's a standard solution: to 
get globally unique IDs (often known as UUIDs, you'll find them in
Microsoft stuff but the originated in OSF RPC if not earlier) you use
a MAC address or similar number for spatial uniqueness, and a (locally 
managed) time stamp for local temporal uniqueness, plus a sequence
number if needed to cope with low resolution clocks.  These field
taken together give you what's needed.  (By the way, a timestamp may
be better than a sequence number.)

	paul

---

From: Marcel Waldvogel <[email-masked]>
Date: Fri, 25 Jun 1999 16:50:35 +0200

> are plenty of pitfalls to be avoided, and at this point it is known

Paul,

would you happen to have pointers to good literature around?

> (By the way, a timestamp may be better than a sequence number.)

I don't see the advantages of a timestamp.
The advantage of a sequence number is that you immediately know about
holes, updates which you have missed. As long as entries are superseding
each other, a timestamp is just fine, but if it is only additive (as with
PGP), I feel that seqnos are more appropriate.

-Marcel

---

From: Paul Koning <[email-masked]>
Date: Fri, 25 Jun 1999 11:06:18 -0400

>>>>> "Marcel" == Marcel Waldvogel <[email-masked]> writes:

 Marcel> On Fri, Jun 25, 1999 at 10:42:21AM -0400, Paul Koning
 Marcel> <[email-masked]> wrote:
 >> layer 3, it's probably a good idea to examine that literature.
 >> There are plenty of pitfalls to be avoided, and at this point it
 >> is known how to do so.

 Marcel> Paul,

 Marcel> would you happen to have pointers to good literature around?

"Interconnections", Radia Perlman (Addison-Wesley, 0-201-56332-0)

The IS-IS spec (ISO 10589, also RFC 1142).

The OSPF spec (RFC 2328)

I can't find citations for the papers by Eric Rosen or for the various 
ones on routing update protocols by Radia Perlman.  You might ask her
([email-masked]). 

 >> (By the way, a timestamp may be better than a sequence number.)

 Marcel> I don't see the advantages of a timestamp.  The advantage of
 Marcel> a sequence number is that you immediately know about holes,
 Marcel> updates which you have missed. As long as entries are
 Marcel> superseding each other, a timestamp is just fine, but if it
 Marcel> is only additive (as with PGP), I feel that seqnos are more
 Marcel> appropriate.

Good point, but make them bigger than 32 bits so you can avoid
worrying about wrapping (which is a problem, see Rosen).  And you may
still want a timestamp, indicating when the counter was initialized,
so you can recover from loss of the counter state.

	paul

---

From: Marcel Waldvogel <[email-masked]>
Date: Fri, 25 Jun 1999 17:24:38 +0200

Paul,

thanks for the references. In our design, we have been using (compressable)
IPv6 addresses and 64 bit counters, although we believe that 32 bit is
more than enough. Even if 32 bits should be exhausted, by adding an additional
IP address (kludge alert), another 2^32 sequence numbers could be allocated.

I see the advantage of the time stamp, but our idea was to recover the
counter state from a query to the local DB at start-up. And if the DB
should have crashed, rebuilding it according to the information received
from the other keyservers will also re-establish counter state.

-Marcel