中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 信息安全国家重点实验室  > 学位论文
Title:
差分和线性分析的代数自动化方法
Author: 吴生宝
Issued Date: 2014-05-25
Supervisor: 王明生
Major: 信息安全
Degree Grantor: 中国科学院研究生院
Place of Degree Grantor: 北京
Degree Level: 博士
Keyword: 分组密码 ; 差分分析 ; 线性分析 ; 代数自动化
Abstract: 密码学技术是解决网络空间信息安全问题的一个有效手段。分组密码作为
密码学的重要组成部分,其速度快、易于标准化以及便于软硬件实现等特点使
其成为保护信息安全的核心密码算法。在近代分组密码的发展历程中,产生了
大量的攻击方法,其中最重要的两类分析方法是差分类分析和线性类分析。围
绕着这两类分析方法,分组密码设计者与分析者做了大量工作,产生了丰硕的
研究成果。近几年,分组密码的一个热点方向是设计与分析的自动化。
从代数观点上看,分组密码可以描述成一个关于明文、密文以及密钥的方
程组系统。设计者与分析者的工作都是围绕这个方程组的性质展开。因此,一
个自然的想法就是:能否从代数观点出发刻画分组密码差分与线性分析中遇到
的问题,将这些问题转换成代数问题之后,再结合已有的代数知识与工具,开
发自动化方法求解这些问题?
本论文工作围绕这个想法展开,取得了如下研究成果:
1. 不可能差分/零相关线性闭包的寻找是进行不可能差分分析/零相关线性
分析的关键步骤。通过建立差分/掩码传播系统,将不可能差分/零相关
线性闭包的判定问题转化为方程组解的存在性判定问题,并提出了一种
新的不可能差分/零相关线性闭包自动化搜索方法。相比于之前的自动化
搜索方法,本方法不但能够找到更多、更长的不可能差分/零相关线性闭
包,还能够自动化搜索比特级分组密码的不可能差分/零相关线性闭包。
利用该方法找到的新结果对于评估已有分组密码抵抗不可能差分,特别
是零相关线性分析的能力有重要意义。
2. 在SP型轮函数设计中,分组密码结构抗差分和线性分析的能力可以转化
成评估一定加密轮数下活跃S盒的个数。通过提取差分/掩码传播系统中
的信息,我们将分组密码结构的最少活跃S盒个数评估问题转换成整数
规划求解问题,得到了分组密码结构抗差分/线性分析能力的通用评估
方法。该方法只需要给定分组密码的结构和轮函数中扩散层的分支数信
息,就能够返回一定加密轮数下最少活跃S盒个数,不但能够为设计者评
估某个结构抗差分/线性分析的能力提供参考依据,还能帮助设计者快速
遴选出一些抗差分和线性分析能力强的结构。通过该方法,我们验证了
之前某些结构的活跃S盒个数评估结果,首次给出了很多知名结构的最少
活跃S盒个数评估结果,并提出了一些新的抗差分和线性分析能力强的结
构。
3. ALE是发表在FSE 2013上的一个新认证加密算法。基于整数规划思想,
我们利用ALE认证加密算法泄露的中间状态值,提出了一种新的伪造
攻击方法――泄露状态伪造攻击。结果表明,ALE抗伪造攻击的能力远
低于其设计者宣称的安全界。特别的,ALE抗伪造攻击的能力在最坏
情况下只有97比特,远没有达到设计者宣称的128比特。如果ALE加密
组建中的4轮AES没有白化密钥层,则抗伪造攻击的能力将进一步降低
至93~94比特。对小版本ALE的实验结果与我们的理论推导结果相符。
本结果是目前ALE伪造攻击的最好结果。
4. 轻量级分组算法要求扩散层的设计轻量化,PHOTON轻量级Hash函数
族的设计者们首次提出了迭代型扩散层的设计方式。我们从元素选取
与结构设计两个方面扩展了这种设计方式,并给出了轻量级迭代型扩散
层的自动化搜索方法,找到了一系列目前为止硬件实现代价最低的迭代
型最优扩散层。这些迭代型扩散层的最优分支数为5~9,在分组密码
常用的S盒规模下(如4比特,8比特等等)都能找到轻量级实例。如果
将PHOTON中使用的扩散层替换成我们的结果,则最好情形下可以节
省22.3%的电路门数。
English Abstract: An effective technique of protecting information security in cyberspace
is cryptography. As an essential part of cryptography, block ciphers have many
good features including fast running speed, easy standardization and convenient
implementation on software and hardware, and these features make them be the
most important algorithms of protecting information security. In the progress
of modern block cipher, numerous attack methods were proposed, and amongst
them, differential cryptanalysis, linear cryptanalysis and their variants are the
most important. A lot of studies related to differential and linear cryptanalysis
have been proceeded by block cipher designers and attackers. Recent years, a
research hotspot of block cipher is the automation of block cipher design and
cryptanalysis.
In the algebraic point of view, a block cipher can be expressed as an equation
system of plaintext, ciphertext and the master key. The studies of designers
and attackers are promoted by analyzing the properties of this system. Thus, an
intuitive idea is : Can we translate the problems of differential and linear cryptanalysis
in block ciphers to algebraic problems first and then propose automatic
tools to solve them by making use of known algebraic knowledge and methods ?
The research of this Ph. D. thesis closely followed this idea, and the following
results were obtained.
1. The key step of promoting impossible differential cryptanalysis / zerocorrelation
linear cryptanalysis is to find impossible differentials / zerocorrelation
linear hulls. We translated the problem of finding impossible
differentials / zero-correlation linear hulls to the problem of judging the existence
of solutions in an equation system, by building the difference / (linear)
mask propagation system of a block cipher. Then, we proposed a new
tool for automatically searching impossible differentials / zero-correlation
linear hulls. Compared with known automatic methods, our tool can not
only find more and longer impossible differentials / zero-correlation linear
hulls, but also be suitable for bit-based block ciphers. New results found
by our tool are significant for evaluating the security of known block ciphers
against impossible differential cryptanalysis and zero-correlation linear
cryptanalysis.
2. The security of a block cipher structure with SP-type round function against
differential and linear cryptanalysis lies on the number of active S-boxes
for several consecutive rounds of encryption. We translated the problem
of evaluating the minimum number of S-boxes to solve integer linear programming
problems, by extracting the information of difference / (linear)
mask propagation system. Then, we presented an unified tool for counting
the minimum number of active S-boxes. To return the minimum number
of active S-boxes for several consecutive rounds of encryption, the tool only
requires the description of a block cipher structure and the branch number
of its diffusion layer. The results can not only help designers grasp the ability
of a structure against differential and linear cryptanalysis, but also help
them select structures with good properties against these attacks. Based
on the tool, we verified previous results of several structures, obtained the
minimum number of active S-boxes for several well-known structures first
time, and proposed three new structures with good properties against differential
and linear cryptanalysis.
3. ALE is a new authenticated encryption algorithm proposed in FSE 2013.
With the help of its leaked internal state and the techniques of solving
integer linear programming problems, we proposed a new forgery attack
— leaked-state-forgery attack on ALE. Results showed that the security
margin of ALE against forgery attack is far from the the security bound
claimed by its designers. In details, the security of ALE against our forgery
attack is only 97 bits in the worst case, while the designers claimed that
ALE has 128-bit security against any forgery attack. Moreover, the security
of ALE against our forgery attack will be reduced to 93~94 bits if the
whitening key layer of 4-round AES in the encryption procedure is removed.
We implemented our attack on a small version of ALE, experimental results
confirm our theoretical analysis. It is the best forgery attack results on ALE
until now.
4. Diffusion layers used in lightweight block ciphers should be low-cost in
hardware implementation. Thus, recursive diffusion layers were proposed
by the designers of PHOTON lightweight hash family. We revisited this
design method and extended it, including the chosen of elements and the
recursive structure, and we also proposed a tool for automatically searching
lightweight recursive diffusion layers. Based on this tool, we got a list of
recursive diffusion layers with maximum branch number and lowest cost in
hardware implementation until now. The branch numbers of our diffusion
layers range from 5 to 9, and they have lightweight instances in popular
S-box sizes, such as 4-bit and 8-bit S-boxes. If the diffusion layers of PHOTON
are substituted by ours, in the best case, 22.3% gate equivalents can
be saved in hardware implementation.
Language: 中文
Content Type: 学位论文
URI: http://ir.iscas.ac.cn/handle/311060/16434
Appears in Collections:信息安全国家重点实验室_学位论文

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

Recommended Citation:
吴生宝. 差分和线性分析的代数自动化方法[D]. 北京. 中国科学院研究生院. 2014-05-25.
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