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

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

關鍵詞：網(wǎng)絡安全;防火墻;安全規(guī)則;密碼雜湊函數(shù)

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

2 優(yōu)化算法

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

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

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

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

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

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

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

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

2.2 安全規(guī)則匹配優(yōu)化算法

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

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

算法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）循環(huán)Num_Rounds輪運算，即

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

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

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

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

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

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

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

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

算法3 規(guī)則匹配算法（IP_Packet_Info，Hash_Table_rules）：

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

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

3 碰撞性與效率分析

3.1 碰撞性分析

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

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

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

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

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

3.2 效率分析

在以前的基于哈希表的規(guī)則匹配算法中，采用非常簡單的哈希算法原因主要是計算哈希值的速度較快，但是隨著CPU、FPGA和ASIC芯片等技術飛速發(fā)展，密碼雜湊函數(shù)的運算速度也非?？欤軌驖M足計算哈希值的速度要求。

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

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

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

4 結語

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

參考文獻：

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

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

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

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

[5] 韓國龍， 王偉， 盛紅雷. 防火墻策略梳理與優(yōu)化方法研究[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北京地區(qū)高校研究生學術交流會， 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，F(xiàn)U 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版.馮登國， 譯. 北京： 電子工業(yè)出版社， 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.

（責任編輯：杜能鋼）