HASH GAME - Online Skill Game GET 300

　　Microcomputer Applications Vo1． 25， No． 4， 2009 研究与设计 微型 电脑应用 2009 年第 25 卷第 4 期 文章编号 ：1007— 757X (2009)4-0017— 03 一种针对磁盘完整性校验的增量 hash 算法 宋宁楠谷大武侯方勇 摘的规模成 比例。 论 文采用增量校 验的思想 ， 设 计 了一种针对磁盘 完整性校 验的 hash 函数称 为 iHash。 该 文介 绍 了算法的设计 ， 描述 了算 法的具体 实现 ，论证 了其在抗碰撞 问题上 的可证 明安 全性 ，详细分析 了该算 法既具有 一般 增量 hash 算 法的性能优 势又具有之前增量 hash 设计领域 未曾提 出的新特性 ，最后给 出 了iHash 与已...

　　Microcomputer Applications Vo1． 25， No． 4， 2009 研究与设计 微型 电脑应用 2009 年第 25 卷第 4 期 文章编号 ：1007 757X (2009)4-0017 03 一种针对磁盘完整性校验的增量 hash 算法 宋宁楠谷大武侯方勇 摘的规模成 比例。 论 文采用增量校 验的思想 ， 设 计 了一种针对磁盘 完整性校 验的 hash 函数称 为 iHash。 该 文介 绍 了算法的设计 ， 描述 了算 法的具体 实现 ，论证 了其在抗碰撞 问题上 的可证 明安 全性 ，详细分析 了该算 法既具有 一般 增量 hash 算 法的性能优 势又具有之前增量 hash 设计领域 未曾提 出的新特性 ，最后给 出 了iHash 与已有 的 hash 函数在性能上 的对 比实验 结果。 关键词：增量hash ；可证明安全；碰撞问题；平衡问题；链表式计算结构 中图法分类号：TP311 文献标识码：A 要：增量hash 函数具有传统迭代 hash 函数所不具备的增量性和并行性，可以使数据校验值的更新时问与该数据被修改 0引言 hash 函数以构造数据的指纹的方式来保障数据的完整 性，一旦数据改变，指纹就不再与之相符。即使数据被存储 在不安全的地方， 通过重新计算数据的指纹并验证指纹是否 改变就能够检测数据的完整性⋯ 。 传统的 hash 函数如 SHA 1，M D5 均是对数据的连续迭 代来生成校验值，而增量 hash 函数具有不同的计算方式。 增量密码技术最早由 Bellare、Goldreich 和 Goldwasser 于 1994 年提出[ 】 I3 1，其主要思想是经过适当设计的密码变换 作用于文档 M 时，改动所带来的计算量与所改动的文档内 容的量成正比。换而言之， 增量技术使得变换的计算量与所 产生的改动相关。对于增量校验技术而言， 对一个文档进行 修改，文档新的校验值不需要重新进行计算，而只需对所改 动的部分进行计算即可，因此有效地高了运行效率。 iIas h 算法采用了增量 hash 的设计思想， 应用主要针对 磁盘数据。 磁盘数据的完整性保护是磁盘数据保护的重要内 容，也是难点之⋯ 。完整性保护的核心内容是防篡改，具体 是指用适当的校验机制来防止攻击者恶意的修改磁盘数据， 特别是攻击者用先前的磁盘数据来替换当前的磁盘数据以 躲避验证机制而实施的重放攻击。为应对重放攻击，我们假 设被保护数据是不安全的， 但是数据的校验值应该存放在安 全的区域使攻击者无法篡改， 这样攻击者即便用先前数据替 换当前数据， 校验值的不同也可使攻击被用户察觉。以下是 iHash 算法的一种应用种场景。 ， l_l_ ： 服务 器 向 用 户 传 递 数 据 的明 空 信 道 1 ： 二 j： 服务 器更新校验值的加密信道 ● _ _： 攻击有对 服务器和明文信道的 攻击 图 1 iHash 算法在 种分布式网络中的应用场景 如图 l 所示，大量数据存储在远程服务器上，服务器用 iHash 算法计算磁盘数据的校验值，通过加密信道交由用户 保存。当服务器上某块数据被修改时，服务器更新校验值， 并重新传给用户。出于性能的考虑， 用户通过明文信道访 问 服务器数据，获得数据后必要时重新计算其校验值，与自己 所保存的校验值作对比便可侦测出数据是否被非法篡改。 这 里攻击者可以直接篡改服务器上的数据也可以对明文信道 作中间人攻击，但是无法篡改用户所保存的校验值。 iHash 算法对磁盘数据的校验粒度是文件系统级别的， 因为作为数据仓库或者远程服务器的磁盘一般容量很大， 如 果每个数据块或文件生成单独的校验值给用户带来的存储 开销会非常高， 也不便于用户管理。如果用传统的迭代 hash 函数计算整个磁盘的校验值，在磁盘数据更新时， 校验值需 要重新计算， 计算时间是巨大的开销。 增量校验的思想可以 有效弥补这一 问题 。 1 iHash 的设计与实现 1 1 iHash 的基本思想 iHash 算法将整个磁盘分成若干连续的数据块，比如按 每个 block的大 小来划分 。整个磁 盘被抽象为消息序 列 = ， 2， ⋯ ， X 。设 Y = ( i + l )， 其中h 是一种伪 随机函数【 4 】，可采用标准 hash 算法，如 MD5 或 SHA ． 1， i 是初始化时统一分配给每个数据块的二进制标识， 最后 个数据块的连接标识需要填充，记为 pad。这些标识的长 度是 log bit。符号“ ”表示两个二进制字符串的连接。h 可看作是将一个二进制字符串向一个群 G 的映射，假定 G t 的运算符为 0 ，则整个磁盘的校验值计算为 iHash(X ) = Y1 0 Y2 0 ⋯ 0 Y 当某块数据 被修改为 按如下方式更新 iHash(X ) = iHash(X ) 0 ( i + 1 )一 0 厅 ( i + 1 ， ) 其中 ( i + 1 oX， ) 是 ( i+ 1eX )在群 G 上的逆元。 这样单个数据块的更新不会像传统的迭代 Hash 函数一样引 起整个磁盘校验值的重新计算， 更新的时间耗费只跟更新的 数据块个数成比例。 M ihir Bellare 曾提出，对于大量数据分组后先随机化再 连接的校验值计算方式应当引入每个数据块的存储位置标 一 时整个磁盘的校验值可以 基金资助：国家高技术研究发展计划 (863) (2006AA01Z446) 作者简介：宋宁楠，上海交通大学计算机系，硕士研究生，上海谷大武，上海交通大学计算机系，教授，博士生导师，上海侯方勇，～ }： 海交通大学计算机系，副教授，上海200240 200240 200240 17