一种新的抵抗差分错误分析的S 盒实现*

徐翌豪, 李智虎, 樊燕红, 王美琴

1. 山东大学网络空间安全学院, 青岛 266237

2. 密码技术与信息安全教育部重点实验室, 青岛 266237

3. 中国电力科学研究院有限公司, 北京 100192

1 引言

密码算法的理论安全性是随着密码分析技术的不断发展而逐渐完善的, 但是现代密码算法安全性的威胁不仅来自对算法层次的数学理论分析. 随着无线传感、射频识别(radio frequency identification,RFID)以及物联网的高速发展, 轻量级密码算法在资源相对受限的环境中应用越来越广泛[1,2], 而轻量级密码算法大多采用硬件方式实现, 这就导致物理攻击对于密码算法安全性的威胁越来越大. 在物理攻击中, 错误注入攻击[3]属于主动的物理攻击, 相比于被动的侧信道分析[4], 错误注入攻击可以极大地减少分析的样本量[5], 极大提高了攻击效率. 错误注入攻击主要通过电磁脉冲、时钟毛刺、激光束等手段在密码算法的硬件实现中使寄存器、门电路或者线发生错误, 之后结合数学统计和分析, 通过注入错误得到的错误密文与正确运算得到的无错密文之间的差分来获取密钥的相关信息, 这就是差分错误分析(differential fault analysis, DFA)[6–9]. 随着错误注入精度以及软硬件逆向技术的提高, 实施错误攻击所依赖的设备条件不断减弱, 成本不断下降, 错误类型和位置已经在一定程度上可以控制, 敌手可以轻松对任意不受保护的密码算法进行错误注入, 因此几乎所有的密码算法都易受到DFA 的威胁. Aghaie 等人[10]从基于错误检测码(error detecting code, EDC) 的并发错误检测(concurrent error detection, CED) 模式[11]出发, 考虑错误传播在组合逻辑电路中的消极影响, 设计出对于给定的敌手模型下对于错误注入的检测有100% 覆盖率的完美电路. Beierle 等人[12]首先在密码算法的设计阶段就考虑到在不同安全级别下抵抗DFA, 并设计出高效的轻量级密码算法CRAFT. CRAFT 的S 盒设计理念充分考虑到错误传播的消极影响, 利用独立特性, 使S 盒的全部输入共同决定输出的1 比特信息, 这样不复用的电路元件之间就可以避免注入错误的扩散, 结合CED 模型, 敌手注入的错误可以100% 被检测到. Baksi 等人[13]从密码算法抵抗差分分析和差分错误分析的权衡出发, 设计出可以用于抵抗DFA 的具有特殊线性结构的S 盒, 为密码算法抵抗DFA 的研究提供了新的思路.

S 盒是分组密码算法的重要组件之一, 是执行非线性运算的算法组件, 安全性和软硬件性能[14–16]是衡量S 盒优劣的两个重要指标. S 盒的实现方式有两种: 查表(lookup table, LUT) 和布尔函数表达式, S 盒的实现环境分为软件实现和硬件实现. S 盒的软硬件实现通常利用LUT 实现. 对于S 盒查表的硬件实现[17]而言, 实现者利用综合器内置的优化算法将S 盒转化为布尔电路. 虽然综合器能够对S盒的LUT 实现进行一定程度的优化, 但是由于其内置的优化算法是面向通用函数的, 对于S 盒的特殊实现要求输出的结果有可能不是最优[18]. 针对不同的实现准则如等价门电路的复杂度(gate equivalent complexity, GEC)、切片门电路的复杂度(bitslice gate complexity, BGC)、深度(depth) 等, 如何找到S 盒较好的布尔函数实现成为近期的热门研究领域. 针对ASIC (application specific integrated circuit)平台, Lighter[18]工具实现了在给定指令集下搜索S 盒的最优面积布尔函数; Guo 等人[19]提出了一种基于深度的S 盒实现方法, 通过递归的算法寻找给定S 盒的深度最优的布尔函数实现; PEIGEN[20]工具是一种集S 盒实现, 评估及设计为一体的综合工具, 其在Lighter 工具的基础上进行改进, 提升了搜索S 盒布尔表达式的效率, 除此之外, PEIGEN 工具也优化了Guo 等人S 盒深度最优的实现方法, 在保证深度最优的前提下同时保证面积的局部最优.

我们的工作深入理解在差分错误分析中错误传播的消极影响, 提出密码算法抵抗DFA 的S 盒独立性实现, 并在实现性能方面进行了提升. Aghaie 等人[10]采用LUT 方法进行S 盒实现, 利用综合软件内部的优化算法进行优化. 综合器对复杂S 盒的LUT 的优化并不是最优的, 因为通用的优化算法不会考虑S 盒的具体实现特性. 我们使用基于图的布尔函数生成算法, 通过回溯的方式筛选出给定S 盒满足独立性的布尔表达式, 在限制深度的同时, 选取面积最优的实现方式, 来优化独立性S 盒的硬件布尔表达式实现. 利用我们提出的生成独立性S 盒的算法, 对GIFT、Khazad、LBlock 等已知S 盒进行实现, 并利用Synopsys DC 综合软件和UMC 55 nm 标准元件库对S 盒独立性布尔表达式实现进行综合. 综合结果显示, 与单纯的依赖综合软件优化的LUT 实现方法相比, 我们提出的S 盒独立性优化实现方法, 不同程度地提升了S 盒的实现效率.

2 研究背景

2.1 独立性

密码算法的错误注入攻击方法首先被Boneh 和DeMillo 等人[3]提出并成功运用到RSA 的CRT 版本中. 随后Shamir 等人[6]利用差分分析的方法与错误注入攻击相结合, 提出差分错误分析的攻击方法,并对传统的DES 算法进行了攻击. 其核心思想就是利用差分错误分析的方法, 使用时钟毛刺、激光束、电磁干扰等手段在密码算法运行时向其中注入错误, 使最终的加密结果出现差错, 从而恢复出相关的密钥信息. 2018 年, Aghaie 等人[10]从错误传播的消极影响出发, 设计出在给定敌手模型下错误检测率100% 的完美电路, 并提出独立性将其应用于抵抗DFA 的S 盒实现中, 下面给出独立性质的定义.

其中Gi代表成员函数Ti的门电路实现集合. 那么满足上述形式的组成电路集合是独立的, 满足独立特性可以避免错误传播, 即一个错误的门最多导致输出1 比特的错误.

由定义可知, 独立性质主要为了避免密码算法执行时在S 盒组件中发生的错误扩散传播, 如果设计的S 盒满足独立特性, 那么在最坏的情况下(注入的错误门一定导致错误的输出), 敌手攻击t个门电路也最多只会导致对应t比特出现错误, 这就使注入的错误不会在电路中发生扩散.

接下来我们介绍非独立性S 盒的实现方式与独立特性S 盒实现方式的区别, 非独立性S 盒实现时一般不考虑门电路是否复用, 这就可能导致在S 盒的具体实现时, 会存在S 盒不同输出复用门电路的情况,使得一个门可能被多个输出共用, 如图1(a) 所示. 独立性S 盒的电路实现避免了门电路的复用问题, S 盒的每一比特输出都独立于其他输出比特对应的电路实现, 如图1(b) 所示. 图中的x,y,z表示电路的输入,x′和y′表示电路的输出.

从图1 可以看出,非独立特性S 盒的两个输出具有一个复用的异或门(XOR),独立特性S 盒的实现没有复用的门. 假设敌手有攻击一个门电路XOR 的能力, 非独立性的实现方式会使错误扩散到第二个OR门从而导致输出的两个比特全部出错, 而独立性的实现方式保证了两个输出对应的门电路独立, 只能影响输出的1 个比特, 这样就阻止了错误的扩散, 使得在并发错误检测模式下可以精准的检测错误.

图1 非独立性电路与独立性电路的错误扩散Figure 1 Error propagation in non-independent circuits and independent circuits

2.2 深度最优的S 盒实现

电路深度复杂度通常定义为从输入门到输出门的最长路径的长度. 在高速电路硬件实现的情况下, 实现者有时候希望将电路的深度保持尽可能低, 以便能够增加时钟频率, 而不必使用更多的门. 例如任何函数都可以通过深度为2 的电路来计算, 即将该函数通过合取或析取范式来表示, 然而这样的表示方法可能会导致电路中门电路数量较大, 这是实现者不希望看到的, 因此需要在电路的深度和门电路数量之间权衡.下面给出S 盒深度的定义.

定义2 (S 盒深度) S 盒深度定义为, 在S 盒输入到输出电路中, 最长路径所包含的逻辑门电路的个数.

Guo 等人[19]提出一种S 盒的深度评估工具, 其核心是预计算的功能模块. 预计算模块通过一个递归算法枚举在某一个深度下S 盒输入比特的所有可能的布尔函数. 深度评估工具通过与预计算得到的布尔函数进行匹配来找到给定S 盒深度最优的布尔函数实现. Bao 等人[20]对文献[19] 中的算法在等价门电路复杂度(GEC) 方面进行了提升, 实现了深度最优、等价门电路局部最优的S 盒布尔表达式的实现. 具体实现方式是在一个指令集β(包括AND, OR, XOR, NAND, NOR, XNOR 和NOT 等) 中, 通过广度优先的方式生成一个图. 图的每一个节点表示一个状态值(即操作数)及其布尔函数,边代表前一层上的节点与当前节点通过操作指令产生的联系. 假设一个i比特输入的S 盒, 初始节点定义为v0,v1,··· ,v(i-1),也称为输入的恒等变换布尔函数, 初始节点对应的层数定义为图的第0 层. 图的扩展以初始节点开始, 以层为单位遍历指令集中的所有指令, 图的生成过程如图2 所示.

图2 布尔函数图的生成示意图Figure 2 Diagram of generation of Boolean function graph

在每一层图节点的生成过程中, 不仅需要对指令集中的操作指令遍历, 同时还要遍历操作数, 操作数包括层数小于当前层数的所有节点, 新生成的节点需要记录生成该节点的操作类型以及操作数, 在图的生成过程中, 对新生成的节点布尔函数的门电路复杂度不断优化, 过滤掉有相同状态值但门电路复杂度较大的节点, 不仅保证S 盒每一个分量的门电路复杂度最小, 同时利用在不同分量之间选择可共享的指令前缀的方式优化等价门电路的全局复杂度, 即对于每一个分量深度最小的前提下找到等价门电路复杂度最小的实现方式, 最后保证图中每个布尔函数都是深度最优, 等价门电路复杂度局部最优.

3 独立性S 盒实现算法

3.1 设计策略

我们借鉴了Guo 等人[19]的生成S 盒的布尔表达式的方法以及Bao 等人[20]的改进方法, 通过生成图的方式在一个指令集β中, 寻找已知S 盒独立实现的最优硬件表达式.

(1) 本文的算法着重于布尔函数的硬件实现的优化, 选择的硬件指令集是单输入的NOT 门以及两输入的逻辑门AND/OR, XOR/XNOR, NAND/NOR. 我们使用∧、∨、⊕和¬分别代表逻辑与、或、异或、非, 指令集及逻辑运算如表1 所示.

表1 算法逻辑指令集Table 1 Logic instruction set in algorithm

(2) 设计的S 盒的门电路实现具有独立特性. 本文设计的独立性布尔函数的过滤策略基于这种以深度扩展的图算法, 独立性要求在门电路实现时没有共用门, 即如果在以初始节点进行第一层图扩展时生成的所有新节点, 在给定S 盒的所有分量布尔函数中至多只出现一次, 则该S 盒的布尔函数实现满足独立特性.

(3) 根据指令集的权重, 寻找满足独立性S 盒的最优面积实现. 我们设计策略是在深度最优的情况下,搜索面积局部最优的独立布尔表达式实现.

3.2 独立性S 盒算法设计

独立性S 盒实现算法包括两个模块的设计: 图生成模块和独立性实现模块. 图生成模块利用指令集和扩展算法构建不同层上的节点, 直至构建出满足S 盒特定状态值的节点. 独立性实现模块的主要功能是:在生成图的基础上, 筛选满足独立特性S 盒的布尔表达式.

3.2.1 图生成模块

在图生成模块中, 与文献[19,20] 的不同之处在于, 我们不对生成的节点进行过滤与优化, 保留所有的节点, 这样生成的图中, 存在多个不同的节点代表的状态值是相同的, 但是他们分别表示不同的布尔函数,这样我们可以得到所有可能的布尔表达式, 以保证进入独立性实现模块的布尔函数的完整性. 当然算法的生成图模块只需执行一次, 对于不同S 盒可以多次重用. 随着图的层数的增加, 节点数量呈指数级增长, 我们考虑有限的计算资源和内存资源, 定义参数λ作为层数阈值,λ可以根据内存资源设定作为图扩展算法的终止条件. 当图的扩展算法完成时, 就得到了在给定指令集下的全部布尔函数, 对于给定的S 盒, 算法可以回溯图中的节点, 推导出该S 盒对应的布尔函数实现.

3.2.2 独立性实现模块

在给定深度和指令集的生成图中, 包含了S 盒对应的所有可能的布尔函数. 算法的独立性实现模块的设计思路是, 在所有可能的布尔表达式实现中, 利用两次过滤的方法, 筛选出满足独立特性的布尔表达式.两次过滤的具体内容如下:

(1) 首先过滤掉面积成本较高的实现方式;

(2) 然后过滤掉不满足独立特性的实现方式.

以4 比特S 盒为例, 我们介绍搜索独立性实现模块的操作流程.

(1) 在生成的图中搜索满足目标S 盒的4 个分量函数的节点并分类存储为4 个组,记C1,C2,C3,C4.

(2) 从4 个组的每一组中任取其中一个元素进行组合, 即可得到给定S 盒的一种布尔函数实现. 这样的组合方式会使一个S 盒有很多种不同的布尔函数实现.

(3) 我们首先针对所有组合, 考虑其实现的等价门电路复杂度, 根据指令集的面积权重设置过滤阈值,滤除面积实现成本高的组合, 这样大大减少了独立性筛选的样本量.

3.3 算法实现

已知S 盒的独立性布尔表达式的优化实现如算法1 所示. 给定参数λ作为层数阈值, 此参数可根据操作系统的内存容量进行调整, 以避免深度过大时的内存溢出, 算法的另一个参数target 是目标S 盒. 以i表示S 盒的位数,V表示图的节点,Vdepth表示在第depth 层的生成的所有节点集合, 其中depth 参数初始化为0, 使用SUCC(v,o) 记录新节点与操作数以及指令之间的运算关系, 使用before 指针记录新节点与操作数节点之间的逻辑关系, 以便于节点指针的回溯. 在判断候选布尔表达式是否为独立特性时, 为了便于表述, 我们使用AreaFilter 函数过滤面积较大的布尔函数实现. 取出分量节点N1,N2,··· ,Ni中的指令面积并求和与AreaThreshold 参数进行比较, 返回值为True 表示面积大于指定阈值, 此函数可以根据给定的S 盒自定义调整以获得局部面积最优的实现方式. 另外使用IsDump 函数表示向量组中是否有重复的节点, 如果返回为真, 则说明给定S 盒的i个候选布尔函数在图的首次扩展时产生了共同了相同的节点, 即最终结果不满足独立特性, 反之, 则表示S 盒的布尔函数实现没有共用的门电路, 即此候选布尔表达式满足独立特性. 算法1 生成图阶段和独立性搜索阶段的时间复杂度均约为226.56, 故本算法总时间复杂度约为227.56, 而在生成图的具体实现时, 本文使用structure 来表示节点记录的信息, 具体包括该节点的状态值及其对应的布尔函数、操作指令、指令权重, 所以, 本文所提算法的空间复杂度约为226.56个structure.

算法1 独立性S 盒实现Input: target, λ Output: 独立布尔函数实现ImplementFile 1 初始化depth ←0,E ←Ø,V0 ←{v0,v1,··· ,vi},G = {V0,E}2 调用图生成函数GenGraph(G,depth,λ)3 遍历图G 搜索目标S 盒targrt 的分量函数, 并将这些节点分别存储在C1,C2,··· ,Ci 中4 for each N1,N2,··· ,Ni in C1,C2,··· ,Ci do 6 while (N1,N2,··· ,Ni) /∈V1 do 5if AreaFilter(N1,N2,··· ,Ni,AreaThreshold) then 7 N1 = N1.before,N2 = N2.before,···, Ni = Ni.before 8 end将N1,N2,··· ,Ni 的切片数据存储到向量Vec 中10if IsDump(Vec) then 9 11Print Result(N1,N2,··· ,Ni,False)12end 13else 14Print Result(N1,N2,··· ,Ni,True)15end 16end 17 end 18 function GenGraph(G,depth,λ)19 Vt = Ø 20 for all o in β do 21if (o == NOT) then 22for all v ∈Vdepth do 23N ←SUCC(v,o)24N.before=v,Vt ←Vt ∪N, E ←E ∪{v →N}25end 26end 27else 28for all vx ∈Vdepth do 29for all vy ∈V do 30N ←SUCC(vx,vy,o), N.before=(vx,vy)31Vt ←Vt ∪N,E ←E ∪{vx →N}32end 33end 34end 35 end 36 depth = depth+1, Vdepth = Vt, G ←G ∪{Vdepth,E}37 if (depth ≤λ) then 38GenGraph(G,depth,λ)39 end 40 return G

4 实验与结果

4.1 实验环境

S 盒独立特性优化实现算法用C++ 语言进行了程序实现, 程序运行的系统环境为: Intel Xeon CPU E5 2620 @2.00 GHz 128 G 内存, 64 位Ubuntu 16.04.4 LTS. 对不同的目标S 盒, 算法程序返回优化后的独立表达式所用的时间平均约为12.36 分钟. 获得S 盒的具有独立性的布尔表达式后, 先使用Verilog HDL 进行硬件实现, 然后在Modelsim 软件上进行功能仿真, 最后使用Synopsys Design Compiler 综合软件与UMC 55 nm 的标准元件库进行硬件电路的综合仿真, 得到S 盒的面积及时延的测试结果.

4.2 实验结果

我们以GIFT 的S 盒为例, 给出生成的独立布尔表达式. 值得注意的是, 使用我们的算法生成的所有布尔表达式中, 可能存在一个给定S 盒的多种不同的表达式实现, 而这些不同的表达式经过综合之后得到相同的硬件面积和时延, 这里只给出其中一种表达式实现. 定义S 盒的输入和输出分别为{X[3],X[2],X[1],X[0]}和{Y[3],Y[2],Y[1],Y[0]}, 其中X[3] 和Y[3] 分别代表最高位.

从如上所示的布尔表达式实现来看, GIFT 的S 盒的每一个分量函数对应的布尔表达式彼此之间互相独立, 这样就可以使注入的错误在S 盒层不发生扩散, 大大提高并发错误检测的效率. 利用我们的S 盒实现算法, 生成了目标S 盒的具有独立特性的布尔表达式. 然后对每个目标S 盒进行两种实现: LUT 和独立布尔函数. 最后利用ASIC 综合平台分别将两种实现方式进行综合, 得到面积和时延的测试结果, 具体的实验结果见表2. 从实验结果可以看出, 对于一个给定的S 盒, 使用本文的算法生成的独立布尔表达式的实现无论在面积或者时延开销上都优于直接独立LUT 的实现方法. 本文对S 盒的独立性实现性能进行提升, 使其在实现时的硬件开销和时延都优于之前的工作, 为抵抗DFA 的S 盒的实现设计提供了新的思路.

表2 实验结果Table 2 Experimental results

5 总结

实验结果显示, 使用我们的算法生成S 盒独立特性的布尔表达式综合之后的结果会好于独立LUT 的方法. 该算法以及思路是首次对于抵抗DFA 的S 盒独立特性的研究, 提出的生成独立特性布尔表达式的新方法, 对于防止差分错误注入分析的S 盒有实践意义, 为研究设计抵抗DFA 的密码算法的组件提供一个新的思路. 虽然我们提出的新思想和新方法对于传统的抵抗DFA 的S 盒有提升, 但是我们提出的算法也有局限性, 对于实现复杂的S 盒, 需要更多的层数来实现, 生成的图的规模会呈指数级别的增长, 从而需要相当大的时间和空间复杂度去生成优化的独立布尔表达式. 接下来我们会继续研究和改进我们的算法,考虑在生成图的过程中如何避免庞大的节点个数以及在独立的布尔表达式的生成过程中如何设计更高效的搜索算法.