《das安全-关于数据篡改的验证.ppt》由会员分享，可在线阅读，更多相关《das安全-关于数据篡改的验证.ppt（48页珍藏版）》请在金锄头文库上搜索。
1、DAS安全-关于数据篡改的验证outlinevDAS安全中关于数据篡改及其验证的介绍vDAS安全中关于数据篡改验证的几种方法：基于数字签名的验证方法基于验证数据结构的方法基于概率的验证方法基于验证查询的方法（本质上也是概率验证）什么是数据篡改v1对于数据库中数据进行非法的增删改操作v2只返回部分查询结果如范围查询的结果集为100条只返回50条等值查询是特殊的范围查询v3对client端的操作置之不理如server没有将client端insert的元组保存到DB中对于数据篡改的验证v目的：保证client端的query结果的正确性和完整性。不管server对存储的数据做了什么操作，只要不影响qu
2、ery结果的正确性和完整性，就认为没有对client的数据进行篡改。对于数据篡改的验证v考察角度：client （而不是server）v考察点：query结果不从用户对数据库的各种操作入手（比如insert、delete是否正确执行）。而是通过对query结果的正确性和完整性的进行验证。数据篡改验证的几种方法：v基于数字签名的验证方法v基于验证数据结构的方法v基于概率的验证方法v基于验证查询的方法基于数字签名的验证方法v正确性验证:对每条记录进行签名，通过签名对数据的正确性进行验证v完整性验证：各条记录采用链式数字签名，链式数字签名记录了元组间的顺序关系，通过链式数字签名验证返回结果集的完整性
3、基于数字签名的验证方法v几种方法：逐条验证 RSA Signature Batch Verification of RSA Signature Condensed RSA signature Aggregated-BGLSDigital Signature Aggregation and Chaining (DSAC)逐条验证 RSA Signaturev功能：能验证tuple的正确性v缺点：不能验证结果集的完整性RSA signature加密解密时间开销比较大结果集很大的时候(thousands of tuples)，数字签名消耗的带宽也很大，验证的时间开销很大Batch Verificat
4、ion of RSA Signature v只能验证tuple的正确性，不能验证结果的完整性。v效率上的改进：批量验证利用RSA加密算法的乘法同态性（multiplicatively homomorphic）Condensed RSA signaturev只能验证tuple的正确性，不能验证结果的完整性。v效率上的改进：将多个数据签名集成为一个返回结果集的签名只有一个减少带宽压力减少客户端的计算压力v缺陷：只能对同一个用户的签名进行集成Aggregated-BGLSv只能验证tuple的正确性，不能验证结果的完整性。v对condensed-RSA的改进方法，可以将多个用户的签名统一集成。v对于
5、多用户签名的情况，验证的开销很大。Digital Signature Aggregation and Chaining (DSAC)v正确性验证：将结果集中所有元组的签名集成为一个v完整性验证：每条元组的签名为链式数字签名数字签名链的生成：vh() is a cryptographic hash function such as SHA, v| denotes concatenation,vIPRi denotes the immediate predecessor tuple along dimension Ivl is the number of searchable dimensions
6、 of that relationvSK is the private signing key of the data owner.DSAC(con2)vThe immediate predecessors of a tuple are computed as follows:(1) Sort the tuples in increasing order along each searchable dimension （排序）(2) The immediate predecessor of a given tuple along a given dimension is a tuple wit
7、h the highest value for that attribute that is less than the value of the given tuple (highest lower bound) along that attribute.（排序后的直接前驱）vThus, each tuple has as many immediate predecessorsas there are searchable attributes (dimensions). In other words, each tuple has l Immediate Predecessors wher
8、e l is the number of searchable dimensions along which a query can be issued.（在可数值有序即可进行range query的列上才需要排序）DSAC(con3)v链式数字签名的生成：DSAC(con4)v完整性的验证过程DSAC的优点v可验证range query的完整性DSAC的不足v要考虑不泄露元组间的顺序关系v结果集的正确性验证消耗大结果集为1条元组的正确性验证消耗：需要同时返回这条元组在l维上的前驱结果集为N条元组时，每条元组都要返回其余l-1维上的前驱，用于验证数据的正确性v链式数字签名的维护开销很大增删改一
9、条数据，可能会导致l维上的排序的改变，从而导致大量元组链式数据签名的改变没有考虑对重复元组的处理 DSAC的缺陷v对于客户端做的增删改的验证：server是否存储了client的操作结果Client没有关于签名最新的信息，不能验证server是否执行了client要求的操作v对于无顺序关系的属性列上的query的完整性的验证：不能作范围查询，因此链式签名中没有此列的信息电子银行中的帐户名，类型为字符串vSelect * from T where name = jony;vResult = null结果集是否真的为空？DSAC不能验证v无法验证集合函数（sum、avg）结果的正确性数据篡改验证的
10、几种方法：v基于数字签名的验证方法v基于验证数据结构的方法v基于概率的验证方法v基于验证查询的方法基于验证数据结构的方法v目前主要的方法：Merkle Hash Tree(MHT)Merkle Hash Tree(MHT)vMHT的构造：某一个维/属性上的元组排序MHT的叶子结点是按照上述排序hash的结果值中间结点就是它的孩子结点值的连接后的hash值对根结点进行签名MHT(con2)vMHT的构造MHT的构造过程就是它的验证过程v正确性验证v完整性验证MHT(con3)v优点：通过hash值 验证元组的正确性，代替了signature能验证简单的元组级的range query结果的完整性M
11、HT(con4)v缺点：不支持join结果集完整性的验证不支持集合函数（sum、avg）的正确性/完整性的验证每个用于范围查询的属性/维度上都需要建立MHT，以保证返回结果集的完整性v维护起来困难，对数据进行增删改操作必然导致MHT的变化v要考虑不泄露数据间的orderv对于重复值的处理没有考虑对于不能做 range query的列（如列类型为字符串），无法保证结果集的完整性用于支持验证的结点的传递占据带宽数据篡改验证的几种方法：v基于数字签名的验证方法v基于验证数据结构的方法v基于概率的验证方法v基于验证查询的方法基于概率的验证方法v正确性验证：We assume the tuple has
12、 an additional field, which allows us to easily check the authenticity of the tuple. For example, the field can be computed as :where H is a one-way hashing function.基于概率的验证方法v完整性验证：在server端插入一些client端可知道/存储的fake tuples，通过验证query结果中fake数据是否与client端符合query的fake tuples相同，来验证返回结果的完整性。Any fake tuples mi
13、ssing in the query result?vReal tuple 与 fake tuple 的区分：基于概率的验证方法v符号介绍：Let Q be a query.Let Cs(Q) be the set of fake tuples in the query result sent back by the serverLet Cc(Q) be the set of fake tuples that satisfy the queryvIntegrity check: Cc(Q) = Cs(Q) If |Cc(Q)| |Cs(Q)|, then there is definitely
14、 a problem.If |Cc(Q)| = |Cs(Q)|, do we need to compare the two sets for equality?基于概率的验证方法vTHEOREM 1. If |Cs(Q)| = |Cc(Q)|, then Cs(Q) = Cc(Q).基于概率的验证方法v验证的关键：fake tuples的构造数据分布对于安全很重要Fake tuple是否是有用的数据？对于完全不会出现在query结果中的fake tuple对于完整性的验证没有意义。出现的几率很小则对于完整性的验证贡献不大。或结果集中的fake tuple数量不多，则发现数据篡改的概率较小。F
15、ake tuple数量太多，则会增加server存储，降低query执行效率，fake tuples的传输增加带宽压力，Cs(Q)与Cc(Q)的比较时间也会加大。基于概率的验证方法v完整性验证方法：随机fake tuple 验证确定的/伪随机 fake tuple 验证随机fake tuple 验证v方法：在client端按real tuple distribution随机生成fake tuple，并存储在client端将fake tuple与real tuple一样处理后存放到serverClient发出query，server返回查询结果，包含符合query的real tuple 与 fa
16、ke tuple Cs(Q)在client端执行同一个query，得到满足query的fake tuple Cc(Q)比较|Cs(Q)|?=|Cc(Q)|，验证返回结果的完整性随机fake tuple 验证v优点：可验证简单的元组级的range query的完整性可验证含join的query的结果集的完整性可验证server对于client发出的增删改的执行v缺点：Client端需要存储和维护fake tuples确定的/伪随机 fake tuple 验证vChoose a family of functions（易于计算部分覆盖元组的个数）e.g., linear functions, qu
17、adratic functionsvRandomly pick a key, which determines a function in the familye.g., coefficients of the linear/quadratic functionsvEach client remembers the functionLittle storage costEfficient to find the count of fake tuples that satisfy a queryFake tuple 的生成vHow about distribution?Divide the fe
18、ature space into gridsCapture the distribution of the real data (count of tuples in each grid)Create a key (hence a deterministic function) for each gridThe count decides how many tuples the function generates for that gridFake tuple 的生成vFake tuple generation:简单查询的完整性验证vChecking integrityJoin操作完整性的验
19、证vIntegrity assurance of JoinsvJoin two tables T1 and T2SELECT *FROMT1 and T2 WHERE T1.B = T2.BvWe have 4 cases here:1. Original tuples from T1 join with original tuples from T22. Fake tuples from T1 join with original tuples from T23. Original tuples from T1 join with fake tuples from T24. Fake tup
20、les from T1 join with fake tuples from T2对于增删改的验证v在进行增删改操作的时候，加入适当的fake tuples，这样在query时，通过验证query结果的完整性，就能验证服务器是否执行了client端发出的增删改操作。基于概率的验证方法v优点：能验证元组的正确性能验证简单的query，join操作的返回结果集的完整性能验证server正确的执行了client端发出的增删改操作Client端无需维护大量的fake tuplesClient端对于满足query的fake tuple元组数的计算速度很快基于概率的验证方法v缺点：随着原数据的增加，ser
21、ver中存储的fake tuple成比例的增加，会降低查询执行效率，增加传输带宽压力，占用server存储空间基于概率的验证方法的不足v给定的函数方法生成的Fake tuple不能很好的模拟real tuple。如int a1; 1a110000; Int a2; 1a210;v此时的fake tuple构造函数在各维上还是均分对real tuple的模拟好吗？1、均分后的数据不会再是整数，但是对范围查询来说不会造成影响，但是在不满足列类型（int）的要求时，是否应该将数据加入server中呢？2、对于a2来说，随着a1上数据增多而进行增多会造成过多的fake tuples，这些fake tu
22、ples对实际query的验证有用吗？v只能验证能numerical的列，对于类型为字符串的列无法验证select name from T where name =jony;结果集为空，怎么验证它的正确性/完整性呢？数据篡改验证的几种方法：v基于数字签名的验证方法v基于验证数据结构的方法v基于概率的验证方法v基于验证查询的方法基于验证query的方法v正确性的验证可以采取与基于概率的验证方法相同的方法v完整性的验证：Client端存储关于real tuple的一些信息，根据client端的信息，自动生成一些针对client端存储的信息的query。比较query结果与client端得到的结果是否一致，验证查询结果的完整性。基于验证query的方法v方法：1、选择性的存储real tuples2、选择性的记录某些统计信息总结 v数据篡改验证的几个方面(从query结果来看):原数据未被非法的增删改简单的元组级select、join操作结果集完整性的验证不可做范围查询的属性列上等值查询完整性的验证 集合函数（sum、avg）正确性的验证Client的增删改操作得到完整执行v性能考虑：计算力存储带宽对查询的影响对数据分布的影响Q & A
