PRESENT算法整个加密过程需要经过31轮加密后，再经过与轮密钥异或的白化操作，输出最后的密文。每轮具体的加密过程如下：

1) 轮密钥异或运算层：每轮加密输出64 bit中间状态与64位的轮密钥进行异或运算。

2) S盒代换层：将异或后64 bit输出在经过16个相同的4-bit输入和4-bit输出S盒。

3) P置换层：通过查询置换表P(i)，对S盒的64 bit输出进行重新排列。

在经过31轮加密后，与第32轮轮密钥再进行一次白化异或运算，输出最后的64 bit密文。

PRESENT密码的每轮轮密钥生成算法主要经过循环移位、S盒代换、与当前加密轮数数目异或运算后得到64bit的密钥。本文主要研究密钥为80 bit ($K = {k_{79}}{k_{78}} \cdots {k_1}{k_0}$)的PRESENT算法，具体密钥生成算法如下：

式中，roundconut表示当前加密轮数，用与PRESENT加密过程相同的64 bit S盒代替运算所用的S盒。

为了能更好地提高针对PRESENT算法的差分故障攻击效率，首先针对PRESENT算法的故障传播特性进行分析。假设在PRESENT算法加密过程的第r轮随机位引入一个单字节错误，输入为(${X_0}$, ${X_1}$, ${X_2}$, ${\gamma _3}$, ${X_4}$, ${X_5}$, ${X_6}{\kern 1pt} $, ${X_7}$)，经过S盒代换层和P置换层后，它的第r+1轮输入为(${\gamma _0}$, ${X_1}$, ${\gamma _2}$, ${X_3}$, ${\gamma _4}$, ${X_5}$, ${\gamma _6}{\kern 1pt} $, ${X_7}$)，经过分析可以发现PRESENT故障传播有如下特性，如图 1所示。

图  1  PRESENT单字节差分故障传播图

进一步在不同的位置插入故障，经过分析可以发现，在加密过程中任意r轮第0字节、第1字节、第2字节、第3字节引入故障，结果故障只会传播在最后密文${C_0},{C_2},{C_4},{C_6}$位置处，其他位置对应的密文不受影响；采用相同的故障引入方式，在任意r轮的第4字节、第5字节、第6字节、第7字节引入单字节故障，故障只会在最后密文的${C_1},{C_3},{C_5},{C_7}$位置发处，其他位置对应正确的单字节密文。由此可以在该密码算法的奇数或者偶数位置随机引入故障，最后错误密文会出现在相应的位置上，通过差分公式得出错误密文与原始密文，相应这些密码字节位置上的密文不一直为零。通过这种故障传播特性可以进一步对PRESENT算法进行差分故障攻击。

针对PRESENT算法采用单字节攻击模型，在随机位置引入随机故障。为了能更好地对PRESENT算法进行分析，在攻击之前提出两点基本假设：

1) 攻击者可以在加密过程中的任意轮对指定的中间状态位置加入故障，但具体的故障值和引入故障位置未知，能够正确记录原始密文和错误密文。

2) 采用相同的明文和轮密钥加密过程中，攻击者能够多次对该密码算法加密相同的轮数和在相同位置引入故障，并记录最后错误密文结果。

任意选择一组明文和密钥，通过加密算法得到正确密文。然后在加密过程的第30轮处导入故障，结合差分故障攻击特点，获取加密过程中密文的部分特性。进一步通过加密算法的逆过程，推导出该轮64 bit轮密钥。在同样的密文和密钥的条件下，多次重复上述过程，直到恢复的轮密钥为唯一值。在第29轮使用同样步骤获取第二个轮密钥后，通过密钥生成算法，就能推导出PRESENT算法的整个原始密钥。

具体的攻击算法分为以下9个步骤：

1) 随机生成PRESENT算法的一个明文P和一个轮密钥${K_i}$，经过31轮加密后得到正确密文C；

2) 用第1)步明文P和原始密钥${K_i}$再经过第30轮加密后，在PRESENT使用的S盒中随机诱导一个单字节的故障，经过最后一轮加密后得到错误密文$C_{31}^*$，再与第31轮正确密文进行差分运算得到差分错误密文$\Delta C_{31}^*$：

3) 第31轮经过P置换层后$\Delta C_{31}^*$的值用$\Delta {Y_{31}}$表示，经过S盒代换后的值用$\Delta {X_{31}}$表示，分别为：

式中，${\rm{P}}{{\rm{L}}^{ - 1}}$表示经过P置换层的逆运算。

因此第30轮最后的输出差分密文为：

式中，${\rm{S}}{{\rm{L}}^{ - 1}}$表示经过S盒的逆运算。

经过差分运算后，非零位只会出现在4个位置上，每个位置可能值为256，所以$\Delta C_{30}^*$的所有值有1 020个，穷举出这1 020个值，并且把它们存入集合M中。由前面的分析得知，在$\Delta C_{30}^*$中所有非零字节只会出现4个位置($\Delta {X_0}$, 0, $\Delta {X_2}$, 0, $\Delta {X_4}$, 0, $\Delta {X_6}$, 0)或(0, $\Delta {X_1}$, 0, $\Delta {X_3}$, 0, $\Delta {X_5}$, 0, $\Delta {X_7}$)，所以其他零位对差分故障攻击没有意义。假设对密文的0、2、4、6位置进行攻击，选择差分输出结果的前两个非零字节密文，根据下面公式计算得出：

穷举$(\Delta {x_{0,30}},\Delta {x_{2,30}})$所有的2¹⁶可能值，依次计算出$(\Delta {c_{0,30}},\Delta {c_{2,30}})$的所有值。

4) 把第3)步得出的$(\Delta {c_{0,30}},\Delta {c_{2,30}})$和穷举集合M中第0、2位字节值进行比较，如匹配结果相同，就将对应的$(\Delta {c_{0,30}},\Delta {c_{2,30}})$存入一个新的集合${T_1}$中。

5) 对集合${T_1}$中的每一条记录进行单字节扩展。首先从${T_1}$中取出一个元素${\alpha _t}$，穷举${x_{4,30}}$所有的2⁸可能值，计算：

然后把$(\Delta {c_{0,30}},\Delta {c_{2,30}},\Delta {c_{4,30}})$与集合M中的第0、2、4位字节值进行比较。如果匹配结果相同，将$(\Delta {c_{0,30}},\Delta {c_{2,30}},\Delta {c_{4,30}})$存入新的集合${T_2}$中。

6) 重复步骤5)，扩展出中间状态的最后一个字节${x_{6,30}}$，将结果存入集合${T_3}$中，此时${T_3}$中可能有多个4字节的元素。

7) 多次重复步骤1)~6)，在加密过程中随机引入故障密文，直至${T_3}$中只剩下唯一的4字节元素，此元素就代表正确加密中间状态。在加密过程中，对密文的后4位进行攻击，按照步骤1)~6)，最后恢复出该算法的后4位中间状态。

8) 此后再根据PRESENT的P置换层和轮密钥异或加密过程，推导出最后异或时使用的密钥${K_{32}}$：

9) 同样在第29轮对PRESENT密码算法进行差分故障攻击，根据已经恢复的${K_{32}}$计算出第30轮的密文${C_{30}}$，重复步骤1)~8)，恢复出密钥${K_{31}}$。

本文根据故障传播特性建立的攻击方式，相比于传统采用的PRESENT密钥直接穷尽搜索有一定的优化，如直接穷尽搜索密钥，需要2⁶⁴复杂度。本文采用依次扩展的方法，根据每一轮中间状态匹配的数量，来降低下一轮穷尽搜索数，复杂度为：

式中，${n_1}$代表穷举前两个字节与可能正确值相匹配数目；${n_2}$、${n_3}$代表秘钥后面两个字节匹配数目。在提供一个故障密文的情况下，通过大量实验获取${n_1}$、${n_2}$、${n_3}$的平均值，可以计算出搜索该轮32 bit密钥的平均计算复杂度为2²⁵，搜索该轮64 bit原始密钥的计算复杂度为2²⁶。

根据PRESENT算法特点，攻击者需要在不同的位置多次引入不同的错误，再根据匹配表把筛选出的可能正确的中间状态取交集。根据文献[14]可知，恢复出一个轮密钥需要的最少故障数目为：

式中，n表示经过S盒代换层运算后输出比特数目；d表示经过线性层P置换后，扩展最后故障输出的比特数目。本文对PRESENT算法进行单字节攻击，恢复出原始轮密钥需的攻击复杂度为：

式中，${n_b}$表示穷举搜索中间状态与正确状态匹配数目；g表示还原出密钥${K_0}$所需要的理论最少轮密钥数目；si表示S盒输入的比特数目。

在加密运算过程中倒数第2轮的非线性层S盒或者线性P置换层引入任意一个单字节故障，最后产生的差分密文不一直零的只有32 bit，根据式(2)理论上最少需要4个单字节故障密文才能恢复出一个PRESENT算法的轮密钥。恢复出全部64 bit原始密钥至少需要8个单字节故障密文，并且经过连续两轮的随机攻击。根据式(3)可以计算理论攻击复杂度，其中${n_1}{n_2} \cdots {n_b})$根据多次实验得出平均值。那么在一个故障密文的情况下，恢复该轮PRESENT的32 bit密钥平均攻击复杂度为2³⁰，恢复该轮64 bit密钥的平均攻击复杂度为2³¹。相比于多重差分链攻击、差分代数攻击、Biclique等攻击方式，本文采用的差分故障攻击在很大程度上降低了攻击时所需的复杂度。

使用Visual Studio 2015工具在普通PC(CPU为Intel(R)Core(TM)i7 4790，3.60 GHz，内存8 GB)上用C++语言实现了PRESENT密码算法的加解密过程和差分故障攻击过程。实验加密明文取值为123456ab，初始密钥值取值为a0b1c2d3e4f5，建立随机攻击位置，随机故障值攻击模型一共完成100组实验。表 1为多次实验中的一组数据，给出了能够恢复出唯一轮密钥需要的故障数目和攻击时间。

在PRESENT算法加密过程中的第30轮和29轮导入随机故障，最后恢复该轮密钥大约需要24个故障密文。继续降低估计轮数，所需要的故障密文也逐渐下降，图 2给出了在不同轮数攻击，需要的故障数目与攻击成功率之间的关系。

图  2  PRESENT不同轮数与故障数目攻击结果

通过图 2可以得出，差分故障攻击轮数和导入故障数目对PRESENT最后的攻击结果会产生显著影响。在低轮数导入故障只需要12个故障密文就能100%恢复该轮密钥，最好情况下只需要6个故障密文。经过大量重复试验统计得出在低轮数进行差分故障攻击平均需要9个故障密文，这与式(2)所描述的理论故障数目基本相符。

利用优化后差分故障攻击方法，对PRESENT整个加密轮数进行攻击。通过C++语言得到实验结果，最后发现影响PRESENT攻击结果的因素有攻击轮数和故障密文数目。分析表明随着攻击轮数的降低，我们需要的故障密文数目随之下降。在低轮数进行随机位置随机故障值的差分故障攻击，平均只需要9个故障密文就能恢复该轮64 bit原始密钥，该方法的单故障密文密钥搜索复杂度和攻击复杂度也同时降低为2²⁶和2³¹。