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