{"id":{"repo_id":"denver","oai_identifier":"oai:digitalcommons.du.edu:etd-1185"},"canonical_url":"https://search.ndltd.org/etd/denver/oai:digitalcommons.du.edu:etd-1185","repository":{"repo_id":"denver","name":"University of Denver","base_url":"https://digitalcommons.du.edu/do/oai/"},"display":{"title":"Routing in the Dark: Pitch Black","abstract":"In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks, direct communication between nodes is limited to specific neighbors. Friendto-friend “darknet” networks have been shown to commonly have a small-world topology; while short paths exist between any pair of nodes in small-world networks, it is non-trivial to determine such paths with a distributed algorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient routing in such small-world networks. Herein this thesis we discuss the first independent security analysis of Clarke and Sandberg’s routing algorithm. We show that a relatively weak participating adversary can render the overlay ineffective without being detected, resulting in significant data loss due to the resulting load imbalance. We have measured the impact of the attack in a testbed of 800 and 400 total nodes using minor modifications to Clarke and Sandberg’s implementation of their routing algorithm in Freenet. Our experiments show that the attack is highly effective, allowing a small number of malicious nodes to cause rapid loss of data on the entire network. We also discuss various proposed countermeasures designed to detect, thwart or limit the attack. We found that the “darknet” topology limits the ability of effective countermeasures. The problem of fixing the topology proved so intractable due to inherent network characteristics that the idea of using a darknet for Freenet has ii been all but abandoned following the public release of this work. Our hope is that the presented analysis acts as a step towards effective analysis and design of secure distributed routing algorithms for restricted-route topologies. It should be noted that this thesis is an extended version of the same work presented at ACSAC 2007. The work appears in the conference proceedings as “Routing in the Dark: Pitch Black” [19] largely unmodified from this thesis.","abstract_html":"In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks, direct communication between nodes is limited to specific neighbors. Friendto-friend “darknet” networks have been shown to commonly have a small-world topology; while short paths exist between any pair of nodes in small-world networks, it is non-trivial to determine such paths with a distributed algorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient routing in such small-world networks. Herein this thesis we discuss the first independent security analysis of Clarke and Sandberg’s routing algorithm. We show that a relatively weak participating adversary can render the overlay ineffective without being detected, resulting in significant data loss due to the resulting load imbalance. We have measured the impact of the attack in a testbed of 800 and 400 total nodes using minor modifications to Clarke and Sandberg’s implementation of their routing algorithm in Freenet. Our experiments show that the attack is highly effective, allowing a small number of malicious nodes to cause rapid loss of data on the entire network. We also discuss various proposed countermeasures designed to detect, thwart or limit the attack. We found that the “darknet” topology limits the ability of effective countermeasures. The problem of fixing the topology proved so intractable due to inherent network characteristics that the idea of using a darknet for Freenet has ii been all but abandoned following the public release of this work. Our hope is that the presented analysis acts as a step towards effective analysis and design of secure distributed routing algorithms for restricted-route topologies. It should be noted that this thesis is an extended version of the same work presented at ACSAC 2007. The work appears in the conference proceedings as “Routing in the Dark: Pitch Black” [19] largely unmodified from this thesis.","abstract_has_math":false,"creators":["Evans, Nathan S."],"institution":null,"degree_name":"M.S.","degree_level":"Masters Thesis","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Christian Grothoff, Ph.D.","Richard Ball, Ph.D.","Chris Gauthier-Dickey","Ramakrishna Thurimella"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:54:41Z","subjects":["Dht","Freenet","P2p","Peer-to-peer","Restricted route","Security","Computer Sciences","Engineering"],"languages":["en"],"rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>","Nathan S. Evans"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/186","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.du.edu/etd/186","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.du.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.du.edu%3Aetd-1185","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Christian Grothoff, Ph.D.","Richard Ball, Ph.D.","Chris Gauthier-Dickey","Ramakrishna Thurimella"]},{"key":"dc:creator","label":"Author","values":["Evans, Nathan S."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2001-01-01T08:00:00Z"]},{"key":"dc:date.copyright","label":"Dc Date Copyright","values":["2009-06-01T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2009-06-01T07:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Dht","Freenet","P2p","Peer-to-peer","Restricted route","Security","Computer Sciences","Engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"]},{"key":"dc:rights.holder","label":"Dc Rights Holder","values":["Nathan S. Evans"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/186"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks, direct communication between nodes is limited to specific neighbors. Friendto-friend “darknet” networks have been shown to commonly have a small-world topology; while short paths exist between any pair of nodes in small-world networks, it is non-trivial to determine such paths with a distributed algorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient routing in such small-world networks. Herein this thesis we discuss the first independent security analysis of Clarke and Sandberg’s routing algorithm. We show that a relatively weak participating adversary can render the overlay ineffective without being detected, resulting in significant data loss due to the resulting load imbalance. We have measured the impact of the attack in a testbed of 800 and 400 total nodes using minor modifications to Clarke and Sandberg’s implementation of their routing algorithm in Freenet. Our experiments show that the attack is highly effective, allowing a small number of malicious nodes to cause rapid loss of data on the entire network. We also discuss various proposed countermeasures designed to detect, thwart or limit the attack. We found that the “darknet” topology limits the ability of effective countermeasures. The problem of fixing the topology proved so intractable due to inherent network characteristics that the idea of using a darknet for Freenet has ii been all but abandoned following the public release of this work. Our hope is that the presented analysis acts as a step towards effective analysis and design of secure distributed routing algorithms for restricted-route topologies. It should be noted that this thesis is an extended version of the same work presented at ACSAC 2007. The work appears in the conference proceedings as “Routing in the Dark: Pitch Black” [19] largely unmodified from this thesis."]},{"key":"dc:description.provenance","label":"Dc Description Provenance","values":["Received from ProQuest"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["84 p."]},{"key":"dc:title","label":"Title","values":["Routing in the Dark: Pitch Black"]}]}],"canonical_facts":{"dc:contributor":["Christian Grothoff, Ph.D.","Richard Ball, Ph.D.","Chris Gauthier-Dickey","Ramakrishna Thurimella"],"dc:creator":["Evans, Nathan S."],"dc:date.available":["2001-01-01T08:00:00Z"],"dc:date.copyright":["2009-06-01T07:00:00Z"],"dc:date.created":["2009-06-01T07:00:00Z"],"dc:description.abstract":["In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks, direct communication between nodes is limited to specific neighbors. Friendto-friend “darknet” networks have been shown to commonly have a small-world topology; while short paths exist between any pair of nodes in small-world networks, it is non-trivial to determine such paths with a distributed algorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient routing in such small-world networks. Herein this thesis we discuss the first independent security analysis of Clarke and Sandberg’s routing algorithm. We show that a relatively weak participating adversary can render the overlay ineffective without being detected, resulting in significant data loss due to the resulting load imbalance. We have measured the impact of the attack in a testbed of 800 and 400 total nodes using minor modifications to Clarke and Sandberg’s implementation of their routing algorithm in Freenet. Our experiments show that the attack is highly effective, allowing a small number of malicious nodes to cause rapid loss of data on the entire network. We also discuss various proposed countermeasures designed to detect, thwart or limit the attack. We found that the “darknet” topology limits the ability of effective countermeasures. The problem of fixing the topology proved so intractable due to inherent network characteristics that the idea of using a darknet for Freenet has ii been all but abandoned following the public release of this work. Our hope is that the presented analysis acts as a step towards effective analysis and design of secure distributed routing algorithms for restricted-route topologies. It should be noted that this thesis is an extended version of the same work presented at ACSAC 2007. The work appears in the conference proceedings as “Routing in the Dark: Pitch Black” [19] largely unmodified from this thesis."],"dc:description.provenance":["Received from ProQuest"],"dc:format":["application/pdf"],"dc:format.extent":["84 p."],"dc:identifier":["https://digitalcommons.du.edu/etd/186"],"dc:language":["en"],"dc:rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"],"dc:rights.holder":["Nathan S. Evans"],"dc:subject":["Dht","Freenet","P2p","Peer-to-peer","Restricted route","Security","Computer Sciences","Engineering"],"dc:title":["Routing in the Dark: Pitch Black"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["M.S."]},"updated_at":"2026-11-19T07:54:41Z"}