一种可抵抗功耗分析的改进型PRESENT加密算法设计∗

刘 鹏

1 引言

PRESENT算法是2007年由A.Bogdanov，L.R.Knuden和G.Lender等学者提出来的一个超级轻量级算法，它的设计结合了DES与AES的部分特点，采用4进4出的S盒，进行异或运算与移位运算，在硬件实现时具有较好的适应性［1～3］，不会对硬件设备的体积造成影响而且比软件实现的速度更快，更加适用于运算资源受限的系统。

1.1 PRESENT加解密过程

该算法为分组密码算法，明文每64比特分为一组，用于加、解密的主密钥长度可以有80比特或128比特两种选择。如图1所示，经过31轮的迭代变换，输入64比特的明文块得到64比特的密文块。在每一轮中，分别经过轮密钥加、S盒变换、P置换这三个操作。

每轮子密钥的长度为64比特，第i轮加密的子密钥为Ki=Ki63Ki62……Ki0，明文块的存放形式为M=m63m62……m0，每一步数据转换之后的状态为b，其中密钥加操作为

中间状态的每一位依次与64比特的密钥进行异或运算，得到新的中间状态。S盒是非线性结构，算法的安全性对其依赖性很大，其构造如表1所示。

表1 PRESENT算法S盒结构

与明文分组相适应，它是一个4进4出的结构，将每一轮运算结束后的64比特数据结果按顺序分成16个4比特的数据块，w15，w14，…，w0。

每一个数据块对应一个16进制的数字，按照S盒将数据进行非线性的转换，同样输出一个16进制的数字，同时得到一个与其对应的4比特数据块，16个数据块依次进行转换，最后得到64位的数据。

P置换是将中间状态的64位数据中的每一位按照P置换表置换到新的位置，其详细设计如表3所示。

每一步置换也可以由如下公式表达［4］：

其中bj代表中间64比特中间状态的第j位数据，(0≤j≤15)。

表3 PRESENT算法P置换规则表

1.2 PRESENT密钥扩展方案

以长为80比特的主密钥为例介绍PRESENT的密钥扩展方案。在加密芯片中初始主密钥以K=k79k78…k0的形式存在，在进行第i轮的密钥加时提取位数最高的64比特作为该轮的轮子密钥，Ki=k79k78……k17k16。每次提取出一个轮子密钥后进行下一轮子密钥的扩展生成。首先，将寄存器中的80比特密钥数据循环左移61比特，然后将最左边的4比特按照S盒的变换方式进行转换，最后将k19k18k17k16k15这5比特数据与轮计数器x进行异或操作，取代原来的5位数据，其公式表达如下［1］：

当密钥长度为128比特时，其扩展方法与之类似，只是取左边最高的8比特，分成两组分别进行两次S盒变换，取k66k65k64k63k62这5位与轮计数器的值x进行异或。

2 PRESENT算法功耗分析方法

密码分析与设计是现代密码学中的相辅相成的两个方向，共同促进了密码技术的提高［5］。在进行密码算法的设计时必须要考虑算法是否可以抵挡这些手段的攻击。

其中，能量分析也叫功耗分析，是侧信道攻击中的一种，1999年由Kocher等提出的，经过大量的实践证明该分析方法适用于绝大部分由硬件实现的密码算法的分析。进行差分功耗分析一般有五个特定的步骤：

1）在密码算法中挑选一个合适的中间值；

2）对中间值函数的执行过程进行多次测量并完整记录能量的消耗值；

3）利用每一个可能的密钥（或密钥的一部分）计算出相应的中间值；

4）将中间值利用仿真技术映射为能量消耗值；

5）将3）中计算出的能量迹与4）中的能量迹进行对比，然后分析出正确的密钥［6～8］。

自从2007年PRESENT算法被提出以后，相关学者利用各种不同的方法对该算法进行了大量的分析研究，并取得了一定的成果。在文献［9］中研究者利用线性分析方法实现了25轮PRESENT的破解，并计算出如果利用相同的方法破解28轮的PRESENT则需要284组明文-密文对；文献［10］中中国学者利用差分分析的方法在已知264个密文的情况下最多可以实现16轮PRESENT的破解；文献［11］中利用代数分析的方法将密钥长度为80比特的6轮PRESENT算法进行选择明文破解也需要203个小时。大量学者利用复杂的方法，在苛刻的条件下对减轮PRESENT算法进行攻击也需要相当长的时间，而目前还没有在合理时间内攻破31轮PRESENT的技术。而文献［12］中作者利用功耗分析计算汉明重量的方法仅用0.63s就实现了对3轮PRESENT的分析，而文献［11］中采用传统分析方法在同等条件下对其进行分析耗时达3593.6s。

3 Random-PRESENT设计

目前，PRESENT算法对传统的密码分析技术具有一定的免疫力，而正在不断发展的功耗分析对其造成了巨大的威胁。而且，为了提高算法处理数据的速度，PRESENT算法大多采用硬件的形式来实现，这就为功耗攻击创造了便利条件。

在原始算法中每轮加密开始阶段是轮子密钥与64比特中间状态异或，然后分成16个4比特的数据块经S盒进行转换，最后S盒输出的16×4比特数据经P置换打乱顺序。由此，可以将4比特的数据块看作最小的处理单元，每一轮加密开始实际上是对16个数据单元依次进行异或、S盒替换、P盒转换的操作，其原理如图2所示。

为了提高算法对功耗攻击的防护能力，现对PRESENT实现过程中的细节进行改进，设计出了一种改进型算法—Random-PRESENT，算法第一轮的加密过程如图3所示，重复进行31轮迭代完成数据的加密处理。

改进的主要思想是在原始PRESENT硬件中加入随机数发生器，对要进行加密的明文以及与其相对应的密钥进行随机化的分组，再对分组后数据依次进行加密操作，使攻击者测量的各个阶段的功耗曲线不具有统计特性。

在Random-PRESENT算法中用随机数控制数据分组，将这16个数据单元打乱顺序，随机分配成x个“加密操作块”，而且每个加密块中含有若干个“4比特数据组”，数量由随机数决定。在进行下一步的加密操作时，同样按照随机化处理过的顺序进行，随机对数据组进行运算。

虽然在硬件中对数据的处理顺序发生了变化但是并不影响输出结果的准确性，同一密钥对同一明文的加密结果是相同的。但是攻击者在进行差分功耗分析时，在同一密钥下对不同的明文进行加密，这一过程中对能量消耗进行分析，所采集的功耗曲线是混乱的，并不具备较强统计特性，因为利用随机数控制执行顺序，攻击者无法确定测量的功耗曲线究竟是哪个操作的能量迹。这一方法可以适用于多种由硬件实现的分组密码算法当中，可以有效地抵抗简单功耗分析与差分功耗分析。

解密时，按照同样的方式进行数据的处理，每4比特的密文数据当作一个小的数据分组，利用随机数再对这16个数据组进行分组，然后依次完成解密操作。解密时生成的随机数不会影响最终输出的结果。

4 Random-PRESENT抵抗功耗攻击原理与效果分析

由3节可知由于差分功耗分析具有不要求攻击者了解被攻击设备的详细知识、可以多次测量功耗轨迹消除噪声等特点，成为了目前比较流行的功耗攻击方法之一。而其攻击过程中的关键是要对硬件执行过程中的能量消耗曲线进行测量记录，而且要精确对齐每一个逻辑运算的功耗轨迹。

Random-PRESENT中每一轮程序的执行顺序都是随机的，攻击者利用假设的密钥对数据进行处理，在对能量消耗值进行测量的过程中，每一次测量时数据处理的次序都发生了改变，每次处理的数据量也不确定，这导致攻击者每次测量的功耗曲线顺序也是随机的，不可能将同一个逻辑运算的功耗轨迹对齐、比较。

例如，在PRESENT算法中第一轮开始时先进行轮子密钥与明文块的异或运算，在硬件中由逻辑指令控制算术逻辑单元完成，输入特定的明文，当密钥为1时执行一个特定的指令，当密钥为0时又是另外一个结果，不同的逻辑运算将导致很明显的功耗差异。在PRESENT算法中，输入同样的明文，用同一个密钥进行加密，在算法芯片中这些微控制器工作顺序以及每次运行所执行的操作是一样的，这将导致输出相同的功耗曲线，当攻击者猜想的密钥k与真实加密密钥相同或相似时将导致功耗曲线的相同或相似。在攻击过程的第二步中攻击者会记录如表4所示的数据。

表4 实际测量能量消耗记录表

该列表相当于一个D×T的矩阵，每一行可以看作是对一个数据分组进行加密的过程，在这一过程中记录了T个操作过程中的能量消耗曲线。每一列则可以看作是同一操作过程在处理不同数据分组时的能量消耗曲线。这一步骤的难点是精确地对齐每一个操作过程，即保证ti记录的是对不同数据进行“操作i”时的能量消耗曲线，这也是攻击成功的关键所在。在后续的攻击过程中，攻击者将利用所有假设密钥信息K依次对D个数据分组进行处理，并记录其进行每一个操作时的能量消耗曲线，经仿真后比较究竟哪个k处理分组数据时与之前的真实能量曲线最接近，从而恢复出密钥信息。

而在Random PRESENT算法中，对程序执行过程进行了随机化处理，当攻击者对D个数据分组进行测量时，不能保证能量迹ti都对应“操作i”，在ti对应的D个操作中会出现不同的硬件执行过程，不能对齐能量迹将导致差分功耗分析的失败。当然，当攻击者将多次测量的假设能量消耗值与经随机处理的“真实能量消耗值”进行匹配时，也几乎不能发现高度吻合的曲线峰值。利用不同的假设密钥信息对数据组进行加密或解密处理后，保存如表5中记录的能量值，每一个能量迹都是对数据进行加密过程的完整记录。当攻击者试图寻找究竟该密码设备是用哪一组密钥信息在对D个数据分组进行加密或者解密操作时会将每一个假定k值对应的假设测量值与表4中的实际能量测量值进行对比，显而易见，攻击者找到两条相似的能量迹的可能性几乎为0。由第4节中对Random-PRESENT的介绍可知，如果随机化控制每一位密钥与中间状态进行异或的顺序后，输入与真实密钥相同的假设密钥后，可能出现峰值的概率也极低，虽然可以利用先进的分析手段确定信息的汉明重量排除一些不可能的密钥值，但是也不容易做到多次测量相同的曲线求平均值来消除噪声，这依然有相当大的工作量，因此Random PRESENT可以在合理时间内抵抗差分功耗分析。

表5 假设密钥能量消耗测量值

当然，不排除攻击者发现一个与真实能量迹高度吻合的假设能量迹，但是其所使用的假设密钥信息k与真实密钥信息相同的概率也是很小的，因为这很可能是一个错误的密钥经过不同顺序的逻辑处理之后产生了这种效果，当再次利用该错误的密钥对消息进行加解密时必然不会得到系统的认可。由此可见，Random PRESENT算法对差分功耗分析有一定的抵抗能力。

5 结语

本文对现有PRESENT算法进行了改进，设计出了一个Random-PRESENT算法，通过随机化数据处理的顺序达到防止差分功耗分析的目的。并对改进的算法进行抗攻击分析，保证算法具有一定的实用价值，更加适应运算资源受限的系统。

［1］张婧.轻量级分组密码PRESENT功耗攻击的研究［D］.上海：上海交通大学，2011.

［2］冯登国，吴文玲.分组密码的设计与分析［M］.北京：清华大学出版社，2000：231-257.

［3］冯登国，裴定一.密码学导引［M］.北京：科学出版社，1999：145-158.

［4］Bogdanow A，Knudseu L R，Leander G．PRESENT：An Ultra-Lightweight B1ock cipher［C］//9th International Workshop for Cryptographic Hardware and Embedded Systems-CHES2007． Vienna：Springer-Verlag， 2007：450-466.

［5］张美玲.分组密码分析技术的研究［D］.西安：西安电子科技大学，2010.

［6］冯登国，周永彬，刘继业.能量分析攻击［M］.北京：科学出版社，2010：145-167.

［7］李翔宇，孙义和.用于密码芯片抗功耗攻击的功耗平衡加法器［J］.半导体学报，2005，26（08）：1629-1634.

［8］张咏，范明钰，王宇飞.对于DES的差分能量分析攻击及其防范对策［J］.电子技术应用，2005，27（05）：23-24.

［9］Joo Yeon Cho． Linear cryptanalysis of reduced-round PRESENT［C］//Topics in Cryptology-CT-RSA． San Francisco：Springer，2010：302-317.

［10］ Meiqin Wang． Differential cryptanalysis of reducedround PRESENT［C］//First International Conference on Cryptology in Africa． Casablanca Morocco：Springer-Verlag，2008：40-49.

［11］卜凡，金晨辉.针对低轮PRESENT的代数攻击［J］.计算机工程，2010，36（6）：128-130.

［12］吴克辉，王韬，赵新杰.基于汉明重的PRESENT密码代数旁路攻击［J］.计算机科学，2011，38（12）：53-56.