LOCKSS: Lots of Copies Keeps Stuff SafeMotivationDesign Goals and AssumptionsDesign PrinciplesLOCKSS OverviewOpinion Poll ProtocolPeer Lists per AUPoll InitiationPoll EffortVote TabulationOuter CircleAdversary AttacksSlide 13Stealth Modification AttackSimulationsSimulation: Lurking TimeSimulation: Alarm TimeSimulation: Damage to AUSimulation: Worst-caseSimulation: Benefit of ChurnConclusionsLOCKSS: Lots of Copies Keeps Stuff SafeUNIVERSITY of WISCONSIN-MADISONComputer Sciences DepartmentCS 739Distributed SystemsAndrea C. Arpaci-DusseauPreserving Peer Replicas By Rate-Limited Sampled Voting, Maniatis, Roussopoulos, Giuli, Rosenthal, Baker, Muliadi (Stanford) -- SOSP’03MotivationLibrarians: Responsibility to preserve important materials Traditional approach:•Acquire lots of copies•Distribute around world•Lend or copy to provide accessAcademic publishing is moving to Web•LOCKSS: Real system used by many libraries (1999) •How to apply techniques to digital preservation?Strength: Real problem that people care about, real solution being usedDesign Goals and AssumptionsMust be cheap to build and maintain•No RAID systemsNeed not operate quickly•Want to prevent change, not expedite itMust function properly for decadesNo centralized controlHandle failures•Handle malicious attackers•Handle catastrophic random failuresHow is this different from other P2P systems?Design PrinciplesCheap storage is unreliableNo long-term secrets•Can’t hold private keys for arbitrary time periodsUse inertia•Rate limit the amount of activity and changeAvoid third-party reputation•Malicious users can lie about good users•Attackers can “cash in” history of good behaviorReduce predictability•Make difficult for attackers to predict behavior of victimsMake intrusion detection intrinsic•Part of the system itselfAssume strong adversary•May want to change, suppress, or steal contentLOCKSS OverviewLibraries run persistent web caches•Collect by crawling journal web-sites•Distribute by acting as limited proxy cache•Preserve by cooperating with others to detect and repair damagePeers vote on large archival units (AU’s)•AU == year’s run of a journal•Each peer holds different AU’s•If AU damaged, call increasingly specific partial pollsOpinion Poll ProtocolTerminology:•Loyal, malign, healthy, damaged peersGoal: •High probability loyal peers are healthy (despite attacks by malign peers and failures)•Low probability even powerful adversary can damage significant proportion of loyal peers without detectionOverview•Poll initiator calls opinion poll on AU >> rate of random damage•Invites small subset of known peers (poll participant or voter)•Voter computes and returns digest of AU•Vote results for poll initiator:–Landslide win: Votes overwhelmingly agree with own version–Landslide loss: Repair AU by fetching copy of AU from peer–Inconclusive poll: Raise alarm for human attention •Who can benefit from the poll? What if voter disagrees?Peer Lists per AULists for every AU•Friends list: Peers have outside relationships with friends•Reference list: Peers encountered recently–Bootstrap: Init with friends list–Inner circle: Those invited to influence poll results–Outer circle: Nominated by inner circlePoll InitiationPoll initiation: (about every 3 months per AU)•Choose N random peers from ref list: Inner circle•Send Poll [Poll ID, Diffie-Hellman Public Key]•Wait for responses..Voter from inner circle: Decide if want to participate•Why might a peer not participate?•Pick new DH public key, compute symmetric session key•How does Diffie-Hellman work?–A chooses secret a, sends g^a mod p–B chooses secret b, sends g^b mod p–Each computes secret (g^b mod p)^a mod p = (g^a mod p)^b mod p •Why encrypt messages??•Send back encrypted YES or NO to participate –Send PollChallenge [Poll ID, DH public key, {challenge, YES}]Poll EffortInitiator: Produce computational effort for voter•Why proof of computation by initiator needed?•Use memory-bound functions (MBF) with poll id and challenge as input–Why are MBF good?•Send back PollProof [Poll Id, poll effort proof]–Even send this to voters who responded NO. Why?Voter: Verifies result•Less computation needed to verify result than compute•Nominate outer circle peers (more later)–Randomly selected from reference list•Send Vote messages for AU–Also send proof of computational effort in rounds–Why proof of computation by voter needed? Why in rounds?Vote TabulationInitiatator: Tabulates valid votes from inner circleThree cases:•Landslide loss: Agreeing votes <= D–Repair AU•Landslide win: Agreeing votes > V-D–Opinion poll concludes successfully; reschedule poll•Inconclusive: Raise alarmRepair•Initiator picks disagreeing voter and requests repair•When is voter willing to supply content?•Retabulate results with new contentOuter CircleWhat is the purpose of the outer circle?Initiator: Picks same number from every nominator•Repeat same steps of protocol with outer circle–Why?•Differences?Update reference list•What is a malign peer trying to do?•Who is removed?•Insert: Valid/agreeing outer circle peers and random friends–Why?Adversary AttacksAssume powerful adversary•Total information awareness•Perfect work balancing•Perfect digital preservation•Local eavesdropping•Local spoofing•Stealth•Unconstrained identities•Exploitation of Common peer vulnerabilities•Complete parameter knowledgeAdversary AttacksStealth modification•Convince loyal peer has damaged AU•Replace protected content with bad version•Focus of paperNuisance•Raise alarmsAttrition•Make loyal peers waste computational resources so can’t repair damageTheft•Acquire published content from peers without fee•How does LOCKSS prevent?Free-loading•Obtain services without supplying to othersStealth Modification Attack1) Lurk phase•Increase foothold: malign peers in reference list (inner circle)–Wait until invited into circle–Act loyal–Nominate more malign peers2) Attack phase•When see poll is vulnerable (I.e., overwhelming majority of inner circle is malign), vote badWhy is attacking successfully hard?•Rate limiting: Must wait for vulnerable polls to occur•Damaged loyal peers call and vote in polls using bad copy–Can be repaired or raise alarms (doesn’t act differently when don’t have majority)•Must expend effort calling polls too–Loyal peer