Preserving Peer Replicas by Rate-Limited Sampled VotingINTRODUCTION (I)INTRODUCTION (II)Digital Preservation SystemsDESIGN REQUIREMENTSDESIGN PRINCIPLES (I)DESIGN PRINCIPLES (II)KEY IDEASEXISTING LOCKKS SYSTEMSlide 10Opinion PollsWhy?Organization (I)Organization (II)Slide 15THE NEW PROTOCOLNEW OPINION POLL PROTOCOLPoll OutcomesRoles for participating peersExchangesPoll Initiation and Poll Effort ProofObjectivesMechanisms UsedTypes of Attacks (I)Types of Attacks (II)Types of Attacks (III)SIMULATION RESULTSCONCLUSIONSPreserving Peer Replicas by Rate-Limited Sampled VotingPetros Maniatis Mema RoussopoulosTJ Giuli David S. H. RosenthalMary Baker Yanto MuliadiStanford UniversityINTRODUCTION (I)•Paper addresses issue of maintaining access to important online documents:–Web-published academic journals•Must at the same time–Ensure long-term access–Guarantee authenticity of document copiesINTRODUCTION (II)•Their solution is LOCKSS:Lot Of Copies Keep Stuff Safe•A digital preservation system•Having many copies ensures the long-term survival of the documents–Same as for hard copies•Peer-to-peer opinion polls guarantee the authenticity of the documentsDigital Preservation Systems•Must resist random failures and deliberate digital attacks for a long time•Have unusual requirements:–Lack of central control–Must avoid long-term secrets like encryption keys•Can make some operations very time consuming without sacrificing usabilityDESIGN REQUIREMENTS•Digital preservation systems:–Must be very cheap to build and maintain•No high-performance hardware (RAID)–Need not to operate quickly•Should prevent rather than expedite changes–Must properly operate for decades without central controlDESIGN PRINCIPLES (I)•Cheap storage is unreliable:–Write-once media are a least as unreliable as disks•No long-term secrets:–Too hard to preserve; too hard to recover from leak•Use inertia:–Prevent change, do not make it too easyDESIGN PRINCIPLES (II)•Avoid third party reputation:–Too vulnerable to slander or subversion(eBay problem)•Intrusion detection is intrinsic:–Not done by extrinsic system•Assume a strong adversary:–Attackers will be able to use very large numbers of hostsKEY IDEAS•LOCKSS is about preserving–Very conservative design•LOCKSS is also about detecting tampering–Can deal with powerful adversariesEXISTING LOCKKS SYSTEM•Makes it appear to library patrons that pages remain available at their original URL even when they are gone–Just like a regular library•Peer-to-peer systemEXISTING LOCKKS SYSTEM•Libraries run persistent web caches that –Collect documents by crawling journal websites–Distribute by acting as limited proxy cache for the library’s patrons–Preserve by cooperating with other caches to detect and repair damagesOpinion Polls•Let sample of peers vote on the hash of a specified part of the contents•Provide peers with confidence in content authenticity and integrityX’ X’ X’ X”Why?•On-line journals–Do not sign the materials they publish–Do not provide manifest enumerating the files forming a paper, issue or volume•Crawling is unreliable•NO completely reliable storage medium exists–All media can be stolen or destroyed•Better to put our trust in number of replicasOrganization (I)•Peers vote on large archival units (AU)–Year run of a journal•Each peer will hold a different set of Aus–No universal library•A peer that loses a poll has a bad AU–Will call a series of increasingly specific partial polls to locate the damageOrganization (II)•Once damage is detected, peers provide site having a damaged copy with a good copy provided that the site has participated in a previous poll–Prevents free-loading•Peers only supply materials to peers that can prove they own these materials–Prevents theftOrganization (II)•System is inexpensive –One PC with three 180GB disk can preserve 210 years of the largest journal(J. of Biological Chemistry)THE NEW PROTOCOL•Assumes no common-mode failure•Several kind of peers–Malign peers–Loyal Peerscan be either•Damaged (has bad AU)•Healthy (has correct AU)NEW OPINION POLL PROTOCOL•Objective is to ensure that loyal peers have a high probability to be in a healthy state•A LOKSS peer–calls a poll much more frequently than any anticipated rate of random damage–invites into its poll a random subset of peersPoll Outcomes•Landslide win: votes overwhelmingly agree with peer’s version of AU–Do nothing•Landslide loss: votes overwhelmingly disagree with peer’s version of AU–Repair peer’s version of AU (by updating it)•Inconclusive poll: –Require human interventionRoles for participating peers•Poll initiator•Poll participants:–Need not find out the result of polls–Inner circle participants are selected by the poll initiator from its Reference List•Only their votes count–Outer circle participants are nominated by inner circle participants and selected by poll initiator •Could be invited into further inner circlesExchanges•Encrypted via symmetric session keysPoll Initiation and Poll Effort Proof•Initiator sends to each inner circle peer a Poll message containing a fresh public key•Inner circle peers reply with Poll Challenge•For each Poll Challenge it has received, initiator produces some computational effort that is provable via a pool effort proof and sends it in a Poll Proof message•Nominate and Vote messages followObjectives•Prevent adversary from gaining a foothold in a poll’s initiator reference list•Make it expensive for adversary to waste another peer’s resources•Make it likely that the adversary ‘s attack will be detected on timeMechanisms Used•Poll effort proof•Mechanism to modify reference list–Reference list churning•Obfuscation of protocol state–Almost everything is encryptedTypes of Attacks (I)•Main objective is getting a foothold in a reference list–Must first take over peers that used to be loyal–Can later nominate other malign peers–Lines of defense are•Loyal peers only change their reference list after a poll they call•Reference lists change (churning)Types of Attacks (II)•Session Hijacking:–Malign peer responds to initiator’s Poll message with spoofed Poll Challenge–If loyal invitee also replies, initiator will receive two Poll Challenges and discard both– Otherwise malign peer will be able to voteTypes of Attacks (III)•Stealth