one-shot distributed revocable forwarding slots #604

New Issue

warner · 2009-02-03T19:46:49Z

warner commented

2009-02-03 19:46:49 +00:00

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.

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.

warner added the

labels 2009-02-03 19:46:49 +00:00

warner added this to the undecided milestone 2009-02-03 19:46:49 +00:00

zooko commented

2009-02-03 21:02:43 +00:00

adding Cc: tahoe-dev

swillden commented

2009-02-03 23:18:38 +00:00

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.

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.

swillden commented

2009-02-03 23:20:32 +00:00

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.

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

davidsarah commented

2011-10-11 02:57:22 +00:00

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

Sign in to join this conversation.