分组密码算法能量分析攻击中效率与容错问题研究

发布时间：2019-04-29 16:08

【摘要】：分组密码是目前应用最为广泛的密码体制之一,它是一类对称密码算法,使用同一密钥进行加密和解密运算。本质上,分组密码是一种带密钥的置换,它将明文数据划分为多个长度相等的分组,并转换为相同长度的密文。目前主流的分组密码算法在数学结构方面具有较高的安全性,很难被数学分析的方法破解。然而,数学分析方法主要针对明文和密文进行分析,在算法通过密码设备实现的安全性分析方面具有一定局限性。自从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]:......
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN918.1

【参考文献】