公钥密码边道攻防研究

1994 年，Shor 提出了大合数分解的快速方法，使破解RSA 成为可能，尽管只是几率性的，但也引起很大震撼。

然而，边信道攻击技术的出现，给密码算法、尤其是密码设备和密码芯片带来了更大的威胁，其严重程度远大于经典的数学分析方法。

1、简述

1999 年，P. Korcher 继1996 年发表有关计时攻击文章后，再次发表“Difference PowerAnalysis”（DPA）的文章，使边信道攻击走上了系统研究和发展轨道。

所谓边信道攻击，指利用信息设备在运行过程中消耗的时间、功率，产生的电磁辐射、故障、声音、温度等“边信息”引起的信息泄漏而发起的攻击。分为计时攻击、功耗分析攻击、电磁攻击、故障攻击等。

图.1 是P.Korcher 等人针对DES 算法S-盒的 DPA 攻击结果，其中有尖峰的曲线代表正确的猜测结果。

自 此以后，国外对分组密码的边信道攻击已有许多成功的范例，国内也有相关研究。国外有关公钥密码的边信道攻击、尤其是功耗分析攻击和防御也取得了不少研究成 果。国内此方面研究也越来越多。但多以某些理论假设为前提，而且以仿真研究为主。真实环境下研究得很少，更鲜见完整破译的报道。在各种边信道攻防研究中， 功耗分析攻击和防御因其攻击的高效性和相对低廉的攻击成本而成为主要研究热点。

2、功耗分析攻击技术关键

功耗分析攻击又分为简单功耗分析（SPA）攻击和差分功耗分析（DPA）攻击。前者不需要统计差分运算，后者的技术关键在于区分函数的设计。好的区分函数可以大幅度提高攻击效率。国外利用这类技术已破译了很多分组密码，因此，我们的研究点集中在公钥密码的功耗分析攻防上。由于影响公钥密码功率消耗的因素很多、也很复杂，以至于Messseges 等人作出“真实硬件环境下利用SPA 不可能提取RSA 密钥”的论断。

实际上，RSA 密钥的SPA 攻击虽然很难，但并非不可能。

3、我们的工作

为了摆脱国外对相关研究工具的出口限制，我们首先自主开发了功耗信息自动采集平台，提高海量数据采集效率。在此基础上，分别对FPGA 或ARM 上以多种方式实现的RSA 算法（严格说来是幂剩余算法，因为参数选择没有遵循RSA 规范，但是对攻击结果不产生本质影响）和部分ECC 算法实施多种功耗分析攻击，均获成功。

3.1 SPA攻击

真实硬件环境下的功耗分析攻击与仿真环境有很大不同：许多理论假设条件在真实环境下并不成立；同样的信号消耗的功率并不恒定；外界干扰多而复杂……。仅对功耗曲线应用数学分析的手段很难实际提取出公钥算法密钥。

图2 – 图6 是针对 FPGA（现场可编程门阵列）芯片上32 位RSA 右-左方式蒙哥马利实现算法的SPA攻击过程。攻击没有采用经典的数学模型，而是应用了SPA  攻击的信号处理模型，并综合运用了统计分析、去噪、通信、信号处理等多种方法和技术。

图5 和图6 是SPA 攻击结果。32 位RSA 右-左方式蒙哥马利实现算法含有1 轮预计算和32 轮迭代，共33 个周期，在图5 和图6 中清晰可见。信号上升的的周期对应指数“1”，下降的周期对应指数“0”。其中第1 个周期是预计算。从第2 个周期开始，曲线与从右向左扫描的二进制指数一一对应。

对1024 位RSA 和2048 位RSA 实施SPA 攻击同样获得成功，因截图过大，不便示例。

此外，对FPGA 上实现的ECC 算法、嵌入式处理器ARM9 上实现的ECC 算法实施SPA 攻击，均获得正确结果。

3.2 SDPA攻击

借鉴模板攻击和差分攻击思想，结合拟合预测方法，提出了简单差分功耗分析攻击SDPA 技术（图7）。根据功耗规律设定阈值，当差分小于阈值时，拟合预测成功，否则失败。这种方法可逐位提取出RSA 密钥，并使某些防御算法（如伪操作插入）实效。图7 显示前7 个周期猜测成功，其余失败。

3.3 DPA 攻击

在对功耗曲线进行大量研究后，大体掌握了FPGA 芯片功耗信息泄露规律，应用信息论思想，设计了合适的区分函数，对RSA 实施DPA 攻击，准确地提取出密钥。理论上证明了DPA 对功耗最大化、伪随机插入、静态掩码等多种加入了抗攻击措施的RSA 算法均可破解，实验亦验证了理论分析结果。

3.4 功耗分析攻击防御

针对功耗分析攻击提出了多种防御算法：RSA 的等功耗编码实现算法、RSA的伪逆操作算法、ECC的功耗插入算法等。三种算法均可防范SPA 和SDPA 攻击，RSA 的等功耗编码和伪逆操作算法还可防范DPA 攻击。上述性能已通过实验验证。伪逆操作算法的缺点是加大了电路功耗。ECC 功耗插入算法将国外提出的伪操作算法效率效率损失降低了大约60%。RSA 的等功耗编码实现算法重编码的分组长度满足一定条件（约等于模数的百分之一）时，抗攻击算法效率甚至高于一般RSA 实现算法。达到了综合优化的目标。

此外，对密码算法的频谱攻击研究正在进行中。

4 研究感悟

• 密码分析离不开数学，但密码分析的数学方法不是唯一的方法。
• 边信息泄露源于电路本身的特性和信号性质，因此边信道攻击采用信号和信息处理及通信等电子信息学科分析手段无疑更有效。
• 密码算法的实现安全不应再被忽视。密码算法设计标准和评估规范需要完善。
• 芯片是信息主要载体，一旦出现信息安全问题，后果十分严重，政府应未雨绸缪，重视和加强安全芯片的研发、推进其产业化进程。
  

【via@程运 《中国密码学会通讯》2010年3期】