原梓清(1996-), 男, 硕士生, 主要研究领域为白盒密码的设计与安全性分析
陈杰(1979-), 女, 博士, 副教授, 主要研究领域为密码算法的设计与安全性分析
传统密码算法的安全性建立在黑盒攻击模型下. 在这种攻击模型下, 攻击者只能获取密码算法的输入输出, 而无法得知密码算法运行时的内部细节. 近年来白盒攻击模型的概念被提出. 在白盒攻击模型下, 攻击者既可以获取密码算法的输入输出, 也可以直接观测或更改密码算法运行时的内部数据. 为保证已有密码算法在白盒攻击环境下的安全性, 在不改变其功能的基础上通过白盒密码技术对其进行重新设计被称为已有密码算法的白盒实现. 研究白盒实现方案的设计与分析对于解决数字版权管理问题具有重要意义. 近年来, 出现了一类针对白盒实现方案的旁信道分析方法. 这类分析手段只需要知道很少白盒实现方案的内部细节, 却可以提取到密钥, 因此是一类对现有白盒实现方案具有实际威胁的分析手段. 对现有白盒实现方案进行此类分析对于确保方案安全性具有重要现实意义. 此类分析方法中的典型代表是基于差分功耗分析原理的差分计算分析. 基于差分计算分析, 对白-武白盒SM4方案进行了安全性分析. 基于对GF(2)上
The security of traditional cryptographic algorithms is based on the black-box attack model. In this attack model, the attacker can only obtain the input and output of the cryptographic algorithm, but not the internal details of the cryptographic algorithm. In recent years, the concept of white-box attack model has been proposed. In the white-box attack model, attackers can not only obtain the input and output of cryptographic algorithm, but also directly observe or change the internal data of cryptographic algorithm. In order to ensure the security of existing cryptographic algorithms under white-box attack environment, redesigning the existing cryptographic algorithms through white-box cryptography technology without changing their functions is called white-box implementation of existing cryptographic algorithms. It is of great significance to study the design and analysis of the white-box implementation scheme for solving the issue of digital rights management. In recent years, a kind of side channel analysis method for white-box implementation schemes has emerged. This kind of analysis method only needs to know a few internal details of white-box implementation schemes, then it can extract the key. Therefore, it is the analysis method with practical threat to the existing white-box implementation schemes. It is of great practical significance to analyze the existing white-box implementation schemes to ensure the security of the schemes. The typical representative of this kind of analysis method is the differential computation analysis (DCA) based on the principle of differential power analysis. This study analyzes the Bai-Wu white-box SM4 scheme based on DCA. Based on the research results of the statistical characteristics of
传统密码算法的安全性建立在运行环境可信的假设下. 在这种假设下, 攻击者只能获取密码算法的输入输出, 而无法得知密码算法运行时的内部细节, 我们称此时的攻击模型为黑盒攻击模型(black-box attack model). 随着信息技术的快速发展, 计算机、智能手机与互联网已被广泛应用于生产生活中, 视频、音乐、图片、软件等数字信息被广泛传播. 在这种情况下, 数字产品常常运行在不可信任终端上, 传统密码算法的运行环境已不再单纯可信, 其安全性受到了新的挑战. 例如, 用户在自己的计算机上用视频播放器播放加密过的视频. 若用户是会员, 则视频播放器使用正确的密钥对视频进行解密后播放. 这种情况下, 这个解密过程很可能是不安全的, 因为整个解密过程是在用户的计算机上进行的, 攻击者(甚至可能是用户本人)可以直接观测密码算法程序运行时的内部细节, 轻易获得密钥信息. 若攻击者将密钥信息泄露给非会员用户(无授权用户), 则那些非会员用户就有可能根据所得密钥信息对加密过的视频直接进行解密, 从而跳过了身份认证过程, 这显然是视频发布方不想看到的.
上文所述针对密码算法运行终端的攻击, 有如下显著特点.
(1) 密码算法运行环境不可信, 攻击者对密码算法程序的运行具有完全的控制力, 能够直接观测或更改程序运行时的内部数据.
(2) 攻击目标是密码算法的软件实现, 攻击目的是提取密钥.
我们称这种攻击模型为白盒攻击模型 (white-box attack model). 与传统黑盒攻击模型不同, 白盒攻击模型对于攻击者能力的限制很少. 在不可信任终端环境下, 白盒攻击是更高级的安全威胁. 能够抵抗白盒攻击的密码算法及其实现被称为白盒密码(white-box cryptography). 其中, 已有密码算法的白盒实现是指将已有的密码算法通过白盒密码技术进行设计, 使得在白盒攻击环境下, 不改变原算法的功能但原算法所希望保证的安全性不受破坏.
白盒攻击模型与白盒密码的概念由Chow等人于2002年首次提出[
对白盒实现方案的安全性分析, 目前主要有两种思路: 一种是在纯白盒环境下, 通过对算法内部细节的安全性分析找到漏洞, 并采用查找表组合、仿射等价算法等手段消除混淆编码, 对密钥相关的查找表进行分析并提取密钥. 这类分析方法要求攻击者洞悉白盒实现方案的内部细节, 实际应用场景中很难满足这样的条件. 这类分析方法的典型代表有: Billet等人提出的BGE攻击[
本文运用差分计算分析方法, 对白鲲鹏等人设计的SM4的白盒实现方案(后称白-武白盒SM4方案)进行了成功分析, 论证了该方案在面对差分计算分析时不能保证安全性. 此外, 基于我们对GF(2)上
本文第1节介绍了所需的预备知识, 包括SM4分组密码算法、白-武白盒SM4方案以及差分计算分析. 第2节描述了我们对GF(2)上
SM4 (原名SMS4)分组密码算法是国家商用密码管理局于2006年首次公开发布的. 2012年3月, SM4被列为国家密码行业标准. 2016年8月, SM4被列为国家标准(GB/T 32907-2016)[
SM4的分组长度与初始密钥长度均为128位. 与通常的分组密码算法一样, SM4包括密钥扩展算法与数据处理算法两大部分.
密钥扩展算法[
数据处理算法包括加密变换与解密变换. 设输入的明文为
其中,
解密变换与加密变换过程相同, 只是轮密钥使用顺序相反, 在此不再赘述.
白-武白盒SM4方案[
(1) 根据密钥扩展算法, 由128位的初始密钥生成32个32位的轮密钥
(2) 生成随机矩阵与随机向量.
首先, 生成32阶随机可逆矩阵
然后按照以下步骤生成16位随机向量
(a) 计算
(b) 记
(c) 将
(3) 用轮密钥, 随机矩阵与随机向量生成查找表.
第
以及以下4个查找表(遍历16位的输入值
其中,
(4) 输入编码如公式(12)所示:
(5) 加密:
若记
(a) 查
由
由
由
由
(b) 重组:
计算
(c) 查
根据
(d) 获取轮输出:
(e) 循环执行步骤(a)–(d) 32次, 得到未解码的加密结果.
(6) 输出解码如公式(14)所示:
以上加密过程未考虑反序变换.
性能方面: 白-武白盒SM4方案的执行速度较快, 但是内存占用较大(整个方案的查找表尺寸共计32.5 M). 安全性方面: 白-武白盒SM4方案能够抵抗多种已知的攻击方式(BGE攻击, MGH攻击, Mulder等人的攻击[
差分计算分析是在2016年由Bos等人首次提出的针对白盒实现方案的旁信道分析方法[
(1) 输入任意一条随机明文, 执行算法程序, 记录程序执行时访问的所有地址与数据, 此即获得了一条软件迹.
(2) 将软件迹可视化, 以此来了解算法程序对内存的使用情况, 通过辨别重复模式的个数, 判断程序实现了哪个密码学原语.
(3) 保持地址空间布局随机化(address space layout randomization, ASLR)关闭, 输入多条随机明文, 记录多条软件迹, 可以选择采用一些记录标准.
(4) 将记录到的所有软件迹序列化为0和1组成的串.
根据文献[
(1) 获取软件迹.
(2) 选取算法计算过程中的某个密钥相关的中间状态字节, 确定选择函数. 选择函数的输出为中间状态字节的某一位, 称为目标比特. 对每种情况的目标比特, 执行如下步骤(3)–(5).
(3) 根据目标比特是0还是1, 将软件迹分为两类.
(4) 分别求两类软件迹的均值迹.
(5) 求两条均值迹的差分迹.
(6) 比较各差分迹的峰值, 其中最大者对应的目标比特为最佳目标比特.
(7) 对每种情况的密钥字节猜测, 执行步骤(2)–(6), 比较各种密钥字节猜测下的最佳目标比特对应的差分迹峰值, 其中最大者对应的密钥字节猜测为最佳密钥字节猜测.
此处简单阐述差分计算分析的原理. 若白盒密码采用可逆矩阵作为密钥相关的查找表的输出编码, 且含有至少1行汉明重为1的行, 则会泄露至少1位的原始输出. 即, 若
其中,
若白盒密码采用可逆的仿射变换作为密钥相关的查找表的输出编码, 则相当于将矩阵乘法的结果再异或上一个常数. 如果矩阵满足之前提出的包含汉明重为1的行, 则编码后的输出的某一位将是该位对应的原始输出异或一个常数后的结果. 但异或至多只会交换分类后的两类软件迹, 即使交换发生也依然可以判别出正确的密钥字节猜测.
若白盒密码采用了可逆矩阵或可逆的仿射变换作为密钥相关的查找表的输出编码, 但是矩阵不含有汉明重为1的行, 则标准差分计算分析失效. 此时需要采用变体差分计算分析, 即将标准差分计算分析的步骤(2)中选择函数的输出(即目标比特)改为中间状态字节各位的某种线性组合的结果. 这样, 在密钥字节猜测正确的情况下, 至少有1种线性组合的结果与软件迹中某样点的值一致, 从而保证最后可以判别出正确的密钥字节猜测. 但这也导致目标比特由8种情况增加到255种情况, 大大延长了分析时间. 事实上, 若编码所用矩阵足够均匀, 则很多情况下标准差分计算分析失效, 下节将就此问题进行研究.
从第1.3节可以看出, 标准差分计算分析能否成功, 与用于编码的随机可逆矩阵各行的汉明重有密切关系. 本节围绕白盒实现方案编码时最常用的一种随机可逆矩阵——定义在GF(2)的
记事件
其中,
其中,
考虑
又
类似地, 可得
根据公式(21)可求出
根据公式(17), 公式(22), 公式(23), 对定义在GF(2)上的8阶, 16阶和32阶均匀随机可逆矩阵的某些概率进行计算, 所得理论结果如
The theorextical results of 8-order, 16-order and 32-order matrix
8阶, 16阶和32阶矩阵的理论结果
矩阵阶数 | 至少有一行汉明重为1的概率
|
至少有一行汉明重为2的概率
|
至少有一行汉明重为3的概率
|
8 | 0.2278958 | 0.6112003 | 0.8672067 |
16 | 0.0038996 | 0.0289017 | 0.1283123 |
32 | 0.0000001 | 0.0000037 | 0.0000370 |
根据
根据文献[
对白-武白盒SM4方案进行差分计算分析的整个实验过程如下.
(1) 编程实现白-武白盒SM4方案.
我们用Java程序语言编程实现白-武白盒SM4方案作为后续实验的测试对象, 程序运行环境如下: 操作系统为Windows 10家庭中文版(64位), JDK版本为1.8.0_221, 开发平台为Eclipse, 处理器为Intel(R) Core(TM) i5-8300H CPU @ 2.30 GHz, 内存8 GB.
该程序的实现步骤如下.
(a) 依据文献[
(b) 生成随机向量与均匀随机可逆矩阵. 其中, 在生成均匀随机可逆矩阵时, 先生成均匀随机矩阵, 再判断所得矩阵是否可逆, 若不可逆则重新生成, 直到所得矩阵可逆为止.
(c) 依据文献[
(d) 随机生成若干条明文.
(e) 依据文献[
(2) 获取软件迹.
如何获取软件迹不在本文的讨论范围内, 故我们假定已经通过某种方式得到了软件迹. 为支持后续实验进行, 可以通过如下方式模拟所需软件迹.
在(1)所得程序中插入辅助代码, 将加密时产生的部分中间结果以及相关的随机明密文对分别存储在两个二进制文件中, 在之后的分析中将加密中间结果对应的二进制文件的内容序列化即可模拟所需的软件迹. 又由文献[
依据上述方法, 我们随机生成200条明文并加密, 得到一个存储着200条中间结果记录的二进制文件以及一个存储着200组明密文对的二进制文件.
(3) 编程实现差分计算分析算法.
我们用C++程序语言编程实现差分计算分析算法, 用于对(2)所得的两个二进制文件进行分析, 程序运行环境如下: 操作系统为Windows 10家庭中文版(64位), 开发平台为Visual Studio 2015, 处理器为Intel(R) Core(TM) i5-8300H CPU @ 2.30 GHz, 内存8 GB.
该程序的实现步骤如下.
(a) 读取(2)所得的两个二进制文件.
(b) 将存储着200条中间结果记录的二进制文件中的内容序列化, 转化为200条软件迹.
(c) 计算目标比特.
由第1.2节公式(11)得公式(24):
令
若进行标准差分计算分析, 则目标比特是
依据上述方法, 我们分别计算了200条随机明文对应的所有密钥字节猜测下的所有情况的目标比特.
(d) 对于每种密钥字节猜测下的每种情况的目标比特, 执行步骤(e)–(h).
(e) 根据目标比特为0还是1, 将步骤(b)所得软件迹分为两类.
(f) 分别求步骤(e)所得的两类软件迹的均值迹.
(g) 求步骤(f)所得的两条均值迹的差分迹.
(h) 求步骤(g)所得的差分迹的峰值.
(i) 求每种密钥字节猜测下的每种情况的差分迹峰值的最大值, 该最大值所对应的密钥字节猜测即为最佳密钥字节猜测.
(4) 判断分析是否成功.
根据(3)中程序输出的最佳密钥字节猜测, 判断其是否与(1)中给定初始密钥所对应的第一轮轮密钥的最高有效字节相同, 若相同则分析成功, 否则分析失败.
根据上述实验过程, 对白-武白盒SM4方案进行标准差分计算分析.
给定初始密钥为: 0x12345678, 0xabababab, 0xcdcdcdcd, 0xffffffff. 此时第一轮轮密钥为: 0xf0b96271. 最高有效字节为0xf0. 对10种不同编码的方案分别采用200条中间结果记录及其对应的200条随机明文进行标准差分计算分析, 其中只有5种方案被成功分析. 假设恢复每个密钥字节的成功率均为0.5, 则恢复整个初始密钥的总成功率仅为0.000 015. 若采用更少的样本进行分析, 成功率只会更低. 显然, 标准差分计算分析对编码所用矩阵均匀的白-武白盒SM4方案效果不佳, 必须采用变体差分计算分析.
根据上述实验过程, 对白-武白盒SM4方案进行变体差分计算分析.
(1) 固定编码所用随机矩阵和随机向量. 对10种不同初始密钥的方案采用数量不等的中间结果记录及随机明文进行变体差分计算分析, 并统计采用各种数量的样本进行分析时的正确率, 结果如
the Accuracy of Variant Differential Computation Analysis
变体差分计算分析的正确率
样本数目 | 10 | 20 | 23 | 30 | 100 | 200 |
分析正确率 (%) | 0 | 0 | 50 | 100 | 100 | 100 |
(2) 固定初始密钥为: 0x12345678, 0xabababab, 0xcdcdcdcd, 0xffffffff. 此时第一轮轮密钥为: 0xf0b96271. 最高有效字节为0xf0. 对10种不同编码的方案分别采用200条中间结果记录及其对应的200条随机明文进行变体差分计算分析, 均能得出正确的结果(f0). 统计分析各种编码的方案时所用的时间, 结果如
the Time Required for Variant Differential Computation Analysis(ms)
变体差分计算分析所需时间(ms)
所用编码 | 编码1 | 编码2 | 编码3 | 编码4 | 编码5 | 编码6 | 编码7 | 编码8 | 编码9 | 编码10 |
所需时间 | 30667 | 30676 | 30820 | 30676 | 30435 | 31002 | 30883 | 30502 | 30567 | 30930 |
可见, 只要采用足量的软件迹进行分析, 变体差分计算分析是一定可以成功恢复密钥的, 白-武白盒SM4方案不能抵抗变体差分计算分析. 由
Difference trace of best target bit for correct key byte guess(f0)
密钥字节猜测正确(f0)时最佳目标比特对应的差分迹
Difference trace of best target bit for wrong key byte guess(c8)
密钥字节猜测错误(c8)时最佳目标比特对应的差分迹
文献[
考虑公式(27).
定理
证明: 因为
其中,
当
当
当
(1) 若
(2) 若
对于(1),
综上, 定理1得证, 证毕.
我们可以计算GF(2)上的32×8的均匀随机矩阵某一行汉明重为1的概率为8×0.5×0.57=0.03125, 某一行汉明重不为1的概率为1–0.03125=0.96875, 所有行汉明重不为1的概率为0.9687532=0.36205529, 至少有一行汉明重为1的概率为1–0.36205529≈0.6379447. 同理, 至少有一行汉明重为2的概率为0.9754396, 至少有一行汉明重为3的概率为0.9996291, 至少有一行汉明重为4的概率为0.999 963 6. 根据定理1, 假若
我们用Java程序语言编写程序, 先生成32阶均匀随机矩阵, 再判断所得矩阵是否可逆, 若不可逆则重新生成, 直到所得矩阵可逆为止, 由此得到GF(2)上的32阶均匀随机可逆矩阵
当样本容量为10000000时, 至少有一行汉明重为1的矩阵的出现频率为0.6378210, 至少有一行汉明重为2的矩阵的出现频率为0.9754459, 至少有一行汉明重为3的矩阵的出现频率为0.9996453, 至少有一行汉明重为4的矩阵的出现频率为0.999 964 0. 可见,
第3节中, 变体差分计算分析的目标比特为
其中,
由第3节
综合上述两条改进思路, 我们得出IDCA的步骤如下.
(1) 获取软件迹.
(2) 选取算法计算过程中的某个密钥相关的中间状态字节, 确定选择函数. 选择函数的输出(即目标比特)为中间状态字节各位的某种线性组合结果, 且根据需要只筛选部分情况的线性组合进行分析.
(3) 对步骤(2)筛选出的每种情况, 执行如下步骤(4)–(8).
(4) 对每种情况的密钥字节猜测, 执行步骤(5)–(8).
(5) 根据目标比特是0还是1, 将软件迹分为两类.
(6) 分别求两类软件迹的均值迹.
(7) 求两条均值迹的差分迹.
(8) 判断差分迹峰值是否大于判决门限, 若大于判决门限则此时的密钥字节猜测就是最佳密钥字节猜测, 分析结束.
与第3节中的实验过程类似地, 我们对白-武白盒SM4方案进行IDCA. 在分析中我们只遍历
(1) 固定编码所用随机矩阵和随机向量. 对10种不同初始密钥的方案采用数量不等的中间结果记录及随机明文进行IDCA, 并统计采用各种数量的样本进行分析时的正确率, 结果如
the Accuracy of Improved Differential Computation Analysis
IDCA的正确率
样本数目 | 10 | 20 | 25 | 30 | 100 | 200 |
分析正确率 (%) | 0 | 0 | 60 | 100 | 100 | 100 |
(2) 固定初始密钥为: 0x12345678, 0xabababab, 0xcdcdcdcd, 0xffffffff. 此时第一轮轮密钥为: 0xf0b96271. 最高有效字节为0xf0. 对10种不同编码的方案分别采用200条中间结果记录及其对应的200条随机明文进行IDCA, 均能得出正确的结果(f0), 与变体差分计算分析所用时间的对比如
Comparison of the Time Required for IDCA and Variant Differential Computation Analysis(ms)
IDCA与变体差分计算分析所需时间的对比(ms)
分析方法 | 编码1 | 编码2 | 编码3 | 编码4 | 编码5 | 编码6 | 编码7 | 编码8 | 编码9 | 编码10 |
IDCA | 2 046 | 301 | 1 095 | 532 | 132 | 140 | 1 950 | 364 | 805 | 161 |
变体差分计算分析 | 30667 | 30676 | 30820 | 30676 | 30435 | 31002 | 30883 | 30502 | 30567 | 30930 |
由
差分计算分析只需要知道少量白盒实现方案的内部细节, 因此是一种对现有白盒实现方案具有实际威胁的攻击手段. 检验现有白盒实现方案抗差分计算分析的能力对于确保方案在实际应用场景下的安全性具有重要意义. 本文基于我们对GF(2)上的
Shi Y, Wei WJ, He ZJ. A lightweight white-box symmetric encryption algorithm against node capture for WSNs. Sensors, 2015, 15(5): 11928–11952. [doi: 10.3390/s150511928]
Bai KP, Wu CK. A secure white-box SM4 implementation. Security and Communication Networks, 2016, 9(10): 996–1006. [doi: 10.1002/sec.1394]
Bai KP, Wu CK, Zhang ZF. Protect white-box AES to resist table composition attacks. IET Information Security, 2018, 12(4): 305–313. [doi: 10.1049/iet-ifs.2017.0046]
林婷婷, 来学嘉. 白盒密码研究. 密码学报, 2015, 2(3): 258–267. [doi: 10.13868/j.cnki.jcr.000077]
Lin TT, Lai XJ. Research on White-box cryptography. Journal of Cryptologic Research, 2015, 2(3): 258–267 (in Chinese with English abstract). [doi: 10.13868/j.cnki.jcr.000077]
Bock EA, Bos JW, Brzuska C, Hubain C, Michiels W, Mune C, Gonzalez ES, Teuwen P, Treff A. White-box cryptography: Don't forget about grey-box attacks. Journal of Cryptology, 2019, 32(4): 1095–1143. [doi: 10.1007/s00145-019-09315-1]
Banik S, Bogdanov A, Isobe T, Jepsen M. Analysis of software countermeasures for whitebox encryption. IACR Transactions on Symmetric Cryptology, 2017, 3(8): 307–328. [doi: 10.13154/tosc.v2017.i1.307-328]
Lee S, Kim M. Improvement on a masked White-Box cryptographic implementation. IEEE Access, 2020, 8: 90992–91004. [doi: 10.1109/access.2020.2993651]
潘文伦, 秦体红, 贾音, 张立廷. 对两个SM4白盒方案的分析. 密码学报, 2018, 5(6): 651–671. [doi: 10.13868/j.cnki.jcr.000274]
Pan WL, Qin TH, Jia Y, Zhang LT. Cryptanalysis of two white-box SM4 implementations. Journal of Cryptologic Research, 2018, 5(6): 651–671 (in Chinese with English abstract). [doi: 10.13868/j.cnki.jcr.000274]