We introduce a novel model of routing security that incorporates the ordinarily overlooked variations in trust that users have for different parts of the network. We focus on anonymous communication, and in particular onion routing, although we expect the approach to apply more broadly.

Today's software update systems have little or no defense against key compromise. As a result, key compromises have put millions of software update clients at risk. Here we identify three classes of information whose authenticity and integrity are critical for secure software updates. Analyzing existing software update systems with our framework, we find their ability to communicate this information securely in the event of a key compromise to be weak or nonexistent. We also find that the security problems in current software update systems are compounded by inadequate trust revocation mechanisms. We identify core security principles that allow software update systems to survive key compromise. Using these ideas, we design and implement TUF, a software update framework that increases resilience to key compromise.

We present Mixminion, a message-based anonymous remailer protocol with secure single-use reply blocks. Mix nodes cannot distinguish Mixminion forward messages from reply messages, so forward and reply messages share the same anonymity set. We add directory servers that allow users to learn public keys and performance statistics of participating remailers, and we describe nymservers that provide long-term pseudonyms using single-use reply blocks as a primitive. Our design integrates link encryption between remailers to provide forward anonymity. Mixminion works in a real-world Internet environment, requires little synchronization or coordination between nodes, and protects against known anonymity-breaking attacks as well as or better than other systems with similar design parameters.