(ExtendedAbstract)
JamesAspnes
⋆⋆
,JoanFeigenbaum⋆⋆⋆,AleksandrYampolskiy†,and
ShengZhong‡
DepartmentofComputerScience,YaleUniversity,NewHavenCT06520-8285,USA
Abstract.Wegiveaformalmodelforsystemsthatstoredatainen-tangledform.Weproposeanewnotionofentanglement,calledall-or-nothingintegrity(AONI)thatbindstheusers’datainawaythatmakesithardtocorruptthedataofanyoneuserwithoutcorruptingthedataofallusers.AONIcanbeausefuldefenseagainstnegligentordishoneststorageproviderswhomightotherwisebetemptedtodiscarddocumentsbelongingtouserswithoutmuchclout.Weshowthat,ifallusersusethestandardrecoveryalgorithm,wecanimplementAONIus-ingaMAC,but,ifsomeoftheusersadopttheadversary’snon-standardrecoveryalgorithm,AONIcannolongerbeachieved.However,evenforthelatterscenario,wedescribeasimpleentanglingmechanismthatpro-videsAONIforarestrictedclassofdestructiveadversaries.
1Introduction
SupposethatIprovideyouwithremotestorageforyourmostvaluableinfor-mation.Imayadvertisevariousdesirablepropertiesofmyservice:undergrounddiskfarmsprotectedfromnuclearattack,dailybackupstochiseledgranitemon-uments,replicationtothousandsofsitesscatteredacrosstheglobe.ButwhatassurancedoyouhavethatIwillnotmaliciouslydeleteyourdataassoonasyoursubscriptioncheckclears?
IfIconsiderdeletingthedataofarichorpowerfulcustomer,Imaybede-terredbyeconomic,social,orlegalrepercussions.ThesmallsecretjoyImightexperiencefromthethoughtofthelosswillnotcompensatemeforlosingapostedbond,destroyingmyreputation,orbeingimprisoned.Butifyouareanordinarycustomerwhodoesnothavemuchclout,andIseealucrativeopportu-nityinaltering—orsimplyneglectingtokeep—yourdata,thendeterrenceloses
itseffectiveness.Consequently,dataofpowerfulcustomersendupbeingmoreprotectedthandataofaveragecustomers.Toconvinceanaveragecustomerthatshewillnotloseherdataatmyrandomwhim,ImightofferstrongertechnicalguaranteesthatIcannotdestroyherdatawithoutseriouscosts.OnewaytodothiswouldbetolinkthefateofherdocumentstothedocumentsofenoughotherusersthatIcannothopetooffendthemallwithimpunity.Weshallcallsuchdocumentsentangled.
Dataentanglementwasinitiallysuggestedasamechanismforincreasingcensorship-resistanceindocument-storagesystems,e.g.,Dagster[21]andTan-gler[22].Thesesystemssplitdataintoblocksinsuchawaythatasingleblockbecomespartofseveraldocuments.Newdocumentsarerepresentedusingsomenumberofexistingblocks,chosenrandomlyfromthepool,combinedwithnewblockscreatedusingexclusive-or(Dagster)or3-out-of-4secretsharing[19](Tan-gler).DagsterandTangleruseentanglementasoneofmanymechanismstopre-ventacensorfromtamperingwithunpopulardata;othersinvolvedisguisingtheownershipandcontentsofdocumentsand(inTangler)storingdocumentsredundantly.
Itisnotclearthatdataentanglementisactuallyusefulforcensorshipresis-tance.Insteadofhavingtospecificallyattackatargetdocument,acensoronlyneedstodamageanydocumententangledwiththetargettoachievehisgoal.Instead,weconsiderdataentanglementforadifferentpurpose:protectingthedatafromanuntrustedstorageproviderthatmightbetemptedtodamageordestroythedatathroughnegligenceormalice.Entanglementprovidesanin-centiveforthestorageprovidertotakeextracareinprotectingaverageusers’documentsbyincreasingthecostoferrors.
WebegininSection2byanalyzingtheintuitivenotionofentanglementprovidedbyDagsterandTangler.WeshowthatentanglementasprovidedbyDagsterandTanglerisnotbyitselfsufficientlystrongtodeteradishoneststorageproviderfromtamperingwithdata,becausenotenoughdocumentsgetdeletedonaveragewhendestroyingablockofatypicaldocument.Thismotivatesoureffortstoobtainastrongerformofanentanglementthantheonesprovidedbythesesystems.
InSection3,wedefineourgeneralmodelofentanglementinanuntrustedstoragesystem.Ourgoalhereistomodeltheentanglementoperationitself,andwedonotaddressthequestionofwhereinthesystementanglementoccurs.However,wedoassumethatthestorageproviderdoesnotcarryouttheentan-glingoperationitself,asgivingittheusers’rawdatawouldallowittostorecopiesthatitcouldselectivelyreturnlater,eveniftheentangledstorewerelostordamaged.Instead,sometrustedthirdpartyisassumedtocarryouttheentanglingoperation,andanegligentormaliciousstorageproviderismodeledseparatelyasa“tamperer”thathasaccessonlytotheentangledstore.
Section4containsourdefinitionsofdocumentdependency,whereadoc-umentcannotberecoveredifanydocumentitdependsonislost,andall-or-nothingintegrity,wherenodocumentcanberecoveredifanydocumentislost.Thesedefinitionsallowasystem-independentdescriptionofthebindingbe-
tweenentangleddocuments.Wethenconsiderhowdifferentlevelsofattacksonthecommondatastoredoordonotpreventenforcementofdocumentdepen-dencyorall-or-nothingintegrity.
Inparticular,weshowthat,ifallclientsuseastandardalgorithmtore-covertheirdata,thenall-or-nothingintegrityrequiresonlytheabilitytodetecttamperingusingaMAC(Section5.1);inthismodel,thestandardrecoveryal-gorithmistoopolitetoreturnanyuser’sdataifanyotheruser’sdatahasbeenlost.Relyingonsuchfastidiousnessprovidesonlyaweakguarantee;whatwere-allywantisthatalldatabecomesirretrievableevenbynon-standardalgorithmsifanyislost.Weshowthatthisgoalisimpossibleifanadversaryisallowedtobothtamperwiththecommonstorearbitrarilyandprovideareplacementrecoveryalgorithm(Section5.2).Despitesuchupgradeattacks,itisstillpos-sibletoprovideaweakerguaranteethatwecallsymmetricrecovery,inwhicheachdocumentisequallylikelytobedestroyed(Section5.3).Furthermore,ifwerestricttheadversarytodestructivetampering,whichreducestheamountofinformationinthecommonstore,all-or-nothingguaranteesarepossibleevenwithupgradeattacks(Section5.4).
Theseresultsprovideafirststeptowardunderstandingdocumentdepen-dency.SuggestionsforfurtherworkaregiveninSection6.
Becauseofspacelimitations,manyproofsareomittedfromthisextendedabstract.Completeproofscanbefoundinthefullversion,availableasaYaleCStechnicalreport[2].1.1
RelatedWork
Entanglementismotivatedbythegoalofdeterringdatatamperingbyuntrustedservers,amoregeneralproblemthathasbeenstudiedextensively.Entangle-menthasbeenusedspecificallyinDagster[21]andTangler[15],aswedescribeinSection2.Otherapproachestopreventingordeterringtamperingincludereplicationacrossglobalnetworksoftamper-resistantservers[1,4,5,9,17,23]ortamperdetection[6–8,12–14,20]usingdigitalsignaturesandMerklehashtrees[16].Replicationprotectsagainstdatalossifasmallnumberofserversarecompromised;tamperdetectionpreventsdatalossfromgoingunnoticed.Bothtechniquescomplementtheentanglementapproachconsideredhere.
All-or-nothingintegrityasdefinedinthepresentworkisrelatedtotheguar-anteeprovidedbytheall-or-nothingtransformproposedbyRivest[18].Anall-or-nothingtransformisaninvertibletransformthatguaranteesthatnobitsofthepreimagecanberecoveredifℓbitsoftheimagearelost.All-or-nothingtransformsarenotdirectlyapplicabletoourproblem,becauseweconsiderthemoregeneralcaseinwhichtheimagemaybecorruptedinotherways,suchasbysuperencryptionoralterationofpartorallofthecommonstore.
2DagsterandTangler
WenowreviewhowDagster[21]andTangler[22]work,concentratingontheiroperationsatablocklevelandomittingdetailsofhowdocumentsaredivided
intoblocks.Wethenanalyzetheresultingentanglingeffectsandshowtheirshortcomingsforprotectingdatafromanegligentstorageprovider,motivatingourstrongernotionsofentanglementinSection4.2.1
Dagster
TheDagsterstoragesystemmayrunonasingleserveroronaP2Poverlaynetwork.EachdocumentinDagsterconsistsofc+1serverblocks:cblocksofolderdocumentsandonenewblock,anexclusive-orofpreviousblockswiththedocument.Thec+1blocksthatmustbeXORedtorecoverthedocumentarelistedinaDagsterResourceLocator.2.2
Tangler
TheTanglerstoragesystemuses(3,4)Shamirsecretsharing[19]toentanglethedata:Eachdocumentisrepresentedbyfourserverblocks,anythreeofwhicharesufficienttoreconstructtheoriginaldocument.TheblocksgetreplicatedacrossasubsetofTanglerservers.Hashesofblocksarerecordedinadatastructure,similartoDagsterResourceLocator,calledaninode.2.3
AnalysisofEntanglement
Atagivenpointintime,aDagsterorTanglerservercontainsasetofblocks{C1,...,Cm}comprisingdocuments{d1,...,dn}ofagroupofusers.(Herem,n∈Nandm≥n.)Dataarepartitionedinawaythateachblockbe-comesapartofseveraldocuments.Wecandrawanentanglementgraph(seeFigure1),whichhasanedge(dj,Ck)ifblockCkbelongstodocumentdj.Thisconnectionisrathertenuous—evenif(dj,Ck)isinthegraph,itmaystillbepossibletoreconstructdjfromblocksexcludingCk.DocumentnodesinDag-ster’sentanglementgraphhaveanout-degreec+1,andthoseinTangler’shaveout-degree4.Entangleddocumentsshareoneormoreserverblocks.InFig-ure1,documentsd1andd2areentangledbecausetheyshareserverblockC1;meanwhile,documentsd1andd2arenotentangled.
Thisshared-blocknotionofentanglementhasseveraldrawbacks.Evenifdocumentdjisentangledwithaspecificdocument,itmaystillbepossibletodeletedjfromtheserverwithoutaffectingthatparticulardocument.Forexample,knowingthatdnisentangledwithd1(asinFigure1),andthatd1isownedbysomeVeryImportantPerson,maygivesolacetotheownerofdn,whomightassumethatnoadversarywoulddareincurthewrathoftheVIPmerelytodestroydn.Butinthesituationdepictedinthefigure,theadversarycanstilldeleteserverblocksC2andCmandcorruptdnbutnotd1.
Theresultingdependencebetweendocumentsisthusveryweak.Inthefullpaper,weshow:
Theorem1.InaDagsterserverwithndocuments,whereeachdocumentislinkedwithcpre-existingblocks,deletingablockofarandomdocumentdestroysonaverageO(c)otherdocuments.
d1d2C1C2
...dnCm
Fig.1.Anentanglementgraphisabipartitegraphfromthesetofdocumentstothe
setofserverblocks.Edge(dj,Ck)isinthegraphifserverblockCkcanbeusedtoreconstructdocumentdj.
Theorem2.InaTanglerserverwithndocuments,deletingtwoblocksofarandomdocumentdestroysonaverageOlogn
phase,inwhichtheindividualusers’dataarecombinedintoacommonstore;atamperingphase,inwhichtheadversarycorruptsthestore;andarecoveryphase,inwhichtheusersattempttoretrievetheirdatafromthecorruptedstoreusingoneormorerecoveryalgorithms.Forsimplicityofnotation,wenumbertheusers{1,...,n},whereeveryuseripossessesadocumentdithathewantstopublish.
Fig.2.Initialization,entanglement,andtamperingstages.
AnencodingschemeconsistsofthreeprobabilisticTuringmachines,(I,E,R),thatrunintimepolynomialinthesizeoftheirinputsandasecurityparameters.Thefirstofthese,theinitializationalgorithmI,handsoutthekeysusedintheencodingandrecoveryphases.Thesecond,theencodingalgorithmE,combinestheusers’dataintoacommonstoreusingtheencodingkey.Thethird,therecoveryalgorithmR,attemptstorecovereachuser’sdatausingtheappropriaterecoverykey.
ˇTˇ,Rˇ),whichalsoActingagainsttheencodingschemeisanadversary(I,
consistsofthreeprobabilisticpolynomial-timeTuringmachines.Thefirstisan
ˇ;likethegoodinitializerI,theevilIˇadversary-initializationalgorithmI
isresponsibleforgeneratingkeysusedbyotherpartsoftheadversaryduring
ˇ,whichmodifiesthetheprotocol.ThesecondisatamperingalgorithmT
ˇ,whichcommonstore.Thethirdisanon-standardrecoveryalgorithmR
maybeusedbysomeoralloftheuserstorecovertheirdatafromthemodifiedstore.
ˇ,TˇandRˇarechosenafterI,E,andRareknownbutthatWeassumethatIˇ,Tˇ,andRˇareusedforarbitrarilylargevaluesofsandn.ThisasinglefixedI
ˇandRˇtohaveanyeffect.isnecessaryforpolynomial-timeboundsonT
ˇTˇ,Rˇ),thestorageGivenanencodingscheme(I,E,R)andanadversary(I,
protocolproceedsasfollows(seealsoFigure2):
1.Initialization.TheinitializerIgeneratesacombiningkeykEusedbytheencodingalgorithmandrecoverykeysk1,k2,...kn,whereeachkeykiisusedbytherecoveryalgorithmtorecoverthedataforuseri.Atthesametime,
ˇforTˇgeneratesthesharedkeykˇandRˇ.theadversaryinitializerI
kE,k1,k2,...kn←I(1s,n),
ˇ←Iˇ(1s,n).k
2.Entanglement.TheencodingalgorithmEcomputesthecombinedstoreC
fromthecombiningkeykEandthedatadi:
C←E(kE,d1,d2,...dn).
ˇaltersthecombinedstoreCintoCˇ:3.Tampering.ThetampererT
ˇC).ˇ←Tˇ(k,C
4.Recovery.Theusersattempttorecovertheirdata.Useriapplieshisre-ˇ.EachRicouldbeeithercoveryalgorithmRitokiandthechangedstoreC
thestandardrecoveryalgorithmR,suppliedwiththeencodingscheme,or
ˇ,suppliedbytheadversary,dependingonthethenon-standardalgorithmR
choiceofthemodel.
ˇd′i←Ri(ki,C)WesaythatuserirecovershisdataiftheoutputofRiequalsdi.3.2
AdversaryClasses
Wedivideourmodelontwoaxes:oneboundingtheusers’choicesofreconstruc-tionalgorithmsandtheotherboundingtheadversary’spowertomodifythe
datastore.Withrespecttorecoveryalgorithms,weconsiderthreevariantsonthebasicframework(listedinorderofincreasingpowergiventotheadversary):–Inthestandard-recovery-algorithmmodel,theusersarerestrictedtoasinglestandardrecoveryalgorithmR,suppliedbythesystemdesigner.For-mally,thismeansRi=Rforallusersi;Theadversary’srecoveryalgorithmˇisnotused.ThisisthemodelusedtoanalyzeDagsterandTangler.R
–Inthepublic-recovery-algorithmmodel,theadversarynotonlymod-ifiesthecombinedstore,butalsosuppliesasinglenon-standardrecovery
ˇtoalloftheusers.Formally,wehaveRi=Rˇforeachi.ThealgorithmR
originalrecoveryalgorithmRisnotused.1Wecallthisanupgradeattackbyanalogytothereallifesituationofacompanychangingthedataformatofdocumentsprocessedbyitssoftwareanddistributinganewversionofthesoftwaretoreadthem.Webelievesuchanattackisarealisticpossibility,becausemostself-interesteduserswillbehappytoadoptanewrecoveryalgorithmifitoffersnewfeaturesorperformance,orifthealternativeislosingtheirdata.
–Intheprivate-recovery-algorithmmodel,theadversarymaychooseto
ˇtoonlyasubsetoftheusers.supplythenon-standardrecoveryalgorithmR
TherestcontinuetousethestandardalgorithmR.Formally,thismodelis
ˇforothers.amixoftheprevioustwomodels:Ri=RforsomeiandRi=RWealsodifferentiatebetweentwotypesoftamperers:
–Anarbitrarytamperercanfreelycorruptthedatastoreandisnotre-strictedinanyway.Mostreal-lifesystemsfitintothiscategoryastheyplace
norestrictionsonthetamperer.
–Adestructivetamperercanonlyapplyatransformationtothestorewhoserangeofpossibleoutputsissubstantiallysmallerthanthesetofin-puts.Thedestructivetamperercansuperimposeitsownencryptiononthecommonstore,transformthestoreinarbitraryways,andevenaddaddi-tionaldata,providedthatthecumulativeeffectofalltheseoperationsistodecreasetheentropyofthedatastore.Thoughadestructivetamperingas-sumptionmaylooklikeanartificialrestriction,itsubsumesnaturalmodelsofblockdeletionorcorruption,andeitheritorsomesimilarassumptionisneededtoachieveall-or-nothingintegrityintheprivate-recovery-algorithmmodel.ˇisandwhichusers,AnadversaryclassspecifieswhatkindoftampererT
ˇastheirrecoveryalgorithm.Altogether,weconsider6(=3×2)ifany,receiveR
adversaryclasses,eachcorrespondingtoacombinationofconstraintsonthetampererandtherecoveryalgorithms.
4DependencyandAll-Or-NothingIntegrity
Wenowgiveourdefinitionofdocumentdependencyforaparticularencodingschemeandadversaryclass.Wefirstdiscusssomebasicdefinitionsandassump-tionsinSection4.1.Ourstrongnotionsofentanglement,calleddependencyandall-or-nothingintegrity,aredefinedformallyinSection4.2.
4.1Preliminaries
BecauseweconsiderprotocolsinvolvingprobabilisticTuringmachines,wemustbecarefulintalkingaboutprobabilities.Fixanencoding(I,E,R),anadversary
ˇTˇ,Rˇ),andtherecoveryalgorithmRiforeachuseri.AnexecutionofA=(I,
theresultingsystemspecifiestheinputskiandditoE,theoutputofE,the
ˇandoutputCˇ,andtheoutputoftherecoveryalgorithmtamperer’sinputk
ˇki,Cˇ)orRˇ(k,ˇ)asappropriate)foreachuser.ThesetofpossibleRi(R(ki,C
executionsofthestoragesystemisassignedprobabilitiesintheobviousway:theprobabilityofanexecutionistakenovertheinputstothestoragesystemandthecointossesoftheencodingschemeandtheadversary.Itwillbeconvenienttoconsidermultipleadversarieswithafixedencodingscheme.Inthiscase,weusePrA(Q)todenotetheprobabilitythataneventQoccurswhenAistheadversary.
Duringanexecutionofthestoragesystem,thetampereraltersthecombined
ˇ.Asaresult,someusersenduprecoveringtheirdocumentsstorefromCintoC
whileothersdonot.Wesummarizewhichusersrecovertheirdocumentsinarecoveryvector,whichisavector-valuedrandomvariablerinwhichri=1
ˇ)=di(i.e.,ifuserirecovershisdocument)and0otherwise.ForifRi(ki,C
example,iftheservercontainsdocumentsd1,d2,andd3andinanexecutionwerecoveronlyd1andd2,thenr=110.4.2
OurNotionsofEntanglement
InSection2,weobservedthattheblock-sharingnotionofentanglementprovidedbyDagsterandTanglerisnotadequateforourpurposes.Thismotivatesustoproposethenotionofdocumentdependency,whichformalizestheideathat“ifmydatadependsonyours,Ican’tgetmydatabackifyoucan’t.”Inthisway,thefatesofspecificdocumentsbecomelinkedtogether:specifically,ifdocumentdidependsondocumentdj,thenwheneverdjcannotberecoveredneithercandi.
Givenjustoneexecution,eitherusersiandjeachgettheirdatabackortheydon’t.Sohowcanwesaythattheparticularoutcomeforidependsontheoutcomeforj?Essentially,wearesayingthatwearehappywithexecutionsinwhicheitherjrecoversitsdata(whetherornotidoes)orinwhichjdoesnotrecoveritsdataandidoesnoteither.Executionsinwhichjdoesnotrecoveritsdatabutidoesarebadexecutionsinthissense.Wewilltrytoexcludethesebadexecutionsbysayingthattheyeitherneveroccuroroccuronlywithverylowprobability.Formally:
Definition1.AdocumentdidependsonadocumentdjwithrespecttoaclassofadversariesA,denoteddi֒→dj,if,foralladversariesA∈A,
Pr[ri=0∨rj=1]≥1−ǫ.
A
A
Remark1.Hereafter,ǫreferstoanegligiblefunctionofthesecurityparameters.2
Theultimateformofdependencyisall-or-nothingintegrity.Intuitively,astoragesystemisall-or-nothingifeithereveryuserirecovershisdataornouserdoes:
Definition2.Astoragesystemisall-or-nothingwithrespecttoaclassofadversariesAif,forallA∈A,
Pr[r=0n∨r=1n]≥1−ǫ.
A
Itiseasytoshowthat
Theorem3.Astoragesystemisall-or-nothingwithrespecttoaclassofad-versariesAifandonlyif,forallusersi,j,di֒→dj.
All-or-nothingintegrityisaverystrongproperty.Insomemodels,wemaynotbeabletoachieveit,andwewillacceptaweakerpropertycalledsymmetricrecovery.Symmetricrecoveryrequiresthatallusersrecovertheirdocumentswithequalprobability:
Definition3.AstoragesystemhassymmetricrecoverywithrespecttoaclassofadversariesAif,forallA∈Aandallusersiandj,
Pr[ri=1]=Pr[rj=1].
A
A
A
Symmetricrecoverysaysnothingaboutwhathappensinparticularexecu-tions.Forexample,itisconsistentwiththedefinitionforexactlyoneofthedataitemstoberecoveredineveryexecution,aslongastheadversarycannotaffectwhichdataitemisrecovered.Thisisnotasstrongapropertyasall-or-nothingintegrity,butitisthebestthatcanbedoneinsomecases.
5PossibilityandImpossibilityResults
Thepossibilityofachievingall-or-nothingintegrity(abbreviatedAONI)de-pendsontheclassofadversariesweconsider.InSections5.1through5.3,weconsideradversarieswithanarbitrarytamperer.WeshowthatAONIcannotalwaysbeachievedinthiscase.TheninSection5.4,welookatadversarieswithadestructivetamperer.Wegiveasimpleinterpolationschemethatachievesall-or-nothingintegrityforadestructivetampererinallthreerecoverymodels.
5.1PossibilityofAONIforStandard-Recovery-AlgorithmModel
Inthestandard-recovery-algorithmmodel,allusersusethestandardrecoveryalgorithmR;thatisRi=Rforallusersi.
Thismodelallowsaverysimplemechanismforall-or-nothingintegritybasedonMessageAuthenticationCodes(MACs).3Theintuitionbehindthismecha-nismisthattheencodingalgorithmEsimplytagsthedatastorewithaMACusingakeyknowntoalltheusers,andtherecoveryalgorithmRreturnsanindividualuser’sdataonlyiftheMAContheentiredatabaseisvalid.
Wenowgiveanencodingscheme(I,E,R)basedonaMACscheme(GEN,TAG,VER):InitializationTheinitializationalgorithmIcomputeskMAC=GEN(1s).It
thenreturnsanencodingkeykE=kMACandrecoverykeyski=(i,kMAC).EntanglementTheencodingalgorithmEgeneratesann-tuple
m=(d1,d2,...,dn)andreturnsC=(m,σ)whereσ=TAG(kMAC,m).RecoveryThestandardrecoveryalgorithmRtakesasinputakeyki=(i,kMAC)
ˇ=(m,andthe(possiblymodified)storeCˇσˇ).ItreturnsmˇiifVER(kMAC,m,ˇσˇ)=
acceptandreturnsadefaultvalue⊥otherwise.Thefollowingtheoremstatesthatthisencodingschemeachievesall-or-nothingintegritywithstandardrecoveryalgorithms:
Theorem4.Let(GEN,TAG,VER)beaMACschemethatisexistentiallyunforgeableagainstchosenmessageattacks,andlet(I,E,R)beanencodingschemebasedonthisMACschemeasabove.LetAbetheclassofadversaries
ˇ.Thenthereexiststhatdoesnotprovidenon-standardrecoveryalgorithmsR
someminimums0suchthatforanysecurityparameters≥s0andanyinputsd1,...,dnwith|di|≤s,(I,E,R)isall-or-nothingwithrespecttoA.5.2
ImpossibilityofAONIforPublicandPrivate-Recovery-AlgorithmModels
Inboththesemodels,theadversarymodifiesthecommonstoreanddistributes
ˇtotheusers(eithertoallusersoronlytoanon-standardrecoveryalgorithmR
afewselectaccomplices).Letusbeginbyshowingthatall-or-nothingintegritycannotbeachievedconsistentlyineithercase:
Theorem5.Foranyencodingscheme(I,E,R),ifAistheclassofadver-ˇ,then(I,E,R)isnotall-sariesprovidingnon-standardrecoveryalgorithmsRor-nothingwithrespecttoA.
Theessentialideaoftheproofistohavetheadversarysupplyadefective
ˇthatfailsrandomlywithprobability1/n.ThisyieldsarecoveryalgorithmR
constantprobabilityconvergingto1/ethatsomedocumentisnotreturned,whileallothersare.
Thisproofisrathertrivial,whichsuggeststhatlettingtheadversarysub-stituteanerror-pronerecoveryalgorithminplaceofthestandardonegivestheadversaryfartoomuchpower.Butitisnotatallclearhowtorestrictthemodeltoallowtheadversarytoprovideanimprovedrecoveryalgorithmwithoutal-lowingforthisparticularattack.AllowinguserstoapplytheoriginalrecoveryalgorithmRcanbedefeatedbysuperencryptingthedatastoreandburyingthe
ˇ;defeatingthisattackwouldrequireanalyz-decryptionkeyintheerror-proneR
ˇtoundothesuperencryptionandremovetheerrors,ataskthatislikelyingR
tobedifficultinpractice.4
Ontheotherhand,wedonotknowofanygeneralmechanismtoensurethat
ˇ,anditisnotoutofthequestionnousefulinformationcanbegleanedfromR
thatthereisanencodingsotransparentthatnosuperencryptioncandisguise
ˇareˇandtheadversary’skeykitforsufficientlylargeinputs,giventhatbothR
public.5.3
PossibilityofSymmetricRecoveryforPublic-Recovery-AlgorithmModel
Aswehaveseen,ifweplacenorestrictionsonthetamperer,itbecomesimpos-sibletoachieveall-or-nothingintegrityinthepublic-recovery-algorithmmodel.Wenowshowthatwecanstillachievesymmetricrecovery.
Becausewecannotpreventmassdestructionofdata,wewillsettleforpre-ventingtargeteddestruction.Thebasicintuitionisthatiftheencodingprocessissymmetricwithrespecttopermutationsofthedata,thenneithertheadversarynoritspartner,thenon-standardrecoveryalgorithm,candistinguishbetweendifferentinputs.Symmetryintheencodingalgorithmisnotdifficulttoachieveandbasicallyrequiresnotincludinganypositionalinformationinthekeysortherepresentationofdatainthecommonstore.Oneexampleofasymmetricencodingisatrivialmechanismthattagseachinputdiwitharandomkiandthenstoresasequenceof(di,ki)pairsinrandomorder.
Symmetryinthedataisastrongerrequirement.Weassumethatusers’docu-mentsdiareindependentandidenticallydistributed(i.i.d.)randomvariables.Ifdocumentsarenoti.i.d(inparticular,iftheyarefixed),wecanuseasimpletricktomakethemappeari.i.d.:Eachuseripicksasmallnumberriindependentlyanduniformlyatrandom,remembersthenumber,andcomputesd′i=di⊕G(ri),
′
whereGisapseudorandomgenerator.Thenewdiarealsouniformandinde-pendent(andthuscomputationallyindistinguishablefromi.i.d.).Theuserscan
thenstoredocumentsd′i(1≤i≤n)insteadoftheoriginaldocumentsdi.To
′
recoverdi,useriwouldretrieved′ifromtheserverandcomputedi=di⊕G(ri).
Weshallneedaformaldefinitionofsymmetricencodings:Definition4.Anencodingscheme(I,E,R)issymmetricif,foranysandn,anyinputsd1,d2,...dn,andanypermutationπoftheindices1throughn,ifthejointdistributionofk1,k2,...,knandCinexecutionswithuserinputsd1,d2,...dnisequaltothejointdistributionofkπ1,kπ2,...,kπnandCinexe-cutionswithuserinputsdπ1,dπ2,...dπn.
Usingthisdefinition,itiseasytoshowthatanysymmetricencodinggivessymmetricrecovery:
Theorem6.Let(I,E,R)beasymmetricencodingscheme.LetAbeaclassofadversariesasinTheorem5.Fixsandn,andletd1,...,dnberandomvariablesthatareindependentandidenticallydistributed.Then(I,E,R)hassymmetricrecoverywithrespecttoA.5.4
PossibilityofAONIforDestructiveAdversaries
Giventheresultsoftheprevioussections,toachieveall-or-nothingintegrityweneedtoplacesomeadditionalrestrictionsontheadversary.
ˇisdestructiveiftherangeofTˇwhenappliedtoAtamperingalgorithmT
aninputdomainofmdistinctpossibledatastoreshassizelessthanm.The
ˇwhenappliedamountofdestructivenessismeasuredinbits:iftherangeofT
ˇdestroyslgm−lgrbitsofentropy.toadomainofsizemhassizer,thenT
ˇaresmallerthanNotethatitisnotnecessarilythecasethattheoutputsofT
itsinputs;itisenoughthattherebefewerofthem.
Below,wedescribeaparticularencoding,basedonpolynomialinterpolation,withthepropertythatafterasufficientlydestructivetampering,theprobabilitythatanyrecoveryalgorithmcanreconstructaparticulardiissmall.Whilethisistriviallytrueforanunrestrainedtampererthatdestroysalllgmbitsofthecommonstore,ourschemerequiresonlythatwithndocumentsthetampererdestroyslightlymorethannlg(n/ǫ)bitsbeforetheprobabilitythatanyofthedatacanberecovereddropsbelowǫ(aformalstatementofthisresultisfoundinCorollary1).Sincencountsonlythenumberofusersandnotthesizeofthedata,forafixedpopulationofusersthenumberofbitsthatcanbedestroyedbeforealluserslosetheirdataiseffectivelyaconstantindependentofthesizeofthestorebeingtamperedwith.
Theencodingschemeisasfollows.ItassumesthateachdataitemcanbeencodedasanelementofZp,wherepisaprimeofroughlysbits.
InitializationTheinitializationalgorithmIchoosesk1,k2,...knindependently
anduniformlyatrandomwithoutreplacementfromZp.ItsetskE=(k1,k2,...,kn)andthenreturnskE,k1,...kn.
EntanglementTheencodingalgorithmEcomputes,usingLagrangeinterpo-lation,thecoefficients
cn−1,cn−2,...c0oftheuniquedegree(n−1)polynomialfoverZpwiththepropertythatf(ki)=diforeachi.ItreturnsC=(cn−1,cn−2,...c0).
RecoveryThestandardrecoveryalgorithmRreturnsf(ki),wherefisthe
polynomialwhosecoefficientsaregivenbyC.Intuitively,thereasonthetamperercannotremovetoomuchentropywithoutdestroyingalldataisthatitcannotidentifywhichpointsd=f(k)correspondtoactualuserkeys.Whenitmapstwopolynomialsf1andf2tothesamecorrupted
ˇ,thebestthatthenon-standardrecoveryalgorithmcandoisreturnstoreC
oneoff1(ki)orf2(ki)givenaparticularkeyki.Butiftoomanypolynomials
ˇ,theoddsthatRˇreturnsthevalueofthecorrectaremappedtothesameC
polynomialwillbesmall.
Acomplicationisthataparticularlycleveradversarycouldlookforpoly-nomialswhosevaluesoverlap;iff1(k)=f2(k),itdoesn’tmatterwhichftherecoveryalgorithmpicks.Butherewecanusethatfactthattwodegree(n−1)polynomialscannotoverlapinmorethan(n−1)placeswithoutbeingequal.Thislimitshowmuchpackingtheadversarycando.
AsinTheorem6,weassumethattheuserinputsd1,...,dnarechosenin-dependentlyandhaveidenticaldistributions.WemakeafurtherassumptionthateachdiischosenuniformlyfromZp.Thisisnecessarytoensurethattheresultingpolynomialsspanthefullpnpossibilities.5
ˇTˇ,Rˇ)beanadversaryTheorem7.Let(I,E,R)bedefinedasabove.LetA=(I,
ˇisdestructive:forafixedinputsizeandsecurityparameter,thereisawhereT
ˇ,constantMsuchthatforeachkeyk
ˇ(k,ˇf)}|≤M,|{T
wherefrangesoverthepossiblestorevalues,i.e.overalldegree-(n−1)polyno-mialsoverZp.IfthediaredrawnindependentlyanduniformlyfromZp,then
ˇistheprobabilitythatatleastoneuserirecoversdiusingR
Pr[r=0]<
A
n
2n2+nM1/n
5
Theassumptionthatthedocumentsarei.i.d.doesnotconstraintheapplicabilityof
ourresultsmuch,becausethetechniquetogetridofitdescribedinSection5.2canalsobeusedhere.
6ConclusionandFutureWork
Ourresultsaresummarizedbelow:
DestructiveTamperer
all-or-nothingsymmetricrecoverynoguaranteespossible
Theyshowthatitispossibleinprincipletoachieveall-or-nothingintegritywithonlymildrestrictionsontheadversary.Whetheritispossibleinpracticeisadifferentquestion.Ourmodelabstractsawaymostofthedetailsofthestor-ageandrecoveryprocesses,whichhidesundesirablefeaturesofouralgorithmssuchastheneedtoprocessalldatabeingstoredsimultaneouslyandtheneedtoreadeverybitofthedatastoretorecoveranydataitem.Someoftheseun-desirablefeaturescouldberemovedwithamoresophisticatedmodel,suchasaround-basedmodelthattreateddataasarrivingovertime,allowingcombiningalgorithmsthatwouldtouchlessofthedatastoreforeachstorageorretrievaloperationatthecostofmakingfewerdocumentsdependoneachother.TheresultingsystemmightlooklikeavariantofDagsterorTanglerwithstrongermechanismsforentanglement.Butsuchamodelmightpermitmoredangerousattacksiftheadversaryisallowedtotamperwithdataduringstorage,andfind-ingtherightbalancebetweenprovidingusefulguaranteesandmodelingrealisticattackswillbenecessary.Wehavemadeafirststeptowardsthisgoalinthepresentwork,butmuchstillremainstobedone.
References
1.R.J.Anderson.Theeternityservice.InProceedingsofPRAGOCRYPT96,pages242–252,1996.
2.J.Aspnes,J.Feigenbaum,A.Yampolskiy,andS.Zhong.Towardsatheoryofdataentanglement.TechnicalReportYALEU/DCS/TR-1277,March2004.Availableathttp://www.cs.yale.edu/~aspnes/entanglement-abstract.html.
3.B.Barak,O.Goldreich,S.Rudich,A.Sahai,S.Vadhan,andK.Yang.Onthe(im)possibilityofobfuscatingprograms.InAdvancesinCryptology-ProceedingsofCRYPTO2001,2001.
4.M.CastroandB.Liskov.PracticalByzantinefaulttolerance.InProceedingsofthe3rdSymposiumonOperatingSystemsDesignandImplementation,pages173–186,1999.
5.I.Clarke,O.Sandberg,B.Wiley,andT.Hong.Freenet:Adistributedinformationstorageandretrievalsystem.InDesigningPrivacyEnhancingTechnologies:Inter-nationalWorkshoponDesignIssuesinAnonymityandUnobservability,volume2009ofLectureNotesinComputerScience,pages46–66,2000.
6.K.Fu,F.Kaashoek,andD.Mazieres.Fastandsecuredistributedread-onlyfilesystem.InProceedingsofthe4thSymposiumonOperatingSystemsDesignandImplementation,pages181–196,2000.
7.G.A.Gibson,D.F.Nagle,K.Amiri,J.Butler,F.W.Chang,H.Gobioff,C.Hardin,E.Riedel,D.Rochberg,andJ.Zelenka.Acost-effective,high-bandwidthstoragearchitecture.InProceedingsofthe8thInternationalConferenceonArchitecturalSupportforProgrammingLanguagesandOperatingSystems,pages92–103,1998.8.E.Goh,H.Shacham,N.Mdadugu,andD.Boneh.Sirius:Securingremoteun-trustedstorage.InProceedingsoftheInternetSociety(ISOC)NetworkandDis-tributedSystemsSecurity(NDSS)Symposium,pages131–145,2003.
9.A.GoldbergandP.Yianilos.Towardsanarchivalintermemory.InProceedingsoftheIEEEInternationalForumonResearchandTechnology,AdvancesinDigitalLibraries(ADL’98),pages147–156.IEEEComputerSociety,1998.
10.S.GoldwasserandM.Bellare.Lecturenotesoncryptography.SummerCourse
“CryptographyandComputerSecurity”atMIT,1996–1999,1999.
11.S.Goldwasser,S.Micali,andR.Rivest.Adigitalsignatureschemesecureagainst
adaptivechosenmessageattack.SIAMJournalonComputing,17(2):281–308,1988.
12.U.MaheshwariandR.Vingralek.Howtobuildatrusteddatabasesystemon
untrustedstorage.InProceedingsofthe4thSymposiumonOperatingSystemsDesignandImplementation,pages135–150,2000.
13.D.MazieresandD.Shasha.Don’ttrustyourfileserver.InProceedingsofthe8th
IEEEWorkshoponHotTopicsinOperatingSystems,pages99–104,2001.
14.D.MazieresandD.Shasha.BuildingsecurefilesystemsoutofByzantinestor-age.InProceedingsoftheTwenty-FirstAnnualACMSymposiumonPrinciplesofDistributedComputing,pages108–117,2002.
15.D.MazieresandM.Waldman.Tangler:Acensorship-resistantpublishingsystem
basedondocumententanglements.InProceedingsofthe8thACMConferenceonComputerandCommunicationsSecurity,pages126–135,2001.
16.R.Merkle.Protocolsforpublickeycryptosystems.InIEEESymposiumonSecurity
andPrivacy,pages122–134,1980.17.MojoNation.Technologyoverview.
Onlineathttp://www.mojonation.net/docs/technical_overview.shtml,2000.18.R.Rivest.All-or-nothingencryptionandthepackagetransform.InFastSoftware
Encryption,volume1267ofLectureNotesinComputerScience,pages210–218,1997.
19.A.Shamir.Howtoshareasecret.CommunicationsoftheACM,22(11):612–613,
1979.
20.J.Strunk,G.Goodson,M.Scheinholtz,C.Soules,andG.Ganger.Self-securing
storage:Protectingdataincompromisedsystems.InProceedingsofthe4thSym-posiumonOperatingSystemsDesignandImplementation,pages165–180,2000.21.A.StubblefieldandD.S.Wallach.Dagster:Censorship-resistantpublishingwith-outreplication.TechnicalReportTR01-380,RiceUniversity,2001.
22.M.WaldmanandD.Mazieres.Tangler:Acensorship-resistantpublishingsystem
basedondocumententanglements.InProceedingsofthe8thACMConferenceonComputerandCommunicationsSecurity,pages126–135,2001.
23.M.Waldman,A.Rubin,andL.Cranor.Publius:Arobust,tamper-evident,
censorship-resistant,webpublishingsystem.InProceedingsof9thUSENIXSe-curitySymposium,2000.
因篇幅问题不能全部显示，请点此查看更多更全内容