基于密碼雜湊函數的安全規則匹配優化算法

李冬 李明 陳琳 王云霄 郭小燕 張丞

摘 要：隨著防火墻、入侵防御系統等網絡安全規則數目的快速增長，規則匹配效率成為影響網絡安全設備性能的一個瓶頸。基于密碼雜湊算法的隨機性、低碰撞性等良好特性，設計了一種用于防火墻等網絡安全設備的安全規則匹配算法。通過調整密碼雜湊算法輪數、存儲空間大小等參數，達到存儲空間資源占用與實現效率的平衡。分析了規則數目、存儲空間大小和發生碰撞概率之間的關系，以及軟硬件實現的速度。該方案比以前的簡單哈希算法碰撞概率低，適用于高性能防火墻等網絡安全設備的性能優化和效率提升。

關鍵詞：網絡安全;防火墻;安全規則;密碼雜湊函數

DOI：10. 11907/rjdk. 182444 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）007-0088-04

Optimized Security Rules Matching Algorithm

Based on Cryptographic Hash Function

LI Dong，？LI Ming， CHEN Lin， WANG Yun-xiao， GUO Xiao-yan， ZHANG Cheng

（Information & Telecommunication Company， State Grid Shandong Electric Power Corporation， Jinan 250001， China）

Abstract： With the rapid progress of firewalls， intrusion protection systems and other network security systems， the efficiency of security rules matching has been a crucial bottleneck of network security devices performance. Based on the randomness and collision resistance property of cryptographic hash algorithms， we propose an optimized security rules matching algorithm for network security devices such as firewalls. By adjusting the parameters such as the number of rounds in SM3 hash algorithm and the size of storage space， we can achieve a balance of storage space and computational efficiency. The relation of the number of security rules， the size of storage space and the probability of collisions are analyzed. This algorithm has a lower collision probability and better randomness than the previous simple hash algorithms. This algorithm can be used to improve the performance and implementation efficiency of network security devices such as firewalls.

Key Words： network security; firewall; security rules; cryptographic hash function

基金項目：國網山東省電力公司科技項目（2018A-079）

作者簡介：李冬（1971-），男，碩士，國網山東省電力公司信息通信公司高級工程師，研究方向為網絡與信息安全;李明（1982-），男，博士，國網山東省電力公司信息通信公司高級工程師，研究方向為網絡與信息安全;王云霄（1991-），男，碩士，國網山東省電力公司信息通信公司助理工程師，研究方向為網絡與信息安全;郭小燕（1990-），女，碩士，國網山東省電力公司信息通信公司工程師，研究方向為網絡與信息安全;張丞（1987-），男，碩士，國網山東省電力公司信息通信公司工程師，研究方向為網絡安全、信息運維;陳琳（1990-），女，碩士，國網山東省電力公司信息通信公司助理工程師，研究方向為網絡與信息安全。

0 引言

隨著互聯網的飛速發展，信息網絡安全已成為保障信息系統正常、穩定運行的重要基石。在電力行業，隨著國家電網公司 “SG186” 信息化工程建設和“三集五大”體系建設的實施，企業信息化已經滲透到電力系統各個部門。

為保障電力等重點行業的信息系統安全，需要在網絡邊界部署防火墻、入侵檢測系統（IDS）、入侵防御系統（IPS）、IPSec VPN、SSL VPN等多種網絡安全設備，并根據安全需求配置眾多安全防護策略。隨著業務系統的擴充和增長，網絡安全策略逐漸累加，一些核心設備的安全規則多達幾萬條。因此，如何提高網絡安全策略和規則的匹配效率成為網絡安全設備性能優化的關鍵問題之一。

在防火墻等網絡安全設備和路由器、網關等網絡基礎設備中，網包分類算法是實現其性能的核心技術[1-2]。包過濾防火墻的基本原理是根據網絡數據包的IP源地址/目的地址、源端口/目的端口等信息，搜索并匹配包過濾規則[3-5]，并根據對應的安全規則判定如何處理IP數據包，即是否允許IP數據包通過還是丟棄。

最直接的安全規則匹配方法是順序查找算法[1]，將安全規則集合按優先級從高到低排列，當接收到新的IP數據包時，根據IP地址和端口號等線性搜索安全規則集合進行匹配，此算法的時間復雜度與規則個數是線性關系。三態內容可尋址存儲器-TCAM（Ternary Content Addressable Memory）[6]是一種支持并行查找的專門硬件，可通過增加硬件成本提高搜索效率，缺點是資源和能量消耗很大。一類安全規則匹配方法是基于決策樹的算法，邊力等[7]提出了一種改進的基于后序遍歷請求樹的策略匹配算法，程玉柱等[8]提出一種基于單元空間劃分的快速防火墻包分類方法。基于哈希表的規則匹配算法[9-13]是利用哈希算法建立數據包與安全規則之間的映射關系，通過直接計算IP地址和端口等信息的哈希值，獲得安全規則的存儲地址，但是可能存在哈希沖突情況，即多個IP數據包對應同一個哈希地址，需要再進行順序查找以確定對應的安全規則。

針對簡單哈希算法碰撞率高和分布不均勻問題，基于SM3密碼雜湊算法的隨機性、低碰撞性等良好特性，本文設計了一種用于防火墻等網絡安全設備的安全規則匹配算法，可通過調整SM3密碼雜湊算法輪數、存儲空間大小等參數，動態調整哈希值計算的效率和占用的存儲空間資源大小。由于SM3密碼雜湊算法的良好隨機性和雪崩效應，IP地址、端口等信息的任意變化都會得到完全不同的哈希值，所以此算法比以前各種簡單的哈希算法具有更低的碰撞概率和更均勻的分布，適用于高性能防火墻等網絡安全設備的性能優化和效率提升。

1 哈希表算法與密碼雜湊算法

哈希表（Hash table，也稱為散列表）是把關鍵碼值映射到數據存儲地址的一種數據組織方式。為了提高計算效率和快速定位訪問地址，一般采用比特截取、異或、線性變換、平方取中法等簡單函數。在防火墻等網絡安全設備的規則匹配過程中，有可能出現兩個數據或IP數據包哈希值相同的情況，需要繼續順序查找、比較，確定真正匹配的安全規則。

由于哈希表算法一般都非常簡單，因此碰撞率比較高，而且哈希值的發布也不均勻。例如，網絡安全設備接收到的網絡包IP地址和端口號取值并不是隨機分布的，有些IP地址和端口出現的頻率較高，如果哈希表算法不合適，可能會出現很多網絡包計算出同一個哈希值情況，存儲分布不均勻，影響規則匹配效率。

密碼雜湊算法（Cryptographic hash algorithm），也稱為散列函數、哈希函數，是3種基本密碼算法（數據加密算法、數字簽名算法、密碼雜湊算法）之一，可以將任意長度的消息壓縮成固定長度的摘要值。MD5、SHA-1、SHA-256/384/512等系列算法是國際上常見的密碼雜湊算法。SM3密碼算法[14]是我國密碼雜湊算法標準，可將任意長度的消息經過計算后得到256比特長度的摘要值，用于數字簽名的雜湊值計算、消息完整性校驗等。

密碼雜湊算法一般用于消息鑒別碼、數字簽名等安全協議，要求具有良好的抵抗原像攻擊、碰撞攻擊、生日攻擊等特性[15]，在隨機性分布和低碰撞率等方面具有良好性質，因此本文采用密碼雜湊函數用于安全規則的存儲地址映射計算。

2 優化算法

基于SM3密碼雜湊算法，本文設計了防火墻等網絡安全設備的安全規則匹配算法，通過對IP數據包的IP地址、端口等信息進行雜湊運算，得到安全規則的對應地址，然后進行規則匹配并采取相應的網絡包處理措施。

2.1 SM3密碼雜湊算法及符號定義

SM3密碼雜湊算法采用Merkle-Damgard結構，輸入為長度<264比特的消息m，輸出摘要長度為256比特，運算過程包括64輪壓縮函數計算，消息塊大小為512比特。

設消息m的長度為|m|比特，后面添加一個比特“1”和k比特“0”，其中|m|+1+k=448 mod 512。然后，再添加一個64比特串，是消息長度|m|的二進制表示。設經過填充后的消息m=B0B1…Bn-1，其中消息塊的個數n=（|m|+k+65）/512，對m進行迭代運算：

其中，CF為SM3雜湊算法的壓縮函數，V0為256比特的初始化向量，IV=0x 7380166F 4914B2B9 172442D7 DA8A0600 A96F30BC 163138AA E38DEE4D B0FB0E4E，Bi為填充后的消息塊分組，最后的摘要值為Vn。

壓縮函數CF（Compression？Function）是對每一個512比特消息塊進行處理的函數。令A、B、C、D、E、F、G、H是8個32比特的寄存器，SS1、SS2、TT1、TT2是中間變量，令⊕表示按比特異或，+表示模232的算術加法，<

壓縮函數Vi+1=CF（Vi， Bi）的計算過程如下：

其中，常量Tj為：[Tj=79CC4519，? 0j157A879D8A，? 16j63] ，FFj（X， Y， Z）和GGj（X， Y， Z）是兩個布爾函數，P0（X）是一個置換函數，Wj和Wj是消息擴展成的32比特字，這些函數和數值的詳細定義見文獻[14]。

2.2 安全規則匹配優化算法

基于SM3密碼雜湊算法的安全規則匹配優化算法，包括哈希值計算、建立哈希表和規則匹配3種算法，詳細描述如下：

設Keys_Info為輸入的網絡數據包的關鍵值信息（包括IP地址、端口等），Length_Hash_Table為存儲的哈希表最大地址的比特長度，1≤Num_Rounds≤64為設定的SM3雜湊運算輪數。

算法1 哈希值計算算法（Keys_Info，Length_Hash_Table，Num_Rounds）：

（1）消息m←Keys_Info，按照SM3輸入消息的填充方法進行填充，得到m。

（2）V0 ← 0x 7380166F 4914B2B9 172442D7 DA8A0600 A96F30BC 163138AA E38DEE4D B0FB0E4E。

（3）ABCDEFGH ← V0。

（4）循環Num_Rounds輪運算，即

（6）將V1填充為Length_Hash_Table的倍數長度，即V1←V1||010101…，其中“||”表示二進制比特串拼接。

（7）令V1=H0||H1||…||Hn，其中每個Hi是一個Length_Hash_Table長度的比特串，0≤i≤n，則最后的哈希值輸出位：Hash_Value ← H0 ⊕ H1 ⊕ … ⊕ Hn。

設Rules表示安全規則的集合，則將安全規則按哈希表存儲的算法進行描述。

算法2 建立哈希表（Rules，Length_Hash_Table，Num_Rounds）：

（1）對于安全規則集合Rules中的每一條規則，循環進行步驟（2）和步驟（3）的操作。

（2）調用哈希值計算算法（Keys_Info，Length_Hash_Table，Num_Rounds）計算本條安全規則的存儲地址Addr，其中Keys_Info為本條安全規則中的IP地址、端口等信息。

（3）將本條安全規則存入地址Addr的存儲單元，如果多條安全規則計算出同一個地址，則以鏈表形式依次存儲。

設IP_Packet_Info表示防火墻等網絡安全設備接收到的網絡數據包的IP地址、端口等信息，Hash_Table_rules表示已經建立的哈希表。

算法3 規則匹配算法（IP_Packet_Info，Hash_Table_rules）：

（1）將IP_Packet_Info作為輸入的關鍵值信息，調用哈希值計算算法（IP_Packet_Info，Length_Hash_Table，Num_ Rounds）計算對應的安全規則地址Addr。

（2）將地址Addr中的安全規則與IP數據包進行規則匹配，如果地址Addr存在多條安全規則，則需要依次匹配，并根據匹配規則進行IP數據包的處理操作。

3 碰撞性與效率分析

3.1 碰撞性分析

密碼學上的雜湊函數[15]（也稱散列函數，哈希函數）主要用于消息鑒別碼和數字簽名等安全機制，其安全特性需滿足單向性和無碰撞性。

密碼雜湊函數h的安全性應滿足：①單向性：給定一個哈希值y，不能在有效時間內找到一個x，使得h（x）=y;②抗第二原像攻擊（弱無碰撞性）：給定一對x和y，h（x）=y，不能在有效時間內找到一個消息x≠x，使得h（x）=h（x）;③強無碰撞性：不能在有效時間內找到一對消息x≠x，使得? ? h（x）=h（x）。

一個良好的密碼雜湊函數應該滿足以上安全特性。對密碼雜湊函數最基本的攻擊方法是生日攻擊，即在一個大約23人左右的班里，至少有兩個人生日相同的概率大于1/2。SM3密碼雜湊算法的輸出長度為256比特，如果隨機選取1.17·2128個輸入數據，則有50%的概率出現碰撞，即至少兩個輸入數據的哈希值相同。在當前主流計算機處理能力下，2128仍然是一個非常龐大的數據量，因此不能在有效時間內窮舉這個數量的隨機數找到碰撞。

SM3密碼雜湊算法是經過廣泛分析的高強度密碼算法，其輸出結果近似于與真隨機數不可區分的偽隨機數，最后的哈希值計算Hash_Value ← H0 ⊕ H1 ⊕ … ⊕ Hn，是將256比特的SM3密碼雜湊值進行分段、異或，因此也是分布均勻的偽隨機數。所以，基于SM3密碼雜湊算法的哈希表計算，比簡單的哈希表算法具有更好的隨機性和更低的碰撞概率。

在本文提出的基于SM3密碼雜湊算法的規則匹配優化算法中，哈希表的地址空間不可能直接用SM3算法的256比特，如在一般的PC計算機環境下，可取1k～256M存儲地址空間，即哈希值結果的比特長度為10～28比特。在安全規則數目一定的前提下，哈希表的地址空間越大發生碰撞的概率越小，同時浪費的存儲空間越多。基于SM3密碼雜湊算法的哈希表計算具有良好的隨機性和低碰撞概率，使安全規則的存儲分布更均勻，平均檢索效率更高。

3.2 效率分析

在以前的基于哈希表的規則匹配算法中，采用非常簡單的哈希算法原因主要是計算哈希值的速度較快，但是隨著CPU、FPGA和ASIC芯片等技術飛速發展，密碼雜湊函數的運算速度也非?？?，能夠滿足計算哈希值的速度要求。

在Intel Xeon E3處理器上實現SM3密碼雜湊算法，在單核單線程環境下測試運算速度可達2.6Gbps，即每秒可計算1 000萬次SM3雜湊運算，在4核、8核等多線程環境下，運算速度可成線性倍數增長。

在Xilinx Kintex-7 FPGA芯片上實現SM3密碼雜湊算法，單模塊測試運算速度可達5.8Gbps，即每秒可計算2 200萬次SM3雜湊運算，并可通過多模塊并行進一步提高性能。

本文提出的安全規則匹配算法，在SM3運算結果基礎上，根據哈希表長度進行分段異或得到最后的哈希結果，每秒計算哈希值的速度與上面的測試結果基本相同，可滿足防火墻等安全設備的性能要求。本文提出的算法可以輸入輪數作為參數，進一步簡化哈希值計算過程，提高計算效率。例如，采用輪數為20輪[16]，計算哈希值的速度能夠提高3倍以上，可以適應不同環境下的計算速度需求。關于SM3算法和其它密碼雜湊算法的安全性，參見參考文獻[17-20]。

4 結語

本文設計了一種用于防火墻等網絡安全設備的安全規則匹配優化算法，利用SM3密碼雜湊算法的隨機性和低碰撞性等良好特性，將密碼雜湊算法應用于安全策略存儲和查找算法中，有效解決了以前各種簡單哈希算法的高碰撞率問題。在Intel Xeon CPU和Xilinx FPGA芯片上的編程實現和測試，具有很高的運算性能，能夠滿足高性能防火墻等網絡安全設備的處理效率需求，達到優化性能目標。將來的研究工作是通過在網絡安全設備上進行各種測試，確定安全規則數量、存儲空間大小與碰撞率之間的關系，達到計算效率與存儲空間的平衡。

參考文獻：

[1] TAYLOR D E. Survey and taxonomy of packet classification techniques[J]. ACM Computing Surveys， 2005， 37（3）：238-275.

[2] 亓亞烜，李軍. 高性能網包分類理論與算法綜述[J]. 計算機學報， 2013， 36（2）：408-421.

[3] 李林. 防火墻規則集關鍵技術研究[D]. 成都：電子科技大學，2009.

[4] 單超. 防火墻配置規則集優化關鍵技術研究[D]. 哈爾濱：哈爾濱工程大學，2014.

[5] 韓國龍， 王偉， 盛紅雷. 防火墻策略梳理與優化方法研究[J]. 電力信息與通信技術， 2018， 16（6）： 31-35.

[6] 丁麟軒， 黃昆， 張大方. 基于TCAM的低能耗正則表達式匹配算法[J]. 通信學報， 2014， 35（8）：162-168.

[7] 邊力， 王煒， 姬瑞龍，等. 基于后序遍歷請求樹的訪問控制策略匹配算法[J]. 軟件導刊， 2015， 14（12）：58-62.

[8] 程玉柱，王偉平，王建新.一種基于單元空間劃分的快速防火墻包分類算法[J].工程科學與技術，2018，50（4）：144-152.？

[9] 孫瑩， 溫巧燕. 一種基于Hash表的防火墻匹配算法 [C]. 2006北京地區高校研究生學術交流會， 2006： 2035-2040.

[10] DONGRE S A，SHIKALPURE S G. Hashing based packet matching algorithm for firewall[J]. International Research Journal of Engineering and Technology （IRJET）， 2015，2（7）： 553-557.

[11] KHUMMANEE S，TIENTANOPAJAI K. High-speed firewall rule verication with o（1） worst-case access time [J]. International Journal of Network Security， 2017， 19（1）： 72-84.

[12] LEE P? J，GUO H B，VEERAVALLI. Enhancing cii firewall performance through hash based rule lookup[C]. TENCON 2017 - 2017 IEEE Region 10 Conference，IEEE， 2017：2285-2290.

[13] RAMAKRISHNA M V，FU E，BAHCEKAPILI E. Efficient hardware hashing functions for high performance computers [J]. IEEE Transaction Computer， 1997， 46（12）：1378-1381.

[14] 王小云，于紅波. SM3密碼雜湊算法 [J]. 信息安全研究，2016，2（11）：983-994.

[15] STINSON D R. 密碼學原理與實踐[M]. 第2版.馮登國， 譯. 北京： 電子工業出版社， 2003.

[16] MENDEL F，NAD T. Finding collisions for round-reduced sm3[C]. International Conference on Topics in Cryptology， 2013：174-188.

[17] KIRCANSKI A，SHEN Y，WANG G， et al. Boomerang and slide-rotational analysis of the SM3 hash function[C]. Selected Areas in Cryptography， 2012： 305-321.

[18] ROGAWAY P，SHRIMPTON T.Cryptographic hash-function basics： definitions， implications， and separations for preimage resistance， second-preimage resistance， and collision resistance [C]. Fast Software Encryption，Springer-Verlag， 2004： 371-388.

[19] STINSON D R. Some observations on the theory of cryptographic hash functions[J]. Design， Codes and Cryptography，2006，38（2）： 259-277.

[20] ZOU J，WU W，WU S， et al. Preimage attacks on step-reduced SM3 hash function[C]. International Conference on Information Security and Cryptology，2011： 375-390.

（責任編輯：杜能鋼）