The Sybil AttackOutlineSlide 3BackgroundMotivation (1/2)Motivation (2/2)Slide 7Model – OverviewModel – DefinitionsModel – CharacteristicsModel – ResourcesModel – Main IdeaSlide 13LemmasLemma 1: ResourcesSlide 16Lemma 1: ResourcesLemma 2: ConcurrencySlide 19Lemma 3: ResourcesLemma 4: ConcurrencySlide 22Slide 23Slide 24ConclusionPros/Cons1The Sybil Attack John R. DouceurMicrosoft ResearchPresented for Cs294-4 byBenjamin PoonCs294-4 Benjamin [email protected] 2OutlineBackgroundMotivationModelLemmasConclusionCs294-4 Benjamin [email protected] 3OutlineBackgroundMotivationModelLemmasConclusionCs294-4 Benjamin [email protected] 4BackgroundP2P systems use multiple, independent entities to mitigate possible damage by other hostile entitiesReplicationComputationsStorageFragmentationProtects against privacy violationsSybil AttackAttacker can assume multiple identitiesAims to control substantial fraction of systemCs294-4 Benjamin [email protected] 5Motivation (1/2)Must protect against Sybil AttackUsing replication or fragmentation requires ability to determine if entities are really differentPaper claims Sybil attacks always possible except under extreme, unrealistic assumptionsNeed logically centralized authorityCs294-4 Benjamin [email protected] 6Motivation (2/2)Centralized authority possibilitiesVeriSignExplicit certificationCFS (cooperative storage)Identities assigned using hash of IP addressProblem?SFS (network file system)Identities assigned using host identifier + DNS nameEMBASSY (multiparty trust system)Identities assigned using hardware-embedded cryptographic keysIssues?Cs294-4 Benjamin [email protected] 7OutlineBackgroundMotivationModelLemmasConclusionCs294-4 Benjamin [email protected] 8Model – OverviewGeneric distributed computing environmentEntities ECorrect C union Faulty F = ESend messagesPipeMessagescloudMessagesUninterrupted, finite-length bit stringCloudBroadcastBounded timeGuaranteedUnorderedCs294-4 Benjamin [email protected] 9Model – DefinitionsIdentityAbstract representation that persists across multiple communication eventsEntities perceive other entities through identitiesPresentEach entity presents an identity to other entities in the systemLocal entity LA specific entity that results are stated with respect toAcceptIf an entity e successfully presents an identity i for itself to L, L accepts iCs294-4 Benjamin [email protected] 10Model – CharacteristicsGeneralLeaves internals of cloud unspecifiedIncludes any topology/geometryFriendlyLimits obstructive power of corrupt entitiesDoS attacks not possibleStrengthens negative resultsQ: Any drawbacks of the model?Cs294-4 Benjamin [email protected] 11Model – ResourcesEntities can perform operations with complexity polynomial in n Allows public-key cryptographyEntities can establish point-to-point communicationCs294-4 Benjamin [email protected] 12Model – Main IdeaEach entity e attempts to present one legitimate identityEach faulty entity f additionally attempts to present one or more counterfeit identitiesGoal: system should accept all legitimate identities, zero counterfeitCs294-4 Benjamin [email protected] 13OutlineBackgroundMotivationModelLemmasConclusionCs294-4 Benjamin [email protected] 14LemmasFour lemmasCollectively show impracticality of establishing distinct identities in large-scale distributed systemProofs trivial (refer to paper)In absence of trusted authority, entities accept identities only when identity is:1. Validated by entity itself (direct validation)Lemmas 1 and 22. Vouched for by other already validated identities (indirect validation)Lemmas 3 and 4Cs294-4 Benjamin [email protected] 15Lemma 1: ResourcesLetmin = minimally capable entityRx = resources of xρ = Rf / Rminf can present floor(ρ) distinct identities to LCs294-4 Benjamin [email protected] 16Lemma 1: ResourcesGives lower bound on damage achievable by fAchieve upper bound by exploiting limitations in resourcesCommunication: L broadcasts request for identities and accept replies that come within given time intervalStorage: L challenges identities to store large amount of unique, uncompressible dataComputation: L challenges identities to solve unique computational puzzleCs294-4 Benjamin [email protected] 17Lemma 1: Resources Computational puzzle exampleGenerate large random value yChallenge identity to find (in limited time) pair of values x and z such that least significant n bits of hash(x | y | z) = 0Given y, find x, z s.t. LSBn(hash(x | y | z)) = 0Time to solve proportional to 2n-1Time to verify constantCs294-4 Benjamin [email protected] 18Lemma 2: ConcurrencyIf L accepts entities not validated simultaneouslyf presents a distinct identity to L using RfRf is freed and f repeats processSingle f can present many counterfeit identities to LCs294-4 Benjamin [email protected] 19Lemma 2: ConcurrencyWorks for temporal resources (computation and communication), not storageL can indefinitely extend challenge duration: periodically demand different data excerptsChallenge consumes R, so real work limitedCs294-4 Benjamin [email protected] 20Lemma 3: ResourcesIf L accepts any identity vouched for by q accepted identities, a group F can present many counterfeit identities to L if either:Size of group F >= q RF >= resources taken by q + |F| minimally capable entitiesCs294-4 Benjamin [email protected] 21Lemma 4: ConcurrencyIf correct entities C do not coordinate time intervals to accept identities, and if L accepts any identity vouched for by q accepted identitiesMinimally capable f can present floor( |C| / q ) counterfeit identities to LCs294-4 Benjamin [email protected] 22Lemma 4: ConcurrencyShows need for multiple entities in C to issue concurrent challengesMay or may not be possible depending on resourceCommunication: possible because of broadcast cloudStorage: information theory says “probably not”Computation: possible by combining puzzlesCs294-4
View Full Document
Unlocking...