[1388] in cryptography@c2.net mail archive
How to build anonymous storage
daemon@ATHENA.MIT.EDU (John Kelsey)
Sat Aug 30 15:55:40 1997
To: "Perry's crypto list" <cryptography@c2.net>, coderpunks@toad.com
From: John Kelsey <kelsey@plnet.net>
Date: Sat, 30 Aug 97 11:06:37 CDT
-----BEGIN PGP SIGNED MESSAGE-----
[ To: Perry's crypto list, coderpunks, sci.crypt ##
Date: 29-Aug-97 ##
Subject: How to build anonymous storage ]
A while back, I got into a conversation with my mother in law,
who is a psychologist, about patient confidentiality rules.
Apparently, unlike a priest or lawyer, your discussions with
your therapist can be subpoenaed for various reasons. She said
that several of her colleagues had stopped keeping written
notes, for fear of having them seized during a messy divorce or
lawsuit. This led me to think about a service that is related to
the Eternity Service, but it somewhat easier to build--an
anonymous data storage service.
Several years back, there was some discussion of this kind of
thing on sci.crypt, but we were focused mainly on storage on the
user's machine, and on dealing with ``rubber-hose''
cryptanalysis. (Ross was talking about this kind of system at
Crypto this year, looking for ideas about how to implement it.)
I don't see a good way to do this on the user's machine that
will both survive being widely-used and also deliver anything
like reasonable convenience, reliability, and storage capacity.
(The problem here is that large blocks of inexplicably random
data lying around in the user's possession are hard to explain
for most people.) Simply stated, the goal is to make it
impossible to decide whether I have stored a document you want
me to give you. Plausible deniability is one part of this
requirement; another may be that you can store ``throwaway
files'' as well as real ones.
REQUIREMENTS
Informally, what we want from such a system is blind storage--I
get to store encrypted data somewhere and nobody can determine
whether or not I have done so. Here's a more complete list of
the requirements:
a. Neither the storage holder nor someone in possession of the
user's computer can tell whether or not she has anything stored
with the anonymous data storage service.
b. All access to the storage is through a user-memorized
passphrase.
c. The user can destroy the information irretrieveably with a
single act, if the pressure on her gets too great.
d. The storage service can't read the user's stored documents.
This prevents attacks based on offering rewards for providing
some piece of blindly-stored information.
MY SIMPLE PROPOSED DESIGN
There are two problems to be solved here: a crypto problem and
a social/financial structures problem. I can solve the crypto
problem without too much trouble. Here's my proposed design:
Storage of File:
Alice chooses a file on her system that is nearly certain to be
unique, and that she will not change over time. A word
processing document containing some historical data she won't
change over time is a good example of this. This is called the
salt file. It is very important that this salt file is unique
among all users, and that it contains too much information to be
guessed even by an attacker who knows Alice well and has access
to many of her documents.
Alice also chooses a passphrase, P, which will be very hard for
an attacker to guess. She forms FK = hash(salt file, P). (The
hash should be some computationally-expensive thing, to make
passphrase-guessing attacks harder.) FK is the encryption key
used for the file.
Alice will need an identification string to use to find the
file. For this, she forms IS = hash(FK).
Alice now encrypts the file she wants to blindly store under key
FK. She then posts it anonymously to the Eternity Service under
the file name IS.
Retrieval:
Alice requests file IS from the Eternity Service. She
apparently gets junk, but of course, she can decrypt it with
her secret key.
Destruction of File:
Alice irretrieveably overwrites her salt file if she wants to
destroy any chance of retrieving the stored document. Of
course, she has to do this carefully, using a secure delete
program and making sure no backup copies have been helpfully
made by her word processor. Fortunately, Alice spends enough
time hanging around crypto conferences that she's aware of these
issues.
Of course, I cheated here by assuming that all the hard
social/financial issues had been solved by someone else, in
implementing the Eternity Service. What we really will need
here is a set of blind storage servers whose physical locations
virtually nobody knows. Alice also has to come up with a way to
pay for this service, as it's clearly going to cost something to
run, just as is the Eternity Service. In fact, the blind
storage problem, in some sense, is a subset of the Eternity
Service problem. (It's not hard to see how to design this using
anonymous remailers with return addresses. The big problem is
the anonymous payment.)
Comments? Has someone else done this system already?
--John Kelsey, Counterpane Systems, kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBNAhCGUHx57Ag8goBAQFQ3wP/WPh50wLa02kb7mDx9TNWUGoiQ7QRsYlz
6v8M01l8XDu728sh1tS2GF4dmoHbMYoUhpwOdCA6CqdLCgcRxdddRhclAJxif/Lf
Ttcnr4XsZi4FKuPcf+MY63Fg4+5MA+HHb/PdYRr/knFkvXfqoKONvlJd8FaGoJ08
TGb11JH+DME=
=5fP5
-----END PGP SIGNATURE-----
--John Kelsey, Counterpane Systems, kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
