《基于密码杂凑函数的安全规则匹配优化算法》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

基于密码杂凑函数的安全规则匹配优化算法

范文

李冬李明陈琳王云霄郭小燕张丞

摘要：随着防火墙、入侵防御系统等网络安全规则数目的快速增长，规则匹配效率成为影响网络安全设备性能的一个瓶颈。基于密码杂凑算法的随机性、低碰撞性等良好特性，设计了一种用于防火墙等网络安全设备的安全规则匹配算法。通过调整密码杂凑算法轮数、存储空间大小等参数，达到存储空间资源占用与实现效率的平衡。分析了规则数目、存储空间大小和发生碰撞概率之间的关系，以及软硬件实现的速度。该方案比以前的简单哈希算法碰撞概率低，适用于高性能防火墙等网络安全设备的性能优化和效率提升。

关键词：网络安全;防火墙;安全规则;密码杂凑函数

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.

（责任编辑：杜能钢）

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。