Hash函数分析与设计
文献类型：学位论文
| 作者 | 林品 |
| 学位类别 | 博士 |
| 答辩日期 | 2008-05-29 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 中国科学院软件研究所 |
| 导师 | 武传坤 ; 吴文玲 |
| 关键词 | hash函数 分组密码 前像攻击 第二前像攻击 碰撞攻击 |
| 其他题名 | Analysis and Design of Hash Functions |
| 学位专业 | 计算机软件与理论 |
| 中文摘要 | Hash函数的概念最初来源于计算机科学，用于把任意长度的字符串压缩成特定长度的字符串，同时保证没有碰撞产生。Hash函数是密码学里非常重要的工具，广泛应用于数字签名、安全性证明、构造密码体制和一些网络安全协议。在数字签名体制里，hash函数用于生成待签名消息的摘要，缩短了签名的长度并增强了签名体制的安全性；在各种密码体制的安全性证明里，hash函数用于模拟随机预言机（random oracle）；在构造密码体制方面，hash函数用于构造MAC、分组密码、流密码等密码体制；除了这些应用，hash函数在一些网络安全协议里也起着重要的作用。因此，分析已有hash函数的安全性、构造安全实用的hash函数有着非常重要的意义。 本文的研究方向着重于hash函数的安全性分析、基于分组密码的hash函数的构造和hash函数构造方法的安全性分析。首先系统分析了hash函数七种通用攻击之间的关系，分析表明这七种通用攻击并不是孤立的，不同的攻击之间存在一定的依赖关系。其次分析了All-or-Nothing方案在前像攻击和第二前像攻击下的复杂度，我们发现原有的对All-or-Nothing方案的复杂度分析是不正确的，随后给出了对该体制在前像攻击和第二前像攻击下正确的复杂度分析。 本文还对Liskov提出的Zipper体制的安全性进行了分析。Zipper是一种和随机预言机在计算上不可区分的hash函数，即在一个密码系统中，可以使用Zipper代替随机预言机而不降低该系统的安全性。我们发现Zipper作为一个hash函数在前像攻击和第二前像攻击下的复杂度不是理想的，没有达到安全的hash函数的要求，而且MD-strengthening填充规则也不能增强Zipper的安全性。我们随后给出了一些高效的PGV压缩函数用于构造高效的抗碰撞的Zipper体制，并通过实验把高效PGV压缩函数实现Zipper的速度和安全的PGV压缩函数实现的Zipper进行了对比，实验发现高效压缩函数的速度比安全的压缩函数要快得多。 在hash函数的构造方面，绝大多数实用的hash函数都是基于Merkle-Damgård方法（简称MD方法）构造的，使用这一方法构造的hash函数统称为MD hash函数。传统的MD hash函数一般假设所使用的压缩函数是随机预言机来保证其安全性。这一假设很强，因为现实中不存在随机预言机。本文提出了一个新的构造安全的hash函数的模型，这个模型使用不安全的基于分组密码的PGV压缩函数来构造安全的hash函数。这些不安全的PGV压缩函数只用了一个密钥不需要每次进行密钥编排，大大提高了hash函数的效率。新的hash函数在多CPU的环境下可以并行运算，可以进一步提高运算速度。我们在黑盒子模型下证明了新的hash函数的安全性。随后我们对一类不安全的PGV压缩函数进行改进，使其可以用MD方法构造抵抗碰撞攻击的hash函数，而在此之前这类压缩函数不能用来在MD方法下构造抗碰撞的hash函数。 Joux证明了对MD hash函数的多碰撞攻击的复杂度和普通的碰撞攻击的复杂度相同，这一分析结果表明所有的单一MD hash函数都不能抵抗多碰撞攻击。Hoch等人进一步证明了任意多个MD hash函数的嵌套和连接也不能抵抗多碰撞攻击，但是对于某些构造方法，比如3C，Hoch等人的攻击并不适用。本文分析了GOST和3C等非MD构造方法在多碰撞攻击下的安全性，发现同普通的MD hash函数一样，GOST和3C以及它们的嵌套和连接也不能抵抗多碰撞攻击。同时，本文还找到了一个新的树形方案的缺陷并对这个树形方案进行了改进。 最后，我们对本文的工作进行了总结，并对今后的一些研究方向进行了展望。 |
| 公开日期 | 2011-03-17 |
| 源URL | [http://124.16.136.157/handle/311060/6282]  |
| 专题 | 软件研究所_信息安全国家重点实验室_学位论文 |
| 推荐引用方式 GB/T 7714 | 林品. Hash函数分析与设计[D]. 中国科学院软件研究所. 中国科学院研究生院. 2008. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。