"Pest" v. 0xFB.
This is a continuation of "Pest" v. 0xFC.
This is the heaviest revision of the spec to date, approaching a total rewrite.
Pedantic details concerning data types and their encodings were added; several algorithms have been reworked and substantially simplified; and a number of ugly gaffes -- corrected.
There is a pretty-printed mirror of this spec.
Edit: various discussions.
There are currently two published prototype implementations of Pest:
"Blatta" (by thimbronion); and "smalpest" (by jonsykkel). Thank you, prototype implementers!
A quite lively Pestnet is now active, and a public log thereof, operated by billymg (WOT) may be seen here.
There is a working draft of v. 0xFA. (Note: it may change without warning!)
The document (very much a work in progress!) is available as a vtree. You will need:
- A V-tron. If you have no idea what V is, start here.
- pest_spec.kv.vpatch
- pest_spec.kv.vpatch.asciilifeform.sig
- pest_spec_FE.kv.vpatch
- pest_spec_FE.kv.vpatch.asciilifeform.sig
- pest_spec_FD.kv.vpatch
- pest_spec_FD.kv.vpatch.asciilifeform.sig
- pest_spec_FC.kv.vpatch
- pest_spec_FC.kv.vpatch.asciilifeform.sig
- pest_spec_FB.kv.vpatch
- pest_spec_FB.kv.vpatch.asciilifeform.sig
Add the above vpatches and seals to your V-set, and press to pest_spec_FB.kv.vpatch.
To "compile" the document to HTML, run make (this requires the "markdown2" utility.)
Please submit any proposed changes to this spec in vpatch form.
The full text is reproduced below, and any reader able to spare the time for a careful reading is invited to comment!
Click here for a printer-friendly version of this text.
- 1. Introduction.
- Version.
- 1.1. What is Pest?
- 1.2. How Pest Differs from IRC and Other Chat Protocols.
- 2. The Pest Station.
- 3. The Pest Wire Protocol.
- 3.1. Types and their Encodings.
- 3.2. Message.
- 3.3. Packets.
- 3.3.1. Red Packet.
- 3.3.2. Black Packet.
- 4. Fundamental Mechanisms.
- 5. NAT Penetration.
- 6. Test Vectors.
- 7. Misc. Clarifications.
- 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 party1 that he was not in fact the author of that message.2
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 away3, 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 peers4 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.5
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.6
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:
-
The operator -- via the operator console, an IRC-compatible interface.
-
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 agreeing7 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 more8 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 address9 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:
Command | Arguments | Description |
---|---|---|
USER |
username hostname servername realname | The string username must equal a preconfigured value stored on disk, or the console connection will be terminated. It is not used for any other purpose. None of the other parameters are used for any purpose, but may be present. |
PASS |
password | This is a password, or a derivative thereof; the exact authentication mechanism is unspecified. If the password is found to be invalid, the console connection will be terminated immediately. |
NICK |
HANDLE |
Every message originating at this station will have a Speaker equal to HANDLE . Importantly, HANDLE may not collide with any peer handle found in the station's WOT ; nor may PEER or AKA later be invoked with an argument equal to this HANDLE . |
JOIN |
#pest |
Valid USER , PASS , and NICK commands must be received prior to accepting this command. The argument must start with # . This is a pseudochannel which must be used in all subsequent IRC commands which require a channel (e.g. PRIVMSG , PART .) In all examples henceforth -- will be illustratively #pest , but in fact it may be any string of up to 128 bytes in length. |
PART |
#pest |
Has no effect. |
VERSION |
Display a description of the implementation and version of the protocol currently in use. | |
PRIVMSG |
(#pest or HANDLE ) MESSAGE |
Transmit MESSAGE as a broadcast message (if first argument starts with # ) or alternatively as a direct message to HANDLE . In the latter case, HANDLE must refer to a peer for whom at least one key is known and an AT entry exists. If these conditions are not satisfied, a warning is displayed and the command has no effect. |
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:
Command | Arguments | Description |
---|---|---|
WOT |
Display the current WOT , with complete (apart from keys) data concerning each peer. This includes the peer's handles; whether the peer is paused; the timestamp of the most recent packet received from the peer; and the current address stored in the AT for the peer. |
|
WOT |
HANDLE |
Display all WOT data concerning the peer identified by HANDLE , including all known keys, starting with the most recently used, for that peer. |
PEER |
HANDLE |
Declare a new peer, identified by HANDLE . This command is required but not sufficient to establish communication with the peer (see also KEY and AT .) |
UNPEER |
HANDLE |
Permanently discard all data concerning the peer identified by HANDLE , including keys and AT entries. |
AKA |
HANDLE ALIAS |
Permit the use of the string ALIAS synonymously with the previously-known HANDLE (which may in turn be the peer's original handle, or an alias added via this command.) |
UNAKA |
HANDLE |
Remove HANDLE from the WOT . However if it is any peer's only known handle, the command has no effect and a warning is displayed. |
PAUSE |
HANDLE |
Temporarily disable all communication with the peer identified by HANDLE , without discarding any data. |
UNPAUSE |
HANDLE |
Re-enable communication with the peer identified by HANDLE . |
KEY |
HANDLE KEY |
Add a KEY for the peer identified by HANDLE . KEY is in all cases a base64-encoded 512-bit value, and may not previously exist anywhere in the WOT . (If it was found to exist, an error message is displayed and nothing further happens.) If HANDLE is unknown, a warning is displayed. If KEY does not base64-decode to precisely 512 bits, an error message is displayed to this effect, and nothing further happens. |
UNKEY |
KEY |
Remove the given KEY from the WOT . However if KEY is any peer's only known key, the command has no effect and a warning is printed. |
GENKEY |
Use the system TRNG to generate and display a new KEY suitable for use with KEY . No change is made to the WOT . |
|
REKEY |
HANDLE |
Attempt a Rekeying with the peer specified by HANDLE . If no handle is specified, attempt rekeying with each peer in the WOT , in random order. All successful rekeyings are reported to the operator console (without displaying keys.) |
RKTOG |
ENABLE or DISABLE |
Toggle processing of Rekeying requests. Defaults to disabled. |
GAG |
HANDLE |
Add HANDLE (which may not correspond to a WOT peer!) to the killfile. Any incoming message where Speaker matches a killfile entry will not be processed. |
UNGAG |
HANDLE |
Undo the effect of a previously-issued GAG command. |
AT |
Display the current AT. | |
AT |
HANDLE |
Display the current AT entry for the peer identified by HANDLE . |
AT |
HANDLE ADDRESS |
Set the current ADDRESS in the AT for the WOT peer identified by HANDLE . In order for two peers to communicate, at least one of them must issue this command to add the other's address to his AT. Subsequently, this value will be updated as required as packets are received. |
KNOB |
Displays a list of all implemented knobs (operator-configured constants.) | |
KNOB |
KNOB |
Displays the current value of KNOB . |
KNOB |
KNOB VALUE |
Sets the knob identified by KNOB to VALUE . |
CUT |
INTEGER |
Sets the station's bounce cutoff to the given INTEGER between 0 and 255. If equal to 0, the station will process only direct messages. |
RESOLVE |
HANDLE |
Resolve a fork afflicting the peer identified by HANDLE . |
SLAVE |
HANDLE |
Intended strictly for use with bots. Set the station into slave mode with respect to the peer identified by HANDLE . The latter is referred to as a master. A broadcast message received solely via one or more peers identified as a master is treated as an immediate message; when rebroadcast, its bounce count will consequently be equal to one. More than one master may be set. |
SLAVE |
Display a list of masters that have been set via the SLAVE command. If this list is currently empty, the message "station is not in slave mode." is displayed. |
|
UNSLAVE |
HANDLE |
Removes the peer identified by HANDLE from the masters list. If the peer was not in the masters list, an error message is displayed and there is no other effect. |
UNSLAVE |
Removes all entries from the masters list. | |
BANNER |
TEXT |
Sets the banner string to be relayed to peers in Prod Messages. By default, this string corresponds to a brief description of the Pest implementation in use at the station. |
2.5.3. Optional Commands.
The console may support certain other commands. These use the same prefix as control commands, and include:
Command | Arguments | Description |
---|---|---|
ACHTUNG |
MESSAGE |
MESSAGE will be transmitted as a WOT circular, i.e. via a direct message addressed to each individual peer, exactly as if it had been issued via /PRIVMSG peername MESSAGE for each peer separately. |
SCRAM |
SCRAMPASS |
If sha512(SCRAMPASS) matches a preconfigured value stored on disk, the station will overwrite all in-memory and on-disk state with random bytes and shut down. This command may trigger other programmatic actions configured in advance by the operator, either before or after zapping all station state (e.g. in a before action -- emit a pre-defined /ACHTUNG deathsquad is here! goodbye friends! ). |
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:
Bytes | Description | Type |
---|---|---|
32 |
K(S) (Signing Key) |
Noise[32] |
32 |
K(C) (Cipher Key) |
Noise[32] |
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:
Bytes | Description | Type |
---|---|---|
8 |
Timestamp |
Time |
32 |
SelfChain |
Hash256 |
32 |
NetChain |
Hash256 |
32 |
Speaker |
AString[32] |
324 |
Payload |
Payload |
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 Timestamp
s must be equal. The receiving station will process them in the correct order using their SelfChain
values.
3.2.1. Timestamp.
A 64-bit timestamp10 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
Message
s. For all other Message
types, the values of these fields are undefined.
3.2.2.1. SelfChain (Broadcast Messages)
A 256-bit hash11 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
Message
s. 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 red12 (i.e. plaintext).
3.3.1. Red Packet.
A Red Packet consists of 448 bytes, representing the following fields:
Bytes | Description | Type |
---|---|---|
16 |
Nonce |
Noise[16] |
1 |
Bounces |
Integer[1] |
1 |
Version |
Integer[1] |
1 |
Reserved |
Zero[1] |
1 |
Command |
Integer[1] |
428 |
Message |
Message |
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:
Value | Command | Text? | Broadcast to Net? | |
---|---|---|---|---|
0x00 |
Broadcast Text | Yes | Yes | |
0x01 |
Direct Text | Yes | No | |
0x02 |
Prod | No | No | |
0x03 |
GetData | No | No | |
0x04 |
Key Offer | No | No | |
0x05 |
Key Slice | No | No | |
... | Undefined (Packet is rejected) | ... | ... | |
0xFE |
Address Cast | No | Yes | |
0xFF |
Ignore | No | Maybe |
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:
Bytes | Description | Type |
---|---|---|
2 | Flag |
Integer[2] |
6 | Address |
PestAddress |
32 | BroadcastSelfChain |
Hash256 |
32 | BroadcastNetChain |
Hash256 |
32 | DirectSelfChain |
Hash256 |
220 | Banner |
UString[220] |
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:
Bytes | Description | Type |
---|---|---|
32 | Hash of Requested Message | Hash256 |
292 | Padding | Zero[292] |
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:
- 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.)
- It in fact possesses a copy of the requested message.
- 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 Offer
s to demonstrate that their Key Slices
had been generated independently of one another.
The Payload
of this Message (324 bytes) consists of:
Bytes | Description | Type |
---|---|---|
64 | Hash of Key Slice to be Offered |
Hash512 |
260 | Padding | Zero[260] |
3.3.1.6.6. Key Slice.
A proposed key slice. In the Rekeying procedure, after the participants have exchanged Key Offer
s 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:
Bytes | Description | Type |
---|---|---|
64 | Proposed Key Slice |
Noise[64] |
260 | Padding | Zero[260] |
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:
Bytes | Description | Type |
---|---|---|
272 | Ciphertext (created with the target's K(C)) | Ciphertext[272] |
48 | Signature (created with the target's K(S)) | Seal |
4 | Padding | Zero[4] |
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:
Bytes | Description | Type |
---|---|---|
16 | Nonce |
Noise[16] |
4 | Cast Command | Zero[4] |
6 | Address | PestAddress |
246 | Padding | Zero[246] |
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:
Bytes | Description | Type |
---|---|---|
448 | Ciphertext | Ciphertext[448] |
48 | Signature | Seal |
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 discarded13. 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
Message
s 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:
- A list
Rm
, consisting of all peers who have supplied copies of the message during its embargo interval. - A time
Tm
, at which the earliest known copy of the message was received during its embargo interval. - 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:
- The station's
WOT
is searched for a peer with a handlenebuchadnezzar
. If there isn't one, ornebuchadnezzar
is currently paused, nothing further happens, and a warning will be emitted to the console. - The most-recently used key
K
fornebuchadnezzar
is found. (If no keys are known fornebuchadnezzar
, nothing further happens, and a warning will be emitted to the console.)K
is aPestKey
, , of which the components areK(S)
(the signing key) andK(C)
(the cipher key). - The AT entry for
nebuchadnezzar
is found. (If one such does not exist... see above.) -
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 time32
SelfChain
hash of shalmaneser
's previous direct message tonebuchadnezzar
32
NetChain
0 32
Speaker
shalmaneser
(padded with null bytes.)324
UString[324]
Come to tea.
(padded with null bytes.) -
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)
)
-
The message is interned into the station's
Long Buffer
. -
The Black Packet bearing the message is transmitted to
nebuchadnezzar
's currentAT
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:
- A list of addressees,
A
, is generated. By default, it will consist of all of the peers inshalmaneser
'sWOT
(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 peerP
inA
, in random order: - The most-recently used key
Pk
forP
is found. (If no keys are known forP
, we move on to the next peer.)Pk
is aPestKey
, of which the components arePk(S)
(the signing key) andPk(C)
(the cipher key). - The AT entry for
P
is found. (If one such does not exist, we move on to the next peer.) -
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 time32
SelfChain
hash of shalmaneser
's previous broadcast message32
NetChain
hash of the previous broadcast message seen by shalmaneser
, not inclusive of this one32
Speaker
shalmaneser
(padded with null bytes.)324
UString[324]
Good morning, everyone!
(padded with null bytes.) -
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)
)
-
The message is interned into the station's
Long Buffer
. -
The above Black Packet is transmitted to its addressee (i.e. to the Address currently known via the
AT
for the peerP
) 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:
Bytes | Description | Value |
---|---|---|
448 | Ciphertext | A Red Packet, ciphered with unknown cipher key K(C) . |
48 | Signature | The result of signing Ciphertext with an unknown signing key K(S) . |
nebuchadnezzar
's station will carry out the following procedure:
- For each key
Pk
innebuchadnezzar
'sWOT
, in random order: P
represents the peer to whom the keyPk
belongs.Pk
is aPestKey
, of which the components arePk(S)
(the signing key) andPk(C)
(the cipher key).HMAC384(Ciphertext, Pk(S))
is compared toSignature
. If they do not match, the next one is tried. If none match, the packet is declared martian and silently discarded.- If a match was found,
Pk(C)
is used to decryptCiphertext
and reproduce the original Red Packet. The packet is now considered to have been sent by the station operated by peerP
. - If a response to a
GetData
request is anticipated, the message is hashed; and if its hash is found in the list of currently-anticipatedGetData
responses, the message is deemed expected, and the next step is skipped. Note, however, thatGetData
responses are not to be rebroadcast. - 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. - If the
Speaker
of the message is present in theGAG
list, the message will not be displayed to the station's console or rebroadcast; however, it may still trigger the issuance ofGetData
requests if its antecedents cannot be found in theLong Buffer
. - 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. - If the message is a
Broadcast Text
orDirect Text
, theLong Buffer
is searched for the message's antecedents; if these cannot be located, aGetData
request is issued. In such a case, the message will be interned in theOrder Buffer
prior to further processing. - Let
H
be the set of all handles found in the station'sWOT
for the peer who was found to have sent the packet; e.g.{shalmaneser, ShalmaneserTheGreat}
. - 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:
- If
Bounces
is not equal to0x00
, the packet is discarded, given as direct messages are not relayed to third parties. - The message is interned into the
Long Buffer
. - The
SelfChain
warning is displayed if required. - If
Speaker
is not inH
, the console will display thePayload
of the message in the following format, e.g. if theSpeaker
isbob
, while the originator isshalmaneser
, then:
bob-shalmaneser: hello
... in the standard format for IRC private messages. (The operator of the receiving station may then choose to execute anAKA
command to storebob
as a handle sometimes used by the originator.) - If (as is normally the case) the
Speaker
is inH
, the console will display theSpeaker
, followed by thePayload
, 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:
Bounces
is compared to the operator-configured cutoff. If it is in excess of the bounce cutoff, the packet bearing the message is discarded.- The next step of the algorithm will depend on whether
Speaker
is inH
:
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.:
- The message is interned into the
Long Buffer
. - If the message had been previously interned into the
Short Buffer
, it is immediately removed from it. - The
Payload
of the message is displayed innebuchadnezzar
'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.:
- If
Bounces
is equal to0x00
, the message is discarded, given as only an immediate broadcast message may have a bounce of zero. - The message is interned into the
Short Buffer
. - 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:
-
The message is interned into the
Long Buffer
. -
The message is removed from the
Short Buffer
. -
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 intervalTm
...Tm + Te
. -
The message's
Bm
is considered to be the the minimum of all of the bounce counts among the copies received. -
A subset of
Rm
,Rbm
, is determined. It consists of such members ofRm
whose packet's bounce count was equal toBm
. -
The message is relayed to all active
WOT
peers, other than those found inRm
. The bounce count in the emitted packets will equalBm + 1
. -
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 inRbm
:
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:
- Station
A
would like to rekey with its peerB
, and generates a 512-bitKey Slice
Sa
using its TRNG. It takes a 512-bit hash ofSa
and encodes it into aKey Offer
Message
, which is then transmitted to stationB
. - Station
B
receivesA
'sKey Offer
. If rekeying is enabled on stationB
, it will proceed with the rekeying algorithm; otherwise it will silently discard the offer packet, and nothing further happens. IfA
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.) - If
B
chooses to acceptA
'sKey Offer
, it will generate its own slice,Sb
, produce aKey Offer
as described in the two preceding steps, and transmit said offer to stationA
. - When station
A
receivesB
'sKey Offer
, it will verify that the latter does not equal its own previously-sentKey Offer
. (If they were found to be identical,B
'sKey Offer
is deemed invalid, andA
will abort the rekeying.) IfA
proceeds with the rekeying, it will now encode its sliceSa
into aKey Slice
Message
and transmit saidMessage
to stationB
. - Station
B
will determine whether the hash inA
'sKey Offer
corresponds toH(Sa)
whereH
is the hash function. If it does not, the offer is deemed invalid and stationB
carries on as before, as if no rekeying request had been made. - However, if the hash matched, station
B
will reply by similarly encoding its sliceSb
into aKey Slice
Message
and transmitting saidMessage
to stationA
. - At this time, station
B
is able to calculate the new keyKn
using the equation:Kn == K xor Sa xor Sb
whereK
is the previous key used for peerA
,Sa
isA
'sKey Slice
, andSb
isB
'sKey Slice
.B
records this key in itsWOT
entry forA
, but does not discard the old keyK
yet. - 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. - If the hash matched, the
Rekey
handshake is deemed successful. - Station
A
will calculate the new keyKn
, similarly toB
in step 7:Kn == K xor Sa xor Sb
whereK
is the previous key shared with peerB
,Sa
isA
'sKey Slice
, andSb
isB
'sKey Slice
.A
records this key in itsWOT
entry forB
, but does not discard the old keyK
yet. - Station
A
will transmit anIgnore
packet to stationB
using the new keyKn
. - Station
B
, upon receiving this packet, will succeed in decoding it usingKn
. It will reply with anIgnore
packet to stationA
, ciphered and signed usingKn
. - Each of the stations will record
Kn
to theirWOT
s under the entry for the respective peer. - After three packets are successfully decoded by each station using
Kn
, the old shared key of the peersK
(with which they carried out steps 1 through 8) will be retired and removed from each station'sWOT
.
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.
- 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 peerP
(via use of theAT
command) will succeed in transmitting aProd
toP
. P
immediately replies toT
with anotherProd
(most NATs will pass an immediate reply to a UDP packet's address and port of origin), informingT
ofT
's own externally-reachable IP and portA
, i.e. aPestAddress
at whichT
can be reached.- The port of
A
will be a random ephemeral port "temporarily" assigned byT
's NAT, and the IP ofA
will be the publicly-routed IP via whichT
's NAT exits to the Internet at large. T
then periodically generatesAddress Cast
Messages
targeted to its still-unreachable peers, requesting to be contacted atA
, and transmits them toP
.P
will relay theAddress Cast
s to the Pest Net, where they will propagate, eventually reaching other peers ofT
.- When each of
T
's still-unreachable peers receives and processes theAddress Cast
Message targeted to it, it will begin sending packets toA
. T
will now succeed in establishing a bidirectional flow of packets with each of these peers.T
will keep the ephemeral ports in the NAT's routing table alive by issuingIgnore
messages to each of its peers everyTi
seconds (an operator-adjustable interval, with a recommended value of no more than10
seconds).- 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 FPMax. If valid packets arrive faster than the planned maximum frequency, a certain portion will be discarded. FPMax 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.
-
For instance, a provocateur, to his handler. ↩
-
Of course, Pest does not somehow prevent operators from creating opposably-signed messages using other software and transmitting them to their peers, on the rare occasions which actually call for this. ↩
-
Since only a valid packet will invoke any response from a Pest station, a stranger cannot -- via any heuristic whatsoever -- determine whether a certain remote IP address is in use by a certain Pest station; or whether a given set of IP addresses may belong to the same Pest station, or to a group of Pest peers; or, for that matter, whether they pertain to any use of Pest at all. It is impossible to port scan for Pest stations. A well-configured station will not use IP addresses shared with any public Internet services (e.g. WWW) for Pest; and will not answer ICMP messages sent to such addresses. Consequently, a stranger is not able to determine whether there even exists a machine at any such address. In other words, an IP address used by a Pest station is, from the point of view of anyone other than a peer of that station, indistinguishable from one assigned to an unplugged machine. ↩
-
Or, for that matter, one which may not have been intended as a Pest packet at all -- but simply happens to consist of 496 bytes. ↩
-
However, sometimes it is necessary to count the number of distinct peers who provided copies of a given message. ↩
-
Via secure means external to Pest, such as GPG, Peh, or an in-person meeting. ↩
-
A
K
is to be generated using a TRNG whenever possible. Multiple keys associated with one peer are permitted. This is convenient when phasing out an old key in favour of a new one. The converse (the use of one key for multiple peers) is prohibited. When addressing outgoing packets to a peer for whom multiple values ofK
are known, the one which validated the most recently-received packet is to be used. ↩ -
That is, the source address of the most recent packet received from this peer. ↩
-
Current time shall be defined as the value of a 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". Station operators must take measures to synchronize their clocks within 15 minutes, a precision entirely achievable without recourse to centralized time servers. ↩
-
In the current protocol: SHA257. The hash encompasses all message fields, in the order they are listed in the table. Any trailing padding bytes required by the hash are to equal zero. ↩
-
Americanism. ↩
-
All discarded packets are discarded silently; at no point is there to be any response to an invalid packet. ↩
At least one hilarious typo in this one!
I'm slowly working on my Pest implementation, writing each piece myself. I'm only leaving this comment here to voice a disagreement with this. It's right and proper to use the correct size of the voodoo function, and not to use the larger and merely truncate it. Any performance concerns are misguided and specific to particular machines. I vote against changing it.