基于FPGA加速云的Hitag2攻击算法

肖 文， 唐 宁， 刘敬术

(桂林电子科技大学 信息与通信学院，广西 桂林 541004)

Hitag2算法是恩智浦半导体(NXP)开发的一种应用在汽车低频电子标签钥匙端的加密算法，使用在NXP向汽车防盗系统供应商提供的pcf7936、pcf7941、pcf7952等防盗芯片上，广泛应用在标志、雪铁龙、本田、尼桑等汽车防盗系统[1-3]。

Hitag2算法属于流密码[4-6]中的一种，具有算法实现简单、加解密速度快、便于硬件实现等优点，在早期确实具备相当的安全性，但随着硬件技术的发展变得越来越脆弱。

鉴于此，利用华为FPGA加速云F1实例，借助云端主机内存大、FPGA板卡逻辑资源多的优势，通过建立32 GB的彩虹表[7]，提出一种FPGA云端攻击算法。该算法可在平均不到10 s时间内获得Hitag2初始内部状态，进而获得Hitag2的密钥。测试结果表明，Hitag2加密算法的安全性已不再可靠。

1 Hitag2算法的弱点分析

对Hitag2算法的攻击需要利用它的3个弱点：

1)利用Hitag2加密算法应用到芯片上协议存在弱点。Hitag2算法在应用到具体芯片时，具有命令短，命令可以重复，可固定随机数的特点，使得采集到一组随机数和签名的情况下，可以得到至少72 bit的密钥流。使用一个低频(125 kHz)采集器，在用钥匙启动汽车时，将采集器放在汽车的点火线圈旁，在扭动钥匙点火过程中，可采集到一组32 bit加密随机数{nR}和32 bit的签名。用一个Pcf7991低频读卡器将采集的64 bit数据发至汽车钥匙芯片，即可得到一组钥匙芯片返回的32 bit的加密数据，因为真实数据未知，所以并不知道密钥流。猜测一个10 bit的某命令(如读block0命令)发至钥匙芯片，若钥匙芯片未返回，则调整猜测命令的数据，重新执行上述操作。根据芯片协议可知，有16/210个读操作命令会被钥匙芯片接受，并返回32 bit的加密数据，再用该数据与32 bit的芯片id异或，得到32 bit的密钥流，利用命令可重复的弱点，用这串密钥流的前10 bit去加密扩展的读block0命令，再次发送给钥匙芯片，若有32 bit的密文数据返回，则证明猜测的命令是正确的读block0命令，否则使用下一个猜测的读block0命令，重复上述操作，直至有32 bit密文数据返回。在成功猜测到读block0命令后，再次将返回的32 bit的密文数据(此时为加密的id)与id的明文异或，得到32 bit的密钥流，通过这串密钥流去加密已扩展至40 bit的读block0命令，并发送至钥匙芯片，可获得32 bit的加密id数据。此时，已经获得72 bit的加密数据，通过将40 bit的读block0命令的明文和32 bit的id的明文与获得的72 bit的密文数据异或，便可获得72 bit的密钥流bibi+1…bi+71。

2)利用其本身线性反馈移位寄存器长度短的弱点。Hitag2密码的线性反馈移位寄存器只有48位，在得到72 bit的密钥流后，可通过暴力破解或折中攻击，得到可生成这72 bit密钥流的线性移位反馈寄存器初始内部状态R0=[a0a1…a47]。

3)得到线性移位反馈寄存器内部状态后，极易倒推出密钥的弱点。Hitag2算法使用一个32 bit的id、48 bit的key和32 bit的随机数nR进行初始化加密，得到线性移位反馈寄存器内部状态Rs0后，利用倒推的方式恢复线性移位反馈寄存器的初始化状态Rinit=[a0a1…a79]和初始密钥流b0b1…b31。利用如下Hitag2初始化规则可解出唯一的密钥：

nRi={nRi}⊕bi，∀i∈[0,31]；

ai=idi，∀i∈[0,31]；

a32+i=ki，∀i∈[0,15]；

a48+i=k16+i⊕nRi，∀i∈[0,31]。

利用上述任何一个弱点都可以对Hitag2进行攻击。本研究用折中攻击法来设计Hitag2攻击算法。利用Hitag2的第一个弱点，攻击者能够获得连续的Hitag2密钥流，然后利用Hitag2的线性反馈移位寄存器内部状态更新规则，固定以215为一条数据链的长度，建立32 GB的彩虹表。根据密钥流序列查询对应的初始内部状态，若彩虹表中存在对应的初始内部状态，则攻击者可以通过初始内部状态、采集电路采集到的32 bit id明文和32 bit随机数的密文倒推出48 bit的Hitag2密钥。当密钥空间确定时，折中攻击法的破解效率取决于计算机的计算性能。

2 使用FPGA加速云对攻击加速

2.1 基于FPGA加速云的Hitag2密码攻击算法设计

基于上述弱点分析，设计了一种基于FPGA加速云的Hitag2折中攻击算法，其主要利用Hitag2的上述弱点进行攻击和解密运算。利用FPGA加速云服务器内存大的优势，可以一次性将32 GB的彩虹表数据读入内存，极大地减少了解密过程中随机访问数据的时延，同时利用FPGA加速云服务器FPGA板卡丰富的逻辑资源，通过例化更多的逻辑模块进一步加速了攻击过程。图1为获取到72 bit密钥流后的折中攻击算法流程图。

图1 Hitag2密码折中攻击算法流程图

2.2 基于FPGA加速云的Hitag2密码攻击算法实现

基于上述算法原理，开发了基于FPGA云计算的Hitag2攻击系统。该系统搭载赛灵思高性能Virtex UltraScale+ VU9P FPGA板卡[8]。服务器主机操作系统为Centos7.0，搭载8核CPU，88 G内存。硬件开发平台使用XILINX公司的VIVADO开发套件。算法的实现过程如下：

1)FPGA高性能硬件接口设计。FPGA高性能硬件接口主要包括算法逻辑的I/O与FPGA板卡I/O的连接关系。其完成时钟信号、密钥流、彩虹表查表地址、查表数据等信号的输入以及结果的输出功能。

2)CPU与FPGA交互的高性能软件设计。软件部分主要完成CPU与FPGA硬件交互的工作，包括密钥流数据的输入、彩虹表的读取以及返回查表数据给FPGA。

3)建立彩虹表。根据Hitag2的加密器工作原理，固定以215为一条数据链的长度，同时固定48位初始内部状态的低16位，彩虹表只存储起点值和端点的地址映射值。遍历232组初始内部状态值，得到32 GB的彩虹表。

4)Hitag2密码并行攻击算法实现。并行攻击算法主要分2个部分：a)根据输入密钥流“猜测”一个内部状态，然后根据这个内部状态作密钥流更新运算，直到这条数据链的端点。若存在与输入的密钥流相同的情况，则表明初始内部状态就是这条数据链的起点，反之，则重新“猜测”一个内部状态；b)根据这条数据链的端点映射的地址找到数据链的起点数据，即初始内部状态，根据Hitag2加密器内部状态更新规则做不超过215次的内部状态和密钥流更新，若存在计算的密钥流等于输入的密钥流，则表明查表得到的数据是真正的初始内部状态。

5)用户逻辑综合实现与加载。在用户逻辑经过VIVADO综合实现后，生成DCP文件，用户通过注册FPGA逻辑镜像生成可供烧录到FPGA的bit文件和bin文件，再通过FPGA镜像加载工具将bit文件加载到FPGA板卡中。

6)FPGA执行程序调用。调用软件驱动程序，完成密钥流数据的输入，控制硬件开始攻击计算。同时将彩虹表加载到主机内存中，并根据解密算法查找主机内存中对应的初始内部状态进行计算，返回最终计算结果。

2.3 性能测试及分析

对文献[9-11]的攻击算法与本攻击算法进行测试和比较分析。图2为在FPGA加速云服务器端测试Hitag2攻击的测试结果。从图2可看出，在输入一组72 bit的密钥流后，本算法能在少于1 s的时间内得到Hitag2加密器的初始内部状态。

图2 测试结果

表1为本算法与现有算法的性能对比。从表1可看出，本算法在时间和存储上均优于现有算法。

表1 本算法和其他算法的性能对比

3 结束语

通过分析Hitag2应用到具体芯片上的弱点，提出并设计了一种基于FPGA的Hitag2折中攻击算法，并用FPGA加速云服务器对攻击过程进行加速。测试结果表明，该算法能在不到1 s的时间得到Hitag2的初始内部状态，进而获得Hitag2的密码。这表明流密码算法Hitag2已不再适合应用到汽车防盗系统上，建议汽车厂商可以考虑使用密钥更长、工作效率更高且便于硬件实现的加密算法，进而提高汽车防盗系统的安全性。