基于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已不再適合應用到汽車防盜系統上，建議汽車廠商可以考慮使用密鑰更長、工作效率更高且便于硬件實現的加密算法，進而提高汽車防盜系統的安全性。