Protocols for AnonymityOverviewApplications of AnonymityChaum’s MIXBasic MIX DesignAnonymous Return AddressesMix CascadeDining CryptographersThree-Person DC ProtocolNon-Payer’s View: Same CoinsNon-Payer’s View: Different CoinsSuperposed SendingDC-Based Anonymity is ImpracticalWhat is Anonymity?Definitions of AnonymityAnonymity and Knowledgek-AnonymityAbsolute AnonymityIdentities Are Not EnoughAnonymity via Randomized RoutingOnion RoutingThe OnionCrowds SystemProbabilistic Notions of AnonymityA Couple of IssuesDeployed Anonymity SystemsCS 395TProtocols for AnonymityOverviewBasic concepts of anonymity• Chaum’s MIX• Dining cryptographers• Knowledge-based definitions of anonymityProbabilistic anonymity• Onion routing• CrowdsIntroduction to probabilistic model checking• Using a probabilistic model checker to analyze randomized routing protocolsApplications of AnonymityPrivacy• Hide online transactions, Web browsing, etc. from intrusive governments, corporations and archivistsDigital cash• Electronic currency with properties of paper moneyAnonymous electronic votingCensorship-resistant publishingUntraceable electronic mailCrypto-anarchy• “Some people say `anarchy won't work’. That's not an argument against anarchy; that's an argument against work.” – Bob BlackGood topic for a projectGood topic for a projectChaum’s MIXEarly proposal for anonymous email• David Chaum. “Untraceable electronic mail, return addresses, and digital pseudonyms”. Communications of the ACM, February 1981.Public key crypto + trusted re-mailer (MIX)• Untrusted communication medium• Public keys used as persistent pseudonymsModern anonymity systems use MIX as the basic building blockBefore spam, people thought anonymous email was a good ideaBasic MIX DesignACDEBMIX{r1,{r0,M}pk(B),B}pk(mix){r0,M}pk(B),B{r2,{r3,M’}pk(E),E}pk(mix){r4,{r5,M’’}pk(B),B}pk(mix){r5,M’’}pk(B),B{r3,M’}pk(E),EAdversary knows all senders and all receivers, but cannot link a sentmessage with a received messageAnonymous Return AddressesM includes {K1,A}pk(mix),K2where K2is a fresh public key {r1,{r0,M}pk(B),B}pk(mix){r0,M}pk(B),BBMIXResponse MIX{K1,A}pk(mix),{r2,M’}K2A,{{r2,M’}K2}K1ASecrecy without authentication(good for an online confession service)Mix CascadeMessages are sent through a sequence of mixesSome of the mixes may be controlled by adversary, but even a single good mix guarantees anonymityNeed traffic padding and buffering to prevent timing correlation attacksDining CryptographersClever idea how to make a message public in a perfectly untraceable manner• David Chaum. “The dining cryptographers problem: unconditional sender and recipient untraceability.”Journal of Cryptology, 1988.Guarantees information-theoretic anonymity for message senders• This is an unusually strong form of security: defeats adversary who has unlimitedcomputational powerImpractical, requires huge amount of randomness• In group of size N, need N random bits to send 1 bitThree-Person DC ProtocolThree cryptographers are having dinner.Either NSA is paying for the dinner, or one of them is paying, but wishes to remain anonymous.1. Each diner flips a coin and shows it to his left neighbor.• Every diner will see two coins: his own and his right neighbor’s.2. Each diner announces whether the two coins are the same. If he is the payer, he lies (says the opposite).3. Odd number of “same” ⇒ NSA is paying;even number of “same” ⇒ one of them is paying• But a non-payer cannot tell which of the other two is paying!Non-Payer’s View: Same Coins?“same” “different”payerpayer?“same” “different”Without knowing the coin tossbetween the other two, non-payercannot tell which of them is lyingNon-Payer’s View: Different Coins?“same” “same”payerpayer?“same” “same”Without knowing the coin tossbetween the other two, non-payercannot tell which of them is lyingSuperposed SendingThis idea generalizes to any group of size NFor each bit of the message, every user generates 1 random bit and sends it to 1 neighbor• Every user learns 2 bits (his own and his neighbor’s)Each user announces (own bit XOR neighbor’s bit)Sender announces (own bit XOR neighbor’s bit XOR message bit)XOR of all announcements = message bit• Every randomly generated bit occurs in this sum twice (and is canceled by XOR), message bit occurs onceDC-Based Anonymity is ImpracticalRequires secure pairwise channels between group members• Otherwise, random bits cannot be sharedRequires massive communication overhead and large amounts of randomnessDC-net (a group of dining cryptographers) is robust even if some members cooperate• Guarantees perfect anonymity for the other membersA great protocol to analyze• Difficult to reason about each member’s knowledgeWhat is Anonymity?FBI intercepted three emails and learned that …Two of the emails came from the same accountEmails are not in EnglishThe recipients are [email protected], Dick Tracy and Osama Bin Laden, but it’s not known who received which emailEmails were routed via Anonymizer.comWrong question: has “anonymity” been violated?Right question: what does FBI actually know?Definitions of Anonymity“Anonymity is the state of being not identifiable within a set of subjects.”• There is no such thing as absolute anonymityUnlinkability of action and identity• E.g., sender and his email are no more related within the system than they are related in a-priori knowledgeUnobservability• Any item of interest (message, event, action) is indistinguishable from any other item of interest“Anonymity is bullshit” - Joan FeigenbaumAnonymity and KnowledgeAnonymity deals with hiding information• User’s identity is hidden• Relationship between users is hidden• User cannot be identified within a set of suspectsNatural way to express anonymity is to state what the adversary should not know• Good application for logic of knowledge• Not supported by conventional formalisms for security (process calculi, I/O automata, …)To determine whether anonymity holds, need some representation of [email protected]@cave.af12WhatactuallyhappenedSender suspects( ) = Alice or Charlie1Sender suspects( ) = Bob or Charlie2Whatattackerknows2-anonymity for senders:2 plausible senders
View Full Document