Skip to Content.
Sympa Menu

bluesky - Re: weak secure IDs

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: Stephen Blackheath <stephen AT blacksapphire.com>
  • To: Wei Dai <weidai AT weidai.com>, "Global-Scale Distributed Storage Systems" <bluesky AT franklin.oit.unc.edu>
  • Cc: Anthony Jones <ajones AT clear.net.nz>, Ross Smith <ross AT smithii.com>
  • Subject: Re: weak secure IDs
  • Date: Mon, 14 Oct 2002 11:22:39 +1300


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Wei Dai,

Hello there! I'm the Grapevine Project guy (along with Ross Smith and
Anthony
Jones), and as you know, we're using your Crypto++ library. I keep meaning
to thank you for it, so here it is: Thank you! Crypto++ is great code and
is perfect for us.

Your weak secure IDs is very helpful to us, because we're using an approach
along similar lines (which we call "Solve A Hard Problem"). Our basic
approach is the same as yours. And, as you've realized, the basic approach
needs to have added to it some way of deciding which nodes to reject. Take a
look at this page under the heading 'SAHP #3' to see one of our proposed
solutions to this problem:

http://grapevine.sourceforge.net/designnotes.php

Currently we're using a very simple variant whereby we just reject any nodes
that are less than a certain hard-coded level, but we intend to improve this
later. The approach on the link above is a sort of inner/outer sanctum idea
- - that a portion of the network is only visible to the highest level nodes,
and the rest of the nodes have no way of even seeing them and can only guess
how many there are. (I don't claim that this idea is original.)

One comment I would make about your idea: the most productive way to defeat
it that I can see is to attack the network with a small number of high-level
nodes rather than a large number of low-level nodes. I think the problem
(which the proposal above also suffers from) is that although you can (or
rather have to) assume the overall processing power available to attackers is
less than that of legitimate nodes, you cannot assume that cancer nodes will
not be among the high-level nodes.

We originally thought about detecting cancer nodes through "reputation
strategies" (as you describe), but we're moving more towards treating cancer
nodes as just another source of unreliability in the network to be worked
around. In other words, we don't try to detect them, because we figure that
if the attacker is clever enough, they will find ever more subtle ways to
fool our detection.

So, we're using a forward error correction-based approach where if a
particular region of the network has been taken down by a cancer node, we
simply use another region instead.

Your idea is great, because it contributes in an area in which we're still a
little stuck. So - the main purpose of this email is to tell you we want our
project to be as open as possible. In other words, to you and to everyone:
More ideas, please! We need them! You will be contributing to a project
that is not that far from showing some results. And if we use your idea, we
will credit you.

And please, everyone - our website has plenty of technical stuff, so take a
look:

http://www.grapevineproject.org/


Steve

On Mon, 30 Sep 2002 10:12, you wrote:
> (I found the term "weak secure IDs" at
> http://iris.lcs.mit.edu/talks/dht-long1.ppt. Does anyone know where it
> originated from?)
>
> The goals of a weak secure ID scheme are (1) to make it costly for an
> attacker to present new identities and (2) to make it difficult for an
> attacker to target a specific ID or range of IDs (which in systems like
> Tapestry translates to responsibility over specific regions in the logical
> address space). It's a decentralized alternative to random IDs assigned
> one to each physical node by a globally trusted party. It's assumed that
> the system using weak secure IDs has enough redundancy to tolerate a
> limited amount of damage, and that malicious nodes can be detected, and
> their IDs blacklisted (in some decentralized way), so that the amount of
> damage that can be done by each weak secure ID is limited.
>
> The Chord project proposed using hashes of IP addresses as weak secure
> IDs, on the assumption that an attacker controls limited number of IP
> addresses. Here I propose an alternative weak secure ID scheme, on the
> assumption that the attacker has limited CPU power. This seems to be a
> safer assumption in the long run, since with IPv6 an attacker can easily
> have control over more IP addresses than the number of honest nodes.
>
> To generate an ID, first generate a public key P and compute its secure
> hash K = H(P). Then find ID_b such that H(b | K | ID_b) shares a b-bit
> prefix with K. Join the system using ID_b as your level-b secure ID. Now,
> using a low-priority thread, for i from b+1 to the length of K, find ID_i
> such that H(i | K | ID_i) shares a i-bit prefix with K. When a new ID_i
> found, withdraw from the system and rejoin using ID_i (which has level-i
> security).
>
> The security levels of the IDs are used as follows. Each routing node
> starts up at level-b security, which means it accepts nodes with level-b
> or above IDs into its routing tables. It maintains a black list of nodes
> that it no longer trusts (they are removed from its routing tables) and
> evidence showing that they are malicious. When the size of the black list
> reaches some threshold, it upgrades to level-b+1 security, which means it
> stops trusting all level-b IDs and removes all nodes with level-b IDs from
> its routing tables and black list. It must itself have a level-b+1 or
> above ID first, otherwise it withdraws as a router from the network until
> it generates a level-b+1 ID. This process may be repeated as the black
> list grows again. (Note that you don't need a weak secure ID to query the
> system, only to provide services. Queries can be secured using
> hashcash/client puzzles.)
>
> As an attacker inserts malicious nodes into the system, the security
> levels of honest routers are increased, until some equilibrium is reached
> where the computational cost of generating new IDs falls below the benefit
> (to the attacker) of the damage a malicious node can do. It's hoped that
> the amount of computing power of the attacker is small enough compared to
> the honest nodes in aggregate, that this equilibrium is reached
> before the system becomes unusable.
>
> ---
> You are currently subscribed to bluesky as: stephen AT blacksapphire.com
> For list information visit http://www.transarc.ibm.com/~ota/bluesky/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9qfIvODO5z8eA7sQRAmbDAJ95VEetnuWpvj+OLPtIRv5Puz82oACePzsP
iDv7KH+Yf3jS7UEsOJX/D8s=
=nQfG
-----END PGP SIGNATURE-----




  • Re: weak secure IDs, Stephen Blackheath, 10/13/2002

Archive powered by MHonArc 2.6.24.

Top of Page