密码Hash函数相关问题研究
文献类型：学位论文
| 作者 | 薛宇 |
| 学位类别 | 硕士 |
| 答辩日期 | 2010 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 北京 |
| 导师 | 吴文玲 |
| 关键词 | Hash函数 差分分析 碰撞攻击 SHA-3 扩散层 |
| 学位专业 | 信息安全 |
| 中文摘要 | 密码Hash函数是信息安全密码学的一个重要研究内容，是一类广泛应用的密码算法，用于把任意长度的字符串压缩成特定长度的字符串，同时需要在各种应用环境下满足一定的安全要求如抗碰撞，抗原象等。Hash函数广泛应用于数字签名、可证明安全、密码算法的构造以及重要的安全协议中。对Hash函数进行研究、分析Hash函数的安全性、构造安全高效的Hash算法有着重要意义。 本文研究了Hash函数的安全性质、设计结构以及常用分析方法，研究了Hash函数扩散层部件的设计，并且对MAME压缩函数算法进行了分析，取得了如下研究结果： (1) 研究了密码Hash函数的安全性质、设计结构、设计原理和常用分析方法，归纳总结了51个SHA-3候选算法的设计特点、设计原理和实现效率，研究了最新的分析进展，总结了新的攻击方法如REBOUND攻击等。NIST仿照AES的征集过程的SHA-3竞赛，目标是选出新的Hash函数标准SHA-3。进入第一轮的候选算法有51个，经过筛选选出其中的14个作为当前第二轮的候选算法。这些新Hash算法是由世界各国密码学家精心设计，是Hash函数领域最新设计思想的集体展示，当中涌现出很多新的设计结构和设计方法，同时激励密码学家发展新的分析方法。 (2) 设计并实现了了有限域上的扩散层构造算法以及扩散层分支数测试的算法，并针对多元域上的扩散层矩阵，本文使用编码理论，利用GRS码和柯西矩阵等设计了多元域扩散层矩阵的构造算法；使用有限域上的高斯消元法和线性码的性质设计了多元域扩散层矩阵的分支数的检测；设计了高效的二元域扩散层矩阵分支数测试算法。 (3) 针对MAME压缩函数算法进行差分分析，MAME算法是SHA-3候选算法Lesamnta的前身，于CHES 2007上提出的面向硬件有效实现的Hash算法。本文利用差分攻击对MAME算法进行分析，首先针对MAME的结构性质利用对通用Feistel结构的攻击方法构造了22轮差分攻击，碰撞攻击的复杂度为2^97，（第二）原象攻击的复杂度为2^197；对23轮的差分攻击需要的预计算是2^64张表，每张表的大小为2^64；对24轮的差分攻击需要的预计算是2^128张表，每张表的大小为2^64。针对24轮差分攻击很大的内存复杂度，我们利用了算法的细节特性，改进了差分攻击，新的差分不需要预计算的辅助内存，（第二）原象的复杂度为2^224。 |
| 英文摘要 | Cryptographic hash function is an important research area of information security and cryptography. It is a class of widely-used cryptographic algorithms which can map arbitrary length string into a fixed length string, meanwhile need satisfy specific security requirements in different kinds of application environments such as collision-resistance, (second) preimage-resistance. Hash function is widely-used in many areas such as digital signature, provable security, construction of cryptographic algorithms and security protocol etc. It is very important that researching the cryptographic hash function, analyzing the security of hash function and constructing efficient secure hash algorithm. In this paper, we mainly research the security properties, design structure, design principle, and common cryptanalysis methods of cryptographic hash function, research design of hash function’s diffusion layer component and analyse the MAME compression algorithm. The main research result that we get include as follows: (1) Research the security properties, design structure and common cryptanalysis methods of cryptographic hash function. Survey and Summarize the design feature, design principle and implementation efficiency of 51 SHA-3 candidates. Summarize the new attacking methods such as REBOUND attack. NIST declares the SHA-3 competition following the success of AES. The goal is to select the new next generation Hash algorithm standard SHA-3 in place of SHA-1 and SHA-2. In the first round there are 51 candidate algorithms. After the first round selection, 14 of them were selected as the second round candidates. These new hash algorithms are designed elaborately by cryptographer all over the world and are collective demonstration of the newest design thinking in the research area of cryptographic hash function. (2) Design and implement the construction algorithms of diffusion layer over finite field and the detection algorithms of diffusion layer’s branch number which is an important security and efficiency indicator of diffusion layer. As for the diffusion matrix over finite field except GF(2), we design construction algorithm using the coding theory such as GRS codes and Cauchy matrix etc and design detection algorithms of diffusion matrix’s branch number using the Gaussian elimination over finite field and the properties of linear codes. As for diffusion matrix over binary field GF(2), we design efficient detection algorithm of the branch number. (3) Differential cryptanalysis on MAME compression function. MAME algorithm is predecessor of SHA-3 candidate---Lesamnta and is a hardware-oriented efficient hash algorithm which was proposed in CHES 2007. In this paper, we give the 22, 23, 24 rounds attacks using the cryptanalysis on generalized Feistel. For 22 rounds, the complexity of collision attack and second preimage attack are respective 2^97 and 2197; For 23 rounds, collision attack and second preimage need extra space and precomputation, require about 2^64 tables and every table is about 2^64 large; For 24 rounds, the precomputation need about about 2128 tables and every table is about 2^64 large. Then we improve the 24 rounds attack using the internal structure of round function. New attack doesn’t need large precomputation and space storage. The complexity of new second preimage attack is about 2^224 and the complexity of new collision attack is about 2^112. |
| 学科主题 | 数据安全与计算机安全 |
| 语种 | 中文 |
| 公开日期 | 2010-06-06 |
| 源URL | [http://124.16.136.157/handle/311060/2307]  |
| 专题 | 软件研究所_信息安全国家重点实验室_学位论文 |
| 推荐引用方式 GB/T 7714 | 薛宇. 密码Hash函数相关问题研究[D]. 北京. 中国科学院研究生院. 2010. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。