【作者】 王丹辉；

【导师】 王小云；

【作者基本信息】 山东大学 ， 信息安全， 2014， 博士

【摘要】 分组密码是目前应用最为广泛的密码体制之一,它是一类对称密码算法,使用同一密钥进行加密和解密运算。本质上,分组密码是一种带密钥的置换,它将明文数据划分为多个长度相等的分组,并转换为相同长度的密文。目前主流的分组密码算法在数学结构方面具有较高的安全性,很难被数学分析的方法破解。然而,数学分析方法主要针对明文和密文进行分析,在算法通过密码设备实现的安全性分析方面具有一定局限性。自从1996年Kocher提出了研究操作时间的计时攻击以来[1],侧信道攻击及防御逐渐成为密码学的一个重要分支。有别于传统的暴力破解,或者针对密码理论的弱点进行研究,侧信道攻击分析密码算法物理实现过程中某些中间值泄露的信息,从而获取密钥。时间、电磁波、乃至声音等信息均可以作为攻击密码系统的侧信道信息,除此之外,能量消耗分析是侧信道攻击最有效的手段之一。在实际应用中,这些攻击通常会借助密码芯片,如微处理器、FPGA (Field-Programmable Gate Array)、ASIC (Application Specific Integrated Circuit)[2]等来实现。1999年,Kocher等人提出了能量分析攻击[3,4],这种攻击能够通过密码芯片执行过程中的瞬时能量消耗来获取中间值信息,从而推导出密钥。之后Chari等人于2002年提出了模板攻击[5]。模板攻击根据密码设备泄露的信息数据以及相关操作的特征来构建模板,寻找与获取的信息最匹配的模板,从而有效缩小密钥搜索空间。2004年,Brier等人提出了相关能量分析,这种攻击建立在差分能量分析的基础上,采用相关系数模型来恢复密钥[6]。本文重点研究针对分组密码算法的能量分析攻击,以AES(Advanced Encryption Standard)算法为例,提出了比现有攻击方法更为有效的容错线性碰撞攻击和基于二阶距离的比特碰撞攻击。并使用比特碰撞攻击改进容错线性碰撞攻击,进而得到容错比特碰撞攻击。最后针对几种经典算法的S盒结构,进行了相关能量分析、模板攻击、以及比特碰撞攻击的效率研究。1.容错线性碰撞攻击相关能量分析[6]和碰撞攻击都是常见的能量分析攻击方法。Bogdanov等人将相关能量分析与碰撞攻击结合,提出了测试链的概念[7],并指出这种方法的攻击效率高于独立的相关能量分析或碰撞攻击。然而,测试链攻击只能纠正相关能量分析部分出现的错误,对碰撞攻击部分出现的错误无能为力。换句话说,一旦在测试链的一条路径中出现错误,它将导致随后连续出现错误,乃至整条路径错误,造成攻击失败。并且由于实际上碰撞攻击的效率低于相关能量分析,这使得Bogdanov等人的方法可能不切实际。我们以测试链思想为基础,提出了容错链的概念。以AES第一个密钥字节k1为例,容错链选取k1作为唯一的自由变量,即从k1出发,通过碰撞攻击构造k1与其它15个密钥字节之间的关系ki(?)ki=△1.i(2≤i≤16).(1)这15个关系式相互独立,因此如果一个关系式出错,其错误结果不会影响其它关系式。在攻击的具体实现中我们采用相关强化碰撞攻击构造容错链。在容错线性碰撞攻击中,我们不仅构造一个容错链,同时还采用相关能量分析对密钥候选值进行排序,并给定一个阈值ThCPA’筛选出每个密钥字节的候选值集合。满足容错链关系式(1)且属于密钥候选集合的密钥,可以判定为正确密钥。由于除k1外的其它密钥字节互不影响,因此可以给定一个碰撞攻击部分的阈值ThCA’使得攻击成功返回的密钥可以包含至多ThCA个错误的字节。随后通过少量搜索能够找到正确的密钥。我们通过仿真实验对容错线性碰撞攻击和测试链攻击进行了效率比对。实验结果表明,当两种攻击的成功率均在90%以上时,容错线性碰撞攻击所需能量迹数量少于测试链攻击。为了进一步缩小密钥搜索空间,我们给出一个纠错机制,能够较为精确的识别错误密钥字节的位置。随后讨论了错误发生在相关能量分析部分和碰撞攻击部分的可能性,并通过实验给出了ThCPA的取值范围。最后我们分析了ThcpA的取值对攻击成功率的影响,根据实验数据建议ThCPA=10为最有效取值。2.基于二阶距离的比特碰撞攻击2010年,Moradi等人提出了针对AES硬件实现的相关强化碰撞攻击。然而,他们的攻击方法在实际操作中存在效率问题。相关强化碰撞攻击按字节进行操作,因此每次攻击至少需要256条平均能量迹。攻击者需要在示波器上对采集的原始能量迹进行平均,然后手动存储；或者将大量原始能量迹存储到计算机中,再使用MATLAB进行平均。其中采集、存储、以及平均能量迹的过程极为繁琐且耗费时间。攻击者通常希望攻击实现尽可能快速有效,我们以此为出发点提出了较为灵活的基于二阶距离的比特碰撞攻击,它使用能量迹距离模型和逐比特比较的思想区分碰撞。以AES算法为例,选定一个全零明文P0和8个特殊明文Pα(α=1,2,..,8),每个Pα包含16个同样的字节pα,其第α比特为1,其它比特为0。Pα与密钥进行异或运算得到S盒的输入值,每个S盒的输入值即为第α比特发生变化的密钥字节,并且运算前后的汉明重量也随之变化。由于输入P0不会引发任何比特改变,因此输入Pα后,通过比较不同S盒输入值的汉明重量之差是否与输入P0相同,可以推断对应的密钥字节的第α比特是否相等。以P0和P1为例,令ΔHW0和ΔHW1分别表示选择P0或P1前两个S盒输入值汉明重量的差值,可以通过条件(2)和(3)判断k1和k2第一个比特u1和v1是否相等。●当且仅当u1=v1时,|△HW°-△HW1|=O.(2)●当且仅当u1≠v1时,|△HW°-△HW1|=2.(3)在实际攻击中,我们使用能量迹距离模型逼近汉明重量模型,因此可以成功区分出碰撞和非碰撞。本文还给出另外一个距离模型。如果用ΔHW0和ΔHW1表示汉明重量之和,即一阶距离的减法运算替换为加法运算,而二阶距离保持不变,此时同样可以实现比特碰撞攻击。其碰撞与否与上述结论(2)和(3)恰好相反。我们对比特碰撞攻击进行了实际操作和仿真实验。在实际操作中给出了差分能量迹和二阶距离的比较图示,证明比特碰撞攻击切实有效。仿真实验分别研究了能量迹数量、操作时间以及采样点数量等指标,对比特碰撞攻击与相关强化碰撞攻击进行了效率比对。由实验数据得知,比特碰撞攻击优于相关强化碰撞攻击,尤其在实际操作中,前者所需时间仅为后者的8%。由于比特碰撞攻击与相关强化碰撞攻击的返回结果均为密钥字节的异或值,而前者效率更高,因此我们使用比特碰撞攻击构造容错链,完成容错线性碰撞攻击中的碰撞攻击部分。改进后的攻击称之为容错比特碰撞攻击。通过实验数据可知,容错比特碰撞攻击的攻击效率高于容错线性碰撞攻击。3.S盒位宽与能量分析攻击效率的关系研究数据加密标准DES (Data Encryption Standard)于1976年被美国联邦政府的国家标准局确定为联邦资料处理标准[9，10],其安全性依赖于破解算法的计算难度大和计算时间长。随着计算机与网络技术的发展,目前所拥有的计算能力已经对DES造成了威胁。1997年,美国国家标准和技术研究所发起征集高级加密标准AES的活动,并于2000年确定了Rijndael算法为AES。Serpent算法也是AES的候选算法之一[11]。目前分组密码的设计主要关注于非线性S盒、置换方法以及密钥扩展方案。S盒首次出现于Lucifer算法中,由于DES的深远影响而被广泛应用。S盒是许多分组密码算法中唯一的非线性部件,因此算法的安全强度很大程度上取决于S盒的安全强度。在一轮运算中,DES使用8个S盒,输入6比特输出4比特；AES使用16个S盒,输入输出均为8比特；Serpent使用32个S盒,输入输出均为4比特。由于实验中使用的AES和Serpent的分组长度为128比特,而DES为64比特,为合理比较攻击效率,我们假设一个DES的扩展结构DES-E,其数据长度为128比特,且一轮使用16个DES结构的S盒。我们在相同的实验环境下研究三种能量分析攻击方法针对一轮加密算法中单个S盒的攻击效率。假设一轮攻击的成功率高于50%,可以推出：DES单个S盒的成功率应达到0.9170,DES-E和AES单个S盒的成功率应达到0.9576,Serpent单个S盒的成功率应达到0.9786。在相关能量分析中,S盒打乱了数据的线性规律,其输出值能更好的体现数据相关性,因此选取S盒的输出值作为攻击对象。由于计算相关系数需要多条能量迹,因此每条能量迹上选取1个采样点即可实现攻击。由实验数据得知,达到期望成功率针对Serpent所需能量迹数量最多,其抗攻击性最强。AES抗攻击性最弱,低位宽S盒的安全强度高于高位宽S盒。在模板攻击中,由于构建模板需要知道精确的汉明重量,因此选取S盒的输入值作为攻击对象。为了较为精确的匹配模板,我们使用简化模板攻击方法并选取10个采样点。由实验数据得知,此时AES抗攻击性最强,DES最弱。在基于二阶距离的比特碰撞攻击中,由于攻击思想也依赖于中间值具体的汉明重量,因此选取S盒的输入值作为攻击对象。为了衡量能量迹间距离,每条能量迹选取10个采样点。由实验数据得知,此时AES抗攻击性最强,Serpent最弱,高位宽S盒的安全强度高于低位宽S盒。因此,在不同的能量分析攻击下,不同结构的S盒抗攻击性各有优劣。算法的设计可以酌情考虑在不同攻击方法下S盒的安全强度,以满足特定需求。更多还原

【Abstract】 The block cipher is one of the most widely used cryptosystems.It is a type of symmetric ciphers, which uses the same key for both encryption and decryption. Es-sentially, a block cipher is a permutation with key. The plaintext is divided into several blocks, and each block yields an output block with the same size. The current ciphers have high security in terms of their mathematical structures, which are strong against the mathematical methods. However, the mathematical methods have some limitations to analysis on the security of cryptoequipment, because they are mostly concerned with plaintexts and ciphertexts.Since timing attack which observes variations on performing time was proposed by Kocher in1996[1], the field of side-channel attacks and countermeasures has grad-ually become an important branch of cryptography. Side-channel attacks, which pay close attention to the intermediate values, are based on the leakage of information from the physical implementation of a cryptosystem, rather than the traditional meth-ods such as brute force or theoretical weaknesses. Although the information of timing, electromagnetism, or even sound can be exploited to attack a cryptosystem, power con-sumption analysis is one of the most effective means of cryptanalysis. In practice, these techniques are typically implemented on cryptographic chips, such as microprocessor, FPGA, and ASIC[2]. In1999, Kocher et al. presented differential power analysis which can recover secret keys by analyzing the information of instantaneous power consump-tion of cryptographic chips[3,4].Template attack was introduced by Chari et al. in2002. The attacker matches the recorded power traces with the power consumption character-istics which are called templates for different key hypotheses in the template attack[5]. In2004, Brier et al. proposed correlation power analysis which recovers secret keys with the correlation coefficient model[6].In this dissertation, we focus on the power analysis attack on block ciphers. First, the fault-tolerant linear collision attack and bitwise collision attack are proposed, and performed on AES for example. Second, the fault-tolerant linear collision attack is im-proved, which is named fault-tolerant bitwise collision attack. At last, for the different S-boxes of DES, DES-E, AES and Serpent, we analysis and compare the efficiencies of the correlation power analysis, template attack and bitwise collision attack respectively.1. Fault-tolerant linear collision attackThe correlation power analysis[6] and collision attack are the common methods of power analysis attack. Bogdanov et al. proposed the concept of test of chain[7], which combines correlation power analysis with collision attack. They specified that their attack is more efficient than either stand-alone correlation power analysis or collision attacks. Although the test of chain discussed the high efficiency of their combined attack, they did not give a practical attack scheme. On the other hand, their method can only correct the errors in correlation power analysis, but can not in the part of collision attack. In other words, once a step error occurs in a path of the chain, it will lead to consecutive errors. And the errors may take place in the entire path, which will result a failed attack. Indeed, the efficiency of typical collision attack is much lower than correlation power analysis, which may lead to the unavailability of Bogdanov’s method.On the basis of test of chain, a concept of fault-tolerant chain is presented. The first key byte k1of AES is taken for example. In the fault-tolerant chain, k1is the only free variable. In other words, the independent relations between k1and the other15key bytes are constructed by collision attack. k1(?)ki=△1,i(2≤i≤16).(4) If one of these expressions is wrong, it does not affect the results of other expressions. In practice, the correlation-enhanced collision attack [F15] is employed for collision detection.In the process of fault-tolerant linear collision attack, not only is the fault-tolerant chain constructed, but also the correlation power analysis is used to sort and filter the key candidates. A threshold ThCPA is given to obtain the sets of key-byte candidates. If a key in the candidate set satisfies the relation expressions (1), it is mostly the correct key. Since the key bytes are independent of each other, a threshold ThCA can be given to tolerant the errors in collision attack. ThCA is the maximum of wrong key bytes. Then the correct key can be searched.The efficiencies of fault-tolerant linear collision attack and test of chain attack are compared in simulations. When the success rates of the two attacks are both above90%, the experimental results show that the trace number of our attack is less than that of Bogdanov’s attack.In order to reduce the search space further, the fault-identification mechanism is presented, which can identify the position of wrong key bytes with high probability. We discuss the probabilities of cases in which part errors occur, i.e. whether errors occur in correlation power analysis or in collision attack. At last, we analysis the relation between the success rate and ThCPA, and suggest ThCPA=10, which corresponds to the maximum success rate of our attack.2. Bitwise collision attack based on second-distanceIn2010, Moradi et al. proposed correlation-enhanced collision attack[8] on hard-ware implementation of AES. However, their inefficiency is a serious problem. In practice, due to its bytewise operations, numbers of power traces are needed to acquire256average traces in correlation-enhanced collision attack. The traces are needed to be averaged on a oscilloscope and stored manually. Or all of them are automatically stored, and then handled in MATLAB. But the process of trace acquisition, storage and averaging is complex and time-consuming.An attack is expected to be fast and efficient as far as possible. So we propose a more flexible attack, which can distinguish the collisions by bit instead of byte based on the trace distance model. Take the bitwise collision attack performed on AES for example. An all-zero plaintext P0and8special plaintexts Pα{α=1,2,...,8) are chosen. Each Pα contains16equal bytes pa. The a-th bit of pα is1, the other bits are0. After pα XORing with key, the inputs of S-box are the changed key bytes whose the ath bits are changed, and their hamming weights are changed too. Since P0will cause no changes, after a comparison between the differences of hamming weights of different inputs with P" and P0, wether the αth bits of different key bytes are equal can be deduced. P0and P1are chosen for example to introduce the basic idea.△HW0and AHW1denote the difference of the hamming weights of inputs of the first two S-boxes with P0or P1. The following conditions (2) and (3) are used to determine whether the first bits of k1and k2are equal:· If and only if u1-v1,|△HW0-△HWX1|=0.(5)· If and only if u1(?)v1,|△HW0-△HW1|=2.(6) In practice, the trace distance model is used to approximate the hamming weight model. So the collision and non-collision can be distinguished.Another distance model is found to implement bitwise collision attack. If the operation of first-order distance is addition instead of substruction, and the second-order distance is unchanged, the conclusions are contrary to those above.Bitwise collision attack has been implemented on an AT89S52singlechip for prac-tical experiment. The differences of average traces and the second-order distances on8bit positions are shown. We also made some simulations on trace number, opera-tion time and point number to evaluate the efficiency of our attack. The experimental results show that the efficiency of our attack is higher than correlation-enhanced col-lision attack. And in practice, the operation time of our attack is only8%of that of correlation-enhanced collision attack. The results of bitwise collision attack and correlation-enhanced collision attack are both the XORed value of key bytes. And the bitwise collision attack is more ef-ficient than correlation-enhanced collision attack. So the fault-tolerant chain can be constructed by bitwise collision. The improved fault-tolerant linear collision attack is named fault-tolerant bitwise collision attack. The experimental data show that the fault-tolerant bitwise collision attack is better than the fault-tolerant linear collision attack.3. The efficiencies of power analysis attack based on S-boxes of block ciphersIn1976, the National Security Agency selected a slightly modified version of DES, which was published as an official Federal Information Processing Standard (FIPS) for the United States[9,10]. The security of DES depends on the difficulty in computational complexity and time consumption. With the development of computer science and network technology, the current ability of calculation has been a threat to DES. In1997, the U.S. National Institute of Standards and Technology (NIST)initiated the solicitation of AES, and the Rijndael cipher was selected in2000. Serpent is also one of the AES candidates[11]. Currently the design of block ciphers focuses on S-box, permutation and key schedule. S-box firstly appeared in Lucifer cipher, and be wide-ly used with DES. S-box is the only nonlinear components of block ciphers, thus the security strength of ciphers are mostly determined by their S-boxes.In one round, DES uses8S-boxes of which each has6-bit input and4-bit output. AES uses16S-boxes of which each has8-bit input and8-bit output. Serpent uses32S-boxes of which each has4-bit input and4-bit output. The block of DES is64bits, and those of AES and Serpent are both128bits. In order to compare the efficiencies in reason, an expansion of DES named DES-E is assumed, which used128-bit block and16S-boxes in one round.Under the same experimental environment, we research on the efficiency of attack on a single S-box in one round. Suppose that the success rate of one round is at least0.5, it is easy to deduce that the success rate on a single DES S-box is0.917, and those of DES-E and AES are both0.9576, and that of Serpent is0.9786. In the correlation power analysis, as S-box disrupts the linear law of data, the at-tack object is the output of S-box. Several traces are needed to compute a correlation coefficient, so one sample point is enough to realize attack. According to the experi-mental results, the most number of traces are needed for Serpent, which is the strongest against correlation power analysis, and AES is the weakest. Thus, low wide S-box is stronger than high wide S-box against power analysis attack.In the template attack, in order to construct templates, we need to know the ac-curate hamming weight, so the attack object is the input of S-box.10sample points are chosen on one trace to match templates precisely. According to the experimental results, AES is the strongest, and DES is the weakest.In the bitwise collision attack, the idea depends on the hamming weights of inter-mediate value, so the attack object is the input of S-box.10sample points are chosen to measure the differences between traces. The experimental results show that AES is the strongest and Serpent is the weakest. In this case, high wide S-box is stronger than low wide S-box.The different S-boxes have advantages and disadvantages against different power analysis attacks. To meet the specific needs, the design of ciphers may follow with interest the security strength of S-boxes under a variety of circumstances.更多还原