rune23 proposal

Outline

This is a proposal to create a standard sequence of bits of pure gibberish. The name is rune23, which stands for a reference uniform experiment with 2^23 outcomes. The result of the experiment is recorded in a 1 MiB binary file. The goal is to conduct the experiment in a way that convinces everyone, even the parties not taking part in the process, that there was no practical possibility for anyone to tamper with the outcome.

It may be possible to achieve a comparable result by conducting a physical experiment, but that would require a very careful and expensive monitoring. Suppose, for example, that we use physical random number generators (RNG) to generate a sequence. If we are to convince everyone that the outcome is fair, we would have to use several different types of RNGs, and have several independent, unbiased experts to conduct an in-depth review of the RNGs (both hardware and software) and the computer system used to interact with the RNG. The entire system would have to be physically guarded the entire time to prevent tampering. Many qualified, yet independent witnesses would have to be physically present on site throughout the generation process, who would be able to monitor the process and obtain exact copies of the sequence as soon as it is produced. Even then, it would still be quite possible for the system to be defective in principle, broken, or tampered with, resulting in a non-uniform, or worse yet, a doctored outcome. It also requires a very high level of coordination, both spatial and temporal, from all participants, which increases the risk of conspiracy.

Instead, we propose a process where a number of people with requisite technical knowledge generate their "drafts" of the sequence in private, and then combine them into the final sequence in a pre-determined way. Encryption is used to ensure that no one can change their choice of the sequence after they've seen other entries. This process won't fail unless all participants make fatal mistakes, or all collude (total conspiracy), or all have their personal security breached by a single hostile entity. If at least one participant submits a fair entry securely, then the outcome will be fair. And if at least some of the participants have reputations for their expertise in encryption and security, then the result will be highly convincing. Even assuming a moderate amount of collusion, the resulting bit sequence will be an outcome of an extremely fair random experiment, and believably so to all but the total conspiracy nuts.

Conventions

Pad is a sequence of bits. There are 8 bits in a byte.

Process is the sequence of steps described within this document, which every participant must eventually follow, and which culminates in the creation of rune23.

Host refers to Ivan Zaigralin (a.k.a. melikamp). The host does not play a special role in the process, other than volunteering to perform certain clerical duties, like hosting all of the involved files and serving as a communication hub. The host may or may not be a participant. Each participant is free to communicate with any other participant. We hope that they won't collude, but they won't be disqualified for it, since the process is designed to be highly resistant to partial collusion.

Process

Qualification

Each participant must have an email address and agree to share it with all of the participants. Each participant must be willing to have his or her full legal name and professional affiliation (if any) listed in the final product, which will be published and placed in the Public Domain. Each participant must have tar 1.2.6 or later, gpg 1.4.11 or later, and a solid understanding of using the latter for creation of public/private key pairs, signing files with private keys, verifying digital signatures, and encrypting files with symmetric ciphers.

Signing all emails with gpg and verifying others' signed emails is encouraged, but not required.

Access to and familiarity with a UNIX-like OS such as a GNU/Linux distribution is assumed in examples, but not required.

Preparing Entries

1. Each participant contacts the host with an agreement to participate in the process and submits a personal email address, which the host will share with all participants, but keep private otherwise. The personal email address will be used for communication between the participants, so it is not good to assume that it will remain private. All other email addresses the host obtains from the participants will be kept private.
2. The host creates a mailing list with all of the personal addresses and from now on publishes either by emailing to the list or by uploading to a public HTTP server known to and accessible by all participants. While it is not expected, any and every participant can pretend to be the host, and whatever they share with all participants is considered to be published for the purposes of this process. The host publishes the mailing list.
3. Each participant settles on a public/private key pair which we will call a mail key pair, and it will be used for authentication while exchanging correspondence and making digital signatures. The private mail key is intended to remain private, and we recommend that participants use one of their existing key pairs for this purpose, although generating a new one is OK.
4. Each participant generates a handle (nickname) for naming files. It must be an ASCII string with at most 32 characters and should not contain any symbols but lowercase Latin letters and the minus sign. We strongly recommend that the lower case versions of participant's first and last names are used, unless it makes the handle too long, or the name cannot be spelled correctly, or it collides with another participant's name. For example, the host's handle would be "ivan-zaigralin".
5. Each participant emails his or her mail public key and handle to the host, who publishes them. Each participant then makes reasonable attempts to authenticate all other participants.
6. Each participant generates the entry passphrase for use with a symmetric cipher in gpg. It must be an ASCII string with 128 characters or more, and it must be acceptable as a gpg passphrase. We strongly recommend using a good random source for this one.
7. Each participant generates a 0x100000 = 1048576 byte (1 MiB) entry pad. rune23 will be the XOR of as many entry pads as possible (as explained in the Revelation), optimally all of them. We strongly recommend to make the generating experiment as random as you can afford. At the same time, we cannot question your decision to do something silly, like submit a pad of zeroes (although we will question your judgment). No pad can be disqualified because of its content.
   The following is just a suggestion for the kind of experiment we expect you to conduct. We encourage the use of pseudo-random generators, as long as it's not the only source. Spend some time interacting with the physical world: take pictures, record sound or video. If you have access to fancy expensive RNGs, use them. In other words, use the world to conduct a number of independent, if not always uniform experiments. XOR the results.
8. Each participant must take all reasonable steps to keep the entry pad and passphrase private until the Revelation stage. If either the pad or the passphrase leaks before the process calls for it, the corresponding entry is disqualified. Consider keeping them on a non-networked system in a physical location with restricted access.
9. Each participant uses gpg and a built-in symmetric cipher of choice (as long as it is present in gpg 1.4.11) to encrypt the entry pad with the entry passphrase. Each participant signs the encrypted entry pad with the mail key, and transmits the encrypted pad and its signature to the host. The host introduces a naming scheme for submitted files, based on the handles.
10. The host creates megapad.tar, the megapad, which is a tar archive containing encrypted entries, corresponding signatures, and a text file with the Entry Statement. The Entry Statement contains the description of the process, and additionally says (in so many words) that the person who signed the megapad went through the process up until this point and has sufficient reasons to believe that his or her entry is unknown to other participants, and that the encrypted entries in the megapad were created by the corresponding participants. The host publishes the megapad.
11. Each participant, if satisfied, signs the megapad and emails the signature to the host. It is essential for each participant to check that their entry is intact and that all other entries are signed correctly, before signing the megapad. If a participant fails to get the megapad signature published before 2012-??-??, then his or her entry is disqualified and we go to the previous step.
12. The host publishes all of the megapad signatures. After this step, the megapad is frozen: no new entries can be made, and none of the entries present in the megapad may be excluded from the process.
13. Based on the number of entries, participants reach a consensus about the threshold, the minimal number of participants required to complete the process (as explained in the Revelation).

Revelation

1. The host publishes a solicitation for entry passphrases and publishes them as they arrive. On the date 2012-??-?? the host freezes the list of revealed entry passphrases. Only these and the corresponding entries will be used in rune23. If their number is below the threshold, the process fails. rune23 is now determined.
   It may be argued that the host appears to be in a position to game rune23 by applying the pads selectively, but in practice it's not likely to be possible. Participants may reveal entry passphrases to each other at this time, and so the revelation process is transparent to all. The only probable reason for an entry to be disqualified at this point must be of a sad nature. Also, without disqualifying entries here we can never hope to scale to any appreciable number of participants. So it is almost guaranteed that almost all (or a very large number of) entries will make it, and if only one fair entry makes it, then the purpose will be achieved.
2. Each participant decrypts the contents of the megapad and XORs the admitted entries to obtain rune23. If an entry is too short, it is padded with zeroes in the end. If too long, an initial segment is taken. Each participant signs rune23 with his or her mail key and emails the host the signature. The host publishes signatures as they arrive. The process stalls until the number of published signatures reaches the threshold. This step adds very little assurance, since gaming rune23 is practically impossible after the megapad and its signatures are published. It is done more for the sake of producing a well-authenticated package which reminds users about the secure nature of the creation process.
3. The host creates and publishes rune23.tar, a tar archive consisting of rune23; all of its published signatures (more can be added later); the list of all participants with their full legal names, handles, professional affiliations (if any), personal emails (if desired), and public mail keys; the description of the process; and the Public Domain dedication of behalf of all participants.