1Privacy TechnologiesInformation AssuranceFall 20062What is Privacy?• “The right to be let alone”• Confidentiality• Anonymity• Access Control• Most privacy technologies focus on Anonymity3What is anonymity?• Unobservability• Unlinkability• Sender anonymity• Receiver anonymity4Overview of Anonymity Concepts• Chaum’s MIX• Dining Cryptographers• Onion Routing• Crowds5Applications beyond privacy• Digital Cash• Anonymous e-voting• Censorship-resistant publishing• Untraceable e-mail6Chaum’s MIX• Presented first in 1981 by David Chaum• Uses public key cryptography for anonymous e-mail• Basic Idea:– E-mails would be sent to a “Mix” which would then forward them onto reciepents• Key building block for anonymity systems7ExampleABKm(B, KA(A,M))KA(A,M)8ExampleABCDEKm(B, KD(D,M))Km(B, KA(A,M))Km(E, KC(C,M))KC(C,M)KD(D,M)KA(A,M)9What does this buy us?• Unlinkability– The adversary knows all the senders and receivers but cannot link senders to receivers1 0MIX Cascade• What if some of the mixes are controlled by adversaries?• A cascade of mixes can be used to handle compromised mixes• How many adversaries can this withstand?– N-11 1Dining Cryptographers• Also introduced by Chaum• Purpose is to release a public message in a perfectly untraceable manner1 2The Protocol• N cryptographers are having dinner• Waiter tells them that the dinner has been paid for but they want to know whether it was one of them that paid or the NSA agent in the corner1 3The Protocol1. Each diner flips a coin and shows it to his left neighbor2. Each diner announces whether he and his neighbor’s coin flips are the same or different. The payer lies3. Odd number of “same” => NSA paperEven number of “same” => one the diners paid1 4Example – NSA PaysDifferentDifferentSameSame1 5Example – Diner paysPayerSameDifferentSameSame1 6Problems with DC• Very Impractical– Only one bit sent at a time– Each party has to have pairwise secure channels– Massive communication overhead1 7Communication overhead• For N ‘diners’• N messages sent to share coins• N broadcast messages to share• All this for 1 bit!• A message that is M bits long will take 2MN messages!1 8How much anonymity is afforded to the sender in DC?• We know the sender is one of n diners• This is called K-anonymity– We know you are one of k persons, but that’s the best we can do1 9Anonymity via Random Routing• Hide message source through random routing• Routers don’t know for sure who the source of the message is2 0Many methods• Onion routing• Crowds• Tor• …2 1Onion Routing• Sender choices a random sequence of routers– Some are honest, some aren’t– Similar to mix cascade• Goal: Hostile routers shouldn’t learn Alice is talking to Bob2 2The Onion• Similar to a message sent in a mix• Layers of encryption are used.• Alice wants to send Bob a message through R1, R2, R3, and R4{M}pk(B){B,K4}pk(R4){ }K4{R4,K3}pk(R3){ }K3{R3,K2}pk(R2){ }K2{R2,K1}pk(R1){ }K12 3Crowds• Routers form a random path– Different then onion routing because the routers choose path, not sender• After receiving a message router flips a biased coin– With probability p, the router forwards the message to another router– With probability 1-p, the router forwards the message to the recipient2 4ExampleR1R2R3R4RRRRAliceBob2 5Probabilistic Notions of Anonymity• Beyond suspicion– The observed source of the message is no more likely to be the true sender than anybody else• Probable innocence– Probability that the observed source of the message is the true sender is less than 50%– Guaranteed by Crowds if there are sufficiently many honest routers: Ngood+Nbad ≥ pf/(pf-0.5)•(Nbad +1)• Possible innocence– Non-trivial probability that the observed source of the message is not the true sender2 6A Couple of issues• Is probable innocence enough?1% 1% 1% 49% 1% 1% … 1%• Multiple-paths vulnerability– Can attacker relate multiple paths from same sender?• E.g., browsing the same website at the same time of day– Each new path gives attacker a new observation– Can’t keep paths static since members join and leave2 7Digital Cash• Cash is a universally anonymous payment system• How can we have anonymous payments online?• Idea– Alice can pay for something with a digital cash token– If she uses the same token her identity should be revealed2 8Blind signatures• Blind signatures are used when you want someone to sign something but you don’t want them to see what they are signing– E.x. A notary• This is done by multiplying the message by a secret number (called blinding).• The signer signs the blinded message• The secret number can be divided out to get a signed version of the message2 9RSA Blind Signatures• Alice wants Bob to sign message M.• She gives him M*rebmod n• Bob signs this giving Alice s’=(M*reb)dbmod n• Alice can then remove the blind by calculating s= s’*r-1 mod n– s = s’*r-1 = (M*reb)db*r-1 = Mdb*reb*db*r-1=Mdb3 0Example• Alice’s Message: 28• Bob’s public key: 17• Bob’s private key: 53 (n = 77)• Alice asks Bob to sign 70(=28*617 mod 77)• Bob signs 70 and sends Alice 42• Alice multiplies 42 by 13 (mod 77) to get 7– 2853mod 77 = 73 1Getting Cash• Alice creates a bunch (lets say N) of money orders for the same amount (say $100)– Each is given a unique identifier– Each also includes an n pairs of identity bit strings$100ID: 1234567Identity bit strings: I1 = (I1L, I1R)I2= (I2L, I2R). . .In= (InL, InR)3 2How the identity bit strings were created• Secret splitting!• How it works:– Alice created an identity I– She then picked n random numbers: r1…rn– Then she calculates sj= I ⊕ rj– Ij= (sj, rj)– Not that for all j, I = sj⊕ rj3 3Getting Cash • Alice blinds these messages and sends them to the bank to sign• The bank asks Alice to unblind N-1 messages (banks choice)• Alice complies and when the banks sees they are all “well formed” then sign the remaining money order• Alice unblinds this remaining (signed) money order and spends it3 4Spending Cash• Alice presents a token to a merchant• The merchant asks Alice to randomly reveal either the right or left half of each identity bit string– Essentially they send her a random bit string of length n, called a selector
View Full Document
Unlocking...