第39卷第3期2019年6月
Vol.39,No.3
Jun.2019桂林电子科技大学学报
Journal of Guilin University of Electronic Technology
基于FPGA加速云的Hitag2攻击算法
肖文，唐宁，刘敬术
(桂林电子科技大学信息与通信学院，广西桂林541004)
摘要：为了验证基于Hitag2加密算法的汽车防盗系统的安全性，研究了Hitag2加密算法的通信协议与加密原理，并根据Hitag2加密算法存在的弱点，提出了一种基于FPGA加速云的Hitag2攻击算法，并在华为云FPGA加速服务器上对攻击算法进行了测试。测试结果表明，该算法能够在得到72YB密钥流后，快速获得Hitag2的初始内部状态，证明了使用Hitag2加密算法的汽车防盗系统已不再安全。
关键词：Hitag2；流密码;FPGA加速云；折中攻击
中图分类号：TP309.7文献标志码：A文章编号：1673/08X(2019)03018703
A Hitag2attack algorithm based on FPGA accelerated cloud
XIAO Wen,TANG Ning,LIU Jinshu
(School of Information and Communication，GuilinUniversity of Electronic Technology，Guilin541004，China)
Abstract:In order to verify the security of the car anti-theft system based on Hitag2encryption algorithm and promote the development of car anti-theft system，this paper studies the communication protocol and encryption principle of Hitag2en­cryption algorithm，and based on the weakness of the Hitag2encryption algorithm applied to the chip，The FPGA acceler­ates the clouds Hitag2attack algorithm and implements the attack algorithm on the Huawei cloud FPGA acceleration server. The test results show that the method can quickly obtain the initial internal state of Hitag2after obtaining the72-bit key stream，which proves that the car anti-theft system using Hitage2encryption algorithm is no longer safe.
Key words：Hitag2algorithm；stream cipher；FPGA cloud computing；time/memory trade-off attract
Hitag2算法是恩智浦半导体(NXP)开发的一种应用在汽车低频电子标签钥匙端的加密算法，使用在NXP向汽车防盗系统供应商提供的pcf7936、pcf7941、pcf7952等防盗芯片上，广泛应用在标志、雪铁龙、本田、尼桑等汽车防盗系统'3&
Hitag2算法属于流密码中的一种，具有算法实现简单、加解密速度快、便于硬件实现等优点，在早期确实具备相当的安全性，但随着硬件技术的发展变得越来越脆弱。
鉴于此，利用华为FPGA加速云F1实例，借助云端主机内存大、FPGA板卡逻辑资源多的优势，通过建立32GB的彩虹表7，提出一种FPGA云端攻击算法。该算法可在平均不到10s时间内获得Hitag2初始内部状态，进而获得Hitag2的密钥。测试结果表明，Hitag2加密算法的安全性已不再可靠。1Hitag2算法的弱点分析
对Hitag2算法的攻击需要利用它的3个弱点：
1)利用Hitag2加密算法应用到芯片上协议存在弱点。Hitag2算法在应用到具体芯片时，具有命令短，命令可以重复，可固定随机数的特点，使得采集到一组随机数和签名的情况下，可以得到至少72bit的密钥流。使用一个低频#25kHz)采集器，在用钥匙启动汽车时，将采集器放在汽车的点火线圈旁，在扭动钥匙点火过程中，可采集到一组32bit加密随机数0)1和32bit的签名&用一个Pcf7991低频读卡器将采集的64bit数据发至汽车钥匙芯片，即可得到一组钥匙芯片返回的32bit的加密数据，因为真实数据
收稿日期：2019-04-13
通信作者：唐宁(1964—)，男，副教授，研究方向为数字专业集成电路设计与测试、EDA技术&E-mailningt@guet.edu 引文格式：肖文，唐宁，刘敬术.基于FPGA加速云的Hitag2攻击算法桂林电子科技大学学报,2019,39(3)：187-189.
188桂林电子科技大学学报2019年6月
未知，所以并不知道密钥流。猜测一个10bit的某命令（如读blockO命令）发至钥匙芯片，若钥匙芯片未返回，则调整猜测命令的数据，重新执行上述操作。根据芯片协议可知，有16/2】。个读操作命令会被钥匙芯片接受，并返回32bit的加密数据，再用该数据与32bit的芯片id异或，得到32bit的密钥流，利用命令可重复的弱点，用这串密钥流的前10bit去加密扩展的读blockO命令，再次发送给钥匙芯片，若有32bit的密文数据返回，则证明猜测的命令是正确的读blockO命令，否则使用下一个猜测的读blockO命令，重复上述操作，直至有32bit密文数据返回。在成功猜测到读blockO命令后，再次将返回的32bit 的密文数据（此时为加密的id）与id的明文异或，得到32bit的密钥流，通过这串密钥流去加密已扩展至4O bit的读blockO命令，并发送至钥匙芯片，可获得32bit的加密id数据。此时，已经获得72bit的加密数据，通过将4O bit的读blockO命令的明文和32bit 的=的明文与获得的72bit的密文数据异或，便可获得72bit的密钥流GG十1-G汁71&
2）利用其本身线性反馈移位寄存器长度短的弱点。Hi；g2密码的线性反馈移位寄存器只有48位，在得到72bit的密钥流后，可通过暴力破解或折中攻击，得到可生成这72bit密钥流的线性移位反馈寄存器初始内部状态K o%'o Q1…Q47（。
3）得到线性移位反馈寄存器内部状态后，极易倒推出密钥的弱点。Hi；g2算法使用一个32bit的=）8bit的key和32bit的随机数n R进行初始化加密，得到线性移位反馈寄存器内部状态心后，利用倒推的方式恢复线性移位反馈寄存器的初始化状态R mit%'o Q1-・Q79（和初始密钥流GG1…G1&利用如下Hi；g2初始化规则可解出唯一的密钥：
n R’%｝㊉b l H i4[0,31]；
a.%l di!l4'3叮；
a32.%k i i4',15（;
a48'i%116十l㊉n R?，V l4'，3叮&
利用上述任何一个弱点都可以对Hi；g2进行攻击。本研究用折中攻击法来设计Hi；g2攻击算法&利用Hi；g2的第一个弱点，攻击者能够获得连续的Hi；g2密钥流，然后利用Hi；g2的线性反馈移位寄存器内部状态更新规则，固定以2】5为一条数据链的长度，建立32GB的彩虹表&根据密钥流序列查询对应的初
始内部状态，若彩虹表中存在对应的初始内部状态，则攻击者可以通过初始内部状态、采集电路采集到的32bit id明文和32bit随机数的密文倒推出48bit的Hi；g2密钥&当密钥空间确定时，折中攻击法的破解效率取决于计算机的计算性能
2使用FPGA加速云对攻击加速
2.1基于FPGA加速云的Hitag2密码攻击算法设计
基于上述弱点分析，设计了一种基于FPGA加速云的Hi；g2折中攻击算法，其主要利用Hi；g2的上述弱点进行攻击和解密运算&利用FPGA加速云服务器内存大的优势，可以一次性将32GB的彩虹表数据读入内存，极大地减少了解密过程中随机访问数据的时延，同时利用FPGA加速云服务器FPGA 板卡丰富的逻辑资源，通过例化更多的逻辑模块进一步加速了攻击过程&图1为获取到72bit密钥流后的折中攻击算法流程图&
图1Hi；g2密码折中攻击算法流程图
2.2基于FPGA加速云的Hi；g2密码攻击算法实现
基于上述算法原理，开发了基于FPGA云计算的Hi；g2攻击系统&该系统搭载赛灵思高性能Virtex UltraScale+VU9P FPGA板卡⑻&服务器主机操作系统为Centos7.0，搭载8核CPU,88G内存&硬件开发
平台使用XILINX公司的VIVADO 开发套件&算法的实现过程如下：
DFPGA高性能硬件接口设计&FPGA高性能硬件接口主要包括算法逻辑的I/O与FPGA板卡I/O的连接关系&其完成时钟信号、密钥流、彩虹表查表地址、查表数据等信号的输入以及结果的输出功能& 2）CPU与FPGA交互的高性能软件设计&软件部分主要完成CPU与FPGA硬件交互的工作，包括密钥流数据的输入、彩虹表的读取以及返回查表数据给FPGA& 3）建立彩虹表&根据Hi；g2的加密器工作原理，固定以2】5为一条数据链的长度，同时固定48位
第！期肖文等：基于FPGA加速云的Hitag2攻击算法189
初始内部状态的低16位，彩虹表只存储起点值和端点的地址映射值。遍历珂组初始内部状态值，得到32GB的彩虹表。
4）Hiag2密码并行攻击算法实现。并行攻击算法主要分2个部分:a）根据输入密钥流“猜测”一个内部状态，然后根据这个内部状态作密钥流更新运算！直到这条数据链的端点。若存在与输入的密钥流相同的情况，则表明初始内部状态就是这条数据链的起点，反之，则重新“猜测”一个内部状态；Y）根据这条数据链的端点映射的地址到数据链的起点数据，即初始内部状态，根据Hiag2加密器内部状态更新规则做不超过2】5次的内部状态和密钥流更新，若存在计算的密钥流等于输入的密钥流，则表明查表得到的数据是真正的初始内部状态。
5）用户逻辑综合实现与加载。在用户逻辑经过VIVADO综合实现后，生成DCP文件，用户通过注册FPGA逻辑镜像生成可供烧录到FPGA的bit文件和bin文件，再通过FPGA镜像加载工具将bit文件加载到FPGA板卡中。
6）FPGA执行程序调用。调用软件驱动程序，完成密钥流数据的输人控制硬件开始攻击计算。同时将彩虹表加载到主机内存中，并根据解密算法查主机内存中对应的初始内部状态进行计算，返回最终计算结果。
2.3性能测试及分析
对文献［9-11］的攻击算法与本攻击算法进行测试和比较分析。图2为在FPGA加速云服务器端测试Hi；g2攻击的测试结果。从图2可看出，在输入一组72bit的密钥流后，本算法能在少于1s的时间 内得到Hi；g2加密器的初始内部状态。
[root@ecs-90d5bin]#./crack_hitag2-i0x56d2bdbb-i0xea86fabb-i0x0O0G0Gea
file read finish
FPGA version：0XEG4616FA
inputdata：0X00G0G0EAEA86FABB56D2IBDBB
Go into cycle
C460DQ0E
□utput_data:G413E59CB13793A
total cost0.280G0G seconds
[root(aecs-90d5bin]#|
图2测试结果
表1为本算法与现有算法的性能对比。从表1可看出，本算法在时间和存储上均优于现有算法。
表1本算法和其他算法的性能对比
算法原理计算耗时/min存储空间/GB
文献［6］暴力破解2102400—
文献［］SAT攻击2880—
文献［］密码学分析51024
本算法FPGA云攻击1/6323结束语
通过分析Hiag2应用到具体芯片上的弱点，提出并设计了一种基于FPGA的Hiag2折中攻击算法，并用FPGA加速云服务器对攻击过程进行加速。测试结果表明，该算法能在不到1s的时间得到Hi；g2的初始内部状态，进而获得Hi；g2的密码。这表明流密码算法Hi；g2已不再适合应用到汽车防盗系统上，建议
汽车厂商可以考虑使用密钥更长、工作效率更高且便于硬件实现的加密算法，进而提高汽车防盗系统的安全性。
参考文献：
[1(NXP Semiconductors.Transponder IC,Hitag2[EB/ OL(.http：//www.datasheetarchive/pd//
download,php?id=020cfdd353el835e832a47658ccf81
ef696e0cCtype=PCterm=HITAG2%2520trans-pon-
der&
[2]NXP Semiconductors.Hitag ro64transponder IC[EB/
OL].p/docs/en/data-sheet/
HTCICC64.pdf.
[3]NXP Semiconductors.PCF7941ATJ Datasheet[EB/
OL(.pdfl.alldatasheet/datasheet-pdf/
vie w/1072413/N XP/P CF7941ATJ.html.
[4]杨波.现代密码学[M(.北京：清华大学岀版社，2003：
214-217.
汽车钥匙芯片[5]宫大力.流密码算法的研究与设计[D].南京：南京航空
航天大学,2011：4-12.
[6]穆昭薇.流密码算法Salsa20的安全性研究[D].西安:
西安电子科技大学,2011:5-15.
[7]郑中翔，吉庆兵，于红波.基于彩虹表的时间一存储折
中攻击改进算法[J].密码学报,2014,1(4):8599. [8]HUAWEI Cloudy.FPGA Development Suite[EB/
OL].github/huaweicloud/huaweicloud-
fpga
[9]PETER S,MARTIN N.Breakin g Hita g2with reconfig­
urable hardware[C]//14th Euromicro Conference on
Digital System Design,2011:558-563.
[10]NICOLAS T,SEAN O,QUISQUATER J.Practical al­
gebraic attacks on the Hitag2stream cipher[C]//12th
InformationSecurityConference20095735:167-176 [11]VERDULT R,GARCIA F D,BALASCH J.Gone in
360seconds:Hijacking with Hitag2[C]//Presented as
Part of the21th Usenix Security Symposium,2012:
237-252
编辑：张所滨