• 1. Introduction.
  • Version.
  • 1.1. What is Pest?
  • 1.2. How Pest Differs from IRC and Other Chat Protocols.
    • 1.2.1. One Station -- One Operator.
    • 1.2.2. Nets Instead of Channels.
    • 1.2.3. Identity is Decentralized.
    • 1.2.4. Messages are Authenticable, but not Opposable.
    • 1.2.5. Ostracism as the Sole Sanction.
    • 1.2.6. Cyclic Connection Graphs Permitted.
    • 1.2.7. Nothing to the Stranger.
      • 1.2.7.1. "Martians".
      • 1.2.7.2. Duplicates.
      • 1.2.7.3. Stales.
    • 1.2.8. Nothing to the Snoop.
• 2. The Pest Station.
  • 2.1. The Station and its Operator.
  • 2.2. Peers and Keys.
  • 2.3. The WOT.
  • 2.4. The AT.
  • 2.5. Operator Console.
    • 2.5.1. IRC-Compatible Commands.
    • 2.5.2. Control Commands.
    • 2.5.3. Optional Commands.
• 3. The Pest Wire Protocol.
  • 3.1. Types and their Encodings.
    • 3.1.1. Integer
    • 3.1.2. Zero
    • 3.1.3. AString
    • 3.1.4. UString
    • 3.1.5. Time
    • 3.1.6. Hash256
    • 3.1.7. Hash512
    • 3.1.8. Seal
    • 3.1.9. Ciphertext
    • 3.1.10. PestKey
      • 3.1.10.1. PestKey: Signing Key
      • 3.1.10.2. PestKey: Cipher Key
    • 3.1.11. Noise
    • 3.1.12. PestAddress
      • 3.1.12.1. PestAddress: Port
      • 3.1.12.2. PestAddress: IP Address
    • 3.1.13. Payload
  • 3.2. Message.
    • 3.2.1. Timestamp.
    • 3.2.2. SelfChain.
      • 3.2.2.1. SelfChain (Broadcast Messages)
      • 3.2.2.2. SelfChain (Direct Messages)
    • 3.2.3. NetChain.
      • 3.2.3.1. NetChain (Broadcast Messages)
      • 3.2.3.2. NetChain (Direct Messages)
    • 3.2.4. Speaker.
    • 3.2.5. Payload.
  • 3.3. Packets.
    • 3.3.1. Red Packet.
      • 3.3.1.1. Nonce.
      • 3.3.1.2. Bounces.
      • 3.3.1.3. Version.
      • 3.3.1.4. Reserved.
      • 3.3.1.5. Command.
      • 3.3.1.6. Message.
        • 3.3.1.6.1. Broadcast Text.
        • 3.3.1.6.2. Direct Text.
        • 3.3.1.6.3. Prod.
          • 3.3.1.6.3.1. Prod: Flag.
          • 3.3.1.6.3.2. Prod: Address.
          • 3.3.1.6.3.3. Prod: BroadcastSelfChain.
          • 3.3.1.6.3.4. Prod: BroadcastNetChain.
          • 3.3.1.6.3.5. Prod: DirectSelfChain.
          • 3.3.1.6.3.6. Prod: Banner.
        • 3.3.1.6.4. GetData.
        • 3.3.1.6.5. Key Offer.
        • 3.3.1.6.6. Key Slice.
        • 3.3.1.6.7. Address Cast.
          • 3.3.1.6.7.1. Black Address Cast
          • 3.3.1.6.7.2. Red Address Cast
        • 3.3.1.6.8. Ignore.
    • 3.3.2. Black Packet.
• 4. Fundamental Mechanisms.
  • 4.1. Message Buffers.
    • 4.1.1. Long Buffer.
    • 4.1.2. Order Buffer.
    • 4.1.3. Short Buffer.
  • 4.2. Message Origination.
    • 4.2.1. Direct Message to a Peer.
    • 4.2.2. Broadcast Message.
  • 4.3. Message Receipt.
    • 4.3.1. Common Prologue for All Packets.
    • 4.3.2. Receiving a Direct Message.
    • 4.3.3. Receiving a Broadcast Message.
      • 4.3.3.1. Receiving a Broadcast Message: Immediate Messages.
      • 4.3.3.2. Receiving a Broadcast Message: Hearsay Messages.
        • 4.3.3.2.1 Hearsay Internment.
        • 4.3.3.2.2 Hearsay Eviction.
  • 4.4. Rekeying.
• 5. NAT Penetration.
• 6. Test Vectors.
  • 6.1. Keys.
    • 6.1.1. Test Key A.
    • 6.1.2. Test Key B.
  • 6.2. Packets.
• 7. Misc. Clarifications.
  • 7.1. Symmetric Cipher.
  • 7.2. Signature.
  • 7.3. Endianism.
  • 7.4. Bots.
  • 7.5. Valid Packets and Station Capacity.
  • 7.7. ICMP.
• Notes.

1. Introduction.

Version.

This document represents Protocol Version 0xFB.

1.1. What is Pest?

Pest is a peer-to-peer network protocol intended for IRC-style chat. It is designed for decentralization of control, resistance to natural and artificial interference, and fits-in-head mechanical simplicity -- in that order.

1.2. How Pest Differs from IRC and Other Chat Protocols.

Pest explicitly rejects the inherently-centralizing concepts of IRC (not even speaking of the even more noxious "walled-garden" atrocities perpetrated in recent years.) In place of IRC's collectivist concept of the server, every Pest user is instead the sole operator of a stand-alone station. A Pest station exchanges authenticably-encrypted messages exclusively with an operator-configured set of peers known as a WOT (web of trust.)

1.2.1. One Station -- One Operator.

An IRC server is typically inhabited by a multitude of casual users and policed by a small group of privileged curators. A Pest station, on the other hand, is under the exclusive control of one person: its operator.

1.2.2. Nets Instead of Channels.

Pest stations organize into nets. A net is formed by a group of station operators with a common interest. An operator who wishes to join a net must peer with at least one existing station in that net.

A broadcast message will reach every reachable member of its sender's net. Nets may easily and organically undergo schismatic splits, or, on the contrary, combine into larger nets, whenever the individual station operators so desire.

1.2.3. Identity is Decentralized.

A prospective Pest station operator need not ask permission from anyone; and the only other people who will need to know about the mere existence of the station will be its peers.

To join a Pest net, an operator must simply find one or more current members of that net who would peer with his station, and securely exchange a small amount of information. An active Pest station may have as few as one peer, or as many as its hardware is able to service at the desired bandwidth capacity.

A Pest station operator may choose any handle he likes, so long as it does not collide with that of a peer. Importantly, one person may easily operate multiple Pest stations, and inhabit multiple disjoint nets; and may use, if he wishes, a different handle on each net.

1.2.4. Messages are Authenticable, but not Opposable.

All Pest messages are authenticable -- a station will only process a message if it carries a valid signature from a peer (though in some cases, the message may not have been authored by that peer.)

However, they are also repudiatable (i.e. non-opposable) -- since all packet signatures are produced with symmetric keys, the recipient of a message cannot, at any point in time, prove to a third party¹ that he was not in fact the author of that message.²

1.2.5. Ostracism as the Sole Sanction.

Because Pest does not impose -- unlike IRC -- a hierarchical structure of control, it offers no direct equivalents to IRC's "kick" and "ban". Instead, an annoying, tedious, or habitually-spamming station operator may be rebuked by his peers; if he persists in his misbehaviour -- ignored via Usenet-style killfiles; and, if he proves incorrigible -- unpeered. Sooner or later, the malefactor will find himself where he belongs: either alone or in the company of his own kind.

1.2.6. Cyclic Connection Graphs Permitted.

Pest broadcast messages are flood-routed -- i.e. they traverse all available propagation paths. Unlike IRC relays, Pest stations may be connected in any topology their operators prefer; concretely, loops are permitted, in the interest of decentralization.

Infinite packet storms are prevented via deduplication at the station level -- rather than by prohibiting loops, or via a spanning tree protocol, or any other traditional routing schemes that enforce acyclic connection graphs by demanding the existence of "root nodes", "supernodes", centrally agreed-upon tables, etc.

Pest station operators are not merely permitted, but in fact encouraged to form richly cyclic connection graphs for the highest attainable resiliency.

1.2.7. Nothing to the Stranger.

From a Pest station's point of view, a stranger is any Internet-connected machine other than a peer.

Unlike virtually all traditional Internet protocols, Pest does not talk to strangers. At all.

Strangers may, of course, send whatever packets where they will -- including to a Pest station. However, because a stranger (by definition) does not know any of the keys in that station's WOT, all such packets will simply get thrown away³, as they are invalid.

An invalid packet is one which is determined to be martian, duplicate, or stale. Conversely, a packet which is neither martian, duplicate, nor stale is considered valid.

It is recommended that a Pest station be provisioned with sufficient hardware resources to process incoming packets at line rate (i.e. at the maximum rate at which they may arrive via the station's physical network interfaces.)

1.2.7.1. "Martians".

An incorrectly-sized packet received by a Pest station -- or a correctly-sized one which does not bear a valid signature from one of its peers⁴ is referred to as a martian. All such packets are silently discarded.

1.2.7.2. Duplicates.

An incoming packet which is correctly-sized and bears a valid peer signature is thereby not a martian. However, it may still turn out to be a duplicate. A packet is considered to be a duplicate if the Message it bears is identical to one encountered in a previously-accepted packet. Duplicates are silently discarded.⁵

1.2.7.3. Stales.

Any packet bearing a Message which has expired, or appears to come "from the future" is considered stale and -- even though it may be valid in every other respect -- is silently discarded.⁶

1.2.8. Nothing to the Snoop.

A stranger who is able to capture some or all of the traffic emitted by a Pest station is referred to as a snoop.

All Pest traffic consists of authenticably-encrypted UDP packets, and the encryption key is known strictly to the sender and the addressee. And so, a Pest packet intercepted en route conveys no useful information to a snoop, apart from the mere fact that a certain machine had sent a string of apparently-random bytes to a certain other.

In the interest of thwarting traffic analysis, a Pest station may occasionally transmit "Pest-like" rubbish packets to peers -- or even to arbitrary IP addresses. These packets offer a snoop no means whereby to distinguish them from bona fide Pest packets.

2. The Pest Station.

2.1. The Station and its Operator.

The operator of a Pest station -- who may be a human or a bot -- has absolute control of the station and its configuration.

A station communicates exclusively with:

1. The operator -- via the operator console, an IRC-compatible interface.

2. An operator-selected set of remote peer stations -- via datagrams.

2.2. Peers and Keys.

In order for a pair of Pest stations to communicate, their operators must decide to peer them by agreeing⁷ on a shared secret key K. Every packet sent by one peer to the other is signed/enciphered by the sender and verified/deciphered by the receiver using this K.

Additionally, at least one of the peers must have a routable, static address (here and below: IPv4 address and port, in a.b.c.d:p notation), and it must be known to the other peer.

If, at some future time, the operator of either station no longer wishes to continue in this relationship, he may terminate the peering unilaterally, and the two stations will then be said to have unpeered. A former peer is treated exactly the same as any other stranger.

2.3. The WOT.

A Pest station may have any number of peers. One or more⁸ K for each peer is kept in a data structure referred to as the station's WOT. The operator may edit this structure at any time, and changes take effect immediately. The WOT is never altered by the station except by direct command of the operator.

Each peer entry in the WOT also contains one or more handles, as well as certain other information concerning that peer.

2.4. The AT.

A Pest station has another data structure, the AT (Address Table), which holds the last known address⁹ of each WOT peer. The AT is used exclusively for determining where to send outgoing packets.

Like the WOT, the AT may also be edited by the operator at any time. Unlike the WOT, the AT is automatically updated by the station when any cryptographically-valid packet is received from a new (i.e. not currently in the AT) address. The AT contains one entry per WOT peer.

2.5. Operator Console.

A Pest station is controlled by its operator through the operator console -- an interface implementing a minimal subset of the classical IRC protocol.

Traditional IRC offers no provisions for secure authentication or encryption; hence, it is recommended that a Pest station and its IRC client reside in one physical machine. Alternatively, they may run on separate machines and connect via an SSH tunnel or similar mechanism.

Per RFC-1459, an IRC message shall not exceed 512 bytes in length, including the mandatory CR-LF terminator. Thus, there are 510 bytes available for a command entered into the console (including its parameters); and similarly for any message emitted via the console.

2.5.1. IRC-Compatible Commands.

The console will accept, at minimum, the following IRC-compatible commands:

2.5.2. Control Commands.

Control commands allow a Pest station's operator to view or update the station's configuration.

All control commands must be found at the beginning of a string entered into the operator console, and are prefixed with % (e.g. %WOT). Any line entered into the operator console which begins with % (i.e. appearing as an IRC message originating from the operator of the form PRIVMSG foo %bar, regardless of foo) must be treated as a control command, and a correct Pest implementation must take care to filter these lines to prevent emission of the command or its arguments as a Pest message. Whitespace may precede the % command prefix and is to be disregarded. If a station operator finds it necessary to transmit a Pest message starting with %, he may prefix it with a second %, i.e.: %%.

A control command may be issued at any time, and must take effect (including preserving any state change to persistent storage) immediately. Responses to control commands will be emitted through the console in the form of IRC NOTICE messages.

The following basic set of control commands must be supported:

2.5.3. Optional Commands.

The console may support certain other commands. These use the same prefix as control commands, and include:

3. The Pest Wire Protocol.

3.1. Types and their Encodings.

The following data types are used in Pest, and must be encoded as described here:

3.1.1. Integer

A Integer[N] is an integer, occupying precisely N bytes, mandatorily in little-endian order when applicable.

3.1.2. Zero

A Zero[N] is required to consist of precisely N bytes, each equal to zero.

3.1.3. AString

A AString[N] is a seven-bit-clean (i.e. pure ASCII) string, at most N characters in length. The field containing the string at all times occupies precisely N bytes, with all unused trailing bytes set to zero.

3.1.4. UString

A UString[N] is a UTF8-encoded string, at most N characters in length. The field containing the string at all times occupies precisely N bytes, with all unused trailing bytes set to zero.

3.1.5. Time

A Time is always an exactly 64-bit value, obtained from a Pest station's 64-bit monotonic epoch clock, traditionally defined as "a 64-bit unsigned fixed-point number, in seconds relative to 00:00:00 January 1, 1970, UTC".

3.1.6. Hash256

A Hash256 is an output of the traditional SHA-256 function, and occupies precisely 32 bytes.

3.1.7. Hash512

A Hash512 is an output of the traditional SHA-512 function, and occupies precisely 64 bytes.

3.1.8. Seal

A Seal is an output of the traditional HMAC-384 function, and occupies precisely 48 bytes. Signatures in Pest are computed exclusively over a Ciphertext and a PestKey's Signing Key.

3.1.9. Ciphertext

A Ciphertext[N] is a ciphertext produced with the Serpent symmetric cipher, operated in Cipher Block Chaining (CBC) mode. N must be a multiple of 16 (Serpent's block size) and refers to the bytewise length of the ciphertext as well as the plaintext it had been produced from.

3.1.10. PestKey

A PestKey is a secret key shared by a given pair of Pest peers, and under no circumstances revealed -- in whole or in part -- to any third party (including other peers.)

The key uniquely identifies the peer relationship from both directions: the identity of the peer who sent a particular packet is determined strictly by attempting signature verification and ciphertext decryption with every PestKey known to the recipient.

A PestKey occupies precisely 512 bits (64 bytes), which consist of the following:

At all occasions where a PestKey must be handled by a human, it is represented in Base-64 format.

3.1.10.1. PestKey: Signing Key

Generated independently of the Cipher Key, this value is used by a pair of peers strictly to produce or verify a Seal.

3.1.10.2. PestKey: Cipher Key

Generated independently of the Signing Key, this value is used by a pair of peers strictly to produce or decrypt a Ciphertext.

3.1.11. Noise

A Noise[N] consists of precisely N bytes of uniformly-distributed noise, obtained from a hardware TRNG where possible.

3.1.12. PestAddress

A PestAddress represents a two-byte port and a four-byte publicly-routable IPv4 address; it occupies precisely 6 bytes.

3.1.12.1. PestAddress: Port

The first byte of this field will consist of the least-significant byte of the port number; the second byte will contain its most-significant byte. (E.g. if the port number is equal to 1337, the first byte will equal 0x39, and the second byte will equal 0x05.)

3.1.12.2. PestAddress: IP Address

The IP field is laid out in order of descending significance. (E.g. if the IP to be encoded is 1.2.3.4, the third byte of the PestAddress will be equal to 0x01; the fourth: 0x02, the fifth: 0x03, the sixth: 0x04.)

3.1.13. Payload

A Payload consists of precisely 324 bytes, and constitutes the useful cargo of a Pest Message. The meaning of a Payload is determined by the Command found in the Red Packet which bears the Message.

3.2. Message.

When a line of text is entered into the operator console, this text -- along with certain other data -- becomes a new message. This message may then be encoded into a packet and transmitted to peers; and these, in turn, will forward it to their operator consoles (and relay it to their peers) if the necessary conditions are met.

The station where a message came into being is referred to as its originator.

A Pest Message consists of 428 bytes, representing the following fields:

Given that a Pest message is able to carry no more than 324 bytes of Payload, a single IRC message entered into the console may require the station to originate two Pest messages. They must be appropriately chained, and their Timestamps must be equal. The receiving station will process them in the correct order using their SelfChain values.

3.2.1. Timestamp.

A 64-bit timestamp¹⁰ from the message's originator, representing the time at which the message was originated. Relaying stations may not alter timestamps.

A station must reject any message which carries a timestamp more than 15 minutes in either direction (i.e. into the past or the future) from the moment (per the station's clock) it was received. Such messages are referred to as stale.

3.2.2. SelfChain.

SelfChain hashes are computed strictly for Broadcast Text and Direct Text Messages. For all other Message types, the values of these fields are undefined.

3.2.2.1. SelfChain (Broadcast Messages)

A 256-bit hash¹¹ of the originator's most recent previous message.

A station that is broadcasting for the first time must set its first message's SelfChain to zero.

If a station receives a broadcast message where SelfChain is equal to zero, and Speaker is e.g. nebuchadnezzar, and this speaker had never been seen previously, it will emit -- prior to the message -- a warning of the following form to the operator console:

Met nebuchadnezzar !

If, however, any messages with a Speaker of nebuchadnezzar were seen at any point in the past, but this message's SelfChain does not match the hash of the previous such message, the following warning shall be emitted to the console prior to the message:

nebuchadnezzar forked! prev.: "blah..."

... where "blah..." is the text of the previously-seen message pointed to by the SelfChain (if available in the buffer; if not, a base-16 representation of SelfChain is displayed instead.)

The peer nebuchadnezzar is henceforth considered forked. While he remains forked, the warning, in the above form, shall be emitted in the console (via NOTICE) every time a message is received where Speaker is nebuchadnezzar.

The fork will be considered resolved only after the station operator executes the command /RESOLVE nebuchadnezzar (after having a stern talk with the peer who had been relaying messages from the phony nebuchadnezzar!) Note that RESOLVE marks the last seen SelfChain as valid; hence, the command should be used only after the operator is reasonably certain that only the genuine nebuchadnezzar remains.

A station must not reject a broadcast message simply because its Speaker and SelfChain indicate a state of forkage. Doing so would make recovery from certain failures (lost packets; data corruption) impossible, and constitutes a denial-of-service vector. However, station operators are encouraged to make use of out-of-band (e.g. GPG) methods to resolve a fork, should one happen to arise; and to mercilessly unpeer anyone found to be deliberately causing a fork under whatever pretext.

3.2.2.2. SelfChain (Direct Messages)

A 256-bit hash of the most recent message previously generated by the originator in direct message sessions with a particular peer. The same rules apply as for broadcast messages.

3.2.3. NetChain.

NetChain hashes are computed strictly for Broadcast Text Messages. For all other Message types, the values of these fields are undefined.

3.2.3.1. NetChain (Broadcast Messages)

A 256-bit hash of the most recent broadcast message previously received or originated by the originator.

Currently this is not used for anything. In the future, it may be used for message reordering and Usenet-style threading.

3.2.3.2. NetChain (Direct Messages)

Must be set to zero.

3.2.4. Speaker.

An AString[32] representing the Handle in use by the originator. Pest Handles are mandatorily pure ASCII to abolish the homoglyph impersonation which plagued traditional chat protocols (e.g. IRC) which permitted UTF in handles.

Speaker may not be less than 3 characters in length. It must consist strictly of alphanumeric ASCII characters, additionally including underscore (a-zA-Z0-9_). Messages bearing a value of Speaker which does not conform to this pattern are rejected.

3.2.5. Payload.

The Payload, i.e. useful cargo, of a Pest Message.

In a Broadcast Text or Direct Text Message, the Payload is a UString[324], i.e. a human-readable text. In other Message types, the Payload is typically a machine-readable data structure.

3.3. Packets.

A message, together with certain information which helps its recipient decide what to do with it, is termed a packet. Every packet starts life as red¹² (i.e. plaintext).

3.3.1. Red Packet.

A Red Packet consists of 448 bytes, representing the following fields:

3.3.1.1. Nonce.

16 bytes of garbage, exclusively for use as cipher nonce; obtained from a hardware TRNG where possible. This value is not used for any purpose following decryption.

Cipher nonces are used to prevent the emission of identical ciphertexts even in a situation where a given plaintext is encrypted with a particular key more than once (and similarly for signatures). They also increase resistance to "known-plaintext attack" of symmetric cipher and signature schemes.

3.3.1.2. Bounces.

A single-byte Integer which represents the number of times the message in this packet had been relayed between stations. A station must reject messages which have experienced more than a preconfigured number of bounces. The recommended cutoff value is 5.

3.3.1.3. Version.

A single-byte Integer representing a "degrees Kelvin" (i.e. decrementing) version.

3.3.1.4. Reserved.

Zero[1], i.e. a single byte which must equal 0.

3.3.1.5. Command.

A single-byte Integer which represents the intended purpose of the message carried by the packet:

3.3.1.6. Message.

This 428-byte field contains the Message carried by the packet.

The intended purpose of the message is determined by the value of the command field of the packet which carried the message.

SelfChain and NetChain are valid strictly for Broadcast Text and Direct Text messages; in all other messages, these fields may contain arbitrary bytes.

3.3.1.6.1. Broadcast Text.

A human-readable message, intended for the broadest possible dissemination. A broadcast message is sent to every peer in the originator station's WOT, and will be propagated to their peers, and so on.

A broadcast message will often reach stations which are not peers of the originator. From the point of view of these stations, such a message is termed hearsay; and, when displayed, it is specially marked so as to distinguish it from an immediate message.

The Payload of a Broadcast Text is a UString[324].

3.3.1.6.2. Direct Text.

A human-readable message, intended strictly for the addressee.

The Payload of a Direct Text is a UString[324].

3.3.1.6.3. Prod.

Prod Messages aid Pest stations in NAT penetration (via the Address Cast mechanism) and chain synchronization (via the GetData mechanism.)

They also allow a station operator to share an arbitrary string with his peers (e.g. advertising his particular Pest implementation, a WWW URL, etc.)

The Payload of a Prod consists of the following:

If the supplied value of BroadcastSelfChain, BroadcastNetChain, or DirectSelfChain disagrees with the addressee's, the latter may issue one or more GetData Messages to the sender of the Prod.

3.3.1.6.3.1. Prod: Flag.

A two-byte Integer, with permitted values of 0 (indicating that an answer to this Prod, consisting of a Prod from the addressee) is requested, or 1 (indicating that this Prod is an answer to one previously received from the addressee.)

3.3.1.6.3.2. Prod: Address.

The Address currently used in the sender's AT for the addressee. It is identical to the one to which the sender intends to transmit the packet bearing this message.

3.3.1.6.3.3. Prod: BroadcastSelfChain.

The sender's current Broadcast SelfChain.

3.3.1.6.3.4. Prod: BroadcastNetChain.

The sender's current Broadcast NetChain.

3.3.1.6.3.5. Prod: DirectSelfChain.

The sender's current Direct SelfChain with the addressee.

3.3.1.6.3.6. Prod: Banner.

An arbitrary human-readable description of the sender's Pest station.

3.3.1.6.4. GetData.

The Payload of a GetData Message consists of a 256-bit hash of a previously-existing Message being requested for retransmission:

GetData Messages do not propagate, i.e. they may only be issued directly to a particular peer.

A GetData Message may be emitted by a station which had received a Broadcast Text or Direct Text Message, and consequently found that it is suffering from a chain gap (i.e. the station is in possession of a Message for which the SelfChain or NetChain antecedent has not been received.

Alternatively, the station may have received a Prod Message and learned that it had not received the most recent Broadcast Text on its Pest Net, or the most recent Direct Text Message a given peer had previously sent its way.

A station which receives a GetData message may reply with a copy of the message identified by the given Hash, if:

1. It has available CPU cycles (all such requests are to be processed on a best-effort basis, i.e. when the CPU would otherwise be idle.)
2. It in fact possesses a copy of the requested message.
3. The requested message was either: a broadcast text message; or a direct text message previously sent to the requesting peer.

A station must originate a GetData message whenever it encounters a Broadcast Text or Direct Text Message having a SelfChain or NetChain for which it does not possess the corresponding antecedent.

If the "offending" message was a Broadcast Text, at least one GetData request is issued to each peer of the station. If the message was a Direct Text, at least one GetData request must be issued to the peer from which the Direct Text had come.

A station which is expecting a response to a GetData request must hash every incoming Broadcast Text or Direct Text message, and check said hash against its list of expected hashes, prior to verifying the message's Timestamp -- as otherwise a GetData response bearing an older message may be deemed stale and discarded.

If the response in turn bears a SelfChain or NetChain for which the station does not possess an antecedent, the above logic is performed recursively on a best-effort basis.

When GetData requests succeed in closing a chain gap, the messages in question must be displayed to the operator console in the correct order (determined by their SelfChain or NetChain hashes.)

If, after an operator-configured interval elapses, GetData requests did not succeed in closing a chain gap, a warning will be issued to the operator, and the fork detector is invoked if appropriate.

If the Timestamp of a GetData response (or the earliest message in a chain of responses) pre-dates that of the message most recently displayed to the console, the operator must be informed of this, by prepending said Timestamp to the text emitted to the console.

3.3.1.6.5. Key Offer.

A 512-bit hash of a proposed key slice. The Rekeying procedure begins with the participants exchanging Key Offers to demonstrate that their Key Slices had been generated independently of one another.

The Payload of this Message (324 bytes) consists of:

3.3.1.6.6. Key Slice.

A proposed key slice. In the Rekeying procedure, after the participants have exchanged Key Offers and determined that they were not identical, each participant reveals his Key Slice to the other. The procedure concludes successfully if and only if each of the slices is found to hash to its respective previously-sent Key Offer. Their new PestKey will equal the xor of their previous key and both of the Key Slices.

The Payload of this Message (324 bytes) consists of:

3.3.1.6.7. Address Cast.

An encrypted-and-signed message to a particular peer, bearing the Address the sender would like to be reached at. The Payload of a Black Address Cast message resembles a Black Packet.

An Address Cast is transmitted as a Broadcast, i.e. will be disseminated as widely as possible on the sender's Pest Net. However, it will only be meaningful to the target -- the peer whose PestKey was chosen for the encryption and signing of the message's encrypted payload.

Address Cast messages are only generated for a target who is presently cold, i.e. a peer from whom no valid packets have been received for at least Tc seconds (an operator-configurable interval) or for whom at least one PestKey is known but no AT entry currently exists.

A station will generate and broadcast an Address Cast message targeted to each such peer in its WOT every Ta seconds (an operator-configurable interval.) Ta must be greater than or equal to Tc.

3.3.1.6.7.1. Black Address Cast

The Payload of the Message (324 bytes) consists of:

The Speaker field of a Message bearing an Address Cast Payload must match a WOT handle corresponding to its apparent originator.

A station which receives an Address Cast Message will attempt to verify and decrypt it (into a Red Address Cast) strictly on a best-effort basis (i.e. when the CPU would otherwise be idle), and strictly if there are currently cold peers in the station's WOT.

The logic is identical to that used for decoding Broadcast Text messages, with the exception of the epilogue, where, instead of treating the (decoded) Ciphertext as Red Packet, it will be interpreted as a Red Address Cast.

3.3.1.6.7.2. Red Address Cast

A Red Address Cast is the decrypted Ciphertext of a Black Address Cast Message. It consists of 272 bytes:

Cast Command must equal 0 (signifying Address Cast).

The Address field represents the IPv4 address and port number on which the originator station wishes to receive Pest packets from the target.

The supplied IP must represent a publicly-routable IPv4 address. (If a receiving station determines that it does not, it must silently reject the message.)

A station which successfully validated and decrypted an Address Cast from a cold peer will execute the equivalent of the AT command, henceforth attempting to use the supplied Address for all outgoing packets intended to reach that peer.

Following this, the station will immediately transmit an unspecified (but greater than or equal to 2) number of packets to said peer, at least one of which will carry a Prod, the rest bearing Ignore (rubbish) Messages.

An Address Cast found to have been received from a warm (i.e. not cold) peer is ignored.

3.3.1.6.8. Ignore.

A garbage message. A station may transmit garbage messages to its peers, to frustrate traffic analysis by snoops. In such cases, the Payload will consist of arbitrary random bytes. A recipient of such a message may relay it to an arbitrary subset of his WOT. Receipt of a garbage message must not result in any console output.

3.3.2. Black Packet.

A station transmits messages exclusively to peers. Prior to transmission, a red packet is ciphered and signed using a PestKey found in the WOT for the peer to whom it is to be sent. After this happens, the packet is referred to as black.

A black Pest packet consists of 496 bytes (excluding IP and UDP headers) representing the following fields:

A third party without knowledge of the key is unable to read such a packet; to distinguish it from arbitrary random noise; or to generate a spurious replacement (including via replay, in whole or in part, of a previously-sent packet) that could be accepted by the addressee.

Every incoming (without exception, black) packet has its Signature verified against each K(S) in the receiving station's WOT, in random order.

If verification of the packet against a particular K(S) succeeds, the packet is then known to have been signed by the peer associated with that key. The packet is then decrypted (with K(C), the corresponding cipher key) and becomes red once again; at this point, the receiving station is able to process the original message.

However, if none of the attempted verifications succeed, the packet is considered "martian" and silently discarded¹³. The receipt of a martian packet has absolutely no effect on a station, aside from wasting a small amount of CPU time. This provides a reasonable degree of DDOS resistance. A station may keep inexpensive statistical counters of martian packets.

4. Fundamental Mechanisms.

4.1. Message Buffers.

A Pest station has three message buffers:

4.1.1. Long Buffer.

The Long Buffer, aka the deduplication buffer, is a ring buffer holding at least the last hour's worth of fully processed unique messages (including ones originated at the station) indexed by message hash for speed of retrieval. Any incoming message found to have been previously interned in the Long Buffer is rejected immediately.

4.1.2. Order Buffer.

The Order Buffer temporarily interns packets bearing Broadcast Text and Direct Text Messages whose SelfChain or NetChain value has triggered the issuance of a GetData request. Such a packet is interned in the buffer for at most Tw seconds (an operator-configurable interval, not in excess of 5 minutes); following which, it is released for further processing, which continues at Step 10 of the Common Prologue.

At any time when the Order Buffer is non-empty, the station will schedule the continued processing of the oldest packet found there, to be executed Tw seconds following the Time at which said message was received.

The Order Buffer may contain packets bearing duplicate messages, and is indexed by Time of message receipt.

4.1.3. Short Buffer.

The Short Buffer, aka the hearsay embargo buffer: a ring buffer holding the last Te seconds worth of embargoed unique messages, indexed by message hash for speed of retrieval. Te is an operator-configurable interval, known as the embargo interval (recommended: 1 second).

Each message interned in the Short Buffer also has the following associated information:

1. A list Rm, consisting of all peers who have supplied copies of the message during its embargo interval.
2. A time Tm, at which the earliest known copy of the message was received during its embargo interval.
3. An integer Bm, representing the lowest bounce count seen among the packets bearing copies of the message.

At any time when the Short Buffer is non-empty, the station will schedule an hearsay eviction task, to be executed Te seconds following the Tm of the oldest message found in the buffer.

4.2. Message Origination.

When a station operator enters a line of text into the console, creating a new message, that station is termed the originator of that message.

There are two forms of message origination:

4.2.1. Direct Message to a Peer.

Suppose that a station operator using the handle shalmaneser had issued the command:

/PRIVMSG nebuchadnezzar Come to tea.

The following actions will be performed:

1. The station's WOT is searched for a peer with a handle nebuchadnezzar. If there isn't one, or nebuchadnezzar is currently paused, nothing further happens, and a warning will be emitted to the console.
2. The most-recently used key K for nebuchadnezzar is found. (If no keys are known for nebuchadnezzar, nothing further happens, and a warning will be emitted to the console.) K is a PestKey, , of which the components are K(S) (the signing key) and K(C) (the cipher key).
3. The AT entry for nebuchadnezzar is found. (If one such does not exist... see above.)

4. A Red Packet is created, where:

   Bytes	Description	Value
   16	Nonce	random bytes
   1	Bounces	0
   1	Version	a single byte representing the Pest protocol version supported by the originating station.
   1	Reserved	0
   1	Command	0x01 (Direct Text)
   428	Message	as given below:

   Bytes	Description	Value
   8	Timestamp	shalmaneser's current time
   32	SelfChain	hash of shalmaneser's previous direct message to nebuchadnezzar
   32	NetChain	0
   32	Speaker	shalmaneser (padded with null bytes.)
   324	UString[324]	Come to tea. (padded with null bytes.)

5. A Black Packet is created from the above Red Packet, where:

   Bytes	Description	Value
   448	Ciphertext	SERPENT_ENCRYPT(K(C), the 448-byte Red Packet)
   48	Signature	HMAC384(Ciphertext,K(S))

6. The message is interned into the station's Long Buffer.

7. The Black Packet bearing the message is transmitted to nebuchadnezzar's current AT address, determined in step 3.

4.2.2. Broadcast Message.

Suppose a station operator using the handle shalmaneser had issued the command:

/PRIVMSG #pest Good morning, everyone!

The following actions will be performed:

1. A list of addressees, A, is generated. By default, it will consist of all of the peers in shalmaneser's WOT (with the exception of any paused peers). However, if the message is a rebroadcast, A will not contain any peers from which copies of the message to be rebroadcast are known to have been received. For each peer P in A, in random order:
2. The most-recently used key Pk for P is found. (If no keys are known for P, we move on to the next peer.) Pk is a PestKey, of which the components are Pk(S) (the signing key) and Pk(C) (the cipher key).
3. The AT entry for P is found. (If one such does not exist, we move on to the next peer.)

4. For each P in A, a Red Packet is created, where:

   Bytes	Description	Value
   16	Nonce	random bytes
   1	Bounces	0
   1	Version	a single byte representing the Pest protocol version supported by the originating station.
   1	Reserved	0
   1	Command	0x00 (Broadcast Text)
   428	Message	as given below:

   Bytes	Description	Value
   8	Timestamp	shalmaneser's current time
   32	SelfChain	hash of shalmaneser's previous broadcast message
   32	NetChain	hash of the previous broadcast message seen by shalmaneser, not inclusive of this one
   32	Speaker	shalmaneser (padded with null bytes.)
   324	UString[324]	Good morning, everyone! (padded with null bytes.)

5. A Black Packet is created from the above Red Packet, where:

   Bytes	Description	Value
   448	Ciphertext	SERPENT_ENCRYPT(Pk(C), the 448-byte Red Packet)
   48	Signature	HMAC384(Ciphertext,Pk(S))

6. The message is interned into the station's Long Buffer.

7. The above Black Packet is transmitted to its addressee (i.e. to the Address currently known via the AT for the peer P) as determined in step 3.

4.3. Message Receipt.

4.3.1. Common Prologue for All Packets.

Suppose that a station operated by nebuchadnezzar has received a packet. The packet is from shalmaneser, but nebuchadnezzar's station does not know this yet, it has to authenticate and decrypt it first. Since all Pest packets traveling over the public internet are black, it will have the structure:

nebuchadnezzar's station will carry out the following procedure:

1. For each key Pk in nebuchadnezzar's WOT, in random order:
2. P represents the peer to whom the key Pk belongs. Pk is a PestKey, of which the components are Pk(S) (the signing key) and Pk(C) (the cipher key).
3. HMAC384(Ciphertext, Pk(S)) is compared to Signature. If they do not match, the next one is tried. If none match, the packet is declared martian and silently discarded.
4. If a match was found, Pk(C) is used to decrypt Ciphertext and reproduce the original Red Packet. The packet is now considered to have been sent by the station operated by peer P.
5. If a response to a GetData request is anticipated, the message is hashed; and if its hash is found in the list of currently-anticipated GetData responses, the message is deemed expected, and the next step is skipped. Note, however, that GetData responses are not to be rebroadcast.
6. The message's Timestamp is compared to the current system time and if it is more than 15 minutes in the past or the future, the packet is considered stale and discarded.
7. If the Speaker of the message is present in the GAG list, the message will not be displayed to the station's console or rebroadcast; however, it may still trigger the issuance of GetData requests if its antecedents cannot be found in the Long Buffer.
8. The message is hashed (if it has not already been); following which, the Long Buffer is queried for the presence of a message with said hash. If found to be present, the message is rejected as a duplicate.
9. If the message is a Broadcast Text or Direct Text, the Long Buffer is searched for the message's antecedents; if these cannot be located, a GetData request is issued. In such a case, the message will be interned in the Order Buffer prior to further processing.
10. Let H be the set of all handles found in the station's WOT for the peer who was found to have sent the packet; e.g. {shalmaneser, ShalmaneserTheGreat}.
11. At this point, the next step in the algorithm depends on the value of the Command field...

4.3.2. Receiving a Direct Message.

Continuing after the final step of the Common Prologue:

If Command is equal to 0x01, the message is a direct message:

1. If Bounces is not equal to 0x00, the packet is discarded, given as direct messages are not relayed to third parties.
2. The message is interned into the Long Buffer.
3. The SelfChain warning is displayed if required.
4. If Speaker is not in H, the console will display the Payload of the message in the following format, e.g. if the Speaker is bob, while the originator is shalmaneser, then: bob-shalmaneser: hello ... in the standard format for IRC private messages. (The operator of the receiving station may then choose to execute an AKA command to store bob as a handle sometimes used by the originator.)
5. If (as is normally the case) the Speaker is in H, the console will display the Speaker, followed by the Payload, e.g: shalmaneser: Come to tea. ... in the standard format for IRC private messages.

4.3.3. Receiving a Broadcast Message.

Continuing after the final step of the Common Prologue:

If Command is equal to 0x00, the message is a broadcast message:

1. Bounces is compared to the operator-configured cutoff. If it is in excess of the bounce cutoff, the packet bearing the message is discarded.
2. The next step of the algorithm will depend on whether Speaker is in H:

4.3.3.1. Receiving a Broadcast Message: Immediate Messages.

If Speaker is in H, the message is known as an immediate message. Given as it was received directly from its originator, it is considered prima facie authentic. Continuing after the final step of 4.3.3. Receiving a Broadcast Message.:

1. The message is interned into the Long Buffer.
2. If the message had been previously interned into the Short Buffer, it is immediately removed from it.
3. The Payload of the message is displayed in nebuchadnezzar's console in the standard form for IRC messages, marked with channel #pest.

4.3.3.2. Receiving a Broadcast Message: Hearsay Messages.

4.3.3.2.1 Hearsay Internment.

If Speaker is NOT in H, the message is known as a hearsay message. This means that the message was received from a peer who was not its originator, but rather its relayer. Duplicates of the message may arrive in rapid succession from multiple relayers. It is also possible that an immediate copy of the message is still in transit and may yet be received, removing the requirement to mark the message as hearsay.

Hearsay messages are processed as follows. Continuing after the final step of 4.3.3. Receiving a Broadcast Message.:

1. If Bounces is equal to 0x00, the message is discarded, given as only an immediate broadcast message may have a bounce of zero.
2. The message is interned into the Short Buffer.
3. The message will be retained in the Short Buffer until its eviction (either after the elapse of its eviction interval, or upon the receipt of an immediate copy of the message directly from its originator.

4.3.3.2.2 Hearsay Eviction.

Upon the elapse of Te seconds after a hearsay message's Tm (the time at which the earliest known copy was received), the following takes place:

1. The message is interned into the Long Buffer.

2. The message is removed from the Short Buffer.

3. The message's Rm is considered to be a complete list of its relayers, i.e. peers who supplied copies of the message during the interval Tm ... Tm + Te.

4. The message's Bm is considered to be the the minimum of all of the bounce counts among the copies received.

5. A subset of Rm, Rbm, is determined. It consists of such members of Rm whose packet's bounce count was equal to Bm.

6. The message is relayed to all active WOT peers, other than those found in Rm. The bounce count in the emitted packets will equal Bm + 1.

7. The Payload of the message is displayed to the station operator's console in one of the two following formats, depending on the number of entries in Rbm :

If Rbm consists of three or fewer peers, the Payload of the message is displayed in the console preceded by a set of square brackets listing the members of Rbm.

For instance, if min-bounce copies of a hearsay message purporting to originate from hammurabi had been received from shalmaneser, nebuchadnezzar, and bob, the list of these relayers will appear in square brackets, separated by | (pipe) characters:

hammurabi[shalmaneser|nebuchadnezzar|bob]: hi there

But if Rbm contains four or more members, the brackets will instead contain simply their total number:

hammurabi[11]: hi

4.4. Rekeying.

All symmetric cipher keys "age" with use. A Pest station may send Rekey requests to a particular peer. The receiving station may process such requests, or silently reject them.

It is recommended that a Rekey be conducted immediately after an initial peering and at regular intervals thereafter. Station operators may disable the processing of incoming Rekey requests (see the RKTOG control command) to preserve the validity of scheduled WOT backups; and re-enable it, when necessary, by mutual verbal agreement.

The Pest rekeying process is such that the initiator and receiver are each required to generate a xor-slice of the proposed new PestKey Kn independently. The new key will be equal to the xor of the previous key K shared by the two peers, with both of the proposed slices: Kn == K xor Sa xor Sb. Consequently, the new key Kn will have an expected entropy greater than or equal to that of the old key K and each of the slices Sa, Sb.

The algorithm takes the following form:

1. Station A would like to rekey with its peer B, and generates a 512-bit Key Slice Sa using its TRNG. It takes a 512-bit hash of Sa and encodes it into a Key Offer Message, which is then transmitted to station B.
2. Station B receives A's Key Offer. If rekeying is enabled on station B, it will proceed with the rekeying algorithm; otherwise it will silently discard the offer packet, and nothing further happens. If A does not receive the answer defined in the next step, it may try again in the future (given as the packet may have been lost in transit.)
3. If B chooses to accept A's Key Offer, it will generate its own slice, Sb, produce a Key Offer as described in the two preceding steps, and transmit said offer to station A.
4. When station A receives B's Key Offer, it will verify that the latter does not equal its own previously-sent Key Offer. (If they were found to be identical, B's Key Offer is deemed invalid, and A will abort the rekeying.) If A proceeds with the rekeying, it will now encode its slice Sa into a Key Slice Message and transmit said Message to station B.
5. Station B will determine whether the hash in A's Key Offer corresponds to H(Sa) where H is the hash function. If it does not, the offer is deemed invalid and station B carries on as before, as if no rekeying request had been made.
6. However, if the hash matched, station B will reply by similarly encoding its slice Sb into a Key Slice Message and transmitting said Message to station A.
7. At this time, station B is able to calculate the new key Kn using the equation: Kn == K xor Sa xor Sb where K is the previous key used for peer A, Sa is A's Key Slice, and Sb is B's Key Slice. B records this key in its WOT entry for A, but does not discard the old key K yet.
8. Station A will perform the same comparison operation as described in step 5. If the hash does not match, B's offer is deemed invalid, and nothing further happens.
9. If the hash matched, the Rekey handshake is deemed successful.
10. Station A will calculate the new key Kn, similarly to B in step 7: Kn == K xor Sa xor Sb where K is the previous key shared with peer B, Sa is A's Key Slice, and Sb is B's Key Slice. A records this key in its WOT entry for B, but does not discard the old key K yet.
11. Station A will transmit an Ignore packet to station B using the new key Kn.
12. Station B, upon receiving this packet, will succeed in decoding it using Kn. It will reply with an Ignore packet to station A, ciphered and signed using Kn.
13. Each of the stations will record Kn to their WOTs under the entry for the respective peer.
14. After three packets are successfully decoded by each station using Kn, the old shared key of the peers K (with which they carried out steps 1 through 8) will be retired and removed from each station's WOT.

All communication in steps 1 through 9 takes place using the previously-known shared key K.

A rekeying is deemed to have aborted (any slice Sx, as well as Kn if it has been generated -- discarded by the station) if it does not complete within an operator-specified interval Tk.

A station which has successfully rekeyed a peer (regardless of which operator initiated the rekeying process) will warn its operator, so that he is made aware of the need to back up his WOT.

5. NAT Penetration.

A Pest station trapped behind a NAT (Network Address Translation) apparatus may at first find itself unreachable by peers located outside of it. Pest offers a simple NAT penetration mechanism which enables a station to "escape" from the NAT, without access to the latter's configuration -- supposing that it is able to communicate with at least one peer in its WOT who is not inside a NAT, or has already succeeded in similarly escaping from his NAT.

1. A freshly-built (or relocated) Pest station T, trapped behind a NAT, which is able to establish a bidirectional flow of packets with at least one peer P (via use of the AT command) will succeed in transmitting a Prod to P.
2. P immediately replies to T with another Prod (most NATs will pass an immediate reply to a UDP packet's address and port of origin), informing T of T's own externally-reachable IP and port A, i.e. a PestAddress at which T can be reached.
3. The port of A will be a random ephemeral port "temporarily" assigned by T's NAT, and the IP of A will be the publicly-routed IP via which T's NAT exits to the Internet at large.
4. T then periodically generates Address Cast Messages targeted to its still-unreachable peers, requesting to be contacted at A, and transmits them to P.
5. P will relay the Address Casts to the Pest Net, where they will propagate, eventually reaching other peers of T.
6. When each of T's still-unreachable peers receives and processes the Address Cast Message targeted to it, it will begin sending packets to A.
7. T will now succeed in establishing a bidirectional flow of packets with each of these peers.
8. T will keep the ephemeral ports in the NAT's routing table alive by issuing Ignore messages to each of its peers every Ti seconds (an operator-adjustable interval, with a recommended value of no more than 10 seconds).
9. The process repeats as-required ad infinitum, such that every station on the given Pest Net at virtually all times possesses a reachable PestAddress for each of its peers.

This mechanism also eliminates the need to manually configure (via the AT command) a PestAddress for a newly-added peer who was already an inhabitant of your Pest Net.

A freshly-booted Pest station will assume that it is trapped behind a NAT. (If this is not so, in fact no change is required in the above algorithm, and the station will function normally, while helping any "trapped" peers to escape their NATs.)

6. Test Vectors.

6.1. Keys.

6.1.1. Test Key A.

The base64-encoded PestKey:

2Newlil7CEAcrLlLJhJaX1bOhYMzhbzX5s/UPYGXM3xTTry7sqvwYyp6ffinpQmgVVKZahjgIGILrPcAH2oI6A==

... when correctly decoded and broken into two 256-bit segments, represents the following (shown here in base-16) signing key:

d8d7b096297b08401cacb94b26125a5f56ce85833385bcd7e6cfd43d8197337c

... and the following cipher key:

534ebcbbb2abf0632a7a7df8a7a509a05552996a18e020620bacf7001f6a08e8

6.1.2. Test Key B.

The base64-encoded PestKey:

DpLg4cXUoraDQHaSfScfO7rV4jJGDKvq1RkpSnHRKKhhCZXMSvaq6QGKgcAbYriNXsw0bdiiz2/M0VeKL1Cb6g==

... when correctly decoded and broken into two 256-bit segments, represents the following (shown here in base-16) signing key:

0e92e0e1c5d4a2b6834076927d271f3bbad5e232460cabead519294a71d128a8

... and the following cipher key:

610995cc4af6aae9018a81c01b62b88d5ecc346dd8a2cf6fccd1578a2f509bea

6.2. Packets.

TBD

7. Misc. Clarifications.

7.1. Symmetric Cipher.

Serpent, in Cipher Block Chaining (CBC) mode, is the only symmetric cipher to be used.

7.2. Signature.

All signatures are to be carried out using HMAC-384.

7.3. Endianism.

All byte ordering in Pest, without exception, is little-endian unless otherwise stated.

7.4. Bots.

If an operator wishes to run bots, guest accounts, etc., additional stations may be set up to peer with his primary one; on the same physical machine, if so desired.

7.5. Valid Packets and Station Capacity.

When provisioning hardware for a Pest station, the operator must provide sufficient CPU cores, so that it may:

• Accept and process all valid packets, at a frequency at or below some planned maximum FP_Max. If valid packets arrive faster than the planned maximum frequency, a certain portion will be discarded. FP_Max valid packets per second, however, will be processed under any possible circumstances, and in particular regardless of the frequency at which invalid packets arrive.
• Reject all invalid packets at the maximum physically-possible rate at which they may arrive (i.e. up to and including the line rate) without affecting processing of valid packets.

7.7. ICMP.

The processing of ICMP packets by a machine housing a Pest station exposes the latter to demasking, violating the nothing to the stranger dictum; it is also a traditional DDOS vector. Therefore it is recommended that Pest station operators disable the processing of ICMP packets under any pretext whatsoever by whatever means required under their operating system or firewall setup.

Notes.