#604 new enhancement

one-shot distributed revocable forwarding slots

Reported by: warner Owned by:
Priority: major Milestone: undecided
Component: code-encoding Version: 1.2.0
Keywords: revocation Cc: tahoe-dev@…
Launchpad Bug:

Description (last modified by davidsarah)

I had an idea this morning.. not sure it's actually good for anything, but I figured I'd write it down just in case.

Suppose that Alice has a static target (say a filecap) that she wants to give to Bob, but she might change her mind later and decide to take back the gift. Since the target is static (Alice is granting knowledge of data rather than performing retrival work on his behalf), once Bob has claimed the gift, it can no longer be revoked. So in addition to being able to revoke the gift up to some point, Alice would like to be able to find out when that point has been passed.

In physical terms, Alice wraps her target in a fragile but opaque box, and nails it to the ground in a secret location. Then she tells Bob where the box is located. When Bob opens the box and claims the gift, the box is destroyed. If/when Alice decides she wants to revoke the gift, she goes to the secret locations and looks at the box. If the box is unopened, she knows that Bob has not yet claimed the gift, and she'll be able to revoke it successfully (she opens the box and takes the target back home with her). If the box is opened, then Bob has already claimed the gift, and she knows it's too late to revoke it.

In the Tahoe world, we want this to be distributed: Bob should be able to claim an unrevoked gift even if Alice or some number of servers are unavailable. (if we could require that Alice was online, this would be a pretty trivial job).

The idea I had was:

  • on the storage servers, define a "one-shot revocable slot", which is referenced by a storage-index, contains a piece of data, and is pointed to by both an "open-cap" and a "revoke-cap". It also has an "opened" flag.
    • if the "open-cap" is used, the opened flag is set, and the data is returned to the invoker.
    • if the "revoke-cap" is used, the data is erased, and the opened flag is returned
  • Alice encrypts the target into a number of shares using a secret-splitting scheme (like FEC but the requirement is that having fewer than k shares gives you no information about the secret). She then encrypts each share with a different per-server key, and sends each encrypted share to a different storage server, along with an open-cap and revoke-cap for each.
  • Alice gives Bob the storage index and the list of per-server keys, and the open-cap for each server.
  • When Bob wants to claim the target, he uses the storage index to find the shares, and the open-cap to read them. Then he uses the per-server keys to decrypt the shares, then undoes the secret-splitting algorithm to derive the original target.
  • If Alice wants to revoke the gift, she uses the revoke-caps to erase the shares. If any of the shares have been opened, her agent informs her that she is too late.

Of course, the list of keys and open-caps would be compressed, by deriving them from some master secret. My hunch is that we could get Bob's claim-cap down to two crypto values.

Secret-splitting is used to allow Alice to revoke an unclaimed gift even if she can't get to all N servers (she just has to get to N-k+1 of them). The per-server keys are used to prevent multiple servers from colluding to learn the secret or something.. I haven't worked out this part too carefully.

In general, the storage servers must not be able to learn the secret, even if they all collude. A single storage server should not be able to make Alice think that the gift is unopened when Bob has actually already opened it.

One extension is to put multiple open-cap/revoke-cap pairs in each slot, and make the same gift available to multiple people.

A separate device could be used for mutable slots: in this case, "revocation" means denying access to versions that are created after some point in time. My thoughts on this are to have each mutable slot contain a list of asymmetric encryption keys (say RSA), one per reader, and a corresponding encrypted AES key for each. Every time the slot is mutated, the new version's AES key is encrypted to each reader and placed in the table. Each reader gets the corresponding RSA decryption key, and can access the AES key (and therefore the real data) by decrypting their row of the table. Revocation consists of removing that reader's row from the table.

Change History (4)

comment:1 Changed at 2009-02-03T21:02:43Z by zooko

  • Cc tahoe-dev@… added

adding Cc: tahoe-dev

comment:2 Changed at 2009-02-03T23:18:38Z by swillden

An effect of the multiple shares is that if Bob wants to get the secret without tripping the opened flag, he has to subvert all of the servers. Without that, perhaps it just happens that Alice places the secret on a server that Bob controls. So if that server has enough information to allow Bob to recover the secret, then he can retrieve the data and see that the flag remains in the unopened state.

Of course, if Alice only contacts servers that Bob controls when she tries to revoke, or if they're the only ones on-line when she checks, then it's possible for Bob to take the secret undetectably.

By setting k high (perhaps even k = N, with large N), Alice can make undetected retrieval hard (increasing the number of servers Bob has to control) at the expense of making the secret less reliable. By choosing small k, she makes the secret reliable, but undetected retrieval easier.

Interesting idea. I don't see any practical applications, but it is interesting.

comment:3 Changed at 2009-02-03T23:20:32Z by swillden

An effect of the multiple shares is that if Bob wants to get the secret without tripping the opened flag, he has to subvert all of the servers.

Er, "k" of the servers.

comment:4 Changed at 2011-10-11T02:57:22Z by davidsarah

  • Description modified (diff)

Correcting "(she just has to get to N-k of them)" in description to "(she just has to get to N-k+1 of them)".

Note: See TracTickets for help on using tickets.