das安全-关于数据篡改的验证.ppt

DAS安全,-关于数据篡改的验证,outline,DAS安全中关于数据篡改及其验证的介绍DAS安全中关于数据篡改验证的几种方法：基于数字签名的验证方法基于验证数据结构的方法基于概率的验证方法基于验证查询的方法（本质上也是概率验证）,什么是数据篡改,1对于数据库中数据进行非法的增删改操作2只返回部分查询结果如范围查询的结果集为100条只返回50条等值查询是特殊的范围查询3对client端的操作置之不理如server没有将client端insert的元组保存到DB中,对于数据篡改的验证,目的：保证client端的query结果的正确性和完整性。不管server对存储的数据做了什么操作，只要不影响query结果的正确性和完整性，就认为没有对client的数据进行篡改。,对于数据篡改的验证,考察角度：client（而不是server）考察点：query结果不从用户对数据库的各种操作入手（比如insert、delete是否正确执行）。而是通过对query结果的正确性和完整性的进行验证。,数据篡改验证的几种方法：,基于数字签名的验证方法基于验证数据结构的方法基于概率的验证方法基于验证查询的方法,基于数字签名的验证方法,正确性验证:对每条记录进行签名，通过签名对数据的正确性进行验证完整性验证：各条记录采用链式数字签名，链式数字签名记录了元组间的顺序关系，通过链式数字签名验证返回结果集的完整性,基于数字签名的验证方法,几种方法：逐条验证RSASignatureBatchVerificationofRSASignatureCondensedRSAsignatureAggregated-BGLSDigitalSignatureAggregationandChaining(DSAC),逐条验证RSASignature,功能：能验证tuple的正确性缺点：不能验证结果集的完整性RSAsignature加密解密时间开销比较大结果集很大的时候(thousandsoftuples)，数字签名消耗的带宽也很大，验证的时间开销很大,BatchVerificationofRSASignature,只能验证tuple的正确性，不能验证结果的完整性。效率上的改进：批量验证利用RSA加密算法的乘法同态性（multiplicativelyhomomorphic）,CondensedRSAsignature,只能验证tuple的正确性，不能验证结果的完整性。效率上的改进：将多个数据签名集成为一个返回结果集的签名只有一个减少带宽压力减少客户端的计算压力缺陷：只能对同一个用户的签名进行集成,Aggregated-BGLS,只能验证tuple的正确性，不能验证结果的完整性。对condensed-RSA的改进方法，可以将多个用户的签名统一集成。对于多用户签名的情况，验证的开销很大。,DigitalSignatureAggregationandChaining(DSAC),正确性验证：将结果集中所有元组的签名集成为一个完整性验证：每条元组的签名为链式数字签名数字签名链的生成：h()isacryptographichashfunctionsuchasSHA,|denotesconcatenation,IPRidenotestheimmediatepredecessortuplealongdimensionIlisthenumberofsearchabledimensionsofthatrelationSKistheprivatesigningkeyofthedataowner.,DSAC(con2),Theimmediatepredecessorsofatuplearecomputedasfollows:(1)Sortthetuplesinincreasingorderalongeachsearchabledimension（排序）(2)Theimmediatepredecessorofagiventuplealongagivendimensionisatuplewiththehighestvalueforthatattributethatislessthanthevalueofthegiventuple(highestlowerbound)alongthatattribute.（排序后的直接前驱）Thus,eachtuplehasasmanyimmediatepredecessorsastherearesearchableattributes(dimensions).Inotherwords,eachtuplehaslImmediatePredecessorswherelisthenumberofsearchabledimensionsalongwhichaquerycanbeissued.（在可数值有序即可进行rangequery的列上才需要排序）,DSAC(con3),链式数字签名的生成：,DSAC(con4),完整性的验证过程,DSAC的优点,可验证rangequery的完整性,DSAC的不足,要考虑不泄露元组间的顺序关系结果集的正确性验证消耗大结果集为1条元组的正确性验证消耗：需要同时返回这条元组在l维上的前驱结果集为N条元组时，每条元组都要返回其余l-1维上的前驱，用于验证数据的正确性链式数字签名的维护开销很大增删改一条数据，可能会导致l维上的排序的改变，从而导致大量元组链式数据签名的改变没有考虑对重复元组的处理,DSAC的缺陷,对于客户端做的增删改的验证：server是否存储了client的操作结果Client没有关于签名最新的信息，不能验证server是否执行了client要求的操作对于无顺序关系的属性列上的query的完整性的验证：不能作范围查询，因此链式签名中没有此列的信息电子银行中的帐户名，类型为字符串Select*fromTwherename=jony;Result=null结果集是否真的为空？DSAC不能验证无法验证集合函数（sum、avg）结果的正确性,数据篡改验证的几种方法：,基于数字签名的验证方法基于验证数据结构的方法基于概率的验证方法基于验证查询的方法,基于验证数据结构的方法,目前主要的方法：MerkleHashTree(MHT),MerkleHashTree(MHT),MHT的构造：某一个维/属性上的元组排序MHT的叶子结点是按照上述排序hash的结果值中间结点就是它的孩子结点值的连接后的hash值对根结点进行签名,MHT(con2),MHT的构造MHT的构造过程就是它的验证过程正确性验证完整性验证,MHT(con3),优点：通过hash值验证元组的正确性，代替了signature能验证简单的元组级的rangequery结果的完整性,MHT(con4),缺点：不支持join结果集完整性的验证不支持集合函数（sum、avg）的正确性/完整性的验证每个用于范围查询的属性/维度上都需要建立MHT，以保证返回结果集的完整性维护起来困难，对数据进行增删改操作必然导致MHT的变化要考虑不泄露数据间的order对于重复值的处理没有考虑对于不能做rangequery的列（如列类型为字符串），无法保证结果集的完整性用于支持验证的结点的传递占据带宽,数据篡改验证的几种方法：,基于数字签名的验证方法基于验证数据结构的方法基于概率的验证方法基于验证查询的方法,基于概率的验证方法,正确性验证：Weassumethetuplehasanadditionalfield,whichallowsustoeasilychecktheauthenticityofthetuple.Forexample,thefieldcanbecomputedas:whereHisaone-wayhashingfunction.,基于概率的验证方法,完整性验证：在server端插入一些client端可知道/存储的faketuples，通过验证query结果中fake数据是否与client端符合query的faketuples相同，来验证返回结果的完整性。Anyfaketuplesmissinginthequeryresult?Realtuple与faketuple的区分：,基于概率的验证方法,符号介绍：LetQbeaquery.LetCs(Q)bethesetoffaketuplesinthequeryresultsentbackbytheserverLetCc(Q)bethesetoffaketuplesthatsatisfythequeryIntegritycheck:Cc(Q)=Cs(Q)If|Cc(Q)|Cs(Q)|,thenthereisdefinitelyaproblem.If|Cc(Q)|=|Cs(Q)|,doweneedtocomparethetwosetsforequality?,基于概率的验证方法,THEOREM1.If|Cs(Q)|=|Cc(Q)|,thenCs(Q)=Cc(Q).,基于概率的验证方法,验证的关键：faketuples的构造数据分布对于安全很重要Faketuple是否是有用的数据？对于完全不会出现在query结果中的faketuple对于完整性的验证没有意义。出现的几率很小则对于完整性的验证贡献不大。或结果集中的faketuple数量不多，则发现数据篡改的概率较小。Faketuple数量太多，则会增加server存储，降低query执行效率，faketuples的传输增加带宽压力，Cs(Q)与Cc(Q)的比较时间也会加大。,基于概率的验证方法,完整性验证方法：随机faketuple验证确定的/伪随机faketuple验证,随机faketuple验证,方法：在client端按realtupledistribution随机生成faketuple，并存储在client端将faketuple与realtuple一样处理后存放到serverClient发出query，server返回查询结果，包含符合query的realtuple与faketupleCs(Q)在client端执行同一个query，得到满足query的faketupleCc(Q)比较|Cs(Q)|?=|Cc(Q)|，验证返回结果的完整性,随机faketuple验证,优点：可验证简单的元组级的rangequery的完整性可验证含join的query的结果集的完整性可验证server对于client发出的增删改的执行缺点：Client端需要存储和维护faketuples,确定的/伪随机faketuple验证,Chooseafamilyoffunctions（易于计算部分覆盖元组的个数）e.g.,linearfunctions,quadraticfunctionsRandomlypickakey,whichdeterminesafunctioninthefamilye.g.,coefficientsofthelinear/quadraticfunctionsEachclientremembersthefunctionLittlestoragecostEfficienttofindthecountoffaketuplesthatsatisfyaquery,Faketuple的生成,Howaboutdistribution?DividethefeaturespaceintogridsCapturethedistributionoftherealdata(countoftuplesineachgrid)Createakey(henceadeterministicfunction)foreachgridThecountdecideshowmanytuplesthefunctiongeneratesforthatgrid,Faketuple的生成,Faketuplegeneration:,简单查询的完整性验证,Checkingintegrity,Join操作完整性的验证,IntegrityassuranceofJoinsJointwotablesT1andT2SELECT*FROMT1andT2WHERET1.B=T2.BWehave4caseshere:1.OriginaltuplesfromT1joinwithoriginaltuplesfromT22.FaketuplesfromT1joinwithoriginaltuplesfromT23.OriginaltuplesfromT1joinwithfaketuplesfromT24.FaketuplesfromT1joinwithfaketuplesfromT2,对于增删改的验证,在进行增删改操作的时候，加入适当的faketuples，这样在query时，通过验证query结果的完整性，就能验证服务器是否执行了client端发出的增删改操作。,基于概率的验证方法,优点：能验证元组的正确性能验证简单的query，join操作的返回结果集的完整性能验证server正确的执行了client端发出的增删改操作Client端无需维护大量的faketuplesClient端对于满足query的faketuple元组数的计算速度很快,基于概率的验证方法,缺点：随着原数据的增加，server中存储的faketuple成比例的增加，会降低查询执行效率，增加传输带宽压力，占用server存储空间,基于概率的验证方法的不足,给定的函数方法生成的Faketuple不能很好的模拟realtuple。如inta1;1a110000;Inta2;1a210;此时的faketuple构造函数在各维上还是均分对realtuple的模拟好吗？1、均分后的数据不会再是整数，但是对范围查询来说不会造成影响，但是在不满足列类型（int）的要求时，是否应该将数据加入server中呢？2、对于a2来说，随着a1上数据增多而进行增多会造成过多的faketuples，这些faketuples对实际query的验证有用吗？只能验证能numerical的列，对于类型为字符串的列无法验证selectnamefromTwherename=jony;结果集为空，怎么验证它的正确性/完整性呢？,数据篡改验证的几种方法：,基于数字签名的验证方法基于验证数据结构的方法基于概率的验证方法基于验证查询的方法,基于验证query的方法,正确性的验证可以采取与基于概率的验证方法相同的方法完整性的验证：Client端存储关于realtuple的一些信息，根据client端的信息，自动生成一些针对client端存储的信息的query。比较query结果与client端得到的结果是否一致，验证查询结果的完整性。,基于验证query的方法,方法：1、选择性的存储realtuples2、选择性的记录某些统计信息,总结,数据篡改验证的几个方面(从query结果来看):原数据未被非法的增删改简单的元组级select、join操作结果集完整性的验证不可做范围查询的属性列上等值查询完整性的验证集合函数（sum、avg）正确性的验证Client的增删改操作得到完整执行性能考虑：计算力存储带宽对查询的影响对数据分布的影响,Q&A,