Access Control

In this document, we describe how peers can control who gets to request which Entries. The basic idea is simple: you only answer requests for Entries if the request comes with some proof that the original author has allowed the requesting peer to access the data.

Read authentication is the process of one peer proving that they were granted access to some data. We employ read capabilities, unforgeable tokens that grant access to some data to the holder of some secret key.

For a capability system to be usable for read authentication it needs to provide three types of semanticsMeadowcap, our bespoke capability system for Willow, just so happens to provide these semantics.: each read capability must have a single receiver (a public key of some signature scheme), it must have a single granted area (an Area), and it must have a single granted namespace (a NamespaceId). Access control can then be implemented by answering only requests for Entries in the granted namespace and granted area of some read capability whose receiver is the peer in question.

Peers can prove that they are the receiver of a read capability by supplying a valid signature over some data that has never been signed by that public key before (this prevents replaying of signatures). To obtain such a piece of data (a nonce), the peers can simply generate a sufficiently large random number. Thankfully, collaboratively generating a random number — even if one of the peers might be malicious — is a solved problem.

A comic visualising nonce generation with one column for each peer. The peers think of their numbers, hash them, exchange the hashes, then exchange their numbers, verify the hash of the received number, xor the numbers together, with one peer using the complement number instead. With the nonces generated, the peers then each sign their nonce, exchange the signatures, and verify the signature they received. After successful verification, they start vivaciously chattering in binary.

To securely negotiate a random m-bit number, each peer locally generates a random m-bit number, hashes it with a well-known, secure hash function, and sends the digest to the other peer. This mechanism is called a commitment scheme; the peers irrevocably commit to their choice and cannot change it later without detection. Once both peers have received the other’s digest, they then exchange their actual numbers, and verify that the number they received hashes to the digest they received before (if it does not, they abort the connection). XOR-ing the two locally chosen numbers then yields the desired random number.

One peer can use this number directly as an access challenge: the other peer can then prove that it holds the secret key that corresponds to some public key (in particular, for the receiver of any read capability) by producing a valid signature for the access challenge. The other peer should use a different access challenge, lest the peers copy each other’s signatures. Hence, the other peer simply uses the inverted number (where every bit is flipped) as its access challenge.

It is important to use this cooperative random number generation rather than allowing each peer to freely choose the access challenge they present to the other peer. If peers immediately transmitted their random choice without transmitting the hash first, a malicious peer could simply wait for the other’s choice before making its own choice, allowing it to freely select the resulting challenge. And if challenges were chosen directly, a malicious peer could simply pose a challenge that it itself needs to answer to a different, honest peer to obtain a valid signature without actually knowing the corresponding secret key.

As closing thoughts, we want to compare this way of controlling read access with that of encrypting data and passing it around freely. Both approaches keep data inaccessible to unauthorised agents as long as the underlying cryptographic primitives remain strong. Freely sharing encrypted data has the drawback that all data becomes public once the encryption primitive is broken, whereas peers could refuse to pass on any data once the signature scheme is broken. Then again, encrypted data can readily propagate through an untrusted peer-to-peer network, whereas access-controlled unencrypted data can only travel between peers with access.

The safest option is to combine both choices. We dicuss recommended techniques for encrypting data in Willow here.