作者:
杜承航
关键词:
对称密码；分组密码；密码分析；差分分析；中间相遇攻击
摘要:
21世纪是信息化时代,人们天天遨游在信息的海洋里。越来越多的人通过计算机网络处理大量信息,如电子邮件、网上交易等。信息成为了人类社会发展的重要资源,成为了当今世界进步和发展的动力和核心。信息交互和信息传输过程中的信息安全问题变得越来越重要。信息安全直接关系到国家安全、电子商务的安全以及广大民众的个人隐私权的保护等问题。信息安全的重要性带动了对密码学的研究。密码学作为一门保证数据信息安全的科学,得到越来越广泛的研究和学习。 密码体制按照密钥共享的方式可以分为对称密码体制和公钥密码体制。对称密码主要包括分组密码、流密码和消息认证码(MAC),具有易于软硬件实现、运行速度快、存储量小等优点。 分组密码是一种有效的带密钥的置换,将定长的明文转换成等长的密文。分组密码的加密密钥和解密密钥相同,或者都能由同一个主密钥得出,而且加密和解密过程有典型的对称特性。分组密码在计算机通信和信息系统安全领域有着广泛的应用。分组密码的安全性分析是密码学研究领域的热点问题。本文重点研究分组密码的安全性。 分组密码算法的设计结构主要有两种：一种是Feistel网络结构。该结构每次只有一半的消息分组进入F函数,因此实现时具有占用硬件资源少的特点,适合在计算能力受限的条件下使用。1977年被确定为国际通用的分组加密标准的早期分组密码加密标准DES[50]就是这种结构的分组算法中的典型代表。DES是2000年前应用最为广泛的分组密码算法。DES的分组大小为64比特,密钥长度为56比特。另一种是代替-置换网络(SPN)结构。现行的高级加密标准AES[15]就是这种结构的代表。AES具有128比特的消息分组长度,密钥长度有128/192/256比特三种。 其它很多分组密码算法的设计也受到了DES和AES设计原理的影响,例如韩国分组密码加密标准ARIA算法[40,52,53]就具有与AES十分相似的结构。该算法由几名韩国密码学者在2003年提出[52],并于2004年改进到版本1.0[53]。它基于SPN网络结构,最大分支数为8,支持128比特消息分组及128/192/256比特的密钥长度,对应加密轮数分别为12/14/16轮。轮函数是SPN结构,由轮密钥异或、S盒变换和字节扩散变换组成。 2003年,ARIA首次在韩国的信息安全年会中公开[52]。此时的版本为0.8,算法具有128比特消息分组,有128/192/256比特三种密钥长度,分别对应10/12/14轮迭代。此版本中使用了两个不同的S盒。其中一个S盒是AES的S盒。后来,ARIA在版本0.9[40]中变为使用4个不同的S盒,迭代轮数没有发生变化。最后,在现行版本1.0[53]中,又将迭代轮数增加2轮,变为12/14/16轮,而且对密钥生成算法进行了适当的调整。2004年,韩国国家技术标准局(KATS)将这一版本在网页http://www.nsri.re.kr/ARIA/上公布,并在同年12月正式确定1.0版本的ARIA为韩国分组密码算法加密标准(KS X 1213)。 由于ARIA与AES在结构上有很高的相似性,所以很多AES的分析方法都对ARIA有效。反之,对ARIA有效的分析方法也很有可能用来分析和攻击AES。对ARIA安全性的分析也变得非常重要。 算法的设计者Daesung Kwon等人首先给出了ARIA的分析[40]。其中包括差分和线性分析,截断差分分析,不可能差分分析,积分攻击,高阶差分分析,插值攻击等。后来于2004年,Alex Biryukov等人对版本0.8进行了安全性评估[11]。他们主要进行了截断差分分析和专用线性分析。2007年吴文玲等人提出了对版本0.9的6轮不可能差分分析[61]。2008年李申华对吴文玲的6轮不可能差分分析进行了改进[44]。2009年李艳俊提出了最多攻击到7轮ARIA-256的积分攻击[45]。唐学海[60]等人在2010年提出最多攻击到8轮ARIA-256的中间相遇攻击。 本文中,我们对现行的1.0版本的ARIA算法进行了安全性分析,主要使用了不可能差分分析及中间相遇攻击的分析方法,并有如下结果： (1)7轮ARIA不可能差分分析 2007年,吴文玲等人首次发现了4轮不可能差分特征,该特征如下：(c,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)(?)(0,j,0,0,0,0,0,0,j,j,j,0,0,0,j,0),其中c和j非零。基于此,吴文玲等人提出了第一个约减至6轮的ARIA不可能差分分析。 李申华又于2008年对ARIA的不可能差分分析进行了改进,发现了新的不可能差分特征。利用这类特征对六轮ARIA进行攻击时,相对于吴文玲的不可能差分分析,可以分别减少猜测第1轮和第7轮轮密钥的1字节,从而使需猜测的密钥数由12字节减少到10字节,有效降低了不可能差分攻击的时间复杂度。 这个四轮不可能差分特征可以描述为：(0,c1,0,0,0,0,0,0,0,0,0,0,c12,0,0,0)(?)(0,0,0,j,0,0,0,0,0,0,0,j,j,j,0,0),其中c1,c12和j非零。 李的攻击需要2 120个选择明文和2 96次六轮加密运算,时间复杂度比吴文玲的攻击降低了2 16。 在此基础上,我们对ARIA的不可能差分性质展开了进一步的研究。我们发现想进一步减少猜测密钥的字节数几乎是不可能的了。因此我们从其他方面入手。我们发现了扩散层的一种重要性质,然后结合我们构造的新的4轮不可能差分特征,我们给出了7轮ARIA-256的不可能差分分析。扩散层性质. 由扩散层(DL)的线性表达式,及扩散层变换的自逆特性,我们发现了第一轮中进行扩散变换前状态的各字节之间的4个关系式,利用这4个关系式,我们可以有效过滤攻击过程中无用的明文对,从而大大降低了时间复杂度,使得对ARIA的不可能差分分析能够攻击到7轮。 这4个等式如下通过使状态ΔX1(SL)的各字节满足上述4个等式,我们能在进行扩散变换前以2-48的概率过滤明文对。我们也构造出了对应此4等式的4轮不可能差分特征,形式如下： 4轮不可能差分特征. 给定一对只在第3字节有差分且其他字节无差分的明文(X3,X'3),经过4轮加密运算后,密文对差分ΔX7不可能产生如下形式：(j,0,j,0,0,0,0,0,j,0,0,j,0,0,0,0),即密文对只在(0,2,8,11)4字节处有非零差分,在其他字节无差分。这一不可能差分性质可用下式表示：(0,0,c,0,0,0,0,0,0,0,0,0,0,0,0,0)(?)(j,0,j,0,0,0,0,0,j,0,0,j,0,0,0,0)其中c和j为任意非零值。 我们在4轮不可能差分特征前边加两轮,后边加一轮,构造我们的7轮不可能差分路线,并在第一轮中通过置换层后的状态用4个等式进行过滤。 我们的攻击共需2 125选择明文和大约2 238 7轮加密。 (2)改进的7轮ARIA-256不可能差分分析 在上述7轮不可能差分分析结果基础上,我们经进一步的研究,又发现了扩散层与上述性质类似的性质,不同的是,这次我们得到7个等式,并由此降低了上述7轮攻击的数据和时间复杂度。 这7个等式为：我们也构造了适用于此7个等式的4轮不可能差分特征,并在特征前加2轮,后边加1轮,构成新的7轮不可能差分路线。差分特征为： 4轮不可能差分特征. 给定一对在第(10,15)字节有差分且其他字节无差分的明文(X3,X'3),经过4轮加密运算后,密文对差分ΔX7不可能产生如下形式：(0,j,0,j,0,0,0,0,0,j,j,0,0,0,0,0),即密文对只在(1,3,9,10)4字节处有非零差分,在其他字节无差分。这一不可能差分性质可用下式表示(0,0,0,0,0,0,0,0,0,c,0,0,0,0,0,c)(?)(0,j,0,j,0,0,0,0,0,j,j,0,0,0,0,0)其中c和j为任意非零值。这一攻击需要2[2]选择明文和大约2 219 7轮加密。 (3) ARIA中间相遇攻击 ARIA算法的中间相遇攻击最早由唐学海[60]等人提出,他们最多攻击到8轮ARIA-256。8轮攻击的数据复杂度为2 56,时间复杂度为2 25.6,预计算复杂度为2 252。而7轮ARIA-192攻击需要2 120个明文,2 1853次7轮ARIA-192加密运算,和2 187次预计算。6轮攻击的数据／时间／预计算复杂度分别为2 56,2 121.5,及2 122.5轮攻击需要25个明文,时间复杂度为2 65.4,预计算复杂度为2 122.5。 在此基础上,我们结合2010年由Orr Dunkelman, Nathan Keller, and Adi Shamir~([24])等人提出的针对AES的中间相遇攻击,提出了新的ARIA中间相遇攻击的4轮区分器,并以此为基础提出了新的最多攻击到8轮的中间相遇攻击,改进了唐学海等人的结果。 4轮区分器 如果δ-集的活性字节是第2字节,用4轮ARIA加密δ-集。则(无序)多重集[△X3,2 0 ,△X6,2 1,…,△X6,2 255]完全由以下30字节变量决定：-状态X 3 0(IN)的7字节1,4,6,10,11,12,15；-状态X 4 0(IN)的全部16字节；-轮密钥k5的7字节1,4,6,10,11,12,15。所以,多重集完全由232字节变量决定。这一多重集共有2 232个可能值。因此如果密钥的猜测值使得对应的多重集产生了上述的2232个值中的一个值,那么这个密钥的猜测值以很高的概率是正确密钥。我们在此区分器前边加1轮,后边加3轮,构造8轮ARIA的中间相遇攻击。我们的8轮攻击需要2 5
在线下载