静园5号院科研讲座 | 西北大学Hai Zhou教授谈硬件IP加密困境和解决方案
关键词：硬件加密
编者按
2019年7月31日，西北大学 Hai Zhou 教授来访北京大学前沿计算研究中心，并在静园五院作了题为“Logic Encryption for Hardware IP Protection: Trilemma and Solutions”的学术报告。报告由高能效计算与应用中心助理主任梁云副教授主持，听众主要来自北京大学信息科学技术学院的师生。
Hai Zhou教授报告现场
本次报告中，Hai Zhou 教授以硬件 IP 加密保护 （Hardware IP Protection）为主题，介绍了传统硬件 IP 加密方法存在的问题、破解途径和相关反制方法。Zhou 教授还分析了目前硬件 IP 加密发展遇到的困境，并从理论角度分析了一个好的硬件 IP 保护方法应该具有的性质，提出了一个可行并安全的方法。
硬件 IP 加密 (Logic Encryption) 的必要性和问题定义
随着全球芯片市场的蓬勃发展，芯片造假和 IP 偷盗问题也愈发严重。芯片造假问题主要体现存在 Fab 厂商过度生产、芯片逆向工程、IP 侵权和植入恶意木马等方面，不仅影响芯片厂商的利益，还将芯片使用者暴露于危险之中。硬件 IP 加密技术旨在反制这些威胁。不失一般性地，我们讨论时假定电路仅有一个输出；形式化地，对于给定的组合电路 f(x): Bn → B，设计一个加密电路 g(x, k): Bn+m → B 使得如下条件成立：
存在 k* 使得 g(x, k*) ≡ f(x)；
对给定的 g(x, k) 及对 f(x) 的黑箱访问，找到 f(x) 是困难的。
传统加密方法和基于 SAT 的攻击方式
传统加密方式（2004-2015）通过在逻辑电路中选择一些信号插入密钥门（“key-gate”, 通常为 XOR 或 XNOR）进行加密；使用时在提供正确 key 的情况下电路可以给出正确的输出。早期方法随机选取密钥门会遭受 ATPG 攻击，通常采取小心选取的信号插入密钥门进行加密。然而，截至2015年的所有方法都会受到基于 SAT 求解器的攻击 [Subramanyan et al. 15]：
1. 令 | C(k) 和 C(k1) 是两个约束集 | |
2. 若 | ||
a. | ||
b. | ||
c. | 重复步骤 2 | |
3. 所 | 求的 k* 即为 SAT(C(k)) | |
这里 | 为 DIP (Differentiating Input Pattern)。 |
SAT 攻击的防御方式和存在问题
SARLock [Yasin et al. 16] 和 Anti-SAT [Xie and Srinistava 16] 均可以反制 SAT 攻击，然而这两种方式都存在两个较为严重的问题：
错误率低：对每个错误的 key 都只有单个错误输入；
a. 依然可以作为假冒芯片售卖（「近似攻击」）
b. 使得整个电路在错误 key 情况下成为一个 trojan
c. 容易通过外加电路修正错误结果（「绕过攻击」）
结构弱点：可以通过逆向工程的方式去掉外部加密用结构。作者均提出了采用重综合（re-synthesis）的方式反制这种攻击。
SARLock 的结构
硬件 IP 加密方法的理论设计空间
Zhou 教授提出，可以使用香农分解（Shannon decomposition）所得到的错误矩阵刻画加密函数 g(x, k) 和 f(x) 的差异，从而衡量某一加密方法的有效性。定义给定方法的加密数为对于所有错误 key 最小的错误输入数量。定义攻击复杂度为找出 f 所需的查询数量。通过查询一次 f，攻击者可以排除所有在错误矩阵中有 1 的列。利用这一性质，有效地攻击一个加密方法转变为一个集合覆盖问题，最小集合覆盖给出攻击复杂度的下界。数学上存在一些该界的上界的结论 [Alon 90] [Chva'tal and McDiarmid 92]，而确切的界仍是一个开放问题。
错误矩阵
如下定理刻画了攻击复杂度和错误数之间的关系：
定理1：对于任意给定加密方式 g(x, k)，如果错误数是 M，那么 m2n/M 次随机尝试将以至少 1−(2/e)m 的概率解密。
定理2：对于给定的 f(x) 和正整数 M，存在加密电路 g(x, k) 有 M 的错误数和至少 2n/M 的攻击复杂度。
通过定理可以很容易看出，错误数较大的传统加密方式有极低的攻击复杂度（错误数很高，受 SAT 攻击），严重偏离最佳的平衡点。
合理的平衡点和理想设计
通过前述集合覆盖求解方式可以求得最优 trade-off，然而这种最优并不现实：所构造的 Shannon Matrix 对应指数级别的具体电路，很难实现。Zhou 教授团队提出线性代价的、trade-off 可调整的加密方式设计如下图。
通过调整 h(v) 可以调整错误数和攻击复杂度之间的 trade-off
根据定理2，对于错误数和攻击复杂度均采用 2n-2 所得到的加密方案如下。
折中的加密方案
Zhou 教授还指出，除了加密数和攻击复杂度的平衡需要调整，设计一个合理的逻辑电路加密方式还需要考虑随机性以保持健壮。Zhou 教授还简略介绍了通过增加 SAT 问题求解难度，使用单向密码学函数的方式抵御 SAT 攻击，由于篇幅限制此处不再展开。
混淆的重要性和对效率的影响
和传统的插入密钥门的方式不同，从 SARLock 到这里提出的理论较优的加密方法均包含明显的结构特征，受结构分析（逆向工程）攻击的影响，因此要成为实用有效的加密方法必须加入混淆。软件工程界已使用混淆技术多年，但直到近年来得到计算理论界关注，一度缺乏完备的理论刻画混淆行为。IO (Indistinguishability Obfuscation) 从理论角度定义了程序混淆：非形式化地，我们称一个混淆方法是 IO，如果对于程序 P 其保持 P 的功能不变，但变换的结果 P' 不暴露关于 P 的任何信息。IO 是一个困难的问题，[Garg et al. 13] 的工作提出了一个可能的 IO 实现。[Apon et al. 14] 则指出可以被混淆的程序的复杂性存在很严格的限制。
Zhou 教授提出ILO (Indistinguishability Logic Obfuscation) 的概念，将原本功能不变的要求放松为在允许 key 输入的情况下输出不变，并指出这种情况远比 IO 简单：通用电路（Universal Circuit, UC）即是满足要求的 ILO。[Valiant 76]（nlog n 对尺寸为 n 的电路）和 [Cook, Hoover 85]（c3d/log c 对尺寸为 c，深度为 d 的电路）给出了关于 UC 的效率的界 ，而 key 输入的位数和 UC 的尺寸呈线性关系。可以看出利用 UC 进行混淆效率上是不优的。
结构安全性、锁定健壮性、加密效率之间的妥协
文字 | 许朋程
致谢 | 梁云老师、孔雨晴老师
往 期 报 告
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”看报告概要等信息