Protocols for Anonymity CS 259Vitaly ShmatikovOverview◆Basic concepts of anonymity•Chaum’s MIX•Dining cryptographers•Knowledge-based definitions of anonymity◆Probabilistic anonymity•Onion Routing•Crowds◆Introduction to probabilistic model checking•Using a probabilistic model checker to analyze CrowdsApplications of Anonymity◆Privacy•Hide online transactions, Web browsing, etc. from intrusive governments, corporations and archivists◆Digital cash•Electronic currency with properties of paper money◆Anonymous electronic voting◆Censorship-resistant publishing◆Untraceable electronic mail◆Crypto-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 MIX◆Early 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 pseudonyms◆Modern 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 sent message with a received messageAnonymous Return AddressesABMIX{r1, {r0,M}pk(B),B}pk(mix){r0,M}pk(B),BM includes {K1,A}pk(mix),K2 where K2 is a fresh public key Response MIX{K1,A}pk(mix),{r2,M’}K2A,{{r2,M’}K2}K1Secrecy without authentication(good for an online confession service)MIX Cascade◆Messages are sent through a sequence of MIXes◆Some of the mixes may be controlled by adversary, but even a single good mix guarantees anonymity◆Need traffic padding and buffering to prevent timing correlation attacksDining Cryptographers◆Clever 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 unlimited computational power◆Impractical, 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.5. 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.6. Each diner announces whether the two coins are the same. If he is the payer, he lies (says the opposite).7. 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 lying?Non-Payer’s View: Different Coins“same” “same”payerpayerWithout knowing the coin tossbetween the other two, non-payercannot tell which of them is lying?“same” “same”Superposed Sending◆This idea generalizes to any group of size N◆For 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 Impractical◆Requires secure pairwise channels between group members•Otherwise, random bits cannot be shared◆Requires massive communication overhead and large amounts of randomness◆DC-net (a group of dining cryptographers) is robust even if some members cooperate•Guarantees perfect anonymity for the other members◆A great protocol to analyze•Difficult to reason about each member’s knowledgeWhat is Anonymity?◆Two of the emails came from the same account◆Emails are not in English◆The recipients are [email protected], Dick Tracy and Osama Bin Laden, but it’s not known who received which email◆Emails were routed via Anonymizer.comFBI intercepted three emails and learned that …Wrong 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 anonymity◆Unlinkability of action and identity•E.g., sender and his email are no more related within the system than they are related in a-priori knowledge◆Unobservability•Any item of interest (message, event, action) is indistinguishable from any other item of interest◆“Anonymity is bullshit” - Joan FeigenbaumAnonymity and Knowledge◆Anonymity deals with hiding information•User’s identity is hidden•Relationship between users is hidden•User cannot be identified within a set of suspects◆Natural 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.af12Sender suspects( ) = Alice or Charlie1Sender suspects( ) = Bob or Charlie2WhatactuallyhappenedWhatadversaryknows2-anonymity for senders:2 plausible senders for each messageAbsolute AnonymityAliceBobCharlie12Sender suspects( ) = Alice, Bob or Charlie1Sender suspects( ) = Alice, Bob or Charlie2WhatactuallyhappenedWhatattackerknowsabsolute sender anonymity:every agent is a plausible sender for every [email protected]@cave.afIdentities Are Not EnoughAliceBobCharlie12Sender suspects( ) = Alice, Bob or Charlie1Sender suspects( ) = Alice, Bob or Charlie2WhatactuallyhappenedWhatattackerknows3Sender( ) = Sender( ) 23We need to be able toexpress this
View Full Document
Unlocking...