一个能抵抗侧信道攻击的SM4白盒实现
本文档主要介绍新设计的SM4白盒实现,包括设计原理、代码实现的详细流程、安全性分析以及与现有SM4白盒实现的比较。该SM4白盒实现在满足一定安全性(抵抗侧信道攻击)的前提下,具有较低的存储复杂度和较高的加密速度。
1 设计原理
根据前期调研,我们选择了非线性的字节置换编码来保护白盒实现内部查找表的输入和输出,并且在SM4的S盒变换和线性变换之后添加混淆矩阵以混淆SM4的线性变换,并使T表的输出更均匀。由于选择非线性置换,因此查找表输出的异或操作需要使用XOR表,单个XOR表输入16bit、输出8bit,需存储空间64KB,为节约白盒实现查找表的存储空间,我们采用XOR表的复用策略以降低存储。下面我们以加密函数为例解释设计原理(解密函数类似)。
1.1 T表与I型XOR表
SM4标准算法轮函数的核心步骤包括了32bit的非线性变换(4个并列的8bit S盒)以及32bit的循环移位变换。白盒实现的核心就是将这两个函数复合成查找表称为T表,如下图所示:
图1 SM4白盒实现的T表示意图
其中,我们将32bit的线性移位变换L拆分成4部分,分别用32×8的矩阵表示。LB表示我们设置的混淆矩阵。在生成T表之前需要将128bit的用户密钥通过SM4的密钥扩展算法生成各轮所需的32bit轮密钥,因此T表是依赖密钥的,所以32轮轮函数需要128张T表,单一T表(8bit输入、32bit输出)需存储空间1KB,全部T表需128KB。图1中的d-NB和e-NB分别表示查找表的输入编码和输出编码(后文都这样表示),其中d-NB不重复利用。 由于我们将线性变换L表示成矩阵形式并进行了拆分,所以T表只实现了一部分矩阵运算,后续还需要进行异或运算,因此需要XOR表。XOR表的输入长度是2字节,输出是1字节,每个输入输出字节都需要编码,因此,XOR表之间是否相同是由这三个非线性编码决定的。一个XOR表的存储大小是一个T表的64倍,因此为了节约空间,我们需要考虑XOR表的重复利用。XOR表不包含关键信息(如密钥),而且其输入输出都有非线性编码保护(编码也难以被恢复),因此重复利用异或表并不会导致关键信息的泄露从而降低安全性。重复利用XOR表,在于编码的重复利用,例如T表的输出编码与其对应的XOR表的输入编码每轮都固定,那么每轮T表对应的XOR表就可以重复利用。图2展示了一类XOR表:
图2 I型XOR表
I型XOR表由2层异或表构成,第一层的8个XOR表将4个T表的输出异或为2个32bit字,再经过第二层的4个XOR表得到1个32bit字,从而实现了SM4的L变换。观察图1和图2不难发现编码的颜色和标注都是对应 的,对应位置的编码只需要生成一次即可,不需要每轮都生成新的编码,字母A、B、C等表示编码所在位置也表示编码的型号,例如B代表的编码位于T表的输出端和I型异或表第一层的输入,这对编码相互抵消来保证加密函数的功能性。既然可以重复利用编码,那为什么同一类型的编码不重复利用?比如B和C类型编码只生成一次,这样第一层XOR表只需要1个,还能再压缩空间。回答这个问题,需要考虑白盒实现的安全性,由于我们采用混淆矩阵是精心设计的,这样T表输出的每个字节都会与S盒对应且输出的每个字节都是均匀的(遍历输入会得到256种取值,对基于Walsh变换的谱分析[3]和DCA[4]等侧信道攻击有较高防御能力),若只采用一个编码,攻击者可以利用频率分析攻击每一轮的T表。而且XOR表的输入端的两个编码不能相同,若相同的话攻击者容易得到关于0的映射信息。在这种设计原则下,I型XOR表需存储空间为12×64KB=768KB。
1.2 混淆矩阵逆变换查找表与II型XOR查找表
我们在T表中添加了混淆矩阵LB,使T表的输出更均匀且提高了白盒实现抵御DCA和谱分析的能力。为了保证算法的标准性,我们需要将LB矩阵抵消掉。由于是矩阵运算,因此我们按照和构造T表一样的方式,将LB的逆矩阵进行拆分,并通过XOR表实现完整的矩阵乘法运算。如下图所示:
图3 混淆矩阵逆变换查找表
在这里,我们需要强调,混淆矩阵是秘密生成的,每一轮的混淆矩阵可以相同也可以不同,这并不会对安全性产生影响,我们的方案选择固定的LB矩阵,因此32轮的查找表大小为4KB,若每轮选择新鲜的LB矩阵,那么查找表大小为128KB。图4是II型XOR表:
图4 II型XOR表
II型XOR表的构造原则与I型相同,需要注意的是,无论是否重复利用混淆矩阵LB都不会影响II型XOR表的生成与存储,因为XOR表只与编码有关。I型XOR与II型XOR表在输出位置都保持了编码的新鲜性,使S盒对应位置的输出都是均匀的,保障了各个位置抵抗DCA和谱分析的能力。II型XOR表需存储空间12×64KB=768KB。
1.3 混淆矩阵的选择
混淆矩阵LB是32×32的矩阵,表示为:
其中表示8×8的矩阵,为使S盒对应位置的输出都是均匀的,要求LB除了可逆还需满足三个条件: (1)满足T表输出的均匀性:
T0:
T1:
T2:
T3:
需要保证上述16个方程对应的16个8×8的矩阵都是满秩的,其中H表示SM4线性变换矩阵L的分块矩阵; (2)I型XOR表第一层输出的均匀性: T0+T1:
T2+T3:
需要保证上述8个8*8的矩阵都是满秩的; (3)I型XOR表第二层输出的均匀性: T0+T1+T2+T3:
需要保证上述4个8×8的矩阵都是满秩的。这样精心设计挑选的混淆矩阵能为T表提供抵御侧信道攻击更高的安全性。