tahoe-lafs/trac

one-shot distributed revocable forwarding slots #604

New issue

Open

opened 2009-02-03 19:46:49 +00:00 by warner · 4 comments

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

c/code-encoding

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

adding Cc: tahoe-dev

swillden commented

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

Owner

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

Owner

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.

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

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.

No labels

c/code-dirnodes

c/code-encoding

c/code-frontend

c/code-frontend-cli

c/code-frontend-ftp-sftp

c/code-frontend-magic-folder

c/code-frontend-web

c/code-nodeadmin

c/code-peerselection

c/dev-infrastructure

kw:AttributeError

kw:DataUnavailable

kw:DeadReferenceError

kw:GetLastError

kw:IFinishableConsumer

kw:LeastAuthority

kw:RIStorageServer

kw:UncoordinatedWriteError

kw:access-control

kw:accessibility

kw:accounting-crawler

kw:anti-censorship

kw:api_auth_token

kw:authentication

kw:availability

kw:backward-compatibility

kw:blocks-cloud-deployment

kw:blocks-cloud-merge

kw:blocks-magic-folder-merge

kw:blocks-merge

kw:blocks-release

kw:brians-opinion-needed

kw:build-helpers

kw:cloud-backend

kw:coding-standards

kw:coding-tools

kw:coding_tools

kw:compatibility

kw:confidentiality

kw:configuration

kw:configuration.txt

kw:connectivity

kw:control.furl

kw:coordination

kw:coveralls.io

kw:create-container

kw:cryptography

kw:cryptography-lib

kw:denial-of-service

kw:desert-island

kw:desert-island-build

kw:design-review-needed

kw:dev-infrastructure

kw:directory-page

kw:disk-backend

kw:earth-dragon

kw:erasure-coding

kw:excess-authority

kw:extensibility

kw:file-descriptor

kw:floatingpoint

kw:forward-compatibility

kw:forward-secrecy

kw:garbage-collection

kw:google-cloud-storage

kw:google-drive-backend

kw:grid-manager

kw:illustration

kw:inlineCallbacks

kw:integration-test

kw:interoperability

kw:interstellar-exploration

kw:introduction

kw:key-value-store

kw:magic-folder

kw:manual-test-needed

kw:more-info-needed

kw:mountain-lion

kw:multiuser-gateway

kw:needs-review

kw:notification

kw:notifyOnDisconnect

kw:openitp-packaging

kw:operation-helpers

kw:optimization

kw:organization

kw:otf-magic-folder-objective1

kw:otf-magic-folder-objective2

kw:otf-magic-folder-objective3

kw:otf-magic-folder-objective4

kw:otf-magic-folder-objective5

kw:otf-magic-folder-objective6

kw:peer-selection

kw:pkg_resources

kw:preservation

kw:pycrypto-lib

kw:pyfilesystem

kw:random-access

kw:raspberry-pi

kw:release-blocker

kw:removable-disk

kw:reserved_space

kw:response-needed

kw:response-time

kw:review-needed

kw:self-contained

kw:servers-of-happiness

kw:setup_requires

kw:setuptools_darcs

kw:simultaneous

kw:space-efficiency

kw:static-analysis

kw:stats_gatherer

kw:tahoe-add-alias

kw:tahoe-archive

kw:tahoe-backup

kw:tahoe-create-alias

kw:tahoe-create-introducer

kw:tahoe-deep-check

kw:tahoe-deepcheck

kw:tahoe-lafs-trac-stream

kw:tahoe-list-aliases

kw:tahoe-magic-folder

kw:tahoe-manifest

kw:tahoe-restart

kw:tahoe-unlink

kw:tahoe-webopen

kw:test-and-set

kw:test-from-egg

kw:ticket999-s3-backend

kw:to-be-closed-on-2011-08-01

kw:tor-protocol

kw:transparency

kw:tub.location

kw:twisted-trial

kw:uncoordinated-writes

kw:unfinished-business

kw:unhandled-error

kw:upload-helper

kw:visualization

kw:volunteergrid2

kw:warners-opinion-needed

kw:welcome-page

kw:windows-related

kw:world-domination

kw:write-enabler

kw:zookos-opinion-needed

kw:zope.interface

p/supercritical

r/cannot reproduce

r/somebody else's problem

r/was already fixed

v/1.9.0-s3branch

No milestone

No project

No assignees

4 participants

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: tahoe-lafs/trac#604

No description provided.