Secure routing for structured peer-to-peer overlay networks (by Castro et al.)The problemIn retrospectThe modelSub-problemsCertified nodeIDsSecure routing table maintenanceOne solution for Pastry: two routing tablesSecure message forwardingProbability of routing to a correct replica b=4Proposed SolutionRouting failure testThe test for PastryRedundant routingPerformance of redundant routing 100,000 nodes, b=4, l=r=32Etc.Secure routing for structured peer-to-peer overlay networks(by Castro et al.)Shariq RizviCS 294-4: Peer-to-Peer SystemsOct 6, 2003 CS 294-4: Peer-to-Peer Systems 2The problemP2P systems: resilient but not secureMalicious nodes:fake IDsdistort routing table entriesprevent correct message delivery“Techniques to allow nodes to join, to maintain routing state, and to forward messages securely in presence of malicious nodes”Oct 6, 2003 CS 294-4: Peer-to-Peer Systems 3In retrospectUnlike Byzantine solutionsspecific to P2P systemsno exact agreement needs to be reachedUnlike the Sybil attackresort to central authentication for IDsOct 6, 2003 CS 294-4: Peer-to-Peer Systems 4The modelN nodesBound f on the fraction of faulty nodesBound cN on the number of faulty nodes in coalitionEvery node has a static IP address“Secure routing ensures that when a non-faulty node sends a message to key k, the message reaches all non-faulty members is the set of replica roots Rk with very high probability”Oct 6, 2003 CS 294-4: Peer-to-Peer Systems 5Sub-problemsSecurely assigning IDs to nodesattacker may capture all replicas for an objectattacker may target a particular victim Securely maintaining routing tablesattackers may populate with faulty entriesmost messages are routed to faulty nodesSecurely forwarding messageseven with proper routing tables, faulty nodes can corrupt, drop, misroute messagesOct 6, 2003 CS 294-4: Peer-to-Peer Systems 6Certified nodeIDsOffline certification authoritiesassign random IDs to nodescertificate binds the ID to public key and IPattacker cannot swap IDs between his nodesbad for dynamic address assignment, host mobility, or organizational changesCAN nodeIDs change when nodes join and departAvoid giving multiple IDs to one entitycharge for each certificate – increases cost of attackbind IDs to existing trustworthy identitiesOct 6, 2003 CS 294-4: Peer-to-Peer Systems 7Secure routing table maintenanceShould have at most fraction f of faulty entriesworst for row 0 of the Pastry routing tableduring node joins, probability of getting a faulty entry is (1 - f) x f + f x 1 > fImpose constraints on the table entryrequired to be closest to some point in ID spacelike ChordOct 6, 2003 CS 294-4: Peer-to-Peer Systems 8One solution for Pastry: two routing tablesNormal locality-aware routing tableA constrained routing tableRow l, column d entry for node i:shares a prefix of length l with Ihas d as its (l+1) st digitclosest nodeID to the point p: p satisfies above properties and has remaining digits same as iNew state initialization algorithm exploiting an interesting propertyOct 6, 2003 CS 294-4: Peer-to-Peer Systems 9Secure message forwardingProbability of routing successfully between two non-faulty nodes is (1-f)h-1h is log2b(N) for PastryProbability of routing correctly to a non-faulty replica root is (1-f)hTradeoff: increasing b decreases the number of hops but also increases the amount of state informationOct 6, 2003 CS 294-4: Peer-to-Peer Systems 10Probability of routing to a correct replicab=4Oct 6, 2003 CS 294-4: Peer-to-Peer Systems 11Proposed SolutionHas to ensure that with high probability, one copy of the message reaches each replica root1. Route message to the key2. Root node returns prospective set of replica roots3. Did routing work? (failure test)Yes: use these as replica rootsNo: use expensive redundant routingOct 6, 2003 CS 294-4: Peer-to-Peer Systems 12Routing failure testTakes a key and the set of prospective replica rootsReturns negative if the set of roots is likely to be correct for the key; otherwise positiveIf no set is returned, returns positiveWorks by comparing the density of nodeIDs in the sender’s neighborhood set with the density of nodeIDs close to the replica roots of the destination keyOct 6, 2003 CS 294-4: Peer-to-Peer Systems 13The test for PastryIn Pastry, the replica set is a subset of the neighbor set of the key’s rootLet µp be the average numerical distance between the consecutive nodeIDs in p’s neighbor setTo test root neighbor set {id0, id1, …}, for a key x, p checks that:1. All nodeIDs in the set have valid certificates, the middle one is the closest nodeID to x, and the nodeIDs satisfy the definition of a neighbor set2. The average numerical distance µrn between consecutive nodeIDs in this set < µp x γγ decides the tradeoff between false positives and false negativesOct 6, 2003 CS 294-4: Peer-to-Peer Systems 14Redundant routingIf the failure test returns positiveUse constrained routing tableP sends the message to key x via different members of its neighborhood setmessages take diverse path (longer paths?)Any non-faulty node that receives the message and has the root of x in its neighborhood set, sends its certificate to pp collects such certificates in a list; sends the list to all nodes in the list. Process iterates upto 3 timesp computes the closest neighbor’s to xOct 6, 2003 CS 294-4: Peer-to-Peer Systems 15Performance of redundant routing100,000 nodes, b=4, l=r=32Oct 6, 2003 CS 294-4: Peer-to-Peer Systems 16Etc.Tolerates upto 25% malicious nodes wellSelf-certifying data – nodes can check the authenticity of returned objectsreduces need for redundant
View Full Document
Unlocking...