[tahoe-lafs-trac-stream] [tahoe-lafs] #604: one-shot distributed revocable forwarding slots

[tahoe-lafs]

#604: one-shot distributed revocable forwarding slots
-------------------------------+------------------------
     Reporter:  warner         |      Owner:
         Type:  enhancement    |     Status:  new
     Priority:  major          |  Milestone:  undecided
    Component:  code-encoding  |    Version:  1.2.0
   Resolution:                 |   Keywords:  revocation
Launchpad Bug:                 |
-------------------------------+------------------------

Old description:

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

New description:

 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.

--

Comment (by davidsarah):

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

-- 
Ticket URL: <http://tahoe-lafs.org/trac/tahoe-lafs/ticket/604#comment:4>
tahoe-lafs <http://tahoe-lafs.org>
secure decentralized storage