空间冗余通过额外的硬件来检测电路是否遭受攻击，引入额外的资源消耗。文献[7]对高级加密标准(Advanced Encryption Standard, AES)加密算法S盒采用基于自检测系统的双模冗余和基于投票器的三模冗余，所需资源分别为基本S盒的1.8倍和2.5倍。时间冗余通过重复执行程序来检测瞬态故障或周期性故障，有很高的时间成本[8]。信息冗余采用错误检测编码[9-10]，在数据中增加冗余信息进行故障检测，所需空间和时间成本较低。
常用的错误检测编码有奇偶校验码、循环冗余码等。文献[11]将奇偶校验码和循环冗余码应用于RC5加密算法的故障注入检测，实验结果显示，后者所需资源明显多于前者。然而，奇偶校验码存在无法检测偶数比特故障的缺陷。文献[12]将奇偶校验应用于AES加密算法的故障检测，结果表明，奇数比特故障的检测率为100%，而2 bit和4 bit故障漏检率非常明显。文献[11, 13]显示，字节奇偶校验可以获得高于字奇偶校验的故障检测率，但所需时间和资源均高于字校验。
基于上述问题，本文提出了一种基于混合粒度奇偶校验的故障注入检测方法。对电路故障注入敏感部分或关键部分处理的数据采用细粒度奇偶校验(即n值较小)，对其他部分采用粗粒度奇偶校验。为了找到最佳粒度混合方案，以n=32、16、8、4 bit的奇偶校验为例，进行了故障检测率及资源使用的理论分析，并给出混合粒度故障检测方法检测率及资源使用的计算公式。为了评估本文提出的故障注入检测方法，将其应用于RC5加密算法并在现场可编程门阵列(Field Programmable Gate Array, FPGA)上实现，同时采用时钟故障注入攻击技术进行攻击，分析了不同混合粒度故障检测方法的性能。
1 奇偶校验及RC5加密算法 1.1 奇偶校验故障检测原理 奇偶校验故障检测结构如图 1所示，在原始电路基础上增加预测电路和比较电路。输入数据x通过原始电路得到其输出结果，并计算得出该结果的奇偶性y。输入数据x同时通过预测电路得到输出结果奇偶性的理论值p。y和p通过比较电路得出比较结果，若二者一致，则认为原始电路输出正确，否则原始电路有故障注入。
 |
| 图 1 奇偶校验故障检测结构 Fig. 1 Parity-code-based fault detection architecture |
| 图选项 |
1.2 RC5加密算法原理 RC5分组密码算法[14]由于其较高的灵活性、运算简洁性和出色的安全性能等优势，非常适合网络数据流、无线传感网络等加密应用。RC5算法的块长w(以比特表示的字的大小，通常取16、32、64 bit)、密钥长度b(常取0~255 Byte)、运算轮数r(取值范围0~255)均为可变参数[15]。这些参数能被调整以满足不同的安全目的和性能。
RC5算法加密时，对2个w字长的数据进行处理，加密过程如下：
 |
其中：初始的w比特数据A, B表示一组待加密的明文，最终的A, B表示加密完成后的一组密文；S序列表示由用户密钥扩展生成的加密密钥；< < < 表示循环左移。
2 混合粒度奇偶校验故障检测方法 2.1 基本思想 由于常用的字奇偶校验故障检测率较低，而字节奇偶校验资源占用较多，提出对电路不同部分采用不同粒度校验方法的混合粒度奇偶校验故障检测方法，以实现故障检测率及资源的折中。其基本思想为根据故障注入攻击特点，对电路中故障注入敏感部分或关键部分处理的数据采用细粒度奇偶校验，其他部分采用粗粒度奇偶校验。
2.2 RC5加密算法混合粒度故障检测实现 以RC5加密电路为例阐述本文提出的混合粒度故障注入检测方法，选取RC5最常用的参数组合(w=32 bit，b=16 Byte，r=12轮)。该方法同样可以应用于其他加密电路及其他参数组合，不同加密电路中包括的运算操作不同，故预测模块中对奇偶性的预测方法不同；同一加密电路的不同参数组合其差别主要在于加密数据比特数及加密轮数，电路模块数不同，设计原理相同。在本设计中，为实现流水线的操作[16]，需要13组加密模块，加密模块0初始化输入明文，加密模块1~12完全相同，执行加密操作，如图 2所示, A0表示明文A经加密模块0后的运算结果；PA0表示数据A0奇偶性实际值；pa0表示数据A0奇偶性理论值；Ta0表示PA0和pa0的比较结果; 以此类推。。
 |
| 图 2 RC5加密电路混合粒度故障检测实现 Fig. 2 Architecture of mixed-grain fault detection for RC5 encrypted circuit |
| 图选项 |
根据混合粒度奇偶校验故障检测思想，对每个加密模块附加预测电路及比较电路。为了实现模块化设计，每个模块输出结果奇偶性的实际值和理论值的计算均在预测模块中完成。预测电路和比较电路同样采用流水线结构。每个预测模块可以采用不同粒度的奇偶校验。
2.3 RC5故障检测预测电路设计 如1.2节所述，RC5加密算法包括3个运算操作：加、异或和循环左移。基于这3个操作解释奇偶性的预测方法。
m比特数据A的奇偶性p(A)通过异或其相应的比特位得
 | (1) |
2个数的和的奇偶性通过异或2个加数的奇偶性、进位输入Cin及加法过程产生的所有进位Cout(i)得
 | (2) |
2个数异或后的奇偶性由异或这2个操作数的奇偶性得
 | (3) |
一个数循环左移k比特后奇偶性不改变
 | (4) |
仅对其中的某些位进行奇偶校验时，计算更复杂。例如常用的字节校验，循环左移k比特后，每个字节奇偶性的计算如下：
 | (5) |
式中：h为字节数。因此，只需考虑ps(A < < < t)，0≤t≤7即可：
 | (6) |
其中：s=h－(k/8)mod4。
由上述分析可知，加和异或操作均需要3个寄存器来存储计算过程中数据的奇偶性，循环左移需要2个寄存器。越细粒度的奇偶校验，所需寄存器越多。
3 奇偶校验故障检测率及资源使用理论分析 为了在设计阶段找到最佳粒度混合方案，对不同粒度奇偶校验的故障检测率和资源使用进行理论分析。故障检测率为检测出的故障数占总故障数的百分比。在对故障检测率进行理论分析时，本文假设故障注入位置随机，不同比特故障出现的概率相等。
以32 bit数据为例，首先分别对32、16、8和4 bit的奇偶校验进行故障检测率理论分析。故障注入攻击可以引起1、2、…、32 bit的故障。根据数据组合原理，可得随机故障的总数为C321+C322+C323+…+C3231+C3232。32 bit奇偶校验方法可以检测到所有奇数比特故障，即可以检测到的故障总数为C321+C323+C325+…+C3229+C3231，所以故障检测率为50%。类似地，可分别计算出16、8和4 bit奇偶校验可检测出的故障总数，从而得出其故障检测率理论值，如表 1所示。
表 1 不同粒度校验方法故障检测率理论值 Table 1 Fault coverage in theory of multi-granularity detection methods
| 不同比特奇偶校验/bit | 故障检测率/% |
| 32 | 50 |
| 16 | 75 |
| 8 | 93.75 |
| 4 | 99.60 |
表选项
在资源消耗理论分析方面，以32 bit数据采用32 bit奇偶校验为例进行分析。由2.3节可得，预测电路需要8个寄存器存储数据奇偶性；在比较电路中，需要1个寄存器来存储加密数据奇偶性实际值与理论值的比较结果。当采用16、8和4 bit校验方法时，由于奇偶位的增加，所需寄存器分别为32 bit校验方法的2、4、8倍，如表 2所示。
表 2 不同粒度校验方法寄存器消耗理论值 Table 2 Register utilization in theory of multi-granularity detection methods
| 不同比特奇偶校验/bit | 寄存器数量 | |
| 预测电路 | 比较电路 | |
| 32 | 8 | 1 |
| 16 | 16 | 2 |
| 8 | 32 | 4 |
| 4 | 64 | 8 |
表选项
在实际故障注入中，不同比特故障数出现的概率并不完全相等，根据电路不同部分对故障注入的敏感程度采用不同粒度奇偶校验，以实现高故障检测率、低资源消耗的混合粒度故障检测方法。
4 实验及结果分析 为了评估本文提出的故障注入检测方法，将其应用于RC5加密算法并在FPGA上实现。通过布局布线后的时序仿真对电路进行时钟故障注入攻击，分析得出不同混合粒度故障检测方法的故障检测率及资源消耗。
4.1 时钟故障注入设置 时钟故障注入攻击在特定的时钟周期对电路注入故障，操作简单，易于实现。本实验先使电路工作在正常状态，之后不断缩小某一时刻时钟周期，如图 3所示，通过不断增大Δ值实现，直到电路关键路径计算结果错误。继续缩小该时刻时钟周期，其他路径也将注入故障，直到电路中所有路径均有故障注入。
 |
| 图 3 时钟故障注入示意图 Fig. 3 Schematic diagram of clock fault injection |
| 图选项 |
4.2 混合粒度奇偶校验故障检测率及资源使用 对于时钟故障注入，传输延迟越大的路径越容易产生故障。因此，对电路进行时序分析得出不同路径的延迟时间，延迟时间较大的路径采用较细粒度的奇偶校验，延迟时间较小的路径采用较粗粒度的奇偶校验。混合粒度奇偶校验故障检测方法的故障检测率计算式为
 | (7) |
式中：D为混合粒度故障检测方法故障检测率；dc为关键路径的故障检测率; di为其他路径采用不同粒度奇偶校验的检测率，理论值如表 1所示；βi为该校验方法在混合粒度故障检测方法中所占权重，对βi进行如下定义：
 | (8) |
其中：λi为不同路径的延迟。RC5加密算法中，每一轮分别对2个数据进行操作，除关键路径外，i的取值为0~24。
资源使用的理论计算式为
 | (9) |
式中：R为混合粒度故障检测方法所占资源；γj为不同粒度奇偶校验的资源使用，j取值为0~25。
根据λi对关键路径外的其他路径采用不同粒度奇偶校验方法，并根据上述理论对故障检测率及资源进行评估，得出最优混合粒度奇偶校验检测方案。
4.3 结果分析 表 3给出了对RC5加密电路进行时钟故障注入，在只考虑电路关键路径的情况下，不同粒度奇偶校验的故障检测率实际值。可见，实际值与表 1中理论值相近。
表 3 不同粒度校验方法故障检测率实际值 Table 3 Fault coverage in practice of multi-granularity detection methods
| 不同比特奇偶校验/bit | 故障检测率/% |
| 32 | 51.92 |
| 16 | 73.97 |
| 8 | 89.24 |
| 4 | 96.28 |
表选项
对图 2所示RC5加密电路采用不同混合粒度奇偶校验，与传统奇偶校验故障检测方法进行比较，所需寄存器个数和故障检测率如图 4和图 5所示。传统奇偶校验对所有路径分别采用32、16、8、4 bit奇偶校验。针对时钟故障注入，混合粒度奇偶校验中延迟越大的路径，故障检测率在总故障检测率中所占比重越大。其中，关键路径的故障检测率起决定性作用。因此，按路径延迟降序排列，分析比较不同路径采用不同粒度校验方法时的故障检测率及资源使用情况，得出图 4和图 5中横坐标所列出的不同混合粒度检测方法。例如，标识为32的设计是电路所有路径均采用32 bit奇偶校验；标识为16-32的设计是关键路径采用16 bit而其他路径采用32 bit的奇偶校验；标识为16-16-32的设计是路径延迟时间最大的前2条路径采用16 bit奇偶校验，而其他路径采用32 bit奇偶校验；标识为16-16-16-32的设计是路径延迟最大的前3条路径采用16 bit奇偶校验，其他路径采用32 bit奇偶校验；以此类推。
 |
| 图 4 不同混合粒度检测方法寄存器消耗值 Fig. 4 Register utilization of different mixed-grain detection methods |
| 图选项 |
 |
| 图 5 不同混合粒度检测方法故障检测率 Fig. 5 Fault coverage of different mixed-grain detection methods |
| 图选项 |
由图 4可见，寄存器数量随着奇偶位的增加而不断增加，所有路径均采用4 bit奇偶校验时，附加奇偶位最多，寄存器数量显著增加。由图 5可知，按路径延迟降序排列，选取相同数目路径采取较细粒度奇偶校验时，关键路径附加奇偶位越多，电路故障检测率越高。如按路径延迟降序排列，对前3条路径所在模块采用不同粒度奇偶校验，其他模块采用32 bit奇偶校验，即图中标识为16-16-16-32、8-8-8-32、4-8-16-32、4-4-4-32的混合粒度奇偶校验，其故障检测率分别为91.37%，97.54%，98.97%，99.33%。且关键路径采用相同粒度校验方法时，其余路径校验方法的选取对电路总故障检测率的影响较小。如关键路径采用4 bit奇偶校验，其余路径选取不同粒度校验方法，即图中标识为4-32、4-8-32、4-8-16-32、4-4-32、4-4-8-16-32、4-4-4-32、4的混合粒度奇偶校验检测方法，其故障检测率分别为98.21%、98.70%、98.97%、98.79%、99.51%、99.33%、99.86%。4-8-16-32、4-4-4-32、4-4-8-16-32的混合粒度奇偶校验与所有路径均采用4 bit奇偶校验相比，故障检测率分别相差0.89%、0.53%、0.35%，可以看出，路径延迟越小的路径，选取不同粒度奇偶校验时，故障检测率的差值越小。综合故障检测率及资源的折中，考虑对前4条路径采用细粒度奇偶校验即可。
综合图 4和图 5实验结果可知，整个电路都采用32 bit奇偶校验时，故障检测率最低，为76.88%；所需资源最少，寄存器消耗为4 427。整个电路都采用4 bit奇偶校验时，故障检测率最高，为99.86%；所需资源也最多，寄存器数量为5 719。按路径延迟时间降序排列，依次对前4条路径采用4、4、8、16 bit奇偶校验，其他路径采用字校验的混合粒度奇偶校验检测方法检测率为99.51%，比全部采用4 bit奇偶校验减小了0.35%，然而寄存器数量较4 bit奇偶校验显著减小，为4 537，减小了20.67%。该方法与全部采用字校验相比，故障检测率提高29.44%，资源消耗仅增加2.48%。综上考虑，4-4-8-16-32的校验方法为混合粒度奇偶校验的最优方法。
5 结论 本文提出一种基于混合粒度奇偶校验的故障注入检测方法，主要目标是实现高故障检测率、低资源占用。
1) 对电路故障注入敏感部分或关键部分处理的数据采用细粒度奇偶校验，对其他部分采用粗粒度奇偶校验，实现了故障检测率和资源的折中。
2) 为了得出不同粒度奇偶校验方法的特性，在设计阶段找到最佳粒度混合方案，分别对32、16、8、4 bit的奇偶校验进行故障检测率及资源使用的理论分析，并给出混合粒度故障检测方法检测率及资源使用的计算公式。
3) 将本文提出的故障注入检测方法应用于RC5加密算法并在FPGA上实现，同时采用时钟故障注入攻击技术攻击该硬件电路。实验结果表明，按路径延迟时间降序排列，依次对前4条路径采用4、4、8、16 bit奇偶校验，其他路径采用字校验的混合粒度故障检测方法为最优检测方法，检测率可达99.51%，和所有路径均采用字校验的方法相比，检测率提高了29.44%，寄存器数量仅增加2.48%。
参考文献
| [1] | BARENGHI A, BREVEGLIERI L, KOREN I, et al. Fault injection attacks on cryptographic devices:Theory, practice, and countermeasures[J]. Proceedings of the IEEE, 2012, 100(11): 3056-3076. DOI:10.1109/JPROC.2012.2188769 |
| [2] | LIU Y N, ZHANG J, WEI L X, et al.DERA: Yet another differential fault attack on cryptographic devices based on error rate analysis[C]//52nd ACM/EDAC/IEEE Design Automation Conference.Piscataway, NJ: IEEE Press, 2015. |
| [3] | DUTERTRE J M, FOURNIER J J A, MIRBAHA A P, et al.Review of fault injection mechanisms and consequences on countermeasures design[C]//International Conference on Design & Technology of Integrated Systems in Nanoscale Era. Piscataway, NJ: IEEE Press, 2011: 5941421. |
| [4] | CHU J, BENAISSA M. Error detecting AES using polynomial residue number systems[J]. Microprocessors & Microsystems, 2013, 37(2): 228-234. |
| [5] | SONDON S, MANDOLESI P, JULIAN P, et al.Heavy-ion micro-beam use for transient fault injection in VLSI circuits[C]//International Conference on Plasma Sciences. Piscataway, NJ: IEEE Press, 2014: 7012614. |
| [6] | KOOLI M, NATALE G D.A survey on simulation-based fault injection tools for complex systems[C]//IEEE International Conference on Design & Technology of Integrated Systems in Nanoscale Era. Piscataway, NJ: IEEE Press, 2014: 6850649. |
| [7] | BENEVENUTI F, KASTENSMIDT F L.Evaluation of fault attack detection on SRAM-based FPGAs[C]//Test Symposium. Piscataway, NJ: IEEE Press, 2017: 7906747. |
| [8] | MESTIRI H, BENHADJYOUSSEF N, MACHHOUT M, et al. A robust fault detection scheme for the advanced encryption standard[J]. International Journal of Computer Network & Information Security, 2013, 5(6): 49-55. |
| [9] | TOMASHEVICH V, SRINIVASAN S, FOERG F, et al.Cross-level protection of circuits against faults and malicious attacks[C]//International on-Line Testing Symposium. Piscataway, NJ: IEEE Press, 2012: 150-155. |
| [10] | MOZAFFARI-KERMANI M, REYHANI-MASOLEH A. Concurrent structure-independent fault detection schemes for the advanced encryption standard[J]. IEEE Transactions on Computers, 2010, 59(5): 608-622. DOI:10.1109/TC.2010.33 |
| [11] | BERTONI G, BREVEGLIERI L, KOREN I, et al. Concurrent fault detection in a hardware implementation of the RC5 encryption algorithm[J]. Application-Specific Systems, Architectures, and Processors, 2003, 16(3): 423-432. |
| [12] | BEDOUI M, MESTIRI H, BOUALLEGUE B, et al.A reliable fault detection scheme for the AES hardware implementation[C]//International Symposium on Signal, Image, Video and Communications. Piscataway, NJ: IEEE Press, 2017: 47-52. |
| [13] | WEN L, JIANG W, JIANG K, et al.Detecting fault injection attacks on embedded real-time applications: A system-level perspective[C]//2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems. Piscataway, NJ: IEEE Press, 2015: 700-705. |
| [14] | GILL H S.Selection of parameter 'r' in RC5 algorithm on the basis of prime number[C]//Engineering and Computational Sciences. Piscataway, NJ: IEEE Press, 2014: 6799519. |
| [15] | RIVEST R L.The RC5 encryption algorithm[C]//International Workshop on Fast Software Encryption. Berlin: Springer-Verlag, 1995: 86-96. |
| [16] | BEVI A R, SHESHU S S V, MALARVIZHI S.FPGA based pipelined architecture for RC5 encryption[C]//Second International Conference on Digital Information and Communication Technology and It's Applications. Piscataway, NJ: IEEE Press, 2012: 214-219. |
