[prev in list] [next in list] [prev in thread] [next in thread] 

List:       pgp-keyserver-folk
Subject:    Re: PGP Keyserver Synchronization Protocol
From:       Marcel Waldvogel <mwa () arl ! wustl ! edu>
Date:       1999-08-20 3:50:39
[Download RAW message or body]


Jack,

> After working over Baumer's paper a bit, I don't understand the fault 
> handling bits of the protocol, in chapter 4.  (Wording quoted here are all 
> from section 4.1, the overview):
> 
> 	- "When a keyserver detects a gap in the sequence number, it sends a 
> _request_ message to another keyserver, ..."  When is the gap checked 
> for?  Upon receipt of an update, no doubt; what about upon receipt of "a 
> _request_ message"?

We thought that the updates and heartbeats should ensure eventual
reliable delivery.  While it might speed up the synchronization by also
acting on requests for unknown sequence numbers, this will require more
bookkeeping at each server. A server willing to seek out for new
sequence numbers based on an incoming request will have to make sure
that it doesn't react to further incoming requests by generating another
request, to prevent livelocks. But other than that, the decision about
the two possible behaviors can be left to the discretion of the
individual implementations (they will still interoperate correctly,
IMHO).

> 	- "... the sequence number ..."  Is that the number of the last contiguous 
> known event, the first missing, the last missing, or the first received 
> noncontiguous?  In general, there may be missing gaps, not merely single 
> events (indeed, this seems more likely to me).  ("The oldest  missing 
> sequence number" seems like a good choice, with the implication that this 
> one and all subsequent known events be transmitted.)

Further down, request messages are described to basically contain an
enumeration of missing sequence numbers, represented in either of three
compact forms (ranges, bitmaps, and "everything above x")

> 	- "Then the Nearest Neighbour sends the information..."  What if the NN is 
> also missing the requested info?  Mention of deadlock elsewhere suggests 
> the NN might in turn requery its NN at this point, but this is nowhere 
> explicit.

The node detecting a missing sequence number will look for the NN having
the information using expanding multicast rings (although building rings
based on increasing TTL will not be too effective in IPv4, where both
scope and TTL are encoded in the TTL). Servers receiving a multicast
request message should not answer if they do not have (part of) the
requested information. Whoever responds first will be considered the NN
for that operation (see 5.8). If all fails, it may revert to the
originator.

> 	- During this period (while a _request_ is pending from the NN), what is
> the behavior of the server with respect to the request itself?  Does it 
> retry its request periodically, and/or after a timeout?  Should the server 
> crash in the interregnum, is it obligated to restore itself in some state 
> that will accept (or re-request) this info?  Or does it wait until yet one 
> more event arrives from the originator?  Does it continue to accept and 
> apply new server-server updates from this originator?  From other originators?

Expanding MC rings require some timeout mechanism during the expansion.
If a search turns out to be fruitless, the server can schedule a search
for a later time (preferrably some exponential backoff), or can wait for
the next heartbeat to occur, which should trigger the next search.

On a restart, the server can locally check for sequence gaps.
Additionally, it can search for someone responding to a
RequestSequenceCheck (i.e., actively soliciting for a unicast heartbeat
message), or simply wait for the next heartbeat to arrive.

> 	- During this period, does it continue to serve uploads and requests from 
> users?  Does it attempt to apply the updates?  (Note that some events, from 
> beyond the gap, from other servers, or from users, may not be possible to 
> apply, without the missing data - a new user ID added but lost, for 
> example, means a subsequent signature on that ID can not be applied - and 
> may not come even from the same originating server, so the potential 
> extends over all updates.)

Yes. Since users have to submit entire keys, there will be no missing
information. But it can occur that this server is uploaded a packet
which (unknown to us) another server has already issued an ID for, in
which case a single packet will receive a second ID (this is expected to
occur in rare cases). Since the linking between signatures and UIDs and
public keys occurs by sending out the higher-level elements also,
stalls as you describe them should not occur.

> 	- How does the distributed database detect and communicate the case where 
> a request to an NN is for some sequence number that in fact does not exist?
> 
> I'm particularly thinking of a potential global denial-of-service attack, 
> by sending a nonsensically-high sequence number into the mbone.  All 
> keyservers then query their NN, but none know the answer.  There is no 
> algorithm apparent here to recover (not to say it couldn't exist, but I 
> don't find it here).

This is true for both request- and update-/heartbeat-triggered
resynchronization and is dealt with in section 5.7, together with other
attacks. The originator can be queried for a signed message containing
the highest sequence number. This assumes that the servers know each
others public key. The signature does not need to be created "live", to
avoid further DoS attacks, but has a lifetime associated with it.
There is also support for cryptographically challenged servers, but
they obviously cannot protect their sequence numbers.

-Marcel

[Attachment #3 (application/pgp-signature)]

[prev in list] [next in list] [prev in thread] [next in thread]