Upfront warning: this is a crazy idea that I literally have to get out of my head or risk neurological damage. Here it goes.
First, a bit of background info: over the past couple of years, Chrome has been accreting increasingly powerful APIs for interacting with the outside world, and recently it hit a critical point where it's possible to write a 'operating system' in it. Of particular interest:
With creative use of these APIs, we can build a microkernel-like OS, using the filesystem API for local storage, the socket API for networking, and the extension API for IPC among 'apps' (either signal-based or channel-based, depending on what we want). Since Chrome's IPC layer (at present) only allows extension IDs as transport-layer addresses, we abstract these away behind a 'name' service, whose role is to map well-known short names (like 'fs') to the authoritative extensions that happen to be running and providing those services. Necessarily, the 'name' service has to run at a well-known extension ID for bootstrapping purposes, but so it goes.
Here's what a design for such a system might look like, broken down into major components, with each component a separate extension (and hence separated strongly by the extension boundary, with communication only via IPC):
On top of these, you could imagine the following services existing:
Digging a little deeper into how these work: for shell, one could imagine a meta-protocol (presented over IPC) for apps that can be used interactively: a way to 'start a session' of them (possibly with args), then IPC methods and signals for input and output. Thus, one could imagine a remote-login flow going like this:
It is important to note that the filesystem is for data only, since 'executables' (threads of javascript code execution) can only come from extensions; therefore, the mechanism shell uses to look up programs to invoke should involve asking name for extensions providing that name and then communicating with them using the 'session' meta-protocol.
This post is going to look at how one can compose cryptographic primitives to produce a protocol with desired properties. The two properties we're most often concerned with as protocol designers are integrity and confidentiality; integrity means data transferred using the protocol has not been tampered with, and confidentiality means data transferred using the protocol has not been read by anyone other than the parties doing the protocol.
First, we'll introduce the cryptographic cast: Alice and Bob are the parties doing the protocol (for the purposes of this post, which will only deal with two-person protocols). Eve is an eavesdropper; Eve can read any data sent between Alice and Bob, but cannot modify it. Mallory is a man (or woman) in the middle, who can both read any data sent between the participants, and modify it arbitrarily. Both Mallory and Eve can attack the confidentiality provided by a protocol, but only Mallory can attack its integrity.
Let's set the scene: Alice and Bob are in physically different places, connected by a network link upon which Eve can eavesdrop and which Mallory can modify. Alice and Bob each has a computer which they can trust to run protocols honestly and store any keys securely (this is often an unrealistic assumption in real life, but this post is about crypto, not software/hardware security). Alice and Bob wish to communicate sensitive data to each other.
A bit of terminology: we're going to write 'A -> B: x' to indicate that A sends x to B, and we're going to usually refer to secret messages being sent as m0, m1, and so on. We'll split our protocols into three phases: the setup phase, the working phase, and the teardown phase. When we first open a connection, we start in the setup phase. Once we've moved from the setup phase to the working phase, we can send messages between the participants. Once we move into the teardown phase, we're done sending messages. The working phase can be written as a pair of functions, which wrap a message to send on the wire and unwrap it after receipt. We'll also use "||" to indicate concatenation, "^" for exclusive-or, and "**" for exponentiation.
Let's first look at the 'null' protocol (that is, the protocol that just sends data in the clear). Eve can easily read the messages going past, and Mallory can both read them and edit them, with such editing being undetectable to the protocol participants, so the null protocol has neither confidentiality nor integrity. In fact, the null protocol is vulnerable to purely accidental data corruption by intermediaries, which Alice and Bob also have no way to detect. We can write the null protocol like this:
null_setup() { }
null_teardown() { }
null_wrap(m) {
return m
}
null_unwrap(m) {
return m
}
Okay, how about if we include the hash h(m0) with m0 when we send it? Now the protocol looks like this:
hash_setup() { }
hash_teardown() { }
hash_wrap(m) {
return m || h(m)
}
hash_unwrap(m || h?) {
if (h(m) == h?)
return m
else
error "Hash mismatch!"
}
Let's suppose that you have a block cipher (E,D) which you believe is strong, but whose key length is worryingly short, and let's suppose that you're in a regime that restricts the ability of its citizens to communicate securely, so you can't use a cipher with a key larger than a certain size. How can you make brute-force attacks more difficult while keeping the key size the same?
One property of most block ciphers (and block cipher modes) is that one can decrypt a single block of ciphertext to get the corresponding single block of plaintext - for example, in the CBC mode, the ciphertext block C_i is given by:
C_{i + 1} = E(K, P_{i + 1} xor C_i) C_{-1} = IV
Since the attacker already has access to C_i and C_{i + 1}, they can decrypt P_{i + 1} in isolation - they only need to do one block cipher operation per key K' they try (namely D(K', C_{i + 1}), and they can test each attempt by xoring the result with C_i and seeing if the resulting plaintext looks sensible.
An All-or-Nothing Transform (AONT) is a way, using our existing block cipher, to encrypt a message such that in order to recover any of the plaintext, one must decrypt all of the ciphertext; the AONT makes the decryption process "all-or-nothing". This does nothing to strengthen the block cipher itself, but it makes attacks against real messages harder, because if a message is n blocks long, an attacker must perform n decryption operations per key they wish to try, instead of just one operation.
Here's an example of an all-or-nothing transform: Let's suppose we have a message m_0, m_1, ..., m_n, and a shared secret key K, and a globally known key K_0. First, let's generate a random key K', and then let m'_i = m_i xor E(K', i). We call m' the pseudomessage. Next, we'll define a function h: h(i) = E(K_0, m'_i xor i), and append a block m'_{n + 1} to the pseudomessage: m'_{n + 1} = K' xor h(0) xor h(1) xor ... xor h(n). Now the actual ciphertext c_i we send is given by c_i = E(K, m'_i). To decrypt, compute all blocks of m', compute h of each of them, xor them together to get K', compute E(K', i) for each i and xor with m' to get m.
Let's look at why this is all-or-nothing, and then we'll look at the exact constructions of h and m'. Let's suppose an attacker is attempting to brute-force K, and I'll make a handwavy argument that they'd have to possess all of m' in order to decrypt any of m. Let's be pessimistic, and suppose that an attacker has trial decryptions of all the blocks of m' except for some block m'_i. Without m'_i, they can't compute h(i), and therefore there are two unknowns when they solve for K': K' = h(0) xor h(1) xor ... xor h(i) xor ... xor h(n), and both K' and h(i) are unknown. This argues that they need all of the blocks of m' to deduce K'. Suppose the attacker instead wants to brute-force K': the only place K' appears is in m'_i = m_i xor E(K', i), so if an attacker wants to brute-force K', they need some m'_i. However, they're out of luck there - there's actually no way to distinguish a valid m'_i from any other value, so they have to perform a nested brute-force attack: first they pick a key Ka to try, produce a putative ma_i from it for some i, and _then_ have to begin brute-forcing for K' - and if their Ka is wrong, they'll have to go back and search a different Ka.
Let's take a look at h and m'. We're using h to ensure that individual blocks of m' can't be moved around, deleted, or duplicated; any change to m' will yield a vastly different K', so in this instance h(0) xor h(1) xor ... xor h(n) serves as a hash function of m' (see, it's not just confusingly-named!). What about m' - what's up with xoring in E(K', i)? Essentially, we're using E to generate a keystream of any length we need from a single key; you might recognize a similar construction from the CTR block cipher mode.
This example of an AONT comes from a 1997 paper by Ron Rivest, but a more widely-used example is in the OAEP padding scheme. OAEP is a way of padding RSA to avoid certain attacks which deserve a separate post, but it contains an all-or-nothing transform: given an encryption function E from k bits to k bits, k0 a 'secure' number of bits, and n = k - k0 the message length. We also need a stretching function G from k0-bit strings to n-bit strings and a hash function H from n-bit strings to k0-bit strings. Choose a random k0-bit string r; now we define our encryption transform T: T(x) = E((x xor G(r)) || (r xor H(x xor G(r)))), and the decryption transform T' the obvious way (decrypt, extract (x xor G(r)), compute H(x xor G(r)), extract r from (r xor H(x xor G(r))), compute G(r), extract x). We can see why this is all-or-nothing: unless one has the entirety of (x xor G(r)), one can't compute H(x xor G(r)), and unless one has the entirety of (r xor H(x xor G(r)), one can't compute r. Therefore, we need to decrypt the entire message to test a decryption.
For an example of how effective this can be: with a 128-bit block, if we encrypt a 16MB message with an AONT, an attacker has to perform 2**20 decryptions to test a single key, so a 64-bit key space requires 2**84 decryptions to brute-force.
The Guy Fawkes Protocol is a cryptographic protocol that provides authentication of a stream of data (of unknown and potentially unbounded size) from authentication of a single small secret. This is really handy for signing streams of data, like video or chat traffic (currently such traffic is often authenticated using an HMAC keyed with a shared secret, but this allows either participant to forge parts of the exchange). If you've already read and understood the paper, this won't be terribly novel.
The original Guy Fawkes protocol is designed to authenticate a stream of messages, each of which we wish to commit to in advance before revealing it, and works like this: if you wish to authenticate a message Mi + 1, we choose a random Xi + 1, then publish Zi + 1 = h(Mi + 1, h(Xi + 1), Xi). Publishing Zi + 1 serves as an authenticated commitment to the contents of Mi + 1. Now we can, in the future, reveal Mi + 1, h(Xi + 1), and Xi, which will provably correspond to the previously-published Zi + 1. Note that the original h(X-1) has to be authenticated by some out-of-band mechanism like a conventional signature with a long-lived key.
Let's look at bit at how this protocol actually provides security. We can look at it inductively, since the protocol is inductive. Since h(X-1) was authenticated out of band, when we want to send M0, we first commit to Z0 = h(M0, h(X0), X-1) then announce Z0. At this point, nobody can tell whether the message is authentic. When we wish to make M0 itself public, we release M0, h(X0), and X-1. Anyone can now verify that this tuple corresponds to our prior committment, and nobody can use the now-revealed X-1 to falsely authenticate their M'0 because it will not match the committed Z0. Furthermore, the fact that we include h(X0) in the message means that an attacker not in possession of X0 cannot produce a false Z'1, since they would have to include X0 in it.
The committment part of this protocol is important: if we transmit Zi alongside the values of which it is a hash, we open ourselves up to an easy forgery attack, because we have revealed all the components of Zi, which makes it easy to construct a Z'i with M'i and replace our outgoing Zi with it. However, what we need is not necessarily a public committment scheme, but rather a strong ordering of events which the verifier can verify (i.e., to prove that Zi was committed to before its contents were revealed). If we're using the protocol for a two-party authenticated session, we already have that, because messages flowing between the two parties arrive in some order which is apparent to the receiver. This means we can handily use the Guy Fawkes protocol for very cheap (as cheap as HMAC) stream authentication between two parties.
As it is, the protocol is repudiable; looking at an exchange after the fact (i.e., without any proof of the order of message exchanges), an observer cannot be sure that a transaction log is authentic. You can see why this is: when we're done with the protocol, all of the secrets used in signing messages have been revealed, since every Xi is included with message Mi + 1, except for the very last Xi, which is committed to as part of the last Zi but never revealed.
We can also add non-repudiation to the protocol pretty easily by remembering the last secret (of which only the hash is ever revealed online) and revealing it if need be; this proves that the revealer corresponds to the transaction participant. We could also e.g. reveal the hash of the entire session to the public, or sign same with our long-term key.
Someone cleverer than me has previously pointed out that one can use something like Bitcoin to do this protocol; one can include hashes in certain blocks, and the messages in subsequent blocks; since the subsequent blocks include the hashes of their ancestors, this proves an ordering between release of Zi and the data of which it is a hash. Implementing this might be an interesting exercise.
Someone please remind me to post about Shamir's Scheme; I laid a bit of the groundwork in an earlier post and I need to finish it up.
I've been thinking about the following design problem lately: suppose you have a service (something like a peer-to-peer version of dropbox or whatever). You need a way for nodes run by a particular user to find each other, for which a centralized service is ideal, assuming your users don't want to remember and type in IP addresses. You'd ideally like for there to be as little trust in this centralized service as possible, but you'd also like for users not to have to manage keys - ideally a username and passphrase pair should do the trick. Let's call this service the Node Naming Service, or NNS. The NNS maintains two kinds of data for users: a set of subsidiary keys which are allowed to insert data, and a set of namespaces, one per subsidiary key.
So let's step back a little bit and look at what we're doing: we're maintaining some data for the user on a server somewhere. That data should be updateable and fetchable by any node configured to do so by the user. We're going to need some kind of digital signature to achieve that. We only have one secret to start off with, which is the user's passphrase. From this we want to produce a long-lived keypair, which we can do by (for example) using PBKDF2 with some large number of iterations applied to the (username, domain, password) tuple, then treating the result as an Ed25519 private key Kpriv (from which the corresponding public key Kpub can be computed). This gives us a long-lived keypair that we can regenerate as desired (although we only need it once per node setup, plus once when we sign up for NNS). When we sign up for NNS, we provide the server with (username, domain, Kpub), which we can use to authenticate to it in future.
Importantly, keys generated this way are not very strong. User passphrases are generally weak, so it is important that we use a large number of PBKDF2 iterations; the inclusion of the username and domain in the PBKDF2 inputs should serve to frustrate rainbow-table attacks on common passphrases.
Once we've signed up to NNS, NNS will only accept inserts of data for username@domain when it is signed by [a key signed by] Kpub, which we provided it at signup time. When we want to configure a node, we type our username@domain and our passphrase into the node software (only once, at startup, and it never keeps this information); the node software recomputes Kpriv and Kpub, paying the PBKDF2 costs again, then generates a random long-lived keypair (Knpriv, Knpub) for itself, signs a request to add Knpub as a subsidiary key with Kpriv, forgets Kpriv and the user's passhrase, then sends the signed add request to NNS. NNS checks that the request is signed with the private key for Kpub and adds the key, creating a new namespace for it. When the node wants to insert data into the namespace, it signs it with Knpriv and sends it to NNS, which inserts it into the namespace for Knpub.
A little more formally, the first-time setup goes like this, with S(x,y) indicating data x signed with private key y.
Setting up a new node looks like this:
Inserting node data v at a key k looks like this:
When fetching data v at a key k for some other Knpub', we can first check that Knpub' was signed by Kpub, which we remember from node installation time; the server remembered the signed insert from when Knpub' was installed and can give it back to us. We can then fetch data out of the Knpub' namespace, all of which is signed as key/value pairs; the server can send us S((k, v), Knpriv'), which suffices to prove to us that Knpub'/k = v was inserted by a node with Knpriv'.
Okay, now we have a namespaced key-value store with authenticated inserts (to the server) and authenticated data (to anyone with the public key for a particular namespace). This is enough to let us discover other nodes if there's a way for us (presenting proof that our node key Knpub was originally signed by the Kpriv of some Kpub) to find all other namespaces inserted signed by that same Kpriv. In fact, we don't really need two separate concepts here; we could just give a namespace to the original Kpub, and store inside it references to all the subsidiary Knpubs as needed.
Unfortunately it's late and I must go; I apologize for the stream-of-consciousness nature of this post. I will try to clean this up and formalize the idea later.
Let f(x) be a polynomial of degree n: f(x) = c0 + c1 x + c2 x2 + ... + cn xn, and let P be a set of points { (x0, y0), (x1, y1), ..., (xm, ym) } with yi = f(xi) of cardinality m.
Assertion: If m = n + 1, P uniquely determines f (that is, P fixes values of c0, c1, ..., cn)
First, we want to show that m = n + 1 implies P uniquely determines f. P uniquely determines f if there is exactly one value for each ci for which every point in P is on f. We can use induction:
Base case: n = 0 (i.e. f(x) = c0). Since m = 1, we have some { (x0, y0) } with y0 = f(x0); since f(x) = c0, y0 = c0, so { (x0, y0) } uniquely determines c0.
Inductive step: Suppose that the inductive hypothesis (m = n + 1 implies P uniquely determines f) is true for n = k. We wish to show it to be true for n = k + 1.
Let f(x) = c0 + c1 x + c2 x2 + ... + ck + 1 xk + 1, and let f'(x) = c0 + c1 x + c2 x2 + ... + ck xk. Note that f'(x) is f(x) with the highest-degree term removed. Let P = { (x0, y0), (x1, y1), ..., (xk + 1, yk + 1) } and P' = { (x0, y0), (x1, y1), ..., (xk, yk) }. Note that P' is P with (xk + 1, yk + 1) removed. Note that the cardinality of P is equal to the degree of f + 1, and the cardinality of P' is equal to the degree of f' + 1.
We appeal to the induction hypothesis on f' and P' to fix c0, c1, ..., ck; now we need only fix ck + 1. We can write our remaining point (xk + 1, yk + 1) like so:
yk + 1 = c0 + c1 xk + 1 + c2 xk + 12 + ... + ck + 1 xk + 1k + 1
Since we fixed c0, c1, ..., ck, and xk + 1 is known, let some constant d = c0 + c1 xk + 1 + c2 xk + 12 + ... + ck xk + 1k (i.e., the equation given for yk + 1, with the ck + 1 xk + 1k + 1 term removed). We now have:
yk + 1 = d + ck + 1 xk + 1k + 1
With yk + 1, d, and xk + 1k + 1 all constant terms, which fixes ck + 1.
Therefore, by induction, m = n + 1 implies P uniquely determines f.
Next up: the other direction! Bonus question: Can you think of any applications for the theorem we derived?
Addendum: the following much more concise argument is due to Michael Kleber on Google Plus: Suppose f and g both pass through all n + 1 points (xi, yi). Their difference h(x) = f(x) - g(x) is a polynomial of degree n which passes through (xi, 0). We can show that h (which is of degree n) can't be 0 at n + 1 points: any polynomial with roots at x0, x1, ..., xn must be a multiple of (x - x0)(x - x1)...(x - xn), which has degree at least n + 1. The only multiple of that with degree n is h(x) = 0, so f(x) = g(x).
Most modern cryptographic hash functions are built using the Merkle–Damgård construction, which is a way of turning a one-way compression function (which takes two inputs of length n and returns an output of length n) into a hash function (which takes one input of arbitrary length and returns an output of length n). The MD construction looks roughly like this, given a one-way compression function C and message blocks m0, m1, ..., mn, with a padding block mn + 1 appended:
S0 = <some constant>
Si + 1 = C(si, mi)
result = Sn + 2
The state after adding block i + 1 is C applied to the state after adding block i and the data in block i. We also append a fake block to the end of the message, consisting of the message's length and then some padding (mn+ 1). This is a pretty neat construction, because it's provably collision-resistant if C is collision-resistant, but there are a couple of problems with it.
One of the problems that comes up is when people decide to use hashes to authenticate data. Given some cryptographic hash function H, if Alice and Bob share a secret key K, it should seem intuitive that Alice could send Bob a message m and then H(K || m) (here "||" means "concatenated with") by way of proving that the message came from her; since an attacker doesn't have K, they can't compute H(K || m), and sending H(K || m) doesn't reveal anything to an eavesdropper, but Bob can compute H(K || m) on his own (since he knows K) and verify that it matches the value sent. This is called a message authentication code.
Unfortunately, if H is built with the Merkle–Damgård construction, there's a critical flaw in this protocol. To make it apparent, we have to delve a little bit into the internals of H. As part of the MD construction we appended some padding to m, which we called mn + 1; let's call it "padding" now. The value of H(K || m) is produced by successive applications of C, which look like this:
H(K || m) = C(C(C(...C(s0, m0), m1), m2)... mn), padding)
Therefore, the returned hash value H(K || m) is really just the last state Sn + 2 of the MD construction. This is the crux of the problem: an attacker knows one of the two inputs which would be fed to C if there was another round, and the other input is... the next block of the message! So our attacker can append a message block mn + 2 of their choosing, and since they have Sn + 2 and mn + 2, they can easily find Sn + 3, which is: H(K || m || padding || mn + 2), and if they send that value to Bob (along with m || padding || mn + 2), Bob will compute the correct hash! (I'm papering over a little bit of complexity to do with the padding, since the bytes that make up the padding are not necessarily acceptable in the middle of the message, but this is not usually insoluble.)
At first glance, this seems like a pretty disastrous attack, since it lets an attacker compute an almost-arbitrary suffix of any message authenticated this way. Well, actually, it is a pretty disastrous attack, which is why nobody should authenticate messages using the H(K || m) approach. Instead, there's a construction called HMAC, which applies H twice, like so:
HMAC(K, m) = H((K ^ opad) || H((K ^ ipad) || m))
opad and ipad are fixed patterns defined by the HMAC construction. The key feature of this design is that it hides the result of H((K ^ ipad) || m) from the attacker, which deprives them of one of the inputs they would need to find H((K ^ ipad) || m || padding || stuff), and the result of H((K ^ opad) || H((K ^ ipad) || m)) isn't vulnerable to length-extension since the length of H((K ^ ipad) || m) is fixed. Cute, isn't it?
I'm going to start moving all my posts out of Google+ and back into my own blog, since I really want stable URLs and a guarantee that my stuff will be available for as long as I want. Stay tuned :).
I started reading a blog that I rather like, by an interesting guy called Sebastian Marshall. He mainly blogs about how to get things done. I suffer from a transfinite todo list (maintained by tdl) and so techniques that can help me do some or all of the things I want to do are important. I've been particularly interested by his posts about time tracking and public accountability, which in this context means listing the things you want to do publicly, under the theory that having to write about them will cause you to do them. He also has somewhat of an obsession with the idea of greatness. I think of myself as being good at the things I try to do; I'm a good programmer, a good partner, a good friend, and a good person overall - but I don't think I'm great at any of those things. His stream-of-consciousness writing style has an infectious energy to it that makes me want to achieve; the structure of the sentences seems to be saying "you should be better" - and they're right. He's also crystallized some viewpoints that I have long held in more concise ways: for example, that production is profoundly more fun than consumption, and that we are conditioned to accept failure as part of the human condition. Highly recommended reading all around.
In the spirit of the previously-linked public-accountability post, I will start keeping a list of things I want to do every day, along with whether they got done each day, and I will publish it for all the world to see. I hope that this will make me get more things done. In one week (on 20111126) I will write a post about how it's been working so far. Wish me luck, internet :).
I've been thinking a bit about politics lately. I'd be interested in feedback about the ideas I'm about to lay out. Please direct it to (elly+blog leptoquark.net) with this blog post's identifier in the subject line.
First principle: the Principle of Least Privilege from the software industry, which briefly states that an agent should have access only to resources and actions required to perform its function. This is a good safeguard against both accidents and malice, so I'll try to apply this to the governmental structure I'm coming up with.
Second principle: Citizens are endowed with certain rights, which I mentally divide into the categories of natural rights and legal rights. As a distinction, I'll say that natural rights are those that exist "by default", in the sense that an individual human on an island by themselves has those rights, whereas legal rights are those that exist by virtue of participation in a society.
The natural rights that occur to me:
Examples of things that are not natural rights, but may be legal rights:
Third principle: A government is an organization charged with protecting the rights of its citizens. It should, ideally, have no functions not necessary to this end, by the first principle.
Okay. By the first principle, let's start with no government at all and build structure from there was we need it. First, it's worth looking at what no government at all offers: none of the natural rights are protected, except insofar as the individual is equipped to defend their own rights; that is to say, a strong or well-armed individual may have all of those rights by virtue of nobody being able to gainsay them, but a weak or unpopular individual may have none. The weak are open to violations of their property, speech, or worship rights at any time by the strong. Not great. (This governmental structure is everyone-for-themselves barbarism. I hesitate to use the word "anarchy" here, because even though anarchy implies no government, anarchy often has other power structures). Under this system, rights can only be defended (more or less) by the use of force by their holders.
The last sentence of that paragraph was important, I think. Part of the property right mentioned above is non-interference with one's person, which is (of course) one's property. However, this right is so important that it's actually worth pulling out on its own as a principle - yet barbarism allows recourse to violation of another's rights in retaliation for a violation of one's own.
Fourth principle?: Only force may be met with force. This principle forbids first use of force, and allows second use of force. This principle has a '?' after its name because I'm not sure it's a principle in the same sense that the other three are.
Let's try defining the smallest government we can get away with that defends the natural rights we enumerated above so that citizens do not need to individually resort to force. Such a government needs to provide, at a minimum, for justice - id est, punishments for violations of others' rights, which entails courts (for finding out whether rights have been violated) and police (for bringing the accused to be judged, and carrying out punishments as necessary). It's important to point out here that the role of the police, as given above, is to carry out the fourth principle on a society-wide scale - the use of force against any member of a society is met with force from the society as a whole, with the police acting as agents of the society.
The police and the courts require some amount of resources to operate, which must be paid by the citizens they protect; this can be done either as a voluntary payment (in which case only citizens who pay are so protected) or an involuntary payment, demanded of all who live within the reach of the justice system's authority. Both of these approaches are somewhat problematic. The former causes people to be outlaws (literally: "outside the protection of the law") by default, whereas the latter requires a violation of the nascent fourth principle: in order to collect an involuntary payment, the justice system must be prepared to use force against a person who has merely refused to pay. If we choose the former, we're looking at the bottom two-thirds of a minarchy (or libertarian capitalist) government; if we choose the latter, we're looking at the very kernel of a republic (there is some scholarly dispute about the meaning of the term 'republic'. Here I use it to mean "government for the people" - id est, "government to protect the people's rights".)
The question of how the laws are written and to whom the government is responsible is also an interesting one. A minarchist system which requires a fixed contribution from each parcipant operates as a direct democracy, where each person's continuing contribution counts as their continued vote in favor of the system. A minarchist system which allows varying contributions operates as a plutocracy, where power is directly determined by wealth (and hence by ability to contribute). A republican system separates the issue of resources for governance from the issue of control of the government, since contribution is involuntary, and therefore requires no like or dislike for the government. Republics are therefore open to a vast array of potential governance styles; currently or historically common ones include democracy of various stripes, monarcy, tyranny, and aristocracy.
Alright, so now we've designed a government that can protect the basic rights of our citizens. However, we're missing a component that is important to the functioning of an economy: the idea of a contract, which is an agreement entered into by two or more citizens, all of their own voluntary choice, which is enforced by society. Without contracts, we find ourselves unable to undertake trade: a seller might accept a buyer's money and then refuse to turn over the goods, for example, and the buyer would have no recourse. We will not touch yet upon the idea of which kinds of contracts citizens may enter into, and just say that a contract is an instrument citizens may enter voluntarily into between themselves, with a defined punishment from society for breaching the terms. The existing justice system can enforce these by making 'breach of contract' a crime. This system is now a full minarchy, or a minimal republic.
That's all for tonight, I think, as it's getting rather late. Tune in next time for a discussion of which legal rights might be desirable and why!
In my pockets:
In my bag:
Earlier today, I made the offhand remark that I wished there was a bank "for people like me" without really thinking about what I meant. I'm really dissatisfied with the ssl/tls security approach taken on the internet at large (i.e., a large set of root CAs, any of whom is allowed to attest that a certificate binds to any name). It's a recipe for disaster, since the security of the entire system depends upon which of the CAs takes the _weakest_ security measures; as an individual website owner, there's nothing you can do if an attacker compromises some other CA, totally unrelated to your business. Also, CAs are paid per cert that they sign, which encourages them to be as lax as they possibly can while not getting their certs pulled from major browsers, and browser vendors are encouraged to be lax about accepting CAs because otherwise "it works in Internet Explorer but Firefox just gives me this scary warning page".
How might we fix this? I posited that perhaps physical businesses could give out USB sticks which, when plugged in, would offer to install a certificate (for that business's site _only_, or a wildcard of their domain, or somesuch). Then businesses like banks or large retailers could distribute these to let people visit their websites securely.
There are a couple of really huge problems with this idea. The first is certificate revocation: there's no handy way to update a cert on someone's machine, and it's not like you can get a CA to just sign you a new cert and revoke the old one. Secondly, it has some pretty big discovery problems: if I haven't interacted with a website in meatspace before, I can't interact with it securely at all.
So perhaps we can throw a web of trust at the problem. Let people or companies use their certs to attest to a dns<->certificate binding, then trust whichever binding has the most votes. We've just traded one problem for another, though: there's still no way to revoke a certificate, and the mechanisms we have for introducing such a way will suffer from attacks where a single malicious signer can bump a certificate serial number and have their cert taken as the 'new' one. There's also no reason to believe that random companies and people would be particularly better verifiers than the current CAs are, but there would be many more of them, which means subverting any individual is less useful.
Perhaps our best bet is DNSSEC. DNSSEC will unify the entity assigning the namespace with the person certifying the name<->host binding - but we can also use TXT records or similar (protected by DNSSEC) to serve pubkey fingerprints, and so bypass the CA model. I think of this as the all-eggs-in-one-basket approach, since the name<->host certifier gains the power to forge any site's certificate - although this is a strict improvement on now, when any CA can forge any site's certificate.
Unrelatedly, I made an x509 ca for openvpn use. Does anyone know how to restrict a CA certificate to domains matching a particular mask? I really want it to only certify *@leptoquark.net for principals and *.leptoquark.net for hosts. If you do (or you have thoughts about my proposals(?) above), please send me mail with this entry's timestamp in the subject :).
Truly excellent game of Apocalypse World this evening. The players had been in pursuit of the leader of a strange cult, and had followed him back to the cult's main compound and then proceeded (in PC fashion) to start a shootout with themselves on one side and about ninety heavily-armed cultists on the other. The PCs took cover inside the cult's temple, at which point a helicopter gunship showed up (!), effectively trapping them inside. They made their way down into the basements, freeing some prisoners (who the Hocus preached the Good Word to), and found a laboratory with... a door. An ordinary, wooden door that opened into a deserted city, filled with the ghosts of its long-dead inhabitants. The PCs entered the city, choking on the heavily-polluted air, and found a band of cultists (led by the aforementioned leader) trying to summon a powerful being from the psychic maelstrom into the world by feeding on the rage of a planet-scale AI haunted by the ghosts of its former citizens. The cult leader succeeded, although the PCs destroyed his corporeal form, and the thing from the maelstrom entered the abandoned city in the shape of a two-hundred-foot-tall demon. The PCs were, as they say, "legging it" at this point, but when they noticed the demon escape, they decided to deactivate as much of the AI as they could to lower the chance of additional things making it through. The savvyhead tried to talk to the AI again, but there was nothing left of it to talk to, so she kicked off the planetwide shutdown process for it, which had been built into it as a failsafe by its original designers. The PCs then ran back through the door to find that the demon had shrunk itself to fit, gotten outside, and was busily butchering the cultists that had had them trapped. By some careful coordination, the PCs managed to hit it with three grenades at once, then shoot it with silver bullets, then decapitate it with a scythe dipped in mercury, which was sufficient to kill it.
I started using a tool called tdl recently. It's quite astonishing how powerful a todo list is for getting stuff done: whenever I can't think of something to do, I open my todo list, and pick something. On the other hand, it has 57 entries in it, which is a little intimidating :).
I want the logical extension of local tree-namespaced ipc systems like dbus: global tree-namespaced ipc systems. Perhaps we could call the wire protocol 'HTTP' and the namespace 'DNS' :).
Sitting on keroserene's floor, listening to some kind of delightful ambient music, drinking luo han guo tea. It's been a wonderful last couple of days even in spite of being away from Liz. The tea is a kind of rich brown color, but more vibrant and earthy than normal tea.
I started doing the 15-411 F11 lab 1 in Racket, which you can find on my github page. I'm still thinking about how to do register allocation; I think a bit of refactoring to not just use unadorned lists everywhere might be in order first, especially if I want it to be presentable :). Two friends of mine are TAing the class; one of them said that if I produce credible Racket base code, they might ship it as an option next semester.
It's been really excellent to get to catch up with old friends, and to feel the exhilaration of socializing without being anxious about it, even when there are a dozen or more people around. We (keroserene and I) stopped by a house party on our way back, but both of us were driven off by the sheer density of drunk people.
An interesting read about a generation gap and new technology. I also started into Complexity: A Guided Tour on the plane, which I'm finding repetitious so far, but I already have a basic grounding in chaos theory so that is somewhat to be expected.
I've been working on my D&D setting. I'm trying something new for me as a DM: I'm taking the Apocalypse World book's guide on worldbuilding to heart and building NPCs from the organization downwards to individuals instead of from individuals up into an organization. It's very interesting and I feel like it will help give the world a more populated feel, so that not every encounter seems like it's part of some overarching plot. I'm also leaving drawing a map until last, I think :). (For inveterate D&D geeks, here are my house rules).
Reading about economics makes me wish that I knew economics better; I think that if I were going to go back to university again, a basic grounding in economics would be one of the first things I'd pick up.
I confess to reading ZeroHedge fairly frequently, even though I don't really understand much of what they write, just because being exposed to that much conspiracy theory all at once is sort of exhilarating somehow. Like all really good conspiracy-theory sites, they tend to link to primary sources quite a lot, which are usually just as bewildering but much more authoritative. Currently, I'm preoccupying myself with:
Depressing news all around, really. On the upside, perhaps the absurdly-pretentiously-named More Intelligent Life or The Believer can cheer us up? I need to start reading the issue of n+1 that I picked up. :)
I have this idea that I've been tossing around in my head for a while, and I'm not really sure how to get started on it. I would like, at some point, to rewrite the entire Linux userland to conform more closely to how I think software should be designed. I want to rewrite much of the userspace in a higher-level language and decompose the system into more smaller daemons communicating over IPC. I have tantalizing bits of this system sketched out, so I think I might just jump in and start hacking on it.
The first thing I linked to above, by the way, is a peer-to-peer IPC system which is actually sort of neat, API-wise; epoll lets you produce really clean interfaces where you hand a single file descriptor back and say "when there is input on this fd, call this function", and that fd can package up all the fds your library needs to use internally using epoll.
Here is an idea for an extension to the identity network idea I posited in 2011.246.48162 to allow posting of messages to subsets of users in an easily-updated, secure way. Definitions:
Suppose that u0 wishes to post a message m0 to (linkset u0 friends), but they do not trust the transport mechanism they use (be it dumb HTTP hosting, some existing blogging platform, or anything else). They can always separately compute (encrypt-to (user->key u) m0) for all u in (linkset u0 friends), but this is inefficient, especially if there are hundreds or thousands of identities in (linkset u0 friends). Therefore, an optimization: for each user u in (linkset u0 friends), u0 maintains a special message called a key set, which we will denote with (key-set u0 u); the elements of the key set are tuples of (linkset id, symmetric key), where the symmetric key is bound to the linkset id (i.e., all elements of (linkset u0 friends) receive the same k in (friends, k) in their key set). Now, to post a message m0 to (linkset u0 friends), u0 computes c = (encrypt (linkset->key (linkset u0 friends)) m0) and publishes c. To add or remove a user from a linkset, we generate a new symmetric key for that linkset and update the key set files for all users now in the linkset.
As an extension to the identity-network format, this might look like this:
A post tree is really a tree of URLs. Assuming that u0's post root is http://www.u0.com/p, the following URLs are defined relative to u0's post root:
Therefore, if u1 has just been added to u0's friends linkset and wishes to check for posts to it, u1 does the following:
Anyone have any thoughts about this? You can send mail to (email "elly+blog" "leptoquark.net"); please put the id number of the blog post (in this case, 2011.254.76724) in the subject line :).
Also, I'll likely start running a D&D game soon. I'll post the house rules and write about them some time, because I think they say something interesting about the design problems in D&D 3.5.
Epic day today, and it's not even done yet. I decided to go to Harvard Square with rlambert (a friend of mine from university). I showed her Raven Books, the Harvard Book Store, and Kofuku, and we got a delicious lunch at Legal Seafood. After that, we accidentally stumbled upon New England Comics (warning: visually offensive website), which I'd heard about but never actually seen before. I picked up the following books, which I'd been looking for:
In case you didn't guess, I'm a bit of a Brian Wood fangirl :). After that, we wandered onto Harvard Common, which is completely beautiful this time of year - there were dozens of people lounging about reading and talking, and a small band playing classics near us. All in all quite extraordinarily peaceful. We watched a squirrel gathering up clumps of grass and carrying them up to the top of a tree; I'd never known that squirrels built nests, but this one certainly seemed to be.
We then went to Alden Playground, which has the most awesome play structure in the history of civilization. The entire place was utterly overrun with sprogs, but rlambert and I had a good time relaxing in the tangle of ropes. One of the kids took a liking to us, and declared that we were supervillains (I was a supervillain, and rlambert was my sidekick) and, apparently, that I had a crush on her. Cue hours of us trying to hide inside the rope structure from first her and then another kid as well; kids of about six turn out to be both surprisingly agile and surprisingly strong, and they were certainly better climbers than me :). It was decided that our villainous plan involved constructing robots with lasers and vacuum cleaners, then releasing rats onto the climbing structure and sucking them up with vacuums (?).
A good time was had by all :).
A friend points out a problem with my previous design: a third party can DoS you by adding arbitrarily many nodes claiming your identifier that will never authenticate to you. You can fix this with a little protocol tweak: when the first node with a given identifier registers with the centralized frontend, it sends it a pair (N, E_k(N)), where N is a nonce and k is the secret shared among all of the user's instances. The centralized service sends putative new clients with that identifier E_k(N) and requires them to reply with N, which filters out junk clients before they get a chance to appear in the peer list for that identifier.
I finished Magic Knight Rayearth today. The ending was Power Of Friendship all the way, but for all that, I found it quite sweet and charming, and I'd recommend it, especially to people who are otherwise new to manga.
Lemma: Brigitte Bardot was a smoking hottie back in the day.
I started reading The Little Black Book of Style. It's pretty fascinating, really, and confirms a lot of my personal prejudices about beauty :). Choice quote: "I was not ugly. I might never be anything for men to lose their heads about, but I need never again be ugly. This knowledge was like a song within me. Suddenly it all came together. If you were healthy, fit, and well-dressed, you could be attractive." Also, "Nothing suits a woman better than this air of self-assurance, and when she truly owns that, she is unyielding and stunning. Confidence is the one thing that can instantly turn the volume up on a woman's beauty." I'm looking forward to the rest of the book immensely.
Liz produced some obscenely delicious chili today out of pinto beans, jalapeno and habanero chilis, and a whole bunch of miscellaneous other stuff. Kinda spicy, quite sweet, and so delicious that between the two of us we ate all of it.
What if there was a hermetic, self-contained cloud-in-a-box that one could drop onto any reasonably modern machine, feed an identifier and a shared secret, and have it bootstrap itself into a replicated, high-availability cloud across all your machines? What I'm thinking is: when one of these nodes comes up, it connects to some centralized (yes, ugh) broker service, gets a list of the other services with the same identifier it has, and authenticates mutually to them with its shared secret; it then starts to replicate data and load-balance, seeking some minimum replication factor and using the high-availability service as a front-end load balancer. You could kick the broker service out into a DHT if you felt so inclined, but the frontend behavior is very useful.
I've put my blog engine (and blog contents!) up on github.
I had one of those days today where I feel like I'm sort of level-grinding; I didn't really get anything *done*, but I gained a lot of expertise that I didn't have before, and I think I leveled up (so to speak, anyway) in understanding the automatic integration and testing infrastructure we use.
I'm about 3/4 of the way through Magic Knight Rayearth now, and I think it's taken a considerable turn upwards since I last wrote about it, although the end of the battle with Ascot felt kind of like being hit in the face with friendship (!) and I don't have much hope for the next big bad, who seems to be a combination of stripper and volleyball player (?). Next on my list is definitely The Little Black Book of Style.
What if one could automatically detect insecure tempfile use using ptrace(), e.g. by faking out the results of any open() after a readdir() as though the file had been created in the mean time with some insecure mode?
I think it is really cute that Misty doesn't look humans in the eye if she can possibly avoid it. Liz and I think this is a wolf-like-dog kind of dominance thing, because other dogs I've had that weren't so wolf-like didn't do that (and in fact, dogs I've had that were sheep/cattle-herding dogs would stare humans in the eyes as a matter of habit).
I woke up earlier than usual to the sound of falling rain in the huge tree just outside, and it's still raining pretty heavily now. I'm feeling basically no desire to get out of bed with Liz and go to work, although I probably should. I think I've been not getting enough sleep lately, which is making me markedly less effective at work, but I am not quite sure how to fix it, since as far as I can tell I'm going to sleep early enough and so on. I'm certainly less tired today than I have been previously, so I think going to bed about 2230 and waking up whenever I wake up works for me, although there is the confounding factor of Misty waking us up basically whenever she feels like it.
Liz reports that she is in my base, and "[I] will not believe what she's doing to my dudes."
I'm halfway through Magic Knight Rayearth (volume 1, I think, although it's not marked as such). It's adorable, and there's a lot of power-of-friendship plot going on - in particular, magic in Cefiro (the world they're in) is powered by emotions and belief, so it seems that anyone can become an incredibly strong sorceror when sufficiently worked up. As a plot device, this makes an excellent excuse for a lot of unstoppable rage. That said, it's cute, and I'd recommend it, even to people who don't otherwise read Manga.
To work we go!
I finished V For Vendetta today (the graphic novel, not the novelization of the movie (!)). It was every bit as brilliant as I'd been lead to believe, and the relationship between order and chaos and anarchy and authority is much more fleshed-out. In general, from the movie I got a kind of hooliganish "smash stuff!" message, whereas the book is much more of an actual anarchist tract - a lot of attention is paid to the constructive side of anarchy and the question of what comes _after_ the smashing.
I've been listening to Fireflight's For Those Who Wait basically all day now. Something about the song really strikes me. I really like the lead singer's voice - she's amazing on Unbreakable too.
Next book up: Magic Knight Rayearth. I picked it up off the shelf at random yesterday. After that, I think I'll try one of the books I picked up on 2011.246. I really like the feeling of having a queue of books to read - it keeps me from doing things that are bad for my mind like gaming, since I can always think to myself "I do have that book to read...". I'm still a bit on the fence about ebooks; they're very convenient, but nothing they can do replicates the sensation of standing in a bookstore and just browsing through the shelves, feeling the stories hidden behind the spines. A Softer World's take on this is very good too.
Ahh, now I've got myself reading A Softer World again. A few of these stick out to me right now. I hope that my passion never leaves me, either for Liz or for writing code, and I really like this one: I love you the way a knife loves a heart / the way a bomb loves a crowd / the way your mother warned you about, essentially.
I think that's a good thought to end on. Think about the way knives love hearts, and the way bombs love crowds; what is it to love a person that way?
Ended up waking up late, spending a long time getting out of bed (ah, the infinite joys of a wonderful primary), eating a light breakfast, and then spending the day with kalenedrael, an old friend (no known PGP key). We wrote code together - I've always found it easier to write code when there are others writing code in the vicinity - then played Supreme Commander, at which we were soundly thrashed by the AI. Afterwards we decided to go out for dinner, so we went to the Border Cafe (warning: totally wretched website). We then wandered around Harvard Square a bit and stumbled into Newbury Comics, where I bought:
I've already read DMZ Volume 7, and I think it is the best volume of the series so far by a big margin. The volume is bookended with two incredibly touching stories, with Zee (my favorite character) making an appearance. The very first story had some echoes, for me, of the way front-line soldiers sometimes behaved during the civil war towards their counterparts in the opposing trenches. Highly recommended all around.
I now have an rss feed for this blog. It's pretty damn hacky. There's also the actual feed.
A proposal by Liz to extend my identity system with detached signatures, since this allows us to feed the identity files directly into a Lisp interpreter.
Additionally, I propose that Lisp comments (i.e., lines beginning with ';') be allowed outside the person form to explain nonstandard URL schemas and other oddities.
Liz and I are now totally Cyberpunk Married. We just got a shared email account and a shared PGP key (A144FEF64DD8785E3073E9FA661E5F76AD899041).
Also, we have totally planned a simple and restrained wedding. Twenty-five people, a forty-five minute ceremony, and then we repair to a restaurant for delicious celebratory dinner. I'm looking forward to it, which it seems the wedding industry would have you believe is illegal or something.
This chunk is rot13d for non-kinky-viewer protection. Nsgre qvaare, Yvm naq V jvyy pbzr onpx gb bhe ubhfr sbe Yvm'f ynfg erpbyynevat. V'yy jevgr nobhg guvf fbzr gvzr fbba.
A while ago I linked back to my website on subjot, and a friend pointed out that there was no way to verify that that linkage was real from the other direction (i.e., to verify that my subjot was me). Therefore, I made up a structured way to express which relationships I have.
The syntax is a datum, written in the Scheme external representation. The structure is a list whose first element is the symbol 'person'; all the remaining elements are lists whose heads are symbols and whose tails are values (dependent on the head symbol for that list). In essence: (person (key values ...) (key values ...) ...). The symbols I have defined (and their values) are:
I sign the file with 'gpg --clearsign --armor -u $ROOTKEYID identities', then put up the resulting identities.asc file.
All it would take to turn this into a genuine social network (as in, one with explicitly, publicly-visible linkages between friends) would be an additional key in the person structure, used to link to another person:
I really like the idea of identifying people first and foremost by some unforgeable identifier like public keys. If there were a way to attach arbitrary metadata to PGP keys (perhaps in the comment field?), you could build a social network on this principle that would be decentralized and secure. You'd just put your public key up on the keyservers with the comment field pointing at some stable URL; at that stable URL, you could have one of these files, which would in turn link to a bunch of other backup URLs. Since you signed the whole thing, your identity file could easily be replicated by other people, and the whole thing needs only be served over dumb HTTP (i.e., no server-side work needed at all).
As an aside, I've created a separate blog key ( 5D11F5C48E4FC49D91AADE988DB93AB8A330A1E6, signed by my root key) with which I will begin signing the HTML source of this blog. The signature will always be available at http://www.leptoquark.net/~elly/blog/sig.
Two very strange dreams today: I dreamt that Liz and I were going to visit some friends I didn't remember, but it was very late at night and we had to be in to work early the next day for some reason, but Liz insisted that it was okay, and then the dream ended when we got there (?), and the other was that I was an NGO worker in North Korea and fell in love with my interpreter/minder and ended up not being able to help her escape.
I got sixty or so pages into Beyond Shelter: Architecture and Human Dignity. It's about how to do long-term rebuilding after disasters in such a way that the communities are better-prepared for the next disaster. There's a sharp contrast of methods: traditional aid agencies often focus on the short term, parachuting in teams of volunteers and massive amounts of food, water, medicine, and emergency shelter, whereas the approach the author espouses (in addition to the traditional one, not in replacement of it!) involves sending a couple of engineer/architects to live with the community they're helping repair for a period of years to help the residents rebuild on their own. The author believes this allows the local people to retain their dignity in a way that the other approach doesn't.
I got four other books yesterday:
I sort of went on a randomized shopping spree at our local bookstore ( Porter Square Books). Fashion and architecture have always been a little bit fascinating to me, not least because I don't really know anything about them, n+1 looked really interesting from a casual flip-through, and the other two - well, I'm just a sucker for math and system design and analysis.
