HASH GAME - Online Skill Game GET 300

　　摘要：在实现一个能抵御硬件攻击的安全处理器时，内存完整性校验是一个关键问题。针对现有完整性校验方法存在的代价大、速度慢等问题，本文提出一种新的、基于Hash树的完整性检验方法，它利用程序访问的局部性特征，根据存储块的访问频率来设置存储块大小，即在热访问区设置较小存储块，在冷访问区设置较大存储块，以此建立两棵Hash树，再基于较小的可信片内存储区保存这两棵Hash树的根结点，来校验不可信外部内存的数据完整性。本文重点讨论了该方法的基本原理、规则和算法，并对操作代价进行了详细分析。模拟实验表明，本文提出的方法比传统Hash树方法性能更好，代价更低，是一种可行的内存完整性校验方案。

　　存储器完整性校验是利用存储在可信计算基中不可被篡改的信息，通过某种算法,对外部非可信存储器实施完整性校验[1]。存储器完整性校验分为脱机(Offline)和联机(Online)校验[2]。脱机校验是在一个存储器操作序列完成后进行检测，它适用于不需精确探测异常的情形，它不需明确指明是哪个操作时被篡改；联机校验是在每一次存储器操作后马上进行校验，这种方式可以杜绝错误结果提交所造成的影响，但联机校验需要更频繁的检测，因而比脱机校验代价更高。

　　重放攻击(replayattacks)是威胁很大的一种攻击行为，用常规的MAC完整性保护方法不能阻止。重放攻击是实现安全计算平台面对的主要问题之一。目前主要有两种类型的重放攻击：一种是重放总线处理的日志，主要有cache-cache之间和cache-memory的总线处理；另一种是重放RAM中的数据。在内存独占的单处理器系统中，[]已经证明，在处理器中硬件实现Hash树或MAC树可以防止重放攻击。本方法是是基于Hash树校验的改进，因此可以防止重放攻击。

　　图1说明了此模型，在此模型中，可信的部件是处理器(图中灰色部分)，它能免于物理攻击， 它的内部状态不能被篡改，也不能通过物理手段直接观察到。处理器即可信计算基(trusted computing base, TCB)，它包括处理器核心、片内Cach、校验机制和加密引擎。处理器用在多任务环境中，运行多个互相不信任的进程。模型中不可信的部件是处理器外部内存、总线和周边设备，入侵者可能通过物理手段直接观查到它们的状态并进行篡改。

　　消息认证码（Message Authentication Code，MAC）[2]是指对每个存储器块进行Hash计算所得到的结果。它验证的基本原理是：首先对要保护的存储器分成多个相等的块，针对每个存储器块进行 Hash计算，保存所得结果，并将结果同存储器块附着在一起，当再次访问时，重新计算存储器块的MAC值，并同原始附着的MAC值进行比较，从而判断该存储器块的内容是否完整。同时为了有效检测到入侵者将一个合法块的内容拷贝到另一块中，MAC在计算时包含块所在的地址信息。MAC的优点是可以被快速计算及比较，但 MAC 不能应对重放攻击（Replay Attack），因为MAC可以保证是处理器保存的，但不能确保内容是最新的，因此目前MAC方法多与其他方法一起使用。

　　Hash 树（Hash Tree）也叫Merkle 树（MerkleTree）[4]，它可以检测出包括重放攻击在内的篡改存储器的行为，基本原理是：先将存储器分成多个等长块，并进行编号，每个存储块对应Hash树的叶结点，每个内部结点为下属两个结点Hash计算的结果，一直到根结点。树的根结点处于安全的存储区（一般置于处理器内的L2-Cache内，这一区域内数据不能被篡改）。在非可信存储器中，对于一个 叉(2) 的Hash 树而言，每次更新数据将导致 次Hash计算，这里N是要校验的存储器块数。Hash树校验存在的问题是：每次校验所需要的开销很大，导致系统性能显著下降。

　　缓冲型Hash 树（Cache Hash Tree）是MIT提出的完整性校验方法[4]，它是基本Hash树的一种优化方法，基本思想是利用处理器的片内Cache来提高基于Hash树的完整性校验效率。该方法假定在CPU内Cache（含L1-Cache和L2-Cache）是可信的，完整性校验装置同L2-Cache并在一起，用作完整性检查的Hash树内部结点被缓冲在L2-Cache中而维持可信，从而校验路径只需到达缓冲在L2-Cache中的结点即可停止，而不必一直进行到根结点。这种方法通过降低校验路径的长度，使得所需Hash计算的次数大大减小，因此可明显提高校验速度，测试结果表明，可使校验的性能代价减小到Hash树的25%。该方法的主要问题是需要较大的L2-Cache以便缓冲足够多的Hash树的内部结点，其次是需要占用较大L2-Cache空间，造成其它程序的运行效率下降。

　　LHash （Log Hash Integrity Checking，日志型Hash完整性检测）和H-LHash（Hierarchical Scheme of Log Hash Integrity Checking，日志型 Hash完整性检测的层次式方案）方法[5]，是MIT提出的“Lazy”型存储器完整性校验技术。通过维护一个存储器读写的操作日志，可以在稍后的某个时间一次性校验一系列存储器访问结果的完整性。LHash是一种脱机校验(Offline checking)，通过减少不必要的校验次数而降低整个校验过程的代价。H-LHash在LHash的基础上利用L2-Cache来缓冲部分结点，能够允许比LHash更频繁的检测，但基本与LHash相似。LHash / H-LHash由于多数时间只记录日志，因而“运行时性能”好，但一次校验代价会更大。因此，若想有效发挥LHash的性能，必须对检验要求是不频繁的。当检验更频繁时，LHash/H-LHash的性能将显著下降。

　　HW-HTree（Hot Access Window based Hash Tree Optimizing Approach，基于热访问窗口的Hash树优化算法）[1]是侯方勇博士提出来的，其主要思想是：维持 Hash 树基本结构不变，为其添加热点区域，通过优化热点区域，缩短校验路径来提高校验性能。具体来说，在校验数据以前，先保存每个热访问窗口的子树顶结点到安全区，这样在校验数据时，每次只校验到子树顶结点，不需要校验到根结点；同时在更新数据时，也只更新到子树顶结点；只有在HotWin平移时，才将更新的结点向上传递到根结点。 这种方法由于每次只校验到子树顶结点，缩短了校验路径，一定程度上提高了校验性能；但它采用统一的存储块划分方式，每个块尺寸较大，平均每次访问的代价仍较高。

　　VC-HTree的基本思想是：将保护的存储区分为热区和冷区，在不同区设置不同的数据块大小，即在热区设置多个大小相等、较小的存储块；在冷区设置多个大小相等、较大的存储块(冷区块大小一般为热区的整数倍)。同时维持两棵Hash树，一棵是热Hash树，由热区组合到一起而构建；另一棵是冷Hash树，由冷区组合到一起而构建。这样得到由两棵树组成的森林，如图1所示。图中左虚线框内为热区，右虚线框内为冷区(仅为了说明问题，实际的热区和冷区可能不止一个)。再将热Hash树和冷Hash树的顶点放在片内Cache中，以保证顶点是安全的(不能被篡改)。在校验时，类似Hash树方法，从叶结点读取数据并计算Hash值，一直计算到根结点。由于热访问区的小块每次操作代价低，操作次数多；冷访问区的大块每次操作代价高，操作次数少，二者综合使平均操作代价降低。

　　为方便说明，借鉴了文献[1]中访问窗口的概念。在热区中更小的访问区称为热访问窗口(HotWin)，图1中h1-h4在某一段时间构成一个HotWin，root1是这个HotWin中Hash子树的顶点，一个热区可有一个或多个HotWin；在冷区的更小的访问区称为冷访问窗口(ColdWin)，图1中h5-h8即为ColdWin，一个冷区也有一个或多个ColdWin，热、冷访问窗口的宽度远小于整个被保护存储空间的大小。

　　对于访问窗口大小的确定，要选取适当的宽度以利于校验。当访问窗口宽度更小，对于小段且离散分布的存储器访问，对访问区的覆盖更加合理，系统性能更好；但同时需要更多数量的访问窗口以覆盖访问聚簇区，且改变访问聚簇区会导致更多的热访问窗口移动，降低系统性能；当访问窗口宽度更大时，与上面效果相反。因此，要确定适当的访问窗口宽度，不能过大或过小，具体如何确定，主要依据模拟实验的结果，也可依据相关的分析和计算来确定。