The 2022 Rack.

Thank you, 2021 Rack Service subscribers! I would like to wish all of you a third great year of hygienic Linux on high-quality non-Fritzed iron!

The 2022 service agreement remains identical to that of 2020 and 2021. (Deedbot Wallet closed in December of 2020, and there is yet no plug-in replacement for it. Hence, the only accepted means of payment remains, until further notice, traditional Bitcoin.)

As before, any and all communication concerning the details of a subscription payment is requested to take place strictly via PGP. And please remember to clearsign each message prior to encrypting; and to verify the signature on any reply of mine after decryption.

Additionally, I regret to inform subscribers that the upstream service cost has increased (thank the Reich's printing presses!) by 90 $; the cost of supplying an IP address has increased by 1.35 $; these increases are reflected in the 2022 Price Calculator.

The new rates take effect on 1 January 2022. Subscribers may however lock in the 2021 rate (for up to a year following their current expiration date) by renewing their subscriptions prior to 1 January 2022.

Since the previous report, there were exactly zero reported outages!

Expiration dates of all current paid subscriptions are listed below (in strictly chronological order, and without identifying the subscriber) :

Subscriber Iron Effective Through
A Dulap-128-4TB 23 Dec 2021
B RK-256 11 Feb 2022
C Dulap-128-4TB 14 Feb 2022
D Colo (1U; 100W; 1 IP) 03 Apr 2022
E APU3-2TB 16 Aug 2022
F RK-128 21 Nov 2022
G RK-256 Pro bono indefinite

If you are a subscriber, you should be able to easily find yourself in this list.

"Pest" v. 0xFD.

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

There is a pretty-printed mirror of this page.

There is now a prototype! (Thank you, thimbronion!)

There is a working draft of v. 0xFC. (Note: it may change without warning!)

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_FD.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 0xFD.

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

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

1.2.8. Nothing to the Snoop.

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

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

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

2. The Pest Station.

2.1. The Station and its Operator.

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

A station communicates exclusively with:

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

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

2.2. Peers and Keys.

In order for a pair of Pest stations to communicate, their operators must decide to peer them by 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 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. 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, irregardless 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 payload 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 the traditional Unix escape character: \%.

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

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. 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
8 Timestamp
32 SelfChain
32 NetChain
32 Speaker
324 Text

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

3.1.1. Timestamp.

A 64-bit timestamp10 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 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.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.

324 bytes comprising the (typically, human-readable) payload of the message. If Text consists of fewer than 324 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 red12 (i.e. plaintext).

3.2.1. Red Packet.

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

Bytes Description
16 Nonce
1 Bounces
1 Version
1 Reserved
1 Command
428 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:

Value Command Text? Broadcast to Net?
0x00 Broadcast Text Yes Yes
0x01 Direct Text Yes No
0x02 Banner Yes 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.2.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.2.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.

3.2.1.6.2. Direct Text.

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

3.2.1.6.3. Banner.

A human-readable description of the sender's station. The treatment of such messages is currently undefined.

3.2.1.6.4. GetData.

A 256-bit hash of a previously-existing message requested for retransmission. See GetData.

3.2.1.6.5. Key Offer.

A 512-bit hash of a proposed key slice. See Rekeying.

The Text payload of the message (324 bytes) must consist of:

Bytes Description
64 Hash of Offered Key Slice
260 Padding of null bytes
3.2.1.6.6. Key Slice.

A proposed key slice. See Rekeying.

The Text payload of the message (324 bytes) must consist of:

Bytes Description
64 Offered Key Slice
260 Padding of null bytes
3.2.1.6.7. Address Cast.

An encrypted-and-signed message to a peer bearing the address the sender would like to be reached at. Address Cast messages are treated as broadcasts, and their payloads resemble black packets.

The Text payload of the message (324 bytes) must consist of:

Bytes Description
276 Ciphertext
48 Signature

A station which receives an address cast 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.) The logic is identical to that used for decoding Broadcast Text messages, with the exception of the epilogue, where, instead of treating the (decoded) payload as human-readable text, it will be treated as a Red Address Cast, i.e. 276 bytes of plaintext, which take the following format:

Bytes Description
4 Cast Command
2 Port
4 IP
266 Padded with null bytes

Cast Command must equal 0 (signifying Address Cast).

A station which successfully validated and decrypted an Address Cast from one of its peers will execute the equivalent of the AT command, henceforth using the supplied address for all outgoing packets intended to reach that peer.

The circumstances under which a station will originate an address cast are presently undefined. (A reasonable behaviour may be to generate one periodically for every peer in the station's WOT).

3.2.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, 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.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 496 bytes (excluding IP and UDP headers) representing the following fields:

Bytes Description
448 Ciphertext
48 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 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 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 253
    1 Reserved 0
    1 Command 0x01 (Direct Message)
    428 Message as given below:
    Bytes Description Value
    8 Timestamp shalmaneser's current time
    32 SelfChain hash of shalmaneser's previous direct message to nebuchadnezzar
    32 NetChain 0
    32 Speaker shalmaneser (padded with null bytes.)
    324 Text Come to tea. (padded with null bytes.)
  6. 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))
  7. The black packet is transmitted to nebuchadnezzar's current address, determined in step 4.

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 253
    1 Reserved 0
    1 Command 0x00 (Broadcast Message)
    428 Message as given below:
    Bytes Description Value
    8 Timestamp shalmaneser's current time
    32 SelfChain hash of shalmaneser's previous broadcast message
    32 NetChain hash of the previous broadcast message seen by shalmaneser, not inclusive of this one
    32 Speaker shalmaneser (padded with null bytes.)
    324 Text Good morning, everyone! (padded with null bytes.)
  6. 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))
  7. Each black packet (one for each peer) is transmitted to its destination, determined in step 4.

4.2. Message Receipt.

4.2.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 key K(C).
48 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. HMAC384(Ciphertext, Pk(S)) is compared to Signature. If they do not match, the next one is tried. If none match, the packet is declared martian and silently discarded.
  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 is a ring buffer holding the last hour's worth of messages. If an identical message is found in the queue, the packet is considered stale and is discarded.
  8. If, in the previous step, the deduplication queue was not found to already contain a copy of the message, a copy is placed there.
  9. 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}.
  10. At this point, the next step in the algorithm depends on the value of the Command field...

4.2.2. Receiving a Direct Message.

Continuing after the final step of the Common Prologue:

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

  1. If Bounces is not equal to 0x00, the packet is discarded.
  2. The SelfChain warning is displayed if required.
  3. If Speaker is not in H, the console will display the Speaker, followed by the entirety of H (in parentheses), followed by the Text:
    bob (shalmaneser): hello
    ... in the standard format for IRC private messages.
  4. If Speaker is in H, the console will display the Speaker, followed by the Text, e.g:
    shalmaneser: Come to tea.
    ... in the standard format for IRC private messages.

4.2.3. Receiving a Broadcast Message.

Continuing after the final step of the Common Prologue:

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

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

4.2.3.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.2.3.2. Receiving a Broadcast Message: Hearsay Messages.

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

If Bounces is equal to 0x00, or in excess of the bounce cutoff, the message is discarded.

A packet bearing a hearsay message is placed into the station's hearsay buffer and will remain there for an operator-configurable interval (recommended: 1 second).

If packets bearing duplicates of the message are received, they must be discarded, but the bounce count of the retained copy must be considered equal to that of the copy bearing the lowest bounce count.

Tthe count of peers who have supplied copies of a particular message is tallied; following which, the message is processed in one of the two ways given below, depending on whether Speaker is in the receiver's WOT:

4.2.3.2.1. Simple Hearsay.

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

If, after the elapse of the embargo interval, an immediate version of the message is found to be in the buffer, it will "knock out" the embargoed hearsay version.

If, however, the embargo interval elapses and an immediate copy was not received -- the message will be processed as hearsay.

4.2.3.3. Receiving a Broadcast Message: Common Epilogue.

Broadcast messages which survived deduplication are processed as follows:

  1. If any duplicates of the message were found to have been received upon the elapse of the embargo interval, the copy of the message bearing the lowest bounce must be selected for further processing, and all others discarded.

  2. The Text of the message will be displayed to the console.

  3. The message will be relayed to all peers.

If the message had been a deemed Hearsay, its Text will be displayed to the console in one of the two following formats, depending on how many peers had sent in duplicates of this message during the embargo interval :

If three or fewer peers had sent in such duplicates, the Text of the message will be displayed in the console preceded by a set of parentheses listing the handle of each such peer.

For instance, if copies of a hearsay message purporting to originate from hammurabi had been received from shalmaneser, nebuchadnezzar, and bob, it will appear as:

hammurabi(shalmaneser, nebuchadnezzar, bob): hi there

But if four or more duplicates of a hearsay message were received during the embargo interval, the parentheses will instead contain simply the total number of peers who had sent them, e.g.:

hammurabi(11): hi

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.

6. Rekeying.

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

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

The algorithm takes the following form:

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

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

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

A station which has successfully rekeyed a peer (irregardless 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.

7. GetData.

The Text payload of a GetData message (324 bytes) must consist of:

Bytes Description
32 Hash
292 Padding of null bytes

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

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

A station must originate a GetData message whenever it encounters a message bearing a SelfChain or NetChain for which it does not possess a corresponding previously-received message. If the "offending" message was a broadcast, at least one GetData request must be issued to each peer of the station. If the message was a direct message, at least one GetData request must be issued to the peer who sent the direct message.

A station which is expecting a response to a GetData request must compare the hash of every incoming broadcast text message or direct text message message to the expected hash prior to verifying its Timestamp, as the response may otherwise be deemed stale.

If the response in turn bears a SelfChain or NetChain for which the station does not possess a corresponding previously-received message, the above logic is performed recursively on a best-effort basis. An unspecified cycle-finder algorithm will be used to detect cyclical chains, and it is recommended that any peer found to be producing cyclical chains under any pretext whatsoever, be unpeered and publicly shamed.

If 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 chain 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 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 the timestamp to the text emitted to the console.

8. Test Vectors.

8.1. Keys.

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

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

8.2. Packets.

TBD

9. Misc. Clarifications.

9.1. Symmetric Cipher.

Serpent is the only symmetric cipher to be used.

9.2. Signature.

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

9.3. Endianism.

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

9.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. For instance, a provocateur, to his handler. 

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

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

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

  5. However, sometimes it is necessary to count the number of distinct peers who provided copies of a given message

  6. Unless the message is an expected response to a getdata

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

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

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

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

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

  12. Americanism. 

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

"The Harper."


"The Harper."
by Vlas Mikhailovich Doroshevich (1864--1922).


The Emperor Jin-La-O, may his memory be sacred to the whole braid-adorned world, was a wise and just Emperor.
One day he summoned his entourage and said to them:
- I would like to learn the name of the greatest villain in all of Beijing - in order to punish him appropriately, frighten the wicked and encourage the virtuous.
The courtiers bowed at his feet and set forth. For three days and three nights they walked around Beijing, visiting bazaars, teahouses, opium dens, temples and generally places where people crowd. They listened attentively.
And on the fourth day they came to the Emperor, bowed at his feet and said:
- We did all that our humble strengths could do to fulfill your heavenly will. And indeed they had.
- Do you now know who is the greatest villain in Beijing? - asked the Emperor.
- Yes, Master of the Universe. We know him. -- His name? - Jian-Fu.
- What has this scoundrel been up to? - exclaimed, boiling over with noble indignation, the Emperor.
- He plays the harp! - the emissaries answered.
- What crimes does this harper commit? Does he kill people? - asked the Emperor.
-- No.
- Does he rob?
-- No.
- Does he steal?
-- No.
- But what, at last, are the incredible doings of this man? - exclaimed the Emperor, lost in conjecture.
- Exactly nothing! - the emissaries answered. - He only plays the harp. And he plays splendidly, I must confess. You yourself, the Lord of the Sun and the Lord of the Universe, have repeatedly deigned to listen to his playing and even approved of it.
-- Yes Yes! Now I recall! Harper Jian-Fu! I recall. An excellent harper! But why do you consider him to be the greatest villain in Beijing?
The courtiers bowed and answered:
- Because all of Beijing scolds him. "Scoundrel Jian-Fu"! "Swindler Jian-Fu"! "Villain Jian-Fu"! - is all you hear at every step you take. We went around all the temples, all the bazaars, all the teahouses, all the places where people crowd - and everywhere everyone spoke only of Jian-Fu. And when they spoke of him, they did nothing but to scold him.
-- Strange! - exclaimed the Emperor. - No, there is surely something amiss here!
And he decided to investigate the peculiar matter himself. He disguised himself as a commoner and, accompanied by two similarly-disguised bodyguards, set off to wander the streets of Beijing. He came to the bazaar.
The morning market was over, the merchants were folding their baskets and chatting among themselves.
- This wretch Jian-Fu! - shouted one of the traders. - He played a sad song again last night at the new moon holiday. If only he would play something merry!
- Don't hold your breath! the other laughed viciously. - Can this scoundrel even play merry songs?! Making merry is for those whose souls are as white as a tea-tree flower. But this swindler has a soul as black as ink. That's why he plays only sad songs.
- How does such a villain cheat the gallows! someone in the crowd exclaimed.
- He ought to be cut in half with a blunt saw, and certainly the long way through! - corrected a neighbor.
- No, tie him to two horses by the arms and legs and tear him apart!
- Put him in a sack with cats that have not been fed for a long time!
And everyone shouted:
- Villain Jian-Fu! - Scoundrel Jian-Fu! - How does the earth stand him!
The Emperor went to the tea house.
Visitors sat on mats and drank tea from tiny cups.
- Good afternoon, good people! Let the souls of your ancestors whisper good advice to your souls! - greeted the Emperor, entering and bowing. - What's new in Beijing?
- Why, before you got here, we were just talking about the villain Jian-Fu! - said one of those present. - Has he done something? - asked the Emperor. -- What? Didn't you hear? The whole city is talking about it! - exclaimed all around. - Yesterday he accidentally hooked his fingernail on the wrong string and hit the wrong note! Scoundrel!
- What a horror it was! one of them exclaimed, pretending to writhe.
- And yet he hasn't been hanged yet! - Nor torn to pieces!
And all, indignant to the depths of their souls, exclaimed:
- Scoundrel Jian-Fu! - Swindler Jian-Fu! - Villain Jian-Fu!
The Emperor went to the opium den. There was a terrible din there.
-- What happened? - asked the Emperor.
-- A! As always! They are arguing about Jian-Fu! - the owner waved his hand.
The smokers, lying on their cots, scolded Jian-Fu through and through.
- He played five songs yesterday! one shouted. - As if two weren't enough! - He played five songs yesterday! - grumbled another. - As if he couldn't have played seven or eight!
And they scolded Jian-Fu until they fell asleep with their eyes open.
And even then, they muttered in their sleep: - That villain Jian-Fu! - Scoundrel Jian-Fu!
- Swindler to rule all swindlers, Jian-Fu!
The Emperor went to the temple.
People prayed to the gods, but when they got tired of praying, they began to exchange remarks and whispered to each other:
- And Jian-Fu, it so happens, is a scoundrel!
In short, until nightfall the Emperor walked around the whole city and everywhere heard only: - Jian-Fu! Jian-Fu! Jian-Fu! The villain! Scoundrel! Swindler! Finally, in the evening, returning home, he stopped on his way at the house of a poor coolie and, wishing the hosts a good supper, asked:
- Have you heard the harper Jian-Fu?
- How could we have! - answered the poor coolie. - Do you think we have time for entertainment or money to pay to hear harp music! We haven't even enough for rice! But we still know that Jian-Fu is a scoundrel! All of Beijing is talking about it.
And the whole family set off nitpicking the playing of a man whom they had never seen or heard, and said: - That villain Jian-Fu! - Scoundrel Jian-Fu! - Swindler Jian-Fu!
The Emperor, returning to the palace, was beside himself with amazement.
- What could all of this mean?
And, despite the late hour, he ordered that Jian-Fu be found right away and brought to him.
The harper was found and immediately brought to the Emperor.
- Hello, Jian-Fu! - said the Emperor. - Do you know that all of Beijing is scolding no one but you?
- I know, Heavenly Wisdom! - replied Jian-Fu as he bowed low.
- All they do is nitpick your playing! They pick on such trifles that it's simply awful. And they scold you for such little things through and through!
- I know, Heavenly Wisdom! - babbled Jian-Fu.
- So why is this happening?
- This happens, it turns out, for a very simple reason! - answered Jian-Fu. They are not allowed to discuss anything except for my harp-playing. So they singled me out for nitpicking and scolding.
The Emperor put his finger to his forehead and said:
-- A!
And he banned all discussion of Jian-Fu's playing as well. The Emperor Jin-La-O was a just Emperor.

"The Story of One Wetnurse."

Lately, I found myself unable to resist the temptation to translate this very pertinent classic to English. If you, reader, know of a better translation, do not hesitate to write in. And so, here goes:


"The Story of One Wetnurse."
by Vlas Mikhailovich Doroshevich (1864--1922).


Emperor Jing-Li-O, nicknamed Hao-Tu-Li-Chi-San-He-Nun, which means Justice Itself, once woke up feeling unwell.

- The Emperor has taken ill!

Rumours spread through the palace. Many stopped bowing to the first minister. The court poet wrote a welcoming ode to the crown prince.

The best doctors, pale with fear, bowed and apologetic, examined the Emperor, whispered in horror, and the chief doctor, falling at his feet, exclaimed:

- Permit me to tell the whole truth, oh consolation of humanity?

- Speak! - the Emperor allowed.

- Of course, you are the Son of Heaven! - said the chief doctor. - But by your unspeakable mercy, you sometimes come down to the people and allow yourself to contract such diseases as ordinary mortals may suffer. Today is the day of your greatest indulgence: your stomach is simply upset.

The Emperor was rather surprised:

- From what? Before bed, I drank nothing but my wetnurse's milk. Three hundred and sixty months have I reigned, and I nourish myself, as befits me, with the milk of a wetnurse. I have changed three hundred and sixty wetnurses, and nothing like this has ever happened to me. Who overfed my wetnurse, and with what?

The strictest investigation was immediately carried out - but it turned out that the wetnurse had eaten only the finest dishes, and that, moreover, they had been given to her in moderation.

- It could be that she fell ill naturally. What were those who chose her for me thinking? - the Emperor was angry. - Execute the culprits.

The culprits were executed, but according to the most thorough investigation, it turned out that they were blameless: the wetnurse was completely healthy.

Then the Emperor ordered his wetnurse to be brought to him.

- Why did your milk spoil? He asked sternly.

- Son of Heaven, Benefactor of the Universe. Justice Itself, - answered the trembling wetnurse, - you are seeking the truth not where it is hidden. Nobody overfed me and I myself did not overeat. Likewise, I have never been ill in my life. My milk has spoiled because I think about everything that is going on at home.

- What is going on at your home? - asked the Emperor.

- I come from the province of Pe-Chi-Li, which you saw it fit to to entrust to the mandarin Ki-Ni. He does terrible things, oh Joy of the Universe. He sold our house and took the money for himself, because we could not give him the bribe he demanded. He took my sister as his concubine, and beheaded her husband so that he would not complain. In addition, he executed my father and imprisoned my mother. In general, he treated us the way he treats everyone. When I remember all of this, I cry - and that's why my milk spoils.

The Emperor was terribly angry.

- Summon all of my advisers to me!

And when they appeared, he strictly ordered:

- Find me an honest man now.

They found one.

And the Emperor said to him:

- Mandarin Ki-Ni, to whom I entrusted governing the province of Pe-Chi-Li, does such things that even my wetnurse's milk has spoiled. Go there now, carry out the most severe investigation in my name and report to me. And there is to be no concealment, you will neither add nor take away - so that the truth reflects in your words, like the moon appears in a calm, sleeping lake. You know, on a quiet night, when you look and cannot make out: where is the real moon and where is the reflection - in the lake or in the sky? Go forth now.

The honest man set out at once with a hundred of the most skilled investigators.

The mandarin, terrified to death, seeing that his position was unenviable, offered the messenger a hefty bribe.

But the honest man, having been sent by the Emperor himself, did not dare to take it.

The moon in heaven went through three changes, and the honest man and his hundred investigators were still unraveling the matter. Finally, when the fourth moon was nearing its end, the honest man came to the Emperor, fell at his feet and asked:

- Is it the whole truth that I shall tell, Justice Itself?

- All of it! - ordered the Emperor.

- If there is in the whole world, which belongs to you and to no one else, a corner worthy of tears, then it is the province of Pe-Chi-Li, the Son of Heaven. Truly, it could bring tears to the eyes of the most malevolent dragon. All over the province, everyone begs for alms, and there is no one to give alms, because everyone is begging for them. Houses are ravaged, rice fields lie fallow. And all of this is not because the inhabitants are uncommonly lazy, but because the Ki-Ni mandarin takes everything from them, no matter what they earn. There is no justice in the courts, and only he who gives the most to the mandarin is in the right. As for good morals, they have forgotten about them entirely. Just as soon as Ki-Ni lays his eyes on a pretty girl, he takes her for himself and away from her father and mother. And not only girls - he takes even married women.

- How could this be! - exclaimed the Emperor.

- Not only the moon, but the sun could vouch for the truth of my words! - replied the honest man. - Everything I have spoken is true. The ornament of your power, the cream of your provinces - the province of Pe-Chi-Li is dying!

The Emperor took his head in his hands, showing deep sorrow.

- I'll have to think about what to do! I'll have to think!

He ordered all of his courtiers to wait in the great hall, while he himself, retiring to his chamber, walked from corner to corner in contemplation. The whole day went by. Before nightfall, the Emperor appeared before his courtiers, solemnly sat down under the canopy and, when all of them fell face down to the ground, announced:

- The province of Pe-Chi-Li is in a terrible state, and therefore We proclaim: never again shall wetnurses be taken from there for the Emperor.

And ever since then, they have never once taken a wetnurse from the province of Pe-Chi-Li for the Emperor.

"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! There is now a prototype! (Thank you, thimbronion!) Or even entirely complete.

Edit: There is a working draft of v. 0xFD. (Note: it may change without warning!)

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!
This version is obsolete! Please read v. 0xFD !

Click here for a printer-friendly version of this text.


"Pest" v. 0xFF.

What follows is a long-promised detailed specification of a DDOS-proof, CPU-inexpensive, ciphered-authenticated peer-to-peer communication protocol.

I would like to thank Thimbronion for implementing a large subset of this spec already despite not having seen it yet!

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.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!
This version is obsolete! Please read v. 0xFE !

Edit: click here for a printer-friendly version of this text.

Repair of sabotaged mathematical glyphs in certain Linux distros.

Recently, I received a tip that some Linux users saw rubbish in place of certain Unicode glyphs appearing in the FFA series (in particular, in Ch. 14.)

If the following two rows of symbols do not appear recognizably-identical in your WWW browser:


← → ⇠ ⇢ ⌊ ⌋

utf test

... the following fix is likely to cure:


... on Gentoo-derived Linuxen:

emerge media-fonts/dejavu


... on Arch-derived Linuxen:

pacman -S ttf-dejavu


Anyone who has witnessed the above dysfunction, or knows the details of when and why this astonishing breakage was introduced, the systems affected, the identities of the perpetrators, or anything else pertinent -- is invited to write in.

Defeating Vendor Lock-Ins: "Liebert GXT4."

Certain double-conversion UPS units by Liebert (in my case -- a GXT4-2000RT120) appear to contain a boobytrap whereby off-the-shelf (needs two 12v/80mm) high-efficiency/quiet fans will not operate -- the boot will abort with a Fan Out of Order error.

The pill: install a 100 ohm wirewound resistor in parallel with the front fan connector (on each side, will need to snip off the original plug and solder to a standard PC 4-pin extender.) This defeats the current sensor which expects to see the original (~0.4A max) fans; but not to the extent where the death of one or both of the new fans will fail to trigger the alarm.

The 2021 Rack.

Thank you, 2020 Rack Service subscribers! I would like to wish all of you another great year of hygienic Linux on high-quality non-Fritzed iron!

The 2021 service agreement is identical to the 2020 one. With the unfortunate exception that Deedbot Wallet is closing down on Dec. 25, 2020, and hence will no longer be accepted as payment starting at Dec. 23, 2020. On that day and henceforth, all subscribers will need to use traditional Bitcoin.

Any and all communication concerning the details of a payment, is to take place strictly via PGP. And please remember to clearsign each message prior to encrypting; and to verify the signature on any reply of mine after decryption.

Additionally, the upstream monthly cost has increased by 20 $, and this increase is reflected in the 2021 Price Calculator.

Since the start of the service in November 2019, there were exactly four days during which outages exceeding five minutes in length were reported. All four were attributable to malfunctions in upstream equipment.

All affected subscribers have been compensated, per the agreed-upon scheme (one day of pro-rated service per each such day; under the condition that a subscriber must publicly report the outage.) This is reflected in the table below.

Expiration dates of all current paid subscriptions are listed below (in strictly chronological order, and without identifying the subscriber) :

Subscriber Iron Effective Through
A Dulap-128-4TB 22 Dec 2020
B RK-256 10 Feb 2021
C Dulap-128-4TB 13 Feb 2021
D Colo (1U; 100W; 1 IP) 03 Apr 2021
E APU3-2TB 16 Aug 2021
F RK-128 21 Nov 2021

If you are a subscriber, you should be able to easily find yourself in this list.

"Finite Field Arithmetic." Chapter 21A-Ter: Fix for a False Alarm in Ch.14; "Litmus" Errata.

This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical "Open Sores" abomination, in that -- rather than trusting the author blindly with their lives -- prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.


You will need:

Add the above vpatches and seals to your V-set, and press to ffa_ch21a_ter_ch14_ch20_errata.kv.vpatch.

You should end up with the same directory structure as previously.

As of Chapter 21A-Ter, the versions of Peh and FFA are 250 and 199, respectively.

Now compile Peh:

cd ffacalc
gprbuild

But do not run it quite yet.


This Chapter concerns fixes for several flaws recently reported by a careful Finnish reader known only as cgra. Thank you, cgra!

Let's begin with his first find: a false alarm bug in Chapter 14B's implementation of Barrett's Modular Reduction. (Note that the proofs given in Ch.14A and Ch.14A-Bis presently stand; the bug exists strictly in the Ada program.)

Recall Step 5 of the algorithm given in Ch.14A :

For each new input X, to compute the reduction R := X mod M:

  1. Xs := X >> JM
  2. Z  := Xs × BM
  3. Zs := Z >> SM
  4. Q  := Zs × M
  5. R  := X - Q
  6. R  := R - M, C := Borrow
  7. R  := R + (M × C)
  8. R  := R - M, C := Borrow
  9. R  := R + (M × C)
  10. R  := R - (R × DM)
  11. R is now equal to X mod M.

... and its optimization, as suggested by the physical bounds proof of Ch.14A-Bis :

2WM
Ignore X
WM - L WM + L
2WM
- Ignore Q
WM - L WM + L
= R
WM + L

... and finally, its implementation in Chapter 14B :

fz_barr.adb:

   -- Reduce X using the given precomputed Barrettoid.
   procedure FZ_Barrett_Reduce(X          : in     FZ;
                               Bar        : in     Barretoid;
                               XReduced   : in out FZ) is
 
   ..............................
 
      -- R is made one Word longer than Modulus (see proof re: why)
      Rl      : constant Indices := Ml + 1;
 
   ..............................
 
      -- Barring cosmic ray, no underflow can take place in (4) and (5)
      NoCarry : WZeroOrDie := 0;
 
   begin
 
   ..............................
 
      -- (5) R  := X - Q (we only need Rl-sized segments of X and Q here)
      FZ_Sub(X => X(1 .. Rl), Y => Q(1 .. Rl),
             Difference => R, Underflow => NoCarry);
 
   ..............................

Even though we had demonstrated that Q ≤ X, the prohibition of a nonzero subtraction borrow in (5) is fallacious.

To illustrate: this Tape, on a 256-bit run of Peh :

  .1 .FF LS .1 .3 MX # QY

... will not print the expected answer to the given modular exponentiation, i.e.:

  0000000000000000000000000000000000000000000000000000000000000002

... with a Verdict of Yes; but instead will print nothing, and yield a Verdict of EGGOG. Specifically, Peh will halt at (5) via a Constraint_Error (range check failed), when the range of NoCarry's WZeroOrDie type is violated by an assignment of 1.

This is because -- early in this modular exponentiation's sequence of Barrett reductions -- and immediately prior to (5) :

X == 0x40000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 
Q == 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

... but what will be actually computed in (5) is X(1 .. Rl) - Q(1 .. Rl), i.e.:

  0x00000000000000000000000000000000000000000000000000000000000000000000000000000000 -
  0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
 
=
 
  1 (Underflow == 1)

... that is, the borrow bit is legitimately 1, in this and in a number of other readily-constructed cases. The constraints we have demonstrated for X, Q, and R do not imply that a borrow will never occur in the subtraction at (5). Therefore, the intended cosmic ray detector is strictly a source of false alarms, and we will remove it:

fz_barr.adb:

   -- Reduce X using the given precomputed Barrettoid.
   procedure FZ_Barrett_Reduce(X          : in     FZ;
                               Bar        : in     Barretoid;
                               XReduced   : in out FZ) is
 
   ..............................
 
      -- Borrow from Subtraction in (5) is meaningless, and is discarded
      IgnoreC : WBool;
      pragma Unreferenced(IgnoreC);
 
   begin
 
   ..............................
 
      -- (5) R  := X - Q (we only need Rl-sized segments of X and Q here)
      FZ_Sub(X => X(1 .. Rl), Y => Q(1 .. Rl),
             Difference => R, Underflow => IgnoreC); -- Borrow is discarded
 
   ..............................

... and that's it.


Cgra's second find concerned the Ch.20 demo script, Litmus. He had discovered that two mutually-canceling bugs exist in the program. Specifically, in :

litmus.sh:

 
..................
 
# Hashed Section Length
get_sig_bytes 2
turd+=$r
hex_to_int
sig_hashed_len=$r
 
# Hashed Section (typically: timestamp)
get_sig_bytes $sig_hashed_len
turd+=$r
sig_hashed=$r
 
# Unhashed Section Length
get_sig_bytes 1
hex_to_int
sig_unhashed_len=$r
 
# Unhashed Section (discard)
get_sig_bytes $sig_unhashed_len
 
..................
..................
 
# RSA Packet Length (how many bytes to read)
get_sig_bytes 1
hex_to_int
rsa_packet_len=$r
 
# The RSA Packet itself
get_sig_bytes $rsa_packet_len
rsa_packet=$r
 
# Digest Prefix (2 bytes)
get_sig_bytes 2
digest_prefix=$r
 
..................

... the Unhashed Section Length is erroneously treated as a 1-byte field, whereas in reality the GPG format gives 2 bytes. The script only worked (on all inputs tested to date) on account of the presence of the superfluous routine (RSA Packet reader, which remained from an early version of the demo!); in all of the test cases to date, the second byte of the Unhashed Section Length (and the unhashed section in its entirety, for so long as it does not exceed 255 bytes in length -- which it appears to never do) are consumed by get_sig_bytes $rsa_packet_len.

I am almost pleased that I had made this mistake; it is in fact a better illustration of programs which operate correctly despite erroneous logic -- as well as the unsuitability of shell script as a language for nontrivial tasks -- than anything I could readily unearth in the open literature.

And the fix is readily obvious :

 
..................
 
# Hashed Section Length
get_sig_bytes 2
turd+=$r
hex_to_int
sig_hashed_len=$r
 
# Hashed Section (typically: timestamp)
get_sig_bytes $sig_hashed_len
turd+=$r
sig_hashed=$r
 
# Unhashed Section Length
get_sig_bytes 2
hex_to_int
sig_unhashed_len=$r
 
# Unhashed Section (discard)
get_sig_bytes $sig_unhashed_len
 
..................
..................
 
# Digest Prefix (2 bytes)
get_sig_bytes 2
digest_prefix=$r
 
..................

I also incorporated cgra's earlier suggestion regarding error checking. Thank you again, cgra!

And that's it for Litmus, presently.


~ The next Chapter, 21B, will (yes!) continue the Extended-GCD sequence of Chapter 21A. ~