"Pest" v. 0xFE.

This is a continuation of "Pest" v. 0xFF.

Edit: A note for the innocent -- this series of articles concerns an algorithm! It is not, at the time of writing, fully implemented anywhere! Or even entirely complete.

Edit: Various problems and discussions.

Edit: billymg made a mirror of this page.

The document (very much a work in progress!) is available as a vtree. You will need:

Add the above vpatches and seals to your V-set, and press to pest_spec_FE.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.

This document represents Protocol Version 0xFE.

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 instead inhabits a stand-alone station of which he is the sole operator. Pest stations exchange authenticably-encrypted messages exclusively with an operator-configured set of peers known as a WOT (wall 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 of the stations in that net.

A broadcast message is sent to every member of a station'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 not Centrally-Registered.

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.

He 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

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". An annoying, tedious, or habitually-spamming station operator is instead to be, at first -- warned by his fellows; then -- ignored via Usenet-style killfiles, and -- if he proves incorrigible -- unpeered by his peers. In the end, 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 are encouraged to form richly cyclic connection graphs for the highest attainable resiliency.

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 agreeing2 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.

2.3. The WOT.

A Pest station may have any number of peers. One or more3 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.

2.4. The AT.

A Pest station has another data structure, the AT (Address Table), which holds the last known address4 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 a cryptographically-valid packet is received from a new address.

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. Control Commands.

Control commands allow a Pest station's operator to view or update the station's configuration. They follow the traditional IRC syntax (i.e. /COMMAND ARGUMENT). Any such 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.
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-byte value, and may not previously exist anywhere in the WOT. If HANDLE is unknown, a warning is displayed.
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.
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.
RESOLVE HANDLE Resolve a fork afflicting the peer identified by HANDLE.

2.5.2. IRC-Compatible Commands.

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

Command Arguments Description
USER username hostname servername realname Must be the first command issued upon connecting to the console. 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 Must be the second command issued upon connecting to the console, and if found to be invalid, the console connection will be terminated. This is a password, or a derivative thereof; the exact authentication mechanism is unspecified.
NICK HANDLE Must be the third command issued upon connecting to the console. 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 Must be the fourth command issued upon connecting to the console. 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.3. Optional Commands.

The console may support certain other commands, including:

Command Arguments Description
GENKEY Use the system TRNG to generate and display a new KEY suitable for use with KEY. No change is made to the WOT.
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.
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.
BACKUP PATH The station will back up its current state (WOT, AT, killfile, and all other) to a file at the given PATH.
RESTORE PATH The station will attempt to restore all state (WOT, AT, killfile, etc) from a file at the given PATH.
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. 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 424 bytes, representing the following fields:

Bytes Description
8 Timestamp
32 SelfChain
32 NetChain
32 Speaker
320 Text

3.1.1. Timestamp.

A 64-bit timestamp5 from the message's originator. A relaying station 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.1.2. SelfChain.

3.1.2.1. SelfChain (Broadcast Messages)

A 256-bit hash6 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.1.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. One such value is stored per peer. The same rules apply as for broadcast messages.

3.1.3. NetChain.

3.1.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.1.3.2. NetChain (Direct Messages)

Must be set to zero.

3.1.4. Speaker.

A 32-byte field representing the Handle used by the originator. If this string consists of fewer than 32 bytes, all trailing bytes must be set to zero.

3.1.5. Text.

320 bytes comprising the (typically, human-readable) payload of the message. If Text consists of fewer than 320 bytes, all trailing bytes must be set to zero.

3.2. 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 red7 (i.e. plaintext).

3.2.1. Red Packet.

A red packet consists of 444 bytes, representing the following fields:

Bytes Description
16 Nonce
1 Bounces
1 Version
1 Reserved
1 Command
424 Message

3.2.1.1. Nonce.

16 bytes of garbage, exclusively for use as cipher nonce; obtained from TRNG, if possible.

3.2.1.2. Bounces.

This 1-byte field 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 3.

3.2.1.3. Version.

This is a 1-byte field representing a "degrees Kelvin" (i.e. decrementing) version.

3.2.1.4. Reserved.

This 1-byte field must equal 0.

3.2.1.5. Command.

This 1-byte field represents the intended purpose of the message carried by the packet, and must have one of these values:

Value Command Description
0x00 Broadcast The message is to be relayed to the entire net.
0x01 Direct The message is strictly for the addressee, and is not intended to be relayed.
0x02 Reserved
... ... Packet is rejected
0xFE Reserved
0xFF Ignore A station may transmit garbage messages to its peers, to frustrate traffic analysis by snoops. In such cases, it 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.2.1.6. Message.

A Pest message can be either:

  1. Direct -- Intended for a single recipient.

  2. Broadcast -- Intended for the widest 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. From the point of view of a receiver, every incoming broadcast message is either immediate or hearsay.

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.

3.2.2. Black Packet.

A station transmits messages exclusively to peers. Prior to transmission, a red packet is ciphered and signed using a K 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 508 bytes (excluding IP and UDP headers) representing the following fields:

Bytes Description
444 Ciphertext
64 Signature

A third party without knowledge of K 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 in the receiving station's WOT, in random order.

If verification of the packet against a particular K succeeds, the packet is then known to have been signed by the peer associated with that K. The packet is then decrypted (with K) 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 discarded8. 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 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.1.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.)
  3. The first 32 bytes of K represent K(S) -- the signing key; while the remaining 32 bytes of K are K(C) -- the cipher key.
  4. The AT entry for nebuchadnezzar is found. (If one such does not exist... see above.)
  5. A red packet is created, where:

    Bytes Description Value
    16 Nonce random bytes
    1 Bounces 0
    1 Version 255
    1 Reserved 0
    1 Command 0x01 (Direct Message)
    424 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.)
    320 Text Come to tea. (Followed by 308 null bytes.)
  6. A black packet is created from the above red packet, where:

    Bytes Description Value
    444 Ciphertext SERPENT_ENCRYPT(K(C),the 424-byte red packet)
    64 Signature HMAC512(Ciphertext, K(S))
  7. The black packet (henceforth -- packet) is stored in shalmaneser's transmission queue.

  8. The packet is transmitted to nebuchadnezzar's current address, determined in step 4.
  9. When an identical packet is echoed back from the above address, the transmission is considered complete. This is expected to happen within an operator-configurable period of time (recommended: 1 second.) If it does not, a warning will be displayed in shalmaneser's console:

    nebuchadnezzar did not ACK!

  10. The packet is removed from shalmaneser's transmission queue.

4.1.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. For each WOT peer P in shalmaneser's WOT, 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.)
  3. The first 32 bytes of Pk represent Pk(S) -- the signing key; while the remaining 32 bytes of Pk are Pk(C) -- the cipher key.
  4. The AT entry for P is found. (If one such does not exist, we move on to the next peer.)
  5. For each peer, a red packet is created, where:

    Bytes Description Value
    16 Nonce random bytes
    1 Bounces 0
    1 Version 255
    1 Reserved 0
    1 Command 0x00 (Broadcast Message)
    424 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.)
    320 Text Good morning, everyone! (padded with null bytes.)
  6. A black packet is created from the above red packet, where:

    Bytes Description Value
    444 Ciphertext SERPENT_ENCRYPT(Pk(C),the 424-byte red packet)
    64 Signature HMAC512(Ciphertext, Pk(S))
  7. The black packets (one for each peer) are stored in shalmaneser's transmission queue.

  8. From here, we proceed exactly as in the direct message example.

4.2. Message Receipt.

4.1.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
444 Ciphertext A red packet, ciphered with unknown key K(C).
64 Signature The result of signing Ciphertext with an unknown K(S).

nebuchadnezzar's station will carry out the following procedure:

  1. For each WOT peer P in nebuchadnezzar's WOT, in random order:
  2. For each Pk known for P... (If no keys are known for P, P is simply ignored.)
  3. The first 32 bytes of Pk represent Pk(S) -- the signing key; while the remaining 32 bytes of Pk are Pk(C) -- the cipher key.
  4. HMAC512(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.
  5. If a match was found, Pk(C) is used to decrypt Ciphertext and reproduce the original red packet.
  6. 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. The deduplication queue (a ring buffer holding the last hour's worth of messages, or last 256kB, whichever represents a greater number of messages) is searched for the message, . If an identical message is found in the queue, the packet is considered stale and is discarded.
  8. The message was not stale; it is placed into the deduplication queue.
  9. An identical copy of the packet is echoed to its originator to acknowledge receipt.
  10. At this point, the next step in the algorithm depends on the value of the Command field...

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}.

4.1.2. Receiving a Direct Message.

Continuing after the final step of the Common Prolog:

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

  1. If Speaker is not in H, a warning is emitted, e.g.:
    Direct message from 'bob' (shalmaneser)
    ... where the string in the parentheses is a WOT handle stored with the K which had validated the packet in step 4.
  2. The SelfChain warning is displayed if required.
  3. nebuchadnezzar's console will display the Speaker, followed by the Text, e.g. shalmaneser: Come to tea. in the standard format for IRC private messages.

4.1.2. Receiving a Broadcast Message.

Continuing after the final step of the Common Prolog:

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 cutoff, the packet is discarded.
  2. The next step of the algorithm will depend on whether Speaker is in H.

4.1.2.1. Receiving a Broadcast Message: Immediate Messages.

If Speaker is in H, the message is known as an immediate message. It is considered prima facie authentic, and displayed in nebuchadnezzar's console in the standard form for IRC messages, marked with channel #pest.

4.1.2.2. Receiving a Broadcast Message: Hearsay Messages.

4.1.2.2.1. Simple Hearsay.

If Speaker is NOT in H, the message is known as a hearsay message.

Consider a message received by nebuchadnezzar where H = {shalmaneser}, but Speaker is in fact hammurabi; and there is not a hammurabi in nebuchadnezzar's WOT.

nebuchadnezzar's station knows that the message was sent by shalmaneser, because a K belonging to shalmaneser had verified it. However, it also knows that this message had not been originated by shalmaneser. (Or, if it had been, he is perhaps suffering from multiple personality disease.)

In any case, nebuchadnezzar must be warned that the message is hearsay.

Therefore the Text will be displayed in nebuchadnezzar's console (in channel #pest) in the following form:

hammurabi(shalmaneser): hey listen!

... where the handle in parentheses corresponds to the peer from whom the packet had come.

4.1.2.2.2. In-WOT Hearsay.

Now suppose that Speaker is not in H, i.e. the message is a hearsay message, but that Speaker in fact is in the receiver's WOT. For instance, a message exactly like the previous example's, but where hammurabi is in fact a member of nebuchadnezzar's WOT.

This can happen if the immediate copy of hammurabi's packet (i.e. received directly from its originator) has been lost or delayed in transit.

When such a packet is received and validated, it is placed into the station's hearsay buffer and will remain there for an operator-configurable interval (recommended: 1 second) with the expectation that the original, immediate version of the packet will arrive shortly, and "knock out" the embargoed hearsay version.

If, however, the embargo interval elapses and the original packet is not received -- the hearsay packet will be processed (placed into the deduplication buffer, emitted to the station's console, and rebroadcast to peers.)

4.1.2.3. Receiving a Broadcast Message: Common Epilogue.

In both Immediate and Hearsay cases, after Text is sent to the console:

  1. Bounces is incremented by 1.
  2. The message is rebroadcast (see 4.1.2. Broadcast Message) to every WOT peer -- in random order.

5. Test Vectors.

5.1. Keys.

5.1.1. Test Key A.

The base64-encoded key:

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

5.1.2. Test Key B.

The base64-encoded key:

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

5.2. Packets.

TBD

6. Misc. Clarifications.

6.1. Symmetric Cipher.

Serpent is the only symmetric cipher to be used.

6.2. Signature.

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

6.3. Endianism.

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

6.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.

Notes.


  1. 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. 

  2. Via secure means external to Pest, such as GPG, Peh, or an in-person meeting. 

  3. 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 of K are known, the one which validated the most recently-received packet is to be used. 

  4. That is, the source address of the most recent packet received from this peer. 

  5. Current time shall be defined as the value of a station's 64-bit monotonic epoch clock. Station operators must take measures to synchronize their clocks within 15 minutes, a precision entirely achievable without recourse to centralized time servers. 

  6. In the current protocol: SHA256. 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. 

  7. Americanism. 

  8. All discarded packets are discarded silently; at no point is there to be any response to an invalid packet. 

This entry was written by Stanislav , posted on Monday September 06 2021 , filed under Bitcoin, Cold Air, Computation, Cryptography, Friends, Hot Air, Idea, Mathematics, ModestProposal, NonLoper, P2P, Philosophy, Progress, SerpentCipher, ShouldersGiants, SoftwareSucks . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

20 Responses to “"Pest" v. 0xFE.”

  • I've waited a while to read this, and I'm not disappointed. I did dislike the focus on IRC regarding the Operator Console; any implementation of Pest I build will use a unique interface that spares me from that terrible protocol. For quite a while I've entertained the idea of an implementation which accepts my messages from one end, and sends all deduplicated incoming messages from another; this idea will require some changes, but nothing that shatters the base idea; I like the idea of a tool which converts the conversation stored in a record file into a doubly-linked list for perusal, with additional linking for the message fields, perhaps similar to Ted Nelson's Zig Zag.

    I'd wondered how initial setup would be handled, and this out-of-band method is probably the only decent way to do this. I like the command terminology and its patterns. I seem to recall encryption wasn't part of the older design, but it doesn't place undue burden on implementation; I should be able to implement the Serpent cipher in one day. Surely little-endian isn't used purely because of the Serpent cipher using that? While it's minor, and transparent at the message level anyway, why was this chosen over big-endian, which is also the Internet order?

    I'm interested in a client which never dynamically allocates, and so there need be suggested limits on such things as aliases, hearsay buffers, and whatnot. A good default for how frequently to send Ignore messages may be each second, with substitution when the transmission queue isn't empty. Should the fifteen minute time boundary be set in stone, rather than merely be the suggested default; why has there been a shift back to epoch time, what I read referred to as "political time", over individual station time? I'll certainly have more ideas later.

    A Pest user is a Pester.

    • Stanislav says:

      Dear Verisimilitude,

      Thanks for the detailed read, and do stay tuned for the following drafts!

      The IRC compatibility is for the obvious reason: I intend to use the existing logotron; and, along with probably every other current Dulapnet resident, also intend to use my existing IRC client for a rather long time, and certainly have no desire to wait for someone to write an entirely new one before switching to P2Pism.

      Initial keying is to be handled out of band (how else ?) via GPGgram or in person.

      Little-endianism is specified because I am sick and tired of catering to the "network order" inherited from the glory days of Sun Micro etc. but existing today on, AFAIK, no recent iron whatsoever.

      Re: allocation -- in Ada you can allocate variably-dimensioned arrays on stack frames, this is amply illustrated in FFA, and ought to suffice.

      Re: Ignore messages (and likewise rekeys, though these have not yet made it into the draft) -- I deliberately left the frequency of their occurrence unspecified. Things on which two peers do not actually need to agree in order to interoperate, do not need to be nailed down in the spec IMHO.

      Re: epoch time -- is simply individual station time. It is impossible to prevent replays in the general case if there is no agreement on time. And I am entirely uninterested in any variant of the protocol where replays cannot be prevented in the general case.

      IMHO it is possible for all operators to get within +/-15min agreement without resorting to centralized NTPism.

      Yours,
      -S

      • I think big-endian is best, but it's clear only a war will solve the question forever; it's of minor importance. I referred to dynamically allocating after any program prologue, and with only predictable stack allocations. Ideally, space for so many peers and whatnot, not necessarily used then, could be allocated at the start and then left alone.

        That rekey idea is interesting; ideally, nowhere near the limit will be purposed, but there are at least a few interesting commands to add. Lastly, the time limit only prevents replays outside of the half hour window, right; I suppose the deduplication is expected to handle what remains.

        • Stanislav says:

          Dear Verisimilitude,

          > ...the time limit only prevents replays outside of the half hour window, right; I suppose the deduplication is expected to handle what remains

          Correct.

          Yours,
          -S

          • Adam says:

            Still reading but I think the deduplication buffer needs to be increased to line speed * 1 hour.

            Consider a busy net with more than 257 kB of broadcast traffic within the 1 hour window. I could continuously replay this data at a single node for at least 15 mins, as by the end of the recorded data it will start bumping the earliest packets out of the deduplication queue. Since they are flood routed the node will happily forward that to all connected nodes, overwhelming their deduplication buffer, so on and so forth.

            • Stanislav says:

              Dear Adam,

              Why would replayed data affect the contents of the victim's deduplication queue? You can't "bump" a message out of the queue by sending in the same message, it is already there. And sending in a message which got bumped on account of age will do nothing -- it will be rejected as stale.

              And recall that it's 256kB or 1 hour, whichever weighs more, rather than merely 256kB.

              The amount of storage required for the queue is in fact exactly linespeed * hour, as specified.

              The 256kB figure is simply an optimization for speeding up deduping in a low-traffic net. One could even make a case against it ("all packets should be processed in worst-case time!".)

              Yours,
              -S

            • Stanislav says:

              Dear Adam,

              On second thought, it isn't clear to me that there is any point in storing messages older than 15 minutes!

              Yours,
              -S

              • Adam says:

                Ah I see, I somehow misread the "whichever represents a greater number of messages."

                Yes 1 hour is more than you need, but I believe you need to store the last 30 minutes of messages to account for allowing up to 15 minutes of forward timestamp skew. A message received with a timestamp 15 minutes in the future, needs to be held in deduplication queue for at least 30 minutes before the timestamp will become stale enough that it won't make it to deduplication.

                I do think the specification would be simpler if it only specified holding the last 30 minutes of messages, and drop the bit about the 256 kB, as storing old messages serves no purpose, they will be rejected due to stale timestamp anyways.

  • bch says:

    > Little-endianism is specified because I am sick and tired of catering to the "network order" inherited from the glory days of Sun Micro etc. but existing today on, AFAIK, no recent iron whatsoever

    Network byte order (big endian) is still here and hton*() ntoh*() available to translate as needed. What problems does forcing little endian solve?

    • DangerNorm says:

      The thing about the argument from triviality, is that it's symmetric. What problems does using big endian solve, or avoid? "Network byte order" will continue to be used in IP and UDP headers forever, but there's no particular reason anything within that needs to have it, just because it's going over a wire, as long as the endianness is explicitly specified (which it should be in any case).

    • DangerNorm says:

      I'd also point out that even for C projects, hton and ntoh depend on an unsafe form of type punning that equivocates uint types with their byte stream representations. Better to treat uints as uints, and byte sequences as byte sequences, converting explicitly as needed. This also applies to reading and writing files.

  • DangerNorm says:

    What's the negative implication if I set my station to accept packets with any timestamp? A case that occurs to me where a stale but valid packet could be received is if a relaying peer receives a message and then loses internet connectivity for more than 15 minutes immediately afterwards. If they get it out eventually, and the signature is still valid, why would I want to not see it?

    • Stanislav says:

      Dear DangerNorm,

      If you process stale packets, your station can be flooded with replays of captured legitimate packets, i.e. it is DDoSable, and in fact will serve as a DDoS-amplifier against your peers, as it will relay the stale rubbish (if it happens to be a broadcast) to them.

      In a flood-routed network, this would be catastrophic.

      Yours,
      -S

  • Matt says:

    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 single unsolicited UDP packet containing garbage bytes can cause a node to perform O(WOT size) HMAC checks; this seems like a DDoS vector, not a source of resistance.

    • Stanislav says:

      Dear Matt,

      IMHO if your machine is not specced to process worst-case (O(WOT)) verification at GB/s (or whatever your line rate is), your machine is underspecced (or your WOT is far too big, and you ought to split your station into N independent substations.)

      Yours,
      -S

  • apeloyee says:

    1.No retransmission? What if a station briefly loses connectivity while a conversation is in progress? The station will then spam the operator with "xyz forked" messages per your spec.
    2.Is HMAC-512 supposed to be HMAC-SHA512?
    3.Using old logger only means it has to be compatible with IRC for messages. Specifying the station control interface as IRC-like is unnecessary.

    • Stanislav says:

      Dear apeloyee,

      Welcome back! (Please consider to visit dulapnet!)

      Re: 1 -- There's a retransmission mechanism in the draft of 0xFD.

      Re: 2 -- Correct.

      Re: 3 -- The intent is for the station apparatus to be controlled entirely via a (machine-local) IRC client, to avoid the chore of writing GUIware that is largely identical to existing softs.

      Yours,
      -S

  • DangerNorm says:

    Since packets are ACK'd by echoing, a MitM can memory hole messages in a way undetectable by either sender or recipient, but in considering this, I also realized that with the small size of messages and the limits of human communication rate, this seems like a protocol that could practically use channel saturation as a means of thwarting traffic analysis, in which IGNORE messages are sent to all peers on a fixed schedule, and substituted with real ones when a message enters the transmission queue (or a message needs to be ACK'd). Doubles as a liveness check, and at least makes memory holing conspicuous as a loss of contact.

    What's the motivation for having ACKing by echoing, rather than with, say, the hash of the plaintext?

    • Stanislav says:

      Dear DangerNorm,

      > Since packets are ACK'd by echoing...

      ACKs are slated to go away entirely in the 0xFD draft: they are quite unnecessary after we introduce getdata.

      > a MitM can memory hole messages in a way undetectable by either sender or recipient...

      Your (or your peer's) ISP certainly could decide to (or simply through malfunction) throw away every other packet; or even proclaim that the only packets that will be routed are to be to or from e.g. Facebook. IMHO it is not correct to call this a "MITM", as the enemy is unable to discriminate among the packets other than by source or destination, or to usefully substitute his own in place of the original.

      Neither is such an action "undetectable", it is entirely detectable via SelfChain and NetChain -- while there is any connectivity at all available to the pair of peers in question.

      If anything, Pest may be (AFAIK) the first attempt at a 100% IP-agnostic protocol (i.e. a peer can make use of as many IP addresses as he has control of, and for so long as some of them work some of the time he will be in business) -- and a step on the road to "regaining the original Internet", where "censorship is damage and we route around it automatically."

      > a protocol that could practically use channel saturation as a means of thwarting traffic analysis, in which IGNORE messages are sent to all peers on a fixed schedule, and substituted with real ones when a message enters the transmission queue...

      This is entirely doable, and even discussed previously in the logs -- but would be rather costly to apply after the protocol is no longer used strictly for chat, but also for e.g. warez.

      Yours,
      -S

Leave a Reply to Stanislav

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre lang="" line="" escaped="" highlight="">


MANDATORY: Please prove that you are human:

124 xor 118 = ?

What is the serial baud rate of the FG device ?


Answer the riddle correctly before clicking "Submit", or comment will NOT appear! Not in moderation queue, NOWHERE!