中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 信息安全国家重点实验室  > 学位论文
学科主题: 计算机科学技术基础学科::数据安全与计算机安全
题名:
密码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.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/2307
Appears in Collections:信息安全国家重点实验室_学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
Binder1.pdf(821KB)----限制开放 联系获取全文

Recommended Citation:
薛宇. 密码Hash函数相关问题研究[D]. 北京. 中国科学院研究生院. 2010-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[薛宇]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[薛宇]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace