re nsdi06 slides

RE: Reliable Email: 

RE: Reliable Email Michael Kaminsky (Intel Research Pittsburgh) Scott Garriss (CMU) Michael Freedman (NYU/Stanford) Brad Karp (University College London) David Mazières (Stanford) Haifeng Yu (Intel Research Pittsburgh/CMU)

Motivation: 

Motivation Spam is a huge problem today More than 50% of email traffic is spam. Large investment by users/IT organizations ($2.3b in 2003 on increased server capacity) But, more importantly…

Email is no longer reliable: 

Email is no longer reliable Users can't say what they want any more Ex: Intel job offer goes to spam folder Ex: Discussion about spam filtering Goal: Improve email's reliability

Outline: 

Outline Background / Related Work Design Social networks and Attestations Preserving Privacy Re: in Practice Evaluation Implementation Conclusion

Basic Terminology: 

Basic Terminology False Positives (FP) Legitimate email marked as spam Can lose important mail Email less reliable False Negatives (FN) Spam marked as legitimate email Annoying and/or offensive

A Typical Spam Defense System: 

A Typical Spam Defense System

Related Work: 

Related Work People use a variety of techniques Content filters (SpamAssassin, Bayesian) Payment/proof-of-work schemes Sender verification Blacklists Human-based (collaborative) filtering Whitelists Re: is complementary to existing systems. Idea: Whitelist friends of friends

Traditional Whitelist Systems: 

Traditional Whitelist Systems Alice Bob From: Charlie Traditional WLs suffer from two problems: Spammers can forge sender addresses

Traditional Whitelist Systems: 

Traditional Whitelist Systems Alice Bob From: Alice Whitelist Debby Tom Traditional WLs suffer from two problems: Spammers can forge sender addresses Whitelists don’t help with strangers Use anti-forgery mechanism to handle (1), similar to existing techniques. Handle (2) with social networks

Approach: Use Social Networks: 

Approach: Use Social Networks Bob (B) Alice (A) trust Attestation: B→A A is a friend of B B trusts A not to send him spam Bob whitelists people he trusts Bob signs attestation B→A No one can forge attestations from Bob Bob can share his attestations Accept!

Approach: Use Social Networks: 

Approach: Use Social Networks Bob (B) Alice (A) Charlie (C) trust trust What if sender & recipient are not friends? Note that B→A and A→C B trusts C because he's a friend-of-friend (FoF) FoF trust relationship Accept?

Find FoFs: Attestation Servers: 

Find FoFs: Attestation Servers Charlie (C) Bob (B) Charlie’s Attestation Server (AS) Recipient (Bob) queries sender’s attestation server for mutual friends… Sharing attestations reveals your correspondents! Note: no changes to SMTP, incremental deployment A→C

Privacy Goals: 

Privacy Goals B’s list of friends Email recipients never reveal their friends Email senders only reveal specific friends queried for by recipients Only users who have actually received mail from the sender can query the sender for attestations Charlie (C) Bob (B) Charlie’s AS C’s list of friends Debby FoF Query X X X

Outline: 

Outline Background / Related Work Design Social networks and Attestations Preserving Privacy Re: in Practice Evaluation Implementation Conclusion

Cryptographic Private Matching: 

Cryptographic Private Matching Recipient (R) friends Sender (S)’s AS friends

PM Details: 

PM Details First implementation & use of PM protocol Based on our previous work [Freedman04] Attestations encoded in encrypted polynomial Uses Homomorphic Encryption Ex: Paillier, ElGamal variant enc(m1+m2) = enc(m1) ∙ enc(m2) enc(c ∙ m1) = enc(m1)c

Restricting FoF Queries: 

Restricting FoF Queries Sender (S) Recipient (R) Signed authentication token Sender can use token to restrict FoF query Users have a public/secret key pair

Restricting FoF Queries: 

Restricting FoF Queries Sender (S) Recipient (R) Sender’s Attestation Server (AS) FoF Query Sender can use token to restrict FoF query Users have a public/secret key pair Recipient can use token to detect forgery

Outline: 

Outline Background / Related Work Design Social networks and Attestations Preserving Privacy Re: in Practice Evaluation Implementation Conclusion

Scenario 1: Valid Mail Rejected: 

Scenario 1: Valid Mail Rejected Mail Server Spam Assassin Mail Client Alice Bob “mortgage...

Scenario 2: Direct Acceptance: 

Scenario 2: Direct Acceptance Spam Assassin Re: Attestation Server Bob’s Friends Alice Tom auth. token Token OK Bob Hit! Alice Mail Server Mail Client “mortgage...

Scenario 3: FoF Acceptance: 

Scenario 3: FoF Acceptance Mail Server Spam Assassin Re: Bob’s Friends Alice Tom Bob Attestation Server Mail Client Charlie token OK & E(?) E(Alice) Charlie is a friend of John Alice No Direct Hit Mutual friend: Alice “mortgage... auth. token & FoF query

Outline: 

Outline Background / Related Work Design Social networks and Attestations Preserving Privacy Re: in Practice Evaluation Implementation Conclusion

Evaluation: 

Evaluation How often do content filters produce false positives? How many opportunities for FoF whitelisting beyond direct whitelisting? Would Re: eliminate actual false positives?

Trace Data: 

Trace Data For each message: Sender and recipient (anonymized) Spam or not as assessed by content-based spam filter Corporate trace One month 47 million messages total (58% spam)

False Positive Data: 

False Positive Data Corporate mail server bounces spam Bounce allows sender to report FP Server admin validates reports and decides whether to whitelist sender We have a list of ~300 whitelisted senders 2837 messages in trace from these senders that were marked as spam by content filter These are almost certainly false positives

Opportunities for FoF Whitelisting: 

Opportunities for FoF Whitelisting FoF relationships help most when receiving mail from strangers. When user receives non-spam mail from a stranger, how often do they share a mutual correspondent? 18% of mail from strangers Only counts mutual correspondents in trace Opportunity: when correspondents = friends

Saved FPs: Ideal Experiment: 

Saved FPs: Ideal Experiment Ideally: run Re: & content filter side-by-side Measure how many FPs avoided by Re: Content Filter Re: List of spam Compare List of FPs List of whitelisted messages

Saved FPs: Trace-Driven Experiment: 

Saved FPs: Trace-Driven Experiment We have an implementation, but unfortunately, no deployment yet No social network data for traces Infer friendship from previous non-spam messages Recall that 2837 messages were from people who reported FPs How many of these would Re: whitelist? Re: would have saved 87% of these FPs (71% direct, 16% FoF)

Implementation: 

Implementation Prototype implementation in C++/libasync Attestation Server Private Matching (PM) implementation Client & administrative utilities 4500 LoC + XDR protocol description Integration Mutt and Thunderbird mail clients Mail Avenger SMTP server Postfix mail client

Performance: 

Performance Direct attestations are cheap Friend-of-friend is somewhat slower PM performance bottleneck is on sender’s AS Ex: intersecting two 40-friend sets takes 2.8 sec versus 0.032 sec for the recipient But… Many messages accepted by direct attestation Can be parallelized Performance improvements possible

Nuances: 

Nuances Audit Trails Recipients always know why they accepted a message (e.g., the mutual friend) Mailing Lists Attest to list Rely on moderator to eliminate spam Profiles Senders use only a subset of possible attestations when answering FoF queries

Conclusion: 

Conclusion Email is no longer reliable because of FPs Idea: Whitelist friends of friends Preserve privacy using PM protocol Opportunity for FoF whitelisting Re: could eliminate up to 87% of real FPs Acceptable performance cost

Backup Slides: 

Backup Slides

Coverage Tradeoff: 

Coverage Tradeoff Trusting a central authority can get you more coverage (DQE) Ex: random grad student Trusted Central Authority

Coverage Tradeoff: 

Coverage Tradeoff Social relationships can help avoid the need to trust a central authority (Re:) Ex: friends, colleagues

Forgery Protection: 

Forgery Protection Sender (S) Recipient (R) Signed authentication token Users have a public/secret key pair Sender attaches a signed authentication token to each outgoing email message {Sender, Recipient, Timestamp, MessageID}SK(Sender)

Forgery Protection: 

Forgery Protection Sender (S) Recipient (R) Sender’s Attestation Server (AS) Authentication token check Recipient asks sender's AS to verify token Assume: man-in-the-middle attack is difficult Advantage: Don't need key distribution/PKI Sender can use token to restrict FoF query

Revocation: 

Revocation What if A’s key is lost or compromised? Two things are signed Authentication tokens Attestations Authentication tokens User uploads new PK to AS AS rejects tokens signed with the old key

Revocation: Attestations: 

Revocation: Attestations Local attestations Delete local attestations (A→*) Remote attestations: expiration If A gave A→B to B, Re: does not currently provide a way for A to tell B to delete the attestation When A→B expires, B will stop using it for FoF If C→A, C should stop trusting attestations signed by A’s old key When C→A expires, C will re-fetch A’s public key

False Negatives: 

False Negatives Assumption: people will not attest to spammers Therefore Re: does not have false negatives What if this assumption does not hold? Remove offending attestations using audit trail Attest without transitivity A trusts B, but not B’s friends Don’t share attestation with attestee Ex: a mailing lists

PM Protocol Details: 

PM Protocol Details Recipient (R) Sender’s Attestation Server (AS) R has kR friends Each xi is one of R’s friends R constructs the P(y) so that each friend is a root of the polynomial Canonical version of P(y)

PM Protocol Details: 

PM Protocol Details Recipient (R) Sender’s Attestation Server (AS)

PM Protocol Details: 

PM Protocol Details Recipient (R) Sender’s Attestation Server (AS) Use homomorphic encryption [Paillier, ElGamal variant] enc(m1+m2) = enc(m1) ∙ enc(m2) enc(c ∙ m1) = enc(m1)c Note: R never sends its attestations

PM Protocol Details: 

PM Protocol Details Recipient (R) Sender’s Attestation Server (AS)

PM Protocol Details: 

PM Protocol Details Recipient (R) Sender’s Attestation Server (AS) random value attestation Computation complexity is O(kS2)

PM Performance: 

PM Performance

WL Effectiveness: Conservative: 

WL Effectiveness: Conservative 17% gain 12% gain

WL Effectiveness:Strangers Only, Conservative: 

WL Effectiveness: Strangers Only, Conservative 425% gain 320% gain

WL Effectiveness: Best Case: 

WL Effectiveness: Best Case 16% gain 13% gain

WL Effectiveness:Strangers Only, Best Case: 

550% gain 380% gain WL Effectiveness: Strangers Only, Best Case