Targeted attacks against network infrastructure are notoriously difficult to guard against. In the case of communication networks, such attacks can leave users vulnerable to censorship and surveillance, even when cryptography is used. Much of the existing work on network fault-tolerance focuses on random faults and does not apply to adversarial faults (attacks). Centralized networks have single points of failure by definition, leading to a growing popularity in decentralized architectures and protocols for greater fault-tolerance. However, centralized network structure can arise even when protocols are decentralized. Despite their decentralized protocols, the Internet and World-Wide Web have been shown both theoretically and historically to be highly susceptible to attack, in part due to emergent structural centralization. When single points of failure exist, they are potentially vulnerable to non-technological (i.e., coercive) attacks, suggesting the importance of a structural approach to attack-tolerance. We show how the assumption of partial trust transitivity, while more realistic than the assumption underlying webs of trust, can be used to quantify the effective redundancy of a network as a function of trust transitivity. We also prove that the effective redundancy of the wrap-around butterfly topology increases exponentially with trust transitivity and describe a novel concurrent multipath routing algorithm for constructing paths to utilize that redundancy. When portions of network structure can be dictated our results can be used to create scalable, attack-tolerant infrastructures. More generally, our results provide a theoretical formalism for evaluating the effects of network structure on adversarial fault-tolerance.
Previous work on incorporating network structure into trust models has focused on authentication protocols, showing that independent paths can reduce an adversary's ability to impersonate a target @cite_30 . Other work has shown that identifying independent paths in arbitrary networks is NP-hard and provided approximation algorithms @cite_26 . Our work complements these by introducing the partial trust assumption extending the focus beyond authentication. When network topology can be controlled, we sidestep the NP-hard problem of finding independent paths on arbitrary networks by using the mathematical structure of the butterfly topology to construct provably independent paths.
@cite_30 @cite_26
2109187517 202035697
We consider using trust information to improve the anonymity provided by onion-routing networks. In particular, we introduce a model of trust in network nodes and use it to design path-selection strategies that minimize the probability that the adversary can successfully control the entrance to and exit from the network. This minimizes the chance that the adversary can observe and correlate patterns in the data flowing over the path and thereby deanonymize the user. We first describe the general case in which onion routers can be assigned arbitrary levels of trust. Selecting a strategy can be formulated in a straightforward way as a linear program, but it is exponential in size. We thus analyze a natural simplification of path selection for this case. More importantly, however, when choosing routes in practice, only a very coarse assessment of trust in specific onion routers is likely to be feasible. Therefore, we focus next on the special case in which there are only two trust levels. For this more practical case we identify three optimal route-selection strategies such that at least one is optimal, depending on the trust levels of the two classes, their size, and the reach of the adversary. This can yield practical input into routing decisions. We set out the relevant parameters and choices for making such decisions. The ubiquity of the Internet has led to increased resource sharing between large numbers of users in widely-disparate administrative domains. Unfortunately, traditional identity-based solutions to the authorization problem do not allow for the dynamic establishment of trust, and thus cannot be used to facilitate interactions between previously-unacquainted parties. Furthermore, the management of identity-based systems becomes burdensome as the number of users in the system increases. To address this gap between the needs of open computing systems and existing authorization infrastructures, researchers have begun to investigate novel attribute-based access control (ABAC) systems based on techniques such as trust negotiation and other forms of distributed proving. To date, research in these areas has been largely theoretical and has produced many important foundational results. However, if these techniques are to be safely deployed in practice, the systems-level barriers hindering their adoption must be overcome. In this thesis, we show that safely and securely adopting decentralized ABAC approaches to authorization is not simply a matter of implementation and deployment, but requires careful consideration of both formal properties and practical issues. To this end, we investigate a progression of important questions regarding the safety analysis, deployment, implementation, and optimization of these types of systems. We first show that existing ABAC theory does not properly account for the asynchronous nature of open systems, which allows attackers to subvert these systems by forcing decisions to be made using inconsistent system states. To address this, we develop provably-secure and lightweight consistency enforcement mechanisms suitable for use in trust negotiation and distributed proof systems. We next focus on deployment issues, and investigate how user interactions can be audited in the absence of concrete user identities. We develop the technique of virtual fingerprinting, which can be used to accomplish this task without adversely affecting the scalability of audit systems. Lastly, we present TrustBuilder2, which is the first fully-configurable framework for trust negotiation. Within this framework, we examine availability problems associated with the trust negotiation process and develop a novel approach to policy compliance checking that leverages an efficient pattern-matching approach to outperform existing techniques by orders of magnitude.