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