低面积复杂度AES低熵掩码方案的研究

姜久兴，厚娇，黄海，赵玉迎，冯新新

（1. 哈尔滨理工大学理学院，黑龙江 哈尔滨 150080；2. 哈尔滨理工大学软件与微电子学院，黑龙江 哈尔滨 150080；3. 哈尔滨理工大学计算机科学与技术学院，黑龙江 哈尔滨 150080）

1 引言

高级加密标准（AES, advanced encryption standard）算法因安全性、效率、灵活性等方面具有良好的性能，因此被广泛地应用在实践中。侧信道攻击（SCA, side-channel attack）技术[1]的出现对加密芯片的安全性构成了很大的威胁，典型的SCA包括时间分析攻击、电磁辐射攻击、功耗分析攻击[2]等，其中差分功耗攻击（DPA, differential power attack）[3]，尤其是高阶DPA，对芯片的硬件安全的威胁最大，采用掩码方案是抵御DPA最有效的方法。AES加密算法的安全性将随着掩码阶数的增加而提高，但掩码阶数的增加会带来硬件成本成倍的增加。目前，掩码方案主要有查找表掩码[4-5]、加法链掩码[6]和复合域掩码[7]这3种，相较于后2种方案，查找表掩码方案具有实现速度快、易于实现等特点，但存在存储空间大的不足，难以应用到资源受限的设备中。针对这一问题，Nassar等[8]提出了一种循环移位S盒掩码（RSM, rotating S-box masking）方案，该方案能够有效地降低面积复杂度，是一种安全性和性能的折中方案，能够抵抗一阶和二阶 SCA。然而，对于一些面积受限的设备，例如智能卡、物联网终端设备等，RSM仍不能满足实际的应用需求[9]。

本文在RSM方案的基础上，分析了RSM方案掩码值的特点，提出了一种基于S盒共用的方案，所提方案能使面积复杂度进一步降低，并针对AES进行了掩码方案架构设计与硬件实现，对整体架构进行了流水线的设计。所提方案与RSM方案相比，大幅度降低了面积复杂度，从理论上和实验上证明了具有更高的安全性和更好的性能。所提方案在满足性能和安全性的前提下，能够有效地节约硬件资源，降低实现成本，对资源受限的设备和民用小型服务器具有重要的意义。

2 相关工作

AES加密算法的掩码方案中，基于查找表的掩码方案通过采用S盒重计算技术增加攻击难度来抵御SCA。1999年，Chari等[10]首次提出了随机查找表方案，对S盒进行了T(u)=S(u⊕r)⊕s的随机化处理，其中，u是明文，r是输入掩码，s是输出掩码。但是该方案没有对AES的所有轮都添加掩码，因此仅能抵御一阶DPA。文献[11]对文献[10]中所提方案采用中间轮攻击操作，得到了正确的密钥。2001年，Itoh等[12]采用固定值掩码方案抵御中间轮攻击，但所有轮操作都采用同一掩码值。该方案着重考虑AES加密算法的加密速度，将随机掩码和根据随机掩码计算得到的S盒存储在ROM中，减少了 RAM 的空间。但是该方案只能抵御一阶SCA，不能抵抗二阶及以上的SCA，因为通过对2个经过掩码的中间结果进行异或处理，就可以去掉掩码值。

Nassar等[8]提出了RSM方案，采用了低熵掩码设计，利用16个不同的S盒，解决了固定值掩码方案难以抵抗二阶SCA攻击的问题。RSM掩码原理如式(1)所示。

其中，SB表示128位数据的字节替代操作，X表示需要掩码的 128位数据j的选取在第一轮，之后每轮都是固定值（即掩码值循环左移），因此掩码值的选取共有 16种可能。在每轮加密操作结束后需要进行掩码补偿，即去掉上次的掩码，添加新的掩码。为了提高 AES加密算法的计算速度，使用重计算的16个S盒存储在ROM中。

RSM 方案的优点在于以牺牲少量面积和性能为代价，达到抵御一阶SCA攻击、二阶SCA攻击、零值攻击等攻击，有效地提高了 AES的安全性。2014年，Yamashita等[13]公布了一种变种的RSM方案 vRSM（variant RSM），该方案去掉了中间轮的重新掩码操作（这些操作对于 RSM 方案是不可或缺的），在不影响安全性的前提下，进一步降低掩码的复杂度，其面积开销为RSM方案的90%，但该方案的输出掩码值是由输入掩码值决定的。2015年，徐佩[14]提出了改进的RSM方案，该方案充分考虑了掩码值的汉明质量，对随机掩码的选取进行了优化设计，同时对S盒循环移位的次数进行了随机化设计，能够抵抗基于一阶偏移量的相关性功耗分析（CPA, correlation power analysis），这是RSM方案不具备的。为了增加算法的加密速度，文献[14]对AES的前两轮和最后两轮采用随机掩码的方式，其他中间轮采用固定值掩码的方式，这样中间轮能够采用相同的掩码S盒，减少计算掩码S盒数量，提高速度。可以看出，文献[14]提出的方案是RSM方案的改进方案，但存在不能抵御中间轮的攻击和面积相对于其他方案面积有所增加的缺点，从安全性方面看，仍不是一个最优的方案。

综上，现有的基于查找表掩码的掩码方案难以兼顾安全性和复杂度。本文在分析 RSM 方案掩码值特点的基础上，提出了一种低熵掩码方案，通过S盒共用思想减少掩码S盒的数量，从而进一步降低RSM方案的面积复杂度。

3 S盒共用的思想

3.1 掩码值的选取

根据文献[15]可知，RSM方案的掩码值必须是正交的，这样才能确保算法的安全性。因此，本文掩码值的选择方法采用文献[16]中的方法，具体如下。假设正交矩阵的维度是Q，列数是N，行数是Q^J，J的选取需满足，首先利用置换方法获得正交矩阵[16]，其中，Q=2，N=15，J=4，生成的正交矩阵A有 15列，如式(2)所示。这 15列的值分别为00ff、0f0f、0ff0、3333、33cc、3cc3、3c3c、5555、55aa、5a5a、5aa5、6666、6699、6969、6996，然后从正交矩阵A中随机选择8列构造满足约束条件的16个掩码值。通过分析矩阵A能够看出，每一列中的4个十六进制数的要么相同，要么取反，这也是本文设计S盒共用掩码方案能够实现的基础。

3.2 S盒共用掩码方案

S盒共用掩码方案是一个通用方案，适用于掩码值满足正交向量要求的任意掩码方案。以随机选取{0x00 0x0f 0x36 0x39 0x53 0x5c 0x65 0x6a 0x95 0x9a 0xa3 0xac 0xc6 0xc9 0xf0 0xff }为例，对该方案进行详细说明。能够看出随机选取的 16位掩码值中，高4位和低4位不是相同就是互补。根据这一特征，进行如下分组，用Mt表示，t∈[1,4]。

在每组掩码分组中选用的掩码值满足如式(7)所示的条件。

其中，x是无掩码的8位数据，Mtr为第t个掩码分组中的第r个掩码值，是S盒的输入掩码，Mt(r+1)mod4是S盒的输出掩码，S代表S盒操作，Sm代表带掩码的S盒操作。

全部128位明文的掩码满足

其中，P、Q、H、N∈t，表示在上述掩码分组中挑选任意一组；p,q,j,n∈[1,4]，表示从每组中选择第几个值为掩码分组的第一个掩码值。上述的掩码分组中能够随机挑选一组作为共用S盒，假设在第t组中可选共用的S盒输入掩码为mt2，输出掩码为mt3。例如在M2中，选择“39”为输入掩码，则“c6”为输出掩码，表示为Sbox_M22_M23，第t组的共用S盒表示为Sbox_Mtr_Mt(r+1)mod4。S盒共用掩码方案原理如图1所示。

图1 S盒共用掩码方案原理

在每组掩码分组中，首先根据选择的输入输出掩码计算得到共用S盒，剩余的3组掩码值与所选择的输入输出掩码存在固定关系，即掩码值的高低位不是相同，就是互补。按照这个规律，利用S盒共用掩码方案可以有效地降低掩码 S盒的数量，具体过程如下。当32位的中间值异或一组掩码值时，能够通过判断该组掩码值的输入掩码和共用 S盒输入掩码高低位关系来选择地址；如果值相同，那么S盒的地址不变，否则，S盒的地址取反；同样能够通过判断该组掩码值的输出掩码和该组共用S盒的输出掩码的高低位关系来选择输出；如果值相同，那么S盒的输出不变，否则，S盒输出取反。因此，每组就能够利用同一个S盒(8位)来实现字节替代操作。

4 AES算法的实现

4.1 线性部分的掩码实现

4.1.1 线性操作的掩码实现

1) XOR掩码——密钥加操作

XOR（exclusive-OR）操作将轮密钥与输入数据进行异或操作，其结果进行字节替代操作，该中间结果和密钥有很强的关系，所以一定要对 XOR操作进行掩码。密钥加是线性操作，能够利用异或操作实现掩码，但必须注意和掩码值异或的顺序，一定要确保所有中间值都是经过掩码的，不能存在某个中间值没有进行掩码就直接进行某个变换，这样才能够保证XOR操作不泄露任何的中间结果。

2) SR掩码——行移位操作

SR（shift row）操作在字节替代变换之后，由式(7)可以看出，经过字节替代操作的中间值仍受掩码保护，所以不需要再添加新的掩码值。

3) MC掩码——列混合操作

SR之后进行MC（mix column）操作，与SR类似，该操作的中间值也是具有掩码的，因此不需要再添加新的掩码值。

4.1.2 掩码补偿

本文方案的掩码补偿发生在每轮加密结束时，通过异或操作去掉原掩码值，增加新掩码来实现掩码更新。为了得到正确的密文，最后一轮仅需去除现在的掩码值，不需要添加新掩码。进行字节替代操作之后，中间值是具有掩码的，根据式(7)～式(9)，把掩码值按照矩阵形式进行排列，其每轮的行变换关系如图2所示。

图2 掩码值每轮的行变换关系

对非最后一轮的输入掩码依次进行行变换（LT,line transformation）操作、SR掩码、MC掩码和添加新的掩码操作，而最后一轮仅需对输入掩码进行LT操作和SR操作。为了保证算法的安全性，在每轮 XOR操作结束时，需要进行掩码补偿操作，即先添加新掩码然后去掉之前的掩码，具体操作如图3所示。

图3 掩码补偿操作

4.2 AES字节替代模块的实现

AES算法中字节替代是唯一的非线性操作，为了满足掩码的基本原则，设计的式(7)能够满足对字节替代操作的掩码，在进行字节替代时要通过重新计获得新的S盒。在4个掩码值分组中，分别计算4个掩码分组中每组内的共用S盒，该组内共用S盒的选择有4种情况，能够随机挑选任意一个作为共用的掩码S盒，所以需要4个共用S盒。

S盒共用掩码方案在进行字节替代操作时，输入值为32位，32位的数据被分为4组，每一组为8位。进行字节替代操作时，根据轮操作中间值的掩码值，选择相应的共用S盒完成操作。在进行字节替代操作时，这4组数据是并行执行的。S盒共用掩码方案字节替代模块的原理如图4所示。首先32位明文被分为4组，每组8位，这4组数据分别与MP、MQ、MH和MN进行异或操作，然后进行字节替代操作，最后把这4组字节替代后的值组合成32位的数据。

4.3 AES密钥扩展模块的实现

AES的密钥扩展是把初始的128位密钥平均分为4组，进行密钥扩展操作，共产生44组密钥（包括初始密钥），每组32位，当分组的组数是4的倍数时，需要进行字节替代操作，这也是密钥扩展模块唯一的非线性操作，字节替代操作共需要4个S盒，其中，S盒与轮操作中的S盒相同，因此共用S盒方案也能够用于密钥扩展模块。对于密钥扩展操作而言，其线性部分和S盒都可按照轮操作的掩码方式进行掩码，从而提高安全性。在进行密钥扩展时，首先128位密钥与掩码值进行异或操作，然后分为4组进行密钥扩展，由于应用S盒共用的掩码方案，因此在进行字节替代操作时仅需要4个掩码S盒。由于密钥扩展产生的密钥添加了掩码，为了得到正确的密文，在进行密钥加操作之后要去掉密钥的掩码值，因为列混合操作之后的中间结果是带有掩码值的数据，所以并不会泄露真实的中间结果。

图4 S盒共用掩码方案的字节替代模块

4.4 流水线设计

为了提高算法的执行效率，对S盒共用掩码方案进行了流水线设计[17-19]。根据文献[19]可知，若交换算法的行移位模块与字节替代模块的操作顺序，不会对密文有影响，从而可实现流水线设计。由于S盒共用掩码方案字节替代用到了4个S盒，最终实现128位数据的字节替代操作需要4个周期，本文设计的流水线时空图如图5所示，其中“(1)”～ “(4)”表示要加密的4个32位数据。当128位明文输入时，按照顺序每组32位进行拆分。每组数据按照字节替代、MC、XOR与掩码补偿的顺序进行操作，再对其他32位数据依次进行同样的操作，直至执行完128位的数据。这样的方式能够确保每个周期所有的硬件模块都在工作，增加了硬件使用率，提高了S盒共用掩码方案的加密速度。

S盒共用掩码方案的流水线设计数据加密结构框架如图6所示，该框架主要包括18个模块，其中，拆分模块对数据进行拆分，选择模块对多组数据进行选择，重组模块对数据进行重组处理，缓存器主要对数据的传输进行缓冲和存储。

图5 流水线时空图

图6 流水线设计数据加密结构框架

4.5 AES的整体实现

本文设计的AES掩码方案如图7所示。该方案首先将明文与随机选择的4组掩码值进行异或，然后进行 XOR操作，这个结果即为中间轮的输入。对于非最后一轮的所有中间轮依次进行 SR、字节替代、MC、XOR与掩码补偿操作，最后一轮加密依次进行 SR、字节替代、XOR，并进行掩码补偿操作得到最后的密文并输出。图7中K0～K43表示的是44组密钥值，每组32位。

为提高算法的安全性，在数据进行加密时采用乱序的方式对4组数据进行字节替代、MC、XOR和掩码补偿等操作。因为增加了乱序执行这4组32 位数据的操作，所以在这128位数据完成上述操作后，要对其进行重新排序，排序之后的结果为下一轮的数据输入，该操作能够确保正确密文的输出。

图7 AES掩码实现

字节替代操作采用串行查找方式进行，每128位数据需要进行4次字节替代操作，通过比较RSM方案和S盒共用掩码方案可知，RSM 方案共占用16个掩码S盒，S盒共用掩码方案仅占用4个，为RSM方案的25%。但进行S盒操作时，128位数据采用串行查找的方式，依次处理32位数据，这样使字节替代操作的吞吐量变为原来的，适用于面积受限的应用。

为了增加算法的运算速度，S盒共用掩码方案利用与固定值掩码方案相同的空间存储方式，在进行加密之前，提前选好掩码值，根据选择的掩码值计算好与之对应的共用S盒，并把共用S盒存储在ROM 中。在进行加密时，根据设计方案选取随机掩码和与之对应的掩码S盒执行操作，这种方式能够降低占用的RAM空间。S盒共用掩码方案需要在ROM中存储的值如下。

1) 具有正交向量特征的掩码值Mt。

2) 根据设计规则选择的每组掩码值的偏移量p、q、h、n。

3) 根据选择的输入输出掩码计算得到的掩码S盒，即共用S盒，数目为4。

4) 根据输出掩码计算每轮的掩码补偿值。

通过上述的设计方案，能够直接从ROM中调用需要的值进行加密运算，RAM 只需要存储临时的变量，如XOR、SR等操作的中间值。因为计算共用S盒需要花费很多的时间，所以对整个算法的时间花费主要集中在初始阶段[9]，之后的操作当需要某些中间值时，直接从ROM中调用即可，通过这样的方式提高了算法的运算速度。与 RSM 方案相比，S盒共用掩码方案占用更少的面积，并且安全性也有所提高。

5 实验结果和比较

5.1 功能仿真

为了验证S盒共用掩码方案的功能正确性，对S盒共用掩码方案进行了Verilog HDL建模，通过Modelsim SE 10.0c仿真软件进行仿真。无掩码AES方案、RSM方案和S盒共用掩码方案的字节替代的仿真结果分别如图8～图10所示。

图8 无掩码AES方案字节替代操作

图9 RSM方案字节替代操作

图10 S盒共用掩码方案字节替代操作

在测试3种方案字节替代的功能时，RSM方案和 S盒共用掩码方案采用相同的测试数据。图 8～图10中data_in和data是需要进行字节替代操作的128位数据，data_out是进行字节替代之后的128位输出数据，m是掩码值，dm是去除掩码后的值，m1是共用S盒对应输入掩码的输出掩码。可以看出，图9和图10中的dm值与图8中的data_out值相同，从而证明了S盒共用掩码方案中字节替代的正确性。

基于S盒共用掩码方案的整个AES掩码方案仿真结果如图11所示，流水线设计的功能仿真结果如图12所示。图11中，cipher_key 是密钥值，plain_text是明文数据，m是掩码值，cipher_text 是加密得到的密文。从图12中能够看出，128位密文“cipher_text”需要4个周期输出，每个周期输出32位。从测试结果可以看出，根据输入的明文和密钥，能够输出正确的密文，可以验证本文所提方案的功能正确性。

图11 S盒共用掩码方案实现AES算法

图12 流水线设计的仿真

5.2 安全性分析

SCA是利用AES操作过程中的中间结果与密钥之间的相关性进行攻击的，因此证明中间结果的概率分布与密钥无关，即可证明算法的安全性。把128位的输入数据分为4个32位的数据进行处理，只用一个字节替代架构，依然能够保证AES算法自身的安全性。

引理 1若被掩码的中间值可表示为'u=ux，其中，u为计算得到的中间值，x是随机掩码。那么u'的概率分布与密钥是不相关的[20]。

文献[20]中给出了引理 1论证，因此根据该理论可以证明S盒共用掩码方案可以抵抗一阶SCA。定义评估的相关系数[21]为

利用 SAT(SAT-solver)求解[22]对 S盒共用掩码方案有 RSM 方案具有的安全性进行证明，即可以抵抗一阶与二阶零偏移量的CPA，有以下结果。

2) 若2个随机变量互补，那么它们的交互信息为MIA=1.817 6 B。对于2个互补的掩码，m是均匀分布的一对，例如但。所以主要的目标是清掉，1.817 6 B对交互信息来说仍是相当大的。

能够发现交互信息I[HW(x⊕m);x]是0.216 8 B。

根据以上引理和结果可证明，S盒共用掩码方案可以抵抗一阶和二阶SCA，有RSM具有的安全性。

因为 CPA是利用中间值与密钥间的联系对加密方案进行攻击的，所以通过证明中间值的概率分布不受密钥的影响，即不相关，就可以证明加密方案可抗 CPA。在文献[14]中给出了一种掩码方案能否抵御CPA的定理，如定理1所示。

定理 1若掩码方案存在n个中间值它们的概率分布都与密钥无关，而且的联合概率分布也不受密钥的任何影响，就可以证明该方案能抵御一阶和高阶CPA。

假设经过掩码的中间值'u=ux，其中，u是算法运算的中间值，x是随机掩码。那么'u的概率分布与密钥没有关系，因此可证明该算法能够抵御一阶CPA。同理，假设有n(n＞1)个中间值，且均服从均匀分布，并且被随机变量进行掩码，同样相互独立，并满足

此外，文献[14-15]指出，RSM方案的安全性存在以下2个漏洞。

1) RSM 方案的掩码值经过异或操作，得到的值的汉明质量存在特定的规律，即 HW(mjXORmj+1)=4，HW(m0XORm15)=8。

2) 该方案的S盒循环偏移量是一个常数，为1。

S盒共用掩码方案相邻掩码值经过异或操作后不存在1)的特征，并且S盒共用掩码方案不需要循环移位，因此也没有2)的缺陷。表1给出了4种方案的安全性对比。

综上所述，S盒共用掩码方案的所有中间值与密钥不相关，可以抵抗一阶和高阶的CPA；采用掩码值随机选取和字节替代顺序随机执行，使相邻掩码进行异或操作之后的汉明质量为随机值，因此可以抵御基于偏移量的CPA。

5.3 与其他方案的比较

在相同的实现方式下，对AES加密算法的无掩码AES方案、RSM方案[8]、vRSM方案[13]和S盒共用掩码方案法进行Verilog建模，并在FPGA上实现。所采用的FPGA芯片为择Cyclone III系列（EP3C120F78017），逻辑综合结果如表2所示。

表2中，括号内的百分比是相比于无掩码方案所占用的资源，“+”号代表增加的百分比，“-”号代表减少的百分比。从表2中能够看出，本文提出的 S盒共用掩码方案需要的掩码 S盒数目是RSM方案的（不包括密钥扩展模块），因此很大程度地减少了面积开销。S盒共用掩码方案需要3 184个总逻辑单元，总逻辑单元数为RSM方案的58%、vRSM方案的61%、无掩码AES方案的63%；其中，时序逻辑单元有2 766个，组合逻辑单元有1 838个，所需的存储位是84 545位，其大小为RSM方案、vRSM方案和无掩码方案的21%。本文所提方案在执行字节替代操作时采用串行方式，因此每轮字节替代操作需4个周期，是其他3种方案的4倍。

表1 安全性分析

表2 4种S盒实现方案比较

表3 流水线实现方案的对比

对无掩码AES方案、RSM方案及S盒共用掩码方案采用流水线的方式实现，得到的结果如表 3所示。从表3可知，S盒共用掩码方案使用了4 352个总逻辑单元，是RSM方案的39%；组合逻辑单元为1 986个，是RSM方案的31%；时序逻辑单元为4 220个，是RSM方案的40%；存储位为81 956位，是RSM方案的20%。结果显示，S盒共用掩码方案在占用资源的花费上有着特别大的优势。采用本文设计的流水线设计实现本文方案，4个128位明文加密需要91个周期；采用非流水线设计实现本文方案，一个128位明文加密需要79个周期。因此，对于4个128位明文加密来说，采用流水线设计和非流水线设计地加速比为

式(12)中S值大于1，说明本文设计的流水线方案能够提高AES加密算法的加密速度。

综上，相比于RSM方案，S盒共用掩码方案所需硬件资源大幅度减少。此外，在使用相同数目掩码值（16个）的情况下，RSM方案和vRSM方案的掩码值选取仅有16种可能。本文提出的S盒共用掩码方案在选取掩码值时可以随机选择 4组数据，因此可选择的掩码值共有24（即2×3×4）种可能，在选择每组中的第一个掩码值时又有 256（即4×4×4×4）种可能，因此本文提出的方案中掩码值选择一共有6 144（即24×256）种可能，相当于RSM方案和vRSM方案的384倍。掩码方案的安全性与掩码值的随机性成正比，可以看出，本文所提方案的安全性高于RSM方案和vRSM方案。

6 结束语

本文在文献[8]的基础上，提出了一种S盒共用的低熵掩码方案，并把这种方案应用到AES算法上。该方案的轮操作中加密的最小单元为32位，而不是128位，并利用流水线技术提高系统性能。实验结果表明，本文所提方案相对于RSM方案大幅度降低了面积复杂度，S盒的数量从16个降低到4个。从理论上证明本文所提方案比RSM方案有更高的安全性，可以抗一阶、高阶的SCA与基于偏移量的CPA攻击。