re nsdi06 slides

Information about re nsdi06 slides

Published on December 18, 2007

Author: Esteban

Source: authorstream.com

Content

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

Related presentations


Other presentations created by Esteban

Chapter 15 Knee Conditions
28. 11. 2007
0 views

Chapter 15 Knee Conditions

S WATER
09. 10. 2007
0 views

S WATER

ELearning Conf collins
12. 12. 2007
0 views

ELearning Conf collins

Istvan Bilik
29. 10. 2007
0 views

Istvan Bilik

The Rise of Mussolini in Italy
01. 11. 2007
0 views

The Rise of Mussolini in Italy

intro cicero
01. 11. 2007
0 views

intro cicero

titanic
05. 11. 2007
0 views

titanic

00 18 pp7
05. 11. 2007
0 views

00 18 pp7

defence ficci
05. 11. 2007
0 views

defence ficci

bisnovatiykogan
13. 11. 2007
0 views

bisnovatiykogan

firm
22. 11. 2007
0 views

firm

UDSL Pres 4
26. 11. 2007
0 views

UDSL Pres 4

Insomnia
29. 11. 2007
0 views

Insomnia

ag environment
28. 12. 2007
0 views

ag environment

SAS781 016ArticleSlideShow
01. 01. 2008
0 views

SAS781 016ArticleSlideShow

Friendship Quotes
02. 01. 2008
0 views

Friendship Quotes

Lesson 16 Leader of Russia
26. 10. 2007
0 views

Lesson 16 Leader of Russia

Electronics 1 20 06
07. 11. 2007
0 views

Electronics 1 20 06

BATALIN FEB 13 04
07. 01. 2008
0 views

BATALIN FEB 13 04

Slides4c
07. 01. 2008
0 views

Slides4c

NRES322 14
08. 01. 2008
0 views

NRES322 14

Weese MRSA
19. 11. 2007
0 views

Weese MRSA

Shore Stephen
13. 12. 2007
0 views

Shore Stephen

Gerberding 07 AAIDD
24. 10. 2007
0 views

Gerberding 07 AAIDD

halloween history
05. 11. 2007
0 views

halloween history

june25 natural dhananjay
20. 02. 2008
0 views

june25 natural dhananjay

BEST03
24. 02. 2008
0 views

BEST03

ch9
27. 02. 2008
0 views

ch9

TrainingPanel
29. 02. 2008
0 views

TrainingPanel

080407
14. 03. 2008
0 views

080407

cares
27. 03. 2008
0 views

cares

UNIDO1
30. 03. 2008
0 views

UNIDO1

Praes WR Glaser DGfPs
16. 11. 2007
0 views

Praes WR Glaser DGfPs

Tireoidites CM 2006
28. 12. 2007
0 views

Tireoidites CM 2006

sommaruga
25. 10. 2007
0 views

sommaruga

Card Sort Indian Artifacts
19. 11. 2007
0 views

Card Sort Indian Artifacts

Exodus08
24. 10. 2007
0 views

Exodus08

Arthur Sadoff
28. 09. 2007
0 views

Arthur Sadoff

research industry partnerships
16. 11. 2007
0 views

research industry partnerships

Molvir Flavi Toga 01 19 06
24. 10. 2007
0 views

Molvir Flavi Toga 01 19 06

Chris Aalberts
25. 12. 2007
0 views

Chris Aalberts

mission mech garden intro
11. 12. 2007
0 views

mission mech garden intro

library agent
30. 10. 2007
0 views

library agent

FallOffDutySafety
06. 11. 2007
0 views

FallOffDutySafety

cours sts intro gen 2005
12. 11. 2007
0 views

cours sts intro gen 2005

JanConrad mar10 06
14. 11. 2007
0 views

JanConrad mar10 06

AMC Italy Intro CMonticelli
31. 10. 2007
0 views

AMC Italy Intro CMonticelli

CROSSMARC Rome Intro
31. 10. 2007
0 views

CROSSMARC Rome Intro

Liz presentation
28. 12. 2007
0 views

Liz presentation

anheuser1
05. 11. 2007
0 views

anheuser1

AUST Overview for Website
06. 11. 2007
0 views

AUST Overview for Website

2b lanciotti
24. 10. 2007
0 views

2b lanciotti

OWK2006 Dixon SBDC
29. 10. 2007
0 views

OWK2006 Dixon SBDC

L23 ch14
03. 10. 2007
0 views

L23 ch14

JAA etno maj 2005
01. 12. 2007
0 views

JAA etno maj 2005

Japansk encefalitt
24. 10. 2007
0 views

Japansk encefalitt

MM5 yhe
04. 01. 2008
0 views

MM5 yhe