Skip to Content.
Sympa Menu

bluesky - Re: The Grapevine Project

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: David Hopwood <david.hopwood AT zetnet.co.uk>
  • To: Global-Scale Distributed Storage Systems <bluesky AT franklin.oit.unc.edu>
  • Subject: Re: The Grapevine Project
  • Date: Tue, 11 Dec 2001 06:36:20 +0000


-----BEGIN PGP SIGNED MESSAGE-----

Anthony Jones wrote:
> On Monday 10 December 2001 04:02, Oskar Sandberg wrote:
> > On Fri, Dec 07, 2001 at 12:16:15PM +0800, Anthony Jones wrote:
> > > This means that you can't just pick an area of keyspace where you want
> > > to
> > > insert the data. Even if you can insert one file in a particular area
> > > of
> > > keyspace you would need to insert a large number of files in a small
> > > area
> > > of keyspace to run it out of disk space.
> >
> > The problem is that, even assuming perfect division of the keyspace
> > between the nodes, the work for finding data that hashes into a nodes
> > "range" using a rejection method is still of the order of the number of
> > nodes in the network. Regardless of the size of the keyspace, you cannot
> > assume that this will be unbreakable - even under the most optimistic
> > growth models it is still << 2**32.
>
> Oscar,
>
> You're right. If we've got a million nodes then it's only going to take a
> million guesses to get the node that you're trying to overload. We're going
> to have to work out a defence for this. Thank you for your help.

A partial defense would be to use expensive hashing; it's a similar problem
to that of deriving a cryptographic key from a low entropy passphrase,
and [1] gives a well-thought-out algorithm for that.

If the number of nodes is only a million, this is not sufficient to prevent
a dedicated attacker from choosing a file location, but OTOH, it doesn't
need to be infeasible by cryptographic standards, in order to be hard enough
to protect against a DoS attack.

It would still be a good idea to try to find other methods to reduce reliance
on the assumption that it is difficult to choose a file location, though.

[1] Niels Provos, David Mazi�res,
"A Future-Adaptable Password Scheme,"
Presented at USENIX '99.
http://www.usenix.org/events/usenix99/provos.html

- --
David Hopwood <david.hopwood AT zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPBWoLTkCAxeYt5gVAQH5CQf9GL+t8tiqlCEBWnHzyv2uYMZbuK60xVbe
vWiAPqOG2n2aNNL2wPv/srPkKADaZoknvN0dEoZ+QUDhjks3v2iw5keSk/bSTRc5
YhCIdteCMAlxT5xsa6f0f5+8gADclRVZOi/79OKlAuW/CHnBbqF9G79oyI+6nxlf
l8FXVBaZvdtTJYA7kelTzngVBCCEC7qopLyRJsrXIbEuqnnHLI0QuIdsTEhLp32F
b2lglwUOAk5lXnuCTDab7ezOO+VZ2PnNI6EQOMW7CN+AEhqmC6oZOVqlTx51zuJR
7C9GGvGHMAevCW7Fq4QRyTxLqG3D9v/rMUEyQ3v2Ko0RW1QIOW1wPw==
=0xC/
-----END PGP SIGNATURE-----




Archive powered by MHonArc 2.6.24.

Top of Page