中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 信息安全国家重点实验室  > 学位论文
Title:
典型密码分析方法的自动化研究
Author: 苏波展
Issued Date: 2012-05-06
Supervisor: 吴文玲
Major: 信息安全
Degree Grantor: 中国科学院研究生院
Place of Degree Grantor: 北京
Degree Level: 博士
Abstract: 密码分析作为密码学的一个重要分支,日益受到人们的重视。对密码算法
进行分析首先是为了发现密码系统的弱点,以完善加密过程,更有利于信息的
安全。另一方面,是为了掌握密码分析者的攻击方法,便于预防他们的攻击。
一个密码系统的安全性只有通过对该系统抵抗已知攻击能力的全面分析才能做
出定论。因此,进行密码分析是非常必要的。
分组密码分析一般包括两步:第一步是寻找密码算法有效的区分器,即找
出密码算法的某种非随机性;第二步是利用该区分器恢复密码算法的密钥。因
此,构造出有效的区分器是密码分析的重要前提。目前区分器的构造方法是手
动或者近乎穷举的搜索算法,效率不高。为了提高区分器的搜索效率,给出更
有效的区分器搜索算法是目前较为重要的研究方向。
本文对差分分析、飞去来器分析、线性分析、近似碰撞以及猜测确定等分
析方法的自动化进行了研究,给出了差分特征、飞去来器区分器、线性特征和
猜测确定路线的搜索算法,并利用这些新结果,分析了若干密码算法的安全
性。取得的主要研究成果和创新点如下:
1. 针对基于S盒的分组密码,给出了Feistel-SP和各种广义Feistel-SP等结
构最少差分(线性)活跃S盒个数的差分(线性)活跃模式的搜索算
法;利用上述差分(线性)活跃模式,给出了针对Feistel-SP 和各种广
义Feistel-SP等结构的最佳差分(线性)特征的搜索算法。针对ARX型分
组密码和杂凑函数,给出了线性化差分特征的自动搜索算法。同时,给
出了ARX型分组密码和杂凑函数的飞去来器特征的搜索算法。给出了2个
猜测确定路线的搜索算法,该搜索算法可以做到比特级,运行速度较
快。
2. SMS4是我国政府公布的第一个商用分组密码,用于无线局域网产品的
安全保护;自2006年公布之后,引起了国内外学术界和产业界的极大关
注。通过研究和分析SMS4分组密码的非平衡广义Feistel结构特点和轮函
数的扩散性质,本文给出了5轮和6轮轮函数的输入差分和输出差分之间
的关系,设计了对于SMS4的差分活跃模式的搜索算法,给出了6、7、8、
9、10和12轮SMS4算法最小活跃S盒个数和差分活跃模式。进一步利用差
分特征搜索算法给出了19轮有效差分特征;利用19轮差分特征,结合一
些分析技巧,给出了23轮SMS4分组密码的差分分析算法。这是目前为止
对SMS4分组密码最好的分析结果。
3. NIST于2007年发起了SHA-3新杂凑函数标准的公开竞选活动,其主要目
的是为了寻找一个替代SHA-2的杂凑函数标准,BLAKE和Skein在SHA-
3最后一轮五名候选者当中。它们使用了异或、模加、循环3种运算,我
们称之为基于ARX结构的杂凑函数。利用ARX型密码算法线性化差分
特征的搜索算法,给出了BLAKE-32的4轮压缩函数的近似碰撞攻击、
BLAKE-64的4轮和5轮压缩函数的近似碰撞攻击;进一步,我们给出
了Skein-256、Skein-512和Skein-1024的24轮压缩函数的近似碰撞攻击。该
攻击结果是目前针对BLAKE和Skein杂凑函数近似碰撞分析中攻击结果最
好的。
4. 源于RFID、物联网等应用的推动,近几年轻量级密码成为密码学的一个
研究热点,先后推出了一系列轻量级分组密码。TWIS是印度学者2009年
公布的一个轻量级分组密码,算法借鉴了CLEFIA的设计思想,设计者
声称TWIS的安全性与CLEFIA相当,有很好的统计特性和雪崩特性,能
抵抗分组密码的很多分析方法。我们给出了TWIS的10轮差分和线性区分
器,并且证明了对于TWIS的结构,任意多轮数都能找到概率为1的差分
特征,从而证明了TWIS是一个非常脆弱的轻量级分组密码。
English Abstract: Cryptanalysis is one of the important part of cryptology, which receive more
attention nowadays. On one hand, the goal of cryptanalysis is to find potential
weaknesses of a cryptographic system, then improve its security. On the
other hand, the goal of cryptanalysis is to better understand the cryptanalytic
approaches, then resist such attacks. Only after comprehensive cryptanalysis
against all kinds of known cryptanalytic approaches, a cryptographic system can
be concluded that it is secure. Therefore, cryptanalysis is very indispensable.
Generally, the analysis of a block cipher has two steps. First, constructing
effective distinguishers, that is to say, finding some non-pseudo-randomness of
the cipher. Second, recovering the seed key using the distinguishers. Hence,
the construction of effective distinguishers is a very important precondition of
cryptanalysis. Currently, the method of constructing distinguishers have been
often hand-made or nearly exhaustive search, which is often inefficient. Therefore,
improving the efficiency of the construction of distinguishers and designing more
efficient search algorithm is an important research direction.
In this thesis, we focus on the automation of differential cryptanalysis,
boomerang attack, linear cryptanalysis, near-collision attack, and guess-anddetermine
attack. We give algorithms to search for differential characteristics,
boomerang distinguishers, linear approximations and guess-and-determine distinguishers.
Using the above results, we analyze the security of some cryptographic
algorithms. The following are our main contributions:
1. For some block cipher structures using S-boxes and linear transformation,
including Feistel-SP and Generalized Feistel-SP structures, we give a search
algorithm to calculate the least number of differential and linear active Sboxes.
Using the above results, we further give an algorithm to search
for the best differential and linear characteristics. For ARX-based block
ciphers and hash functions, we give an algorithm to automatically search
for the linear differential characteristics; Moreover, we give an algorithm to
automatically search for the boomerang distinguishers. Finally, we give two
algorithms to automatically search for the guess-and-determine characteristics
for non-linear equation sets, the algorithms are efficient and bit-wise.
2. SMS4 is the first commercial block cipher released by Chinese government,
which is used for security protection of products in wireless local area networks.
Since its release in 2006, it has attracted great attention from worldwide
academia and industry. By researching and analyzing features of its
generalized Feistel structure and diffusion properties of its round function,
we give some relationships between input difference and output difference
of the round function of 5-round and 6-round SMS4. Then, we present
a search algorithm of differential active pattern of SMS4, and give the
least number of differential active S-boxes and differential active pattern
of 6-,7-,8-,9-,10- and 12-round SMS4. Furthermore, we present differential
characteristics for 19-round SMS4. Finally, we present an analytical algorithm
of 23-round SMS4 using 19-round differential characteristics and
some analytical techniques. Our results are the best known on SMS4 so
far.
3. The National Institute of Standards and Technology (NIST) opened a public
competition in 2007 to develop a new cryptographic hash algorithm -
SHA-3, which will replace the hash standard SHA-2. Blake and Skein are
two of the 5 finalists. The two algorithm only uses 3 kinds of operations,
i.e., XOR, modular addition and circular shift, which is usually called ARXbased
hash functions. Using the search algorithm of linearized differential
trails of ARX-based ciphers, we present a near-collision attack on 4-round
compression function of BLAKE-32, and near-collision attacks on 4- and
5-round compression function of BLAKE-64; Moreover, we present nearcollision
attacks on 24-round compression function of Skein-256, Skein-512
and Skein-1024. Our results are the best known near-collision attacks on
BLAKE and Skein.
4. Due to the application development such as RFID and Internet of things,
light-weight cryptology is a research focusc of cryptology, a series of lightweight
block ciphers have been proposed. TWIS is a light-weight block
cipher designed by Indian researchers in 2009, which uses the design ideas
of CLEFIA block cipher. The designers claimed that the security strength
of TWIS is quite near that of CLEFIA, TWIS has very good statistical
and avanlanche properties, and TWIS can resist many cryptanalytical approaches
of block ciphers. However, we can design 10-round differential
and 10-round linear distinguishers of TWIS. Furthermore, we can find some
differential characteristics with probability 1 for arbitrary rounds of TWIS
structure. Our results show that TWIS is a very weak light-weight block
cipher.
Language: 中文
Content Type: 学位论文
URI: http://ir.iscas.ac.cn/handle/311060/14552
Appears in Collections:信息安全国家重点实验室_学位论文

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

Recommended Citation:
苏波展. 典型密码分析方法的自动化研究[D]. 北京. 中国科学院研究生院. 2012-05-06.
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-2019  中国科学院软件研究所 - Feedback
Powered by CSpace