Mixminion: Design of a Type III Anonymous Remailer ProtocolGeorge DanezisUniversity of [email protected] DingledineThe Free Haven [email protected] MathewsonThe Free Haven [email protected] present Mixminion, a message-based anonymous re-mailer protocol with secure single-use reply blocks. Mixnodes cannot distinguish Mixminion forward messages fromreply messages, so forward and reply messages share thesame anonymity set. We add directory servers that allowusers to learn public keys and performance statistics of par-ticipating remailers, and we describe nymservers that pro-vide long-term pseudonyms using single-use reply blocksas a primitive. Our design integrates link encryption be-tween remailers to provide forward anonymity. Mixminionworks in a real-world Internet environment, requires littlesynchronization or coordination between nodes, and pro-tects against known anonymity-breaking attacks as well asor better than other systems with similar design parameters.1. OverviewChaum first introduced anonymous remailers over 20years ago [7]. The research community has since intro-duced many new designs and proofs [1, 14, 16, 19, 28, 29],and discovered a variety of new attacks [3, 5, 6, 9, 23, 35].But because many of the newer designs require considerablecoordination, synchronization, bandwidth, or processing re-sources, deployed remailers still use Cottrell’s Mixmasterdesign from 1994 [8, 26]. Here we describe Mixminion, aprotocol for asynchronous, loosely federated remailers thatmaintains Mixmaster’s flexibility while addressing the fol-lowing flaws:• Replies: Mixmaster does not support replies or anony-mous recipients — people who want these functionsmust use the older and less secure Cypherpunk TypeI remailer design [31], which is vulnerable to replayattacks. We introduce a new primitive called a single-use reply block (SURB), which makes replies as se-cure as forward messages. Furthermore in Mixminionthe remailers themselves cannot distinguish reply mes-sages from forward messages. We also describe howto use these SURBs to securely build higher-level sys-tems such as nymservers. By integrating reply capa-bilities into Mixminion, we can finally retire the TypeI remailer network.• Forward anonymity: Mixmaster uses SMTP (normalmail) for transport. We use TLS over TCP for linkencryption between remailers and use ephemeral keysto ensure forward anonymity for each message. Linkencryption also blocks many active and passive attackson the communication links.• Replay prevention and key rotation: If an adversaryrecords the input and output batches of a mix and thenreplays a message, that message’s decryption will re-main the same. Thus an attacker can completely breakthe security of the mix-net [7]. Mixmaster 2.0 offeredreplay prevention by keeping a list of recent messageIDs — but because it expired old entries to keep thelist short, the adversary simply has to wait until themix has forgotten a message and replay it. Newer ver-sions of Mixmaster keep a replay cache and also dis-card messages more than a certain number of days old.To block timestamp attacks, clients randomly add orsubtract a few days from the timestamp. But this ap-proach may still be open to statistical attacks; see Sec-tion 5.4. Mixminion instead counters replays by intro-ducing key rotation: a message is addressed to a givenkey, and after the key changes no messages to the oldkey will be accepted, so the mix can forget about allthe messages addressed to old keys. The number ofIDs a node needs to remember between key rotationsis not too great a burden.• Exit policies: Exit abuse is a serious barrier to wide-scale remailer deployment: most Internet ServiceProviders (ISPs) do not tolerate systems that poten-tially deliver hate mail, etc. Mixminion provides aconsistent mechanism for each node to specify and ad-vertise an exit policy. We further describe a protocolwhich allows recipients to opt out of receiving mailfrom remailers, but at the same time makes it difficultfor an adversary to deny service to interested recipi-ents.• Integrated directory servers: Mixmaster uses sev-eral ad hoc approaches to distribute information aboutremailer availability, performance, and keys. But thefact that users and remailers operate with different in-formation introduces partitioning attacks. Mixminionuses a small group of synchronized redundant direc-tory servers to provide uniform information about thenetwork.• Dummy traffic: Cottrell briefly mentions dummymessages in [8], but they are not part of the specifica-tion [26]. Mixminion uses a simple dummy policy fornow, but because we use our own transport, we supportmany link padding and dummy traffic schemes.We review mixes and mix-nets in Section 2, describe ourgoals and assumptions in Section 3, and then address theabove list of improvements in Sections 4-7. We then sum-marize how our design stands up to known attacks, and con-clude with a list of open problems.2. BackgroundChaum introduced the concept of using relay servers, ormixes, for anonymous communications [7]. Each mix hasa public key which senders use to encrypt messages to it.The mix accumulates a batch of these encrypted messages,decrypts them, and delivers them. Because a decrypted out-put message looks nothing like the original encrypted inputmessage, and because the mix collects a batch of messagesand then sends out the decrypted messages in a rearrangedorder, an observer cannot learn which incoming messagecorresponds to which outgoing message. Chaum showedthe security of a mix against a passive adversary who eaves-drops on all communications but is unable to observe thereordering inside the mix. Pfitzmann fixed a weakness inChaum’s original scheme based on the properties of rawRSA encryption [32].However, trusting a single mix is dangerous: the mix it-self could be controlled by an adversary. Therefore userssend their messages through a series of mixes: if someof the mixes are honest (not run by the adversary), someanonymity is preserved. In some schemes, such as Mix-master [26] and Babel [14], the sender chooses the mixesthat make up her message’s path. Specifically, when Al-ice wants to send an anonymous message to Bob throughmixes M1, M2, and M3, she encrypts her message succes-sively with the public keys of the mixes in reverse order.She includes routing information at each hop, so that eachmix Mireceives the address of Mi+1along with
View Full Document
Unlocking...