杂凑函数原象攻击的方法研究

摘要

Hash函数作为密码学的一个重要工具，在数字签名、消息认证和数据完整性方面有着广泛的应用。关于Hash函数的安全性分析是密码学中的一个重要而活跃的研究课题。近来出现的常见Hash函数算法的原象攻击方法，对于Hash函数的研究具有重要意义。与碰撞攻击相比较，原象攻击的难度较大，但原象攻击对Hash函数的影响将是致命的。
　　 本论文对近两年国际上提出的对MD-4、MD-5和SHA-0的原象攻击方法进行了深入的分析与研究，提出了改进方案，主要完成的工作如下：
　　 (1)对MD-4布尔函数的吸收特性、压缩函数的可逆性、消息扩展方式的特殊性、中间相遇攻击以及随机图理论进行了深入的研究和总结。
　　 (2)对Leurent提出的MD-4原象攻击的方法进行了改进，分别提出两种改进方案。第一种方案将攻击的空间复杂度从231降低到216，第二种方案将攻击的时间复杂度从2102降低到298。
　　 (3)深入分析了Tu Sasaki等的MD-5原象攻击方法，进一步探讨了Leurent的方法用于MD-5原象攻击的困难性。对已有的减少轮次的MD-5原象攻击方法和完整的MD-5原象攻击方法进行了分析比较，剖析了完整的MD-5原象攻击方法的思路来源。同时对一种新的可行初始结构方式进行了探讨。
　　 (4)深入分析了Cannière等的50步SHA-0原象攻击方法和K.Aoki等的52步SHA-0原象攻击方法，并尝试用消息修改技术解决状态变量的选取问题；同时对部分伪原象的计算与转化的复杂度的平衡点问题进行了探索。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景及现状

1.2论文工作

1.3论文章节安排

第二章Hash函数的基本知识概述

2.1 Hash函数的定义和性质

2.2 Hash函数的构造方式

2.3 MD结构及基本Hash函数算法介绍

2.3.1 MD结构设计原则

2.3.2 MD-4算法简介

2.3.3 MD-5算法简介

2.3.4 SHA-1算法简介

2.4 Hash函数的安全性分析

2.4.1生日攻击

2.4.2中间相遇攻击

2.4.3不动点攻击

2.4.4模差分攻击

2.4.5多碰撞攻击

2.4.6长消息第二原象攻击

2.4.7原象攻击

2.5本章小结

第三章MD-4原象攻击方法的研究

3.1对Leurent MD-4原象攻击结果的分析

3.1.1步函数的可逆性

3.1.2 MD-4非线性布尔函数的性质

3.1.3 MD-4部分伪原象算法

3.2对MD-4压缩函数的伪原象到原象转化的分析

3.2.1基于中间相遇攻击的伪原象转化分析

3.2.2基于分层的Hash树方法的伪原象转化分析

3.3 MD-4原象攻击的改进

3.3.1基于前向树和后向树的MD-4原象攻击的改进方案

3.3.2基于随机图的MD-4原象攻击的改进方案

3.4本章小结

第四章MD-5原象攻击方法的研究

4.1 Yu Sasaki MD-5原象攻击的结果

4.1.1初始结构

4.1.2 MD-5布尔函数的交叉吸收性质

4.1.3部分固定和部分匹配技术

4.1.4一致性检测技术

4.2对Yu Sasaki MD-5原象攻击方法的分析

4.2.1初始结构的构造

4.2.2部分固定与部分匹配在跳跃步的应用分析

4.2.3 MD-5原象攻击复杂度的计算

4.3对MD-5原象攻击的探讨

4.3.1 Leurent的MD-4原象攻击方法用于对MD-5原象攻击的困难性

4.3.2对局部碰撞和初始结构的分析

4.3.3对一种新的可行初始结构的分析

4.3.4几种MD-5原象攻击方法的分析比较

4.4本章小结

第五章减少轮次的SHA-0原象攻击的研究

5.1 Cannière对50步SHA-0原象攻击的结果

5.2对Cannière 50步SHA-0原象攻击方法的分析

5.2.1压缩函数的逆运算

5.2.2逐列修定

5.2.3阻止进位

5.3对K.Aoki 52步SHA-0原象攻击方法的分析

5.4对SHA-0原象攻击的探讨

5.4.1 SHA-0部分状态变量的选取

5.4.2 SHA-0部分伪原象的计算与转化的复杂度的平衡点

5.5 MD-4、MD-5和SHA-0原象攻击方法的比较

5.6本章小结

第六章总结与展望

6.1总结

6.2展望

致谢

参考文献

研究生期间研究成果