有限域向量空间上的细粒度数据完整性检验方法

摘要

本发明有限域向量空间上的细粒度数据完整性检验方法，属于计算机及信息安全领域，在细粒度层次上实现利用较少的检验数据指示较多的数据对象的完整性，可根据用户需求设定压缩程度、准确指示出错的数据对象数量。所述的细粒度数据完整性检验方法将待检验源数据对象映射到有限域GF(q)上的d维向量空间，将所有数据对象进行均匀划分，不同划分之间实现均匀交叉。每一种划分生成一组Hash，最终得到全面的数据完整性检验方案。本发明可节省存储完整性检验数据需要的存储空间和传输完整性检验数据需要的网络带宽，适用于大量数据的完整性检验，及电子数据业务中的数据安全验证，原始取证映像完整性和电子数据证据固定等场合。

说明书

技术领域

本发明涉及计算机学科、信息安全学科中的数据安全领域，具体涉及计 算机取证领域的证据固定。

背景技术

使用单向Hash函数生成数据的数字摘要信息后存储下来，通过重新生 成待检验数据的数字摘要信息和所存储的信息进行比较可以检查验证数据是 否有变化，从而实现数据完整性检验——如果数字摘要信息不完全相同，则 数据已发生变化。上述数字摘要信息是具有固定长度的Hash数据。数字摘 要信息的实际长度取决于完整性检验中采用的单向Hash函数，该长度和 Hash函数本身的安全性对完整性检验问题的安全性产生影响。为方便描 述，Hash函数生成的一份Hash数据称为一个Hash数据或一个Hash。在关 心源数据是否具有完整性时，重新生成Hash数据进行比较，验证数据的完 整性。信息社会人们面对的往往是海量数据，大量的场合需要确认数据(信 息)的安全性。计算机取证领域典型的应用是在进行取证复制的过程中计算 并存储取证映像的数字摘要信息以实现证据固定，从而保证取证分析用的副 本、最后的实际证据等的完整性。

取证映像(完全复制件)的完整性如果只停留在整体是否可靠的层面， 则偶然的数据变化就会影响全部数据的可用性，给数据的安全、证据的选用 带来灾难性的影响。所以，使用细粒度的数据完整性检验是计算机取证的必 然需求，即我们需要分别判断单个文件或小数据块(以下统称为数据对象) 是否具有完整性。依照传统的方法就需要每个数据对象都需要单独存储一份 固定长度的Hash数据。当处理海量数据对象时，细粒度完整性检验面临新 问题——完整性检验Hash数据也成了大规模数据，且Hash检验数据具有 随机性，无法使用数据压缩技术进行压缩，这将给完整性检验数据的存储和 网络传输效率带来较大的负面影响。例如：一个512GB硬盘的扇区级MD5 Hash值将需要16GB的存储量，如果使用强度较高的SHA-256则需要 32GB。

Vassil Roussev等人在文献“md5bloom：Forensic Filesystem Hashing Revisited”(见期刊Digital Investigation，2006，vol.3(s1)：82-90)中考虑衡量海 量数据之间的相似性时意识到了Hash数据的大数据量问题，引入 Bloomfilter技术将若干数据对象的Hash存储到一起形成一个Hash包—— Bloomfilter。该方法的Hash包不满足原来单向Hash函数的单向性，即不具 有抗碰撞性，即使两个相同的Hash包对应的原始数据也可能不同，所以不 能用于完整性检验。

Merkel在文献“Protocols for Public Key Cryptosystems”(见论文集IEEE Symposium on Security and Privacy，Oakland，California，USA，1980，122-134) 中讨论存储器内容完整性检验时为了加快频繁计算单个Hash时的计算速 度，采用了Hash数据的再Hash方式，其Hash数据关系形成一个多叉树结 构。侯方勇、王志英、刘真在可信计算问题中对非可信存储器的完整性检验 应用中也采用与此相同的基本思想，参见文献“基于Hash树热点窗口的存 储器完整性校验方法”(计算机学报.2004，Vol.27(11)：1471-1479)。该方法 的本质仍是单Hash检验单个数据对象——一个Hash检验一片存储区域。

由于人们过去没有关注细粒度的大量、海量数据，按照传统思路，有以 下三种选择：

一是忽略细粒度的完整性检验的需求，仍使用单一Hash数据；

二是每份细粒度数据都生成独立Hash数据，存储大规模的Hash数 据；

三是折衷使用某一中等规模的粒度，生成适量的Hash数据。

第一、二种选择即会出现前面分析的问题，或者完整性检验需求未得到 满足，或者Hash数据规模太大。第三种选择只实现了比细粒度要大的中等 粒度的完整性检验，也没有很好地满足完整性检验的需求。

陈龙等在“基于纠错码的电子证据网络化保全方法”(通信技术， 2008，Vol.41(11)：156-157，159)论文中讨论了细粒度数据完整性检验的简单 情形，只能指示很少的几个错误，且只能进行少量Hash压缩。

本发明在有限域的多维向量空间上设计了一种高效的均匀交叉的完整性 检验方案，在数据对象出现不满足完整性(简称出错)的可能性较小，或者 在所有数据对象中出错的数据对象较少时(以下简称低错误率)，利用该方 案使用适量的Hash数据即可实现细粒度的数据完整性检验。

发明内容

本发明设计了一种新的数据组合交叉完整性检验方法，在低错误率的条 件下将所有数据对象进行组合交叉，一个Hash监督若干数据对象，一个数 据对象被若干个Hash监督。本发明实现了细粒度的数据完整性检验，且实 现了Hash数据压缩，从而提供一种高压缩率的细粒度数据完整性检验方 案。利用较少的完整性检验数据——Hash数据指示较多的数据对象的完整 性，节省存储完整性检验数据需要的存储空间和传输完整性检验数据需要的 网络带宽。

为了实现完整性检验并同时实现Hash数据压缩的目的，本发明采用如 下的技术方案：首先根据需求，生成不同有限域GF(q)(具有q个元素的有 限域记为GF(q))和不同维度d(d>2)上具有特殊性质的向量组T。其中T的 每个向量都是d维向量，向量分量的元素属于GF(q)有限域。该特殊性质指 从向量组中任取的d个向量都满足线性无关的性质(称T为d-线性无关向 量组)。依据T中的每个向量设计一个对应的投影函数实现GF(q^d)到GF(q) 的映射。该映射实现了将q^d个元素映射到q个元素，且映射到每个元素的 元素个数都相同。

然后确定数据对象监督关系。一个Hash由某个数据对象作为其数据来 源的一部分，则该Hash对该数据对象进行了监督，依据该Hash可检验该 数据对象的完整性。依照固定的次序将q^d个数据对象进行编号以对应到 GF(q^d)的每个元素。上面的映射可把q^d个数据对象进行划分为q个部分—— 数据对象集合，每个部分有q^d-1个数据对象，即得到所有数据对象的一种均匀 划分。一个划分的每个数据对象集都生成1个Hash，一种划分就得到q个 Hash。若使用k个向量，k个映射就可以得到k个划分，由向量之间的线性 无关特性，不同划分之间实现了均匀交叉。

本发明实现时每个数据对象受k个Hash监督，即需要参与k次Hash生 成的计算过程。Hash计算的数据对象读取是时间性能方面的主要制约因 素，因此，提供并发计算方式保证数据对象只需读取一次，减少磁盘等外设 数据的输入时间，此部分的时间花费和传统方案相同。同时，由于Hash生 成时计算量较大，所以在保证只读入一次数据的同时，还提供一种可选的快 速再Hash计算方式实现Hash生成，所需时间只比传统的所有数据生成单 一Hash的方法略有增加，从而实现和传统简单完整性检验大体相当的时间 性能而计算速度无大的差异。

本方法可按照用户的需求来自由设定数据对象的实际粒度，例如，具体 数据对象既可以是一个大文件中的逻辑数据块，也可以是一系列物理扇区数 据块，同时还可以是目录中的具体文件。本方法可在一定范围内按照用户的 需求来设定准确指示的错误数量t和Hash数据压缩的程度。本发明生成较 多的独立Hash数据组，任一组Hash数据可在某一中间粒度独立指示所有 数据的完整性，多组Hash数据组合起来则在更小的基本粒度指示数据的完 整性。

该方法可实现细粒度的数据完整性检验，能准确指示出出错的任意t个 数据对象，在超出该数量范围的情形，也能大部分正确指示出实际错误来， 但不会出现出错对象被判定为正常对象，从而不影响实际的应用。可广泛应 用于计算机取证领域的证据固定。

说明书附图

图1 Hash并发计算流程图

图2 再Hash计算流程图

图3 完整性检验流程图

具体实施方式

细粒度数据完整性检验可以减小因偶然的错误或少数的篡改而造成整体 数据失效的灾难性影响。本方法针对总量较多的细粒度数据对象，通过交叉 检验的方法，使用较少的Hash数据实现较多数据对象的完整性检验。

本方法包括向量组系列生成，确定数据对象监督关系，数据的完整性 Hash生成(其中含Hash并发计算方式和Hash后再Hash计算方式两种具体 实现方式)，完整性Hash数据比较、待检验数据的完整性判定等模块组成。 将待检验的若干细粒度数据对象组织成有限域上的立方体或超方体结构，即 依照固定的次序将q^d个数据对象进行编号以对应到有限域GF(q^d)的每个元 素。使用有限域向量空间上的投影函数对数据对象进行均匀划分，每一种划 分生成一组Hash数据，进行均匀交叉检验，最终得到全面的数据完整性检 验方案，实现一定数量的出错数据对象的准确指示和Hash数据压缩。Hash 检验方法本身基于通用的安全单向Hash函数。

本方法按以下步骤实施：

1)生成向量组系列

将待检验的若干细粒度数据对象组织成有限域上的立方体或超方体结 构，不同的有限域GF(q)和不同维度d(d>2)上都生成各自的d-线性无关向量 组T，有限域GF(q)中q只能取素数或素数的幂，常用的情形是d＝3， 4≤q≤23。其中T的每个向量都是d维向量，向量的分量的元素属于GF(q)， 从向量组T中任取的d个向量都线性无关。

显然，GF(q)上的d维向量中的任一非0向量及其所有的线性表示中只 有一个有可能加入d-线性无关向量组，于是选择d个向量(1，0，...，0)、 (0，1，...，0)、...、(0，...，0，1)构成初始的向量组T，他们的其中1个分量为单位 元1、其它分量为0。同样根据单位元1的特殊性再将全1向量(1，1，...，1)加 入向量组T。理论上与上述某个向量线性相关的向量都可以替换该向量，而 且其它向量在满足加入后向量组T中的任意d个向量都线性无关的条件时 都可以加入。只依据这一原则任选某个向量并测试是否可以加入，效率很 低。

利用该条件我们知道某个向量及其所有的线性表示中只有一个有可能加 入，所以可直接进行限制加快搜索速度。所有新加入向量都限制第1个分量 为1(其它任意非0元素均是其线性表示)，第2个分量为与已加入向量对 应分量不同的任意元素，第3个分量为与第2个分量不等且与已加入向量对 应分量不同的任意元素，其它分量依据相同原则处理。逐个加入新向量直到 不能添加任何新的向量。

由于可能的组合还是非常多，基于这些启发式规则进行搜索逐步加入其 它向量，以找到最多的向量加入d-线性无关向量组。现已得到常用有限域 GF(q)上的3-线性无关向量组的总体信息见表1。

表1 已知3-线性无关向量组的最大向量数γ及编码可用参数

 

有限域 GF(q) T中的向量 数γ 错误指示 能力最大t 数据对象数 n＝q³数据对象受 监督次数 k＝2t+1GF(4)62645GF(5)621255GF(7)733437GF(8)1045129GF(9)947299GF(11)10413319GF(13)125219711GF(16)188409617GF(17)146491313GF(19)157685915GF(23)1781216717

2)用户设定需求

用户可自主设定自己的需求。由用户选择Hash压缩率，错误指示能力 t，提供需要实现检验的数据对象的粒度和总的数据对象规模。对所有数据 对象进行分组，每组数据对象分别应用该交叉检验方法。下面即设定每组数 据对象数量为n。

3)确定数据对象监督关系

设数据对象个数为n，错误指示能力为t。选取适当的素数或素数幂q， 及维数d，使得n≤q^d且k＝(d-1)t+1≤γ。从有限域GF(q)上的d-线性无关向量 组中选取k个向量(包含全部有0分量的向量)。数据对象对应到有限域的元 素：把数据对象依次编号为0到n-1，将每个编号i(i＝0，1，...，n-1)表示为 GF(q)上的d维向量(r_d，...，r₂，r₁)，满足i＝(r_d，...，r₂，r₁)＝r_dq^d-1+...+r₂q+r₁。对数据 对象进行投影划分：计算数据对象i(i＝0，1，...，n-1)在第j个(j＝1，2，...，k)向量 (记v_j＝(a_d，...，a₂，a₁))上的投影u，即$u={\pi }_{v_j}\left(i\right)=a_d{r}_d+...+a_2{r}_2+a_1{r}_1$(投影函数即 为把投影向量和数据对象向量的对应分量分别相乘再相加，其乘法及加法为 有限域GF(q)中的特殊运算)，依据投影u判定第i个数据对象参与第u+1 行第j列的Hash计算，即同一投影函数下投影相同的元素受同一个Hash监 督。每个Hash值都是由同一投影函数下投影相同的q^d-1个数据对象计算 Hash值得到的。每个投影函数可生成一组Hash，有q个。k个投影函数所 生成的Hash共得到q行k列的Hash矩阵，见表2。

表2 Hash矩阵

 

Hashk...211h_1，k...h_1，2h_1，12h_2，k...h_2，2h_2，1...............qh_q，k...h_q，2h_q，1

下面以实例详细说明有限域向量空间上的数据对象划分。以有限域 GF(2)，d＝3为例，数据对象的划分方法如下：

假设共有2³＝8个待检测的数据对象，依次编号为0、1、2、3、4、5、 6、7，将8个对象的编号表示为有限域3维向量空间上的点(0，0，0)， (0，0，1)，(0，1，0)，(0，1，1)，(1，0，0)，(1，0，1)，(1，1，0)，(1，1，1)。q＝2，d＝3对应线 性无关向量组T的4个向量为{(1，0，0)、(0，1，0)、(0，0，1)、(1，1，1)}。用T中 的1个向量和数据对象对应的向量进行投影运算：对应分量相乘再相加(加 法和异或运算结果相同)。如向量(1，0，0)——投影向量的第3维为1，且有 限域GF(2)只有0和1两个元素，所以划分的依据就是数据对象的向量在该 维上是0还是1；结果前4个数据对象得到0，后4个数据对象得到1，所 以第1个向量将数据对象分为(0，1，2，3)和(4，5，6，7)，可分别生成两个 Hash。同理，第2个向量将数据对象分为(0，1，4，5)和(2，3，6，7)；第3个 向量将数据对象分为(0，2，4，6)和(1，3，5，7)；第4个向量将数据对象分为 (0，3，5，6)和(1，2，4，7)。

如表3所示为数据对象与Hash之间的均匀交叉检验关系(以 GF(2)，d＝3，t＝1为例，表中1表示有监督关系，0表示没有)。

表3 数据对象与Hash之间的均匀交叉检验关系

4)Hash矩阵生成算法：

Hash矩阵生成包含并发计算和再Hash两种方式，可选其中之一生成 Hash矩阵。

并发计算方式依次读入数据对象，同时推进所有Hash的计算过程，该 方式保证源数据只需读入一次，每个数据对象参与Hash计算k次，所得 Hash与将相关数据读入直接计算Hash结果相同。Hash的数据计算总量为 原来的k倍。

如图1所示为Hash并发计算方式Hash矩阵生成流程图。

并发计算算法描述如下：

步骤1：根据有限域GF(q)、维数d以及指示错误能力t值从准备好的 相应d-线性无关向量组中取出k＝(d-1)*t+1个向量；

步骤2：初始化Hash矩阵(由单向Hash函数决定)，i＝0；

步骤3：读入数据对象i；

步骤4：由k个投影向量按前述方法计算该数据对象的监督关系，确定 需参与计算的k个Hash；

步骤5：分别取出Hash矩阵中对应中间结果或初值计算所有k个 Hash，将中间结果再存入Hash矩阵；

步骤6：i＝i+1，重复3到5直到数据对象处理完；

步骤7：输出Hash矩阵

再Hash计算方式的原理是用完整性数据H(H(D₁)+H(D₂)+...+H(D_q×q))替代 H(D₁+D₂+...+D_q×q)作为检验用的依据。其中H表示完整性检验单向Hash函数， +表示数据连接，D_i为数据对象。该方式同样保证源数据只需读入一次，每 个数据对象只参与Hash计算1次，另每个数据对象的Hash数据参与k次 Hash计算。由于一般情况下Hash数据比源数据少得多(按512字节的数据 块大小计算，MD5的Hash数据量是源数据的1/32)，所以最终Hash计算 数据总量只比源数据多出少量数据。又因为数据输入占实际执行时间的相当 大一部分，所以总时间将和传统所有数据计算单个Hash的时间相差很小。 再Hash方式的计算过程中也采用了并发计算方式同时推进所有Hash计算 过程的思想。

如图2所示为再Hash计算方式Hash矩阵生成流程图。

再Hash计算算法描述如下：

步骤1：根据有限域GF(q)、维数d以及指示错误能力t值从准备好的 相应d-线性无关向量组中取出k＝(d-1)*t+1个向量；

步骤2：初始化Hash矩阵(由单向Hash函数决定)，置数据对象 i＝0；

步骤3：建立和Hash矩阵一一对应的缓冲数据矩阵；

步骤4：读入数据对象i；

步骤5：计算该数据对象的Hash数据h；

步骤6：由k个投影向量按前述方法计算该数据对象的监督关系，确定 监督该数据对象的k个Hash以及相应的Hash数据缓冲位置(两者在各自矩 阵中位置相同)；

步骤7：将Hash数据h分别存入缓冲数据矩阵中的对应k个位置(已 有缓冲数据之后)；

步骤8：如果k个位置中某个或某几个位置的数据达到合适的规模(如 32字节、512字节等)，分别取出Hash矩阵中对应中间结果或初值计算缓 冲数据的对应Hash，将中间结果再存入Hash矩阵，并把缓冲数据清除；否 则继续；

步骤9：i＝i+1，重复4到8直到数据对象处理完；

步骤10：输出Hash矩阵

5)Hash检验算法：

如图3所示为细粒度完整性检验流程图。

步骤1：选取原Hash数据生成时相同的参数，采用相同的Hash计算方 式生成Hash矩阵

步骤2：将所得Hash矩阵和原Hash矩阵进行比较，如果任意一组 (列)Hash完全相符，则没有出错，所有数据都具有完整性，结束。否则 任意一组中至少有一个Hash不相符，继续下一步；

步骤3：先检查含0分量的d个向量生成的Hash组，统计不相符的Hash 数量；

步骤4：设这d组分别有x_d，...，x₂，x₁个Hash不相符，则最多有 x_d^*...^*x₂^*x₁个数据对象出错；

步骤5：从Hash矩阵相应列x_d个hash中取1个得到其行号(从小到 大)r_d，同理取得r_d-1，...，r₂，r₁。向量(r_d-1，...，r₂-1，r₁-1)可对应到一数据对象i；

依据数据对象监督关系依次检查数据对象i在其他(d-1)t-d+1组Hash中 对应Hash是否相符，若全都不相符，则数据对象i出错，不具有完整性；

步骤6：重复步骤5验证其它数据对象是否出错。

本发明的目的是设计出新的数据完整性交叉检验方法，能在准确指示一 定数量的出错数据对象的同时实现Hash数据压缩，显著地提高了Hash数 据的压缩效率；可以减小因偶然的错误或少数的篡改而造成整体数据失效的 灾难性影响；可以有效压缩海量Hash数据，节省完整性检验数据的存储空 间和传输时的网络带宽。

本方法主要应用于大量数据的完整性检验，适合包括电子数据业务等各 类数据安全验证场合，计算机取证领域的原始取证映像完整性和电子数据证 据固定等等场合。