Skip to Content.
Sympa Menu

bluesky - weak secure IDs

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: Wei Dai <weidai AT weidai.com>
  • To: bluesky AT franklin.metalab.unc.edu
  • Subject: weak secure IDs
  • Date: Sun, 29 Sep 2002 18:12:02 -0400


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




Archive powered by MHonArc 2.6.24.

Top of Page