The Grapevine Project

David Hopwood david.hopwood@zetnet.co.uk
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 w=
ant to
> > > insert the data.  Even if you can insert one file in a particular a=
rea of
> > > keyspace you would need to insert a large number of files in a smal=
l 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 can=
not
> > 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 tak=
e 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 probl=
em
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 preve=
nt
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 eno=
ugh
to protect against a DoS attack.

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


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

- -- =

David Hopwood <david.hopwood@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 0=
1
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 b=
een
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=3D=3D
=3D0xC/
-----END PGP SIGNATURE-----