Network coordinate systems allow a node to estimate the network latency between any pair of nodes on the Internet, without having to directly contact the nodes. Existing network coordinate systems have been shown to be very accurate in predicting network distances, and efficient with low computational and communication overhead. However, a malicious node participating in the system can lie about either its network coordinates or its network latency to other nodes, with the end result being to disrupt the whole system, making it inaccurate in predicting network latencies, or isolating targeted victims from the rest of the network. Over the past few years, several schemes have been proposed to secure network coordinate systems. They can be categorized in two: 1) statistical methods that try to filter out malicious peers, and 2) non-statistical methods such as reputation systems to ensure that nodes' reported coordinates are correct and verified.
The main contributions of this thesis are to 1) introduce a new attack, the Frog-Boiling attack that bypasses all the "secure" schemes previously designed, 2) define a security model and realistic threat model, 3) show how insecure network coordinates can be mis-used to attack a real application, such as hijacking the routing layer of the Vuze BitTorrent client, and 4) propose two secure designs; the first one, Treeple is provably secure under our model while providing accurate estimations, and the second scheme, KoNKS is secure on an average-case but provides a completely decentralized solution to network coordinates, and can be used as a "base" for existing secure network coordinate schemes.