基于压缩HMAC 算法的传感器网络范围查询方法

胡乔木，邓 昀

（1.桂林理工大学 信息科学与工程学院，广西 桂林 541006；2.广西嵌入式技术与智能系统重点实验室，广西 桂林 541006）

0 概述

无线传感器网络（Wireless Sensor Networks，WSN）由大量资源受限的感知节点构成［1-2］，通过数据聚集和数据查询等操作实现监控以及侦查等功能，具有广泛的应用场景［3-5］。其中，两层无线传感器网络由于路由简单、寿命较长等优点，备受研究人员的关注，并基于两层无线传感器网络提出范围查询［6-7］、top-k 查询［8-9］、最值查询［10-11］等安全高效的查询方案。

文献［12］中提出一种范围查询方法SafeQ，感知节点使用对称加密算法对数据进行加密得到邻居链，同时使用了前缀成员验证技术对数据进行加密获得前缀成员编码，存储节点基于前缀成员编码特性将满足范围查询要求的邻居链发送至基站，基站通过邻居链对数据进行完整性验证。但是由于SafeQ 采用了前缀成员编码技术，需要上传较多的编码数据，同时其采用了邻居链的方式进行完整性验证，也增加了感知节点的负担［13］。

因此，文献［14］中提出了一种范围查询方法CSRQ（Communication-efficient Secure Range Query），该方法使用对称加密算法对数据进行加密构建加密约束链，并使用0-1 编码和HMAC（Hash-based Message Authentication Code）算法获取比较项，将加密约束链和比较项发送至存储节点进行存储，存储节点利用比较项性质返回满足基站查询要求的加密约束链，基站通过加密约束链特性对数据进行完整性验证，但加密约束链依然包含了较多的冗余数据，使得感知节点上传的信息较多，能耗较高［13］。

为降低感知节点能量消耗，本文提出一种安全高效的多维数据范围查询方法。在数据上传阶段，感知节点运用AES 加密算法加密数据得到数据密文，使用压缩HMAC 算法减少上传的HMAC 编码，压缩HMAC 算法对数据最值进行加密得到最值比较链。在数据查询阶段，存储节点存储感知节点上传的信息，接收基站的查询命令，通过最值比较链将满足查询条件的数据密文、加密索引链发送至基站。在数据验证阶段，基站接收存储节点发送的信息，根据加密索引链性质对数据进行完整性验证。

1 相关模型

1.1 网络模型

基于两层无线传感器网络，将网络分割为多个查询单元，每个查询单元包含一个存储节点φ和多个感知节点{e1，e2，…，en}，记为UUnit={φ，{e1，e2，…，en}}。在查询单元中，感知节点资源有限，存储能力较弱，而存储节点资源丰富，存储能力强，可以存储感知节点上传信息，响应基站查询命令，发送相应信息。两层无线传感器网络模型如图1 所示。

图1 两层无线传感器网络模型Fig.1 Two-layer wireless sensor networks’model

1.2 查询模型

采用多维数据的查询模型，以两维数据为例，可以形式化为以下公式：

其中：E为待查询感知节点集合；H为查询时间周期集合；[low1，high1]为第一维数据的查询范围区间；[low2，high2]为第二维数据的查询范围区间，表示查询集合E内的感知节点在时间周期集合H内第一维数据满足范围区间[low1，high1]，第二维数据满足范围区间[low2，high2]的所有数据。如Q=({e1，e2，…，e20}，{h1，h2}，[10，30]，[40，60])，表示感知节点e1～e20在时间周期h1～h2内的第一维数据满足区间[10，30]，第二维数据满足区间[40，60]的所有数据。

1.3 安全模型

无线传感器网络普遍缺少人类的管理，容易被第三方窃取或者篡改感知节点数据。目前针对两层无线传感器网络的研究，主要有以下3 种安全模型：

1）半诚实模型。存储节点可以遵守相应规则，但可能会泄露其中的感知节点上传信息。

2）完整性攻击模型。被俘获的存储节点可能会对查询结果进行篡改或丢弃，使返回基站的查询结果不完整。

3）强安全模型。被俘获的存储节点不仅会泄露感知节点上传的数据，而且会对查询结果进行伪造或丢弃，使得查询结果不完整。

基于强安全模型，本文提出一种安全高效的多维数据范围查询方法，有效维护两层无线传感器网络的安全。

2 隐私保护范围查询算法

2.1 反向0-1 编码

使用反向0-1 编码实现密文形式下的数值大小比较，该编码方法不需额外进行数值化处理，降低了节点的计算能耗。设S为长度为n的二进制序列，即S={sn sn-1…s1|1≤i≤n∧si∈{0，1}}，则二 进制序列S的反向0 编码集合如下：

二进制序列S的反向1 编码集合如下：

性质1设数字α和数字β的二进制序列长度相同，当数字α的反向1 编码和数字β的反向0 编码有交集时，则α>β。

证明如果2 个编码集合存在一个相同的数据sn sn-1...si+10 1…1，则对于sn sn-1...si+1位α与β相同，而对于si位，α的该位实际为1，β的该位实际为0，由此可知α>β。而如果α>β，则其二进制序列存在最高的某一位，α的该位为1 而β的该位为0，由于α采用反向1 编码，该位的1 变成了0，β采用反向0 编码，该位的0 保留，则从最高位到该位的序列必然相同，由此证明性质1。

性质2设数字α和数字β的二进制序列长度相同，当数字α的反向1 编码和数字β的反向0 编码没有交集时，则α≤β。

证明由性质1 可知，当数字α的反向1 编码和数字β的反向0 编码有交集时，则α>β，而数字α的反向1 编码和数字β的反向0 编码没有交集，可知α≤β。而如果α≤β，数字α的反向1 编码中的数据要小于α，数字β的反向0 编码中的数据要大于等于β，数字α的反向1 编码和数字β的反向0 编码必然没有交集，由此证明性质2。

性质3设数字α和数字β的二进制序列长度相同，当数字α的反向0 编码与数字β的反向0 编码相同时，或者数字α的反向1 编码与数字β的反向1 编码相同时，则α=β。证明同理。

2.2 压缩HMAC 算法

基于文献［15］提出的压缩HMAC 算法，本文提出一种新的压缩HMAC 算法。设HMAC 编码输出有μ位，设Nμ为HMAC编码的全局空间，则Nμ={0，1，…，2μ-1}，采用如下Hash 函数对HMAC 编码进行压缩处理：

其中：x∈Nμ∧τ<μ，经过Hash 函数的处理后，可以将μ位的HMAC编码转换成τ位的压缩HMAC编码。

对于任意2 个在Nμ中的HMAC 数据x1、x2，根据Hash 的计算规则，如果x1=x2，则有Hash(x1)=Hash(x2)成立，如果x1≠x2，当x1和x2对2τ求余相同时，Hash(x1)=Hash(x2) 成立，否则Hash(x1)≠Hash(x2)成立。

性质4对于2 个HMAC 编码集合X和Y，若X∩Y≠∅，则Hash(X)∩Hash(Y)≠∅必然成立。

证明当X∩Y≠∅时，则在X集合中至少存在一个xi，在Y集合中至少存在一个yi，满足xi=yi，则可知必然满足Hash(xi)=Hash(yi)。因此，如果2 个HMAC 集合相交不为空集，则这2 个集合经过Hash运算后的集合相交必然不为空集。也即若X∩Y≠∅，则Hash(X)∩Hash(Y)≠∅必然成立。当2 个HMAC 集合相交时，Hash 后的集合也相交，不影响其相交结果正确性。

性质5对于2 个HMAC 编码集合X和Y，若X∩Y=∅，则Hash(X)∩Hash(Y)≠∅可能成立。

证 明当X∩Y=∅时，则对于任意xi∈X，yi∈Y，均有xi≠yi成立。当xi和yi对2τ求余不同时，有Hash(xi)≠Hash(yi)成立，此时Hash(X)∩Hash(Y)=∅。然而，当xi和yi对2τ求余相同时，则有Hash(xi)=Hash(yi) 成立，即发生了碰撞，此时Hash(X)∩Hash(Y)≠∅，Hash 后的2 个集合相交结果与原来集合相交的结果不一致，出现了失误。因此，若X∩Y=∅，则Hash(X)∩Hash(Y)≠∅可能成立。

因此，本文主要讨论出现失误的概率Pe，即在X∩Y=∅时发生Hash(X)∩Hash(Y)≠∅的最大概率。设HMAC集合X包含v个HMAC数据，即X={x1，x2，…，xv}，HMAC 集合Y包含w个HMAC 数据，即Y={y1，y2，…，yw}。假设HMAC 集合X经过Hash 运算后产生θ个数据，可以知道1≤θ≤v，则在Nμ中共有(2μ/2τ)×θ个HMAC 数据组成集合R，满足：R中任一数据x通过Hash 运算得到的数据都在集合Hash(X)中。所以，对于Y中的任一数据yi，Hash(yi)∉Hash(X)的概率等于yi不在集合R中的概率，即：

而只有当HMAC 集合Y中所有w个HMAC 数据，通过Hash 运算后的数据都不在Hash(X)中时，Hash(X)∩Hash(Y)=∅才成立，即X∩Y=∅时发生Hash(X)∩Hash(Y)=∅的概率如下：

当发生失误时，即当X∩Y=∅时发生Hash(X)∩Hash(Y)≠∅的概率如下：

显然，当θ=v时，Pe最大，即：

在范围查询算法中，设HMAC 集合X有16 个HMAC数据，HMAC集合Y有32个HMAC数据，即v=16，w=32，设μ=128，τ=24，代入式（8）可得到Pe=3.05×10-5。这一失误概率对感知数据的大小比较的影响十分小，但Hash 运算却可以使得上传的HMAC 数据显著减少，有利于降低感知节点能量消耗。

2.3 算法流程

算法主要包含数据上传、数据查询和数据验证3个阶段。反向0-1 编码记为RZO，反向0 编码记为RZO0，反向1 编码记为RZO1，MIN 表示取2 个集合中元素最少的集合，AES 加密算法记为AES，HMAC-MD5 加密算法记为HMAC，HMAC-MD5加密算法具有单向性和抗冲突性［16-17］，经过HMAC-MD5 加密后的数据依然能够进行大小比较［18-19］，且不能逆向解密成原始数据［20-21］。

2.3.1 数据上传阶段

感知节点采集多维的数据，以二维数据为例，采集二维数据：

使用AES 加密算法进行加密，得到数据密文φ：

同时，获取二维数据中的最小值和最大值，即：

使用AES 加密算法进行加密得到加密索引链λ：

将二维数据的最小值和最大值进行反向0-1 编码：

为减少感知节点上传的信息，获取二维最值数据反向0-1 编码的最小集合：

先对其使用HMAC 算法，再使用Hash 算法进行优化，得到最值比较链ψ：

将数据密文、加密索引链、最值比较链组成最终数据d1发送至存储节点，即：

2.3.2 数据查询阶段

基站获取二维数据的查询范围区间：

对区间进行反向0-1 编码：

对反向0-1 编码的结果运用HMAC 算法和Hash算法得到查询范围区间的压缩HMAC 数据ζ：

基站获取查询时间区间[Tstart，Tend]，与查询范围区间的压缩HMAC 数据ζ组合成查询命令query 发送至存储节点，即：

存储节点接收到基站发送的query 之后，在满足查询时间区间[Tstart，Tend]的数据中，判断每维的数据是否满足如下的三个条件之一，这里以第一维数据为例：

其中：当Amin使用反向0 编码时，Alow和Ahigh使用反向1编码进行判断，反之使用反向0 编码进行判断；同理，当Amax使用反向0 编码时，Alow和Ahigh使用反向1编码进行判断，反之使用反向0 编码进行判断。

如果所有维度的数据都满足上述三个条件之一时，表明该数据满足基站的查询要求，将数据中的数据密文φ，加密索引链λ发送至基站，即：

2.3.3 数据验证阶段

基站接收来自存储节点的信息，解密数据密文，获取二维数据的最小值和最大值，即：

解密加密索引链，判断数据密文中的最值是否与加密索引链中的数据最值一致，如果不一致则数据被伪造或者篡改，再与查询区间进行比较，以第一维数据举例：

满足上述条件后数据才是完整的，在数据密文中筛选满足查询要求数据，并显示在查询程序界面中。

2.4 算法安全性分析

在两层无线传感器网络中，范围查询方法的安全性分析分为隐私安全性分析和查询结果完整性分析。隐私安全性分析主要针对范围查询过程中感知数据，查询范围以及查询结果是否泄露，而查询结果完整性分析主要针对基站接收查询结果之后判断查询结果是否被伪造或者删除。

2.4.1 隐私安全性分析

范围查询方法使用AES 对称加密算法对感知节点采集数据进行加密，使数据不被破解，AES 对称加密算法需要相同密钥才可进行解密，范围查询方法通过DH 密钥交换（Diffie-Hellman key exchange）进行密钥的生成，第三方无法获取密钥信息，因此保障了感知数据的隐私安全性。

基站将查询范围进行反向0-1 编码、HMAC 加密和Hash 算法优化，再发送至存储节点。反向0-1 编码用于进行大小的比较，HMAC 具有单向不可逆性质，Hash 算法可以优化HMAC 编码，加密后的数据依旧可以用于大小比较，并且不能逆推回原始数据，即使存储节点被捕获也无法获取其明文数据，从而确保了查询范围的隐私安全性。

感知节点上传数据密文，加密索引链和最值比较链到存储节点，存储节点接收数据并进行存储，基站发送查询命令给存储节点，存储节点利用最值比较链进行大小比较，将对应的信息发送至基站。在比较过程中使用最值比较链进行比较，第三方无法逆推出原始数据，上传的信息使用了AES 对称加密，第三方无法在未知晓密钥的情况下进行破解。因此，保障了查询结果的隐私安全性。

综上，该范围查询算法可以保障感知数据、查询范围和查询结果的隐私安全性。

2.4.2 查询结果完整性分析

存储节点返回的数据如下：

1）当存储节点返回数据中的φ、λ两者不全时，表明数据被删除，返回的数据不完整。

2）解密数据密文和加密索引链，若解密出错，则数据被伪造或者篡改，返回数据不完整。

3）将数据密文和加密索引链的最值进行比较，如果两者最值数据不一致，表明数据被伪造或者篡改，返回数据不完整。

4）将数据密文最值与查询区间进行比较，如果数据密文最值不满足查询区间要求，则表明数据被伪造或者篡改，返回数据不完整。

对于存储节点返回基站的数据，如果满足上述4 个步骤，返回数据才是正常的，满足范围查询算法的查询结果完整性要求。

3 实验结果与分析

3.1 实验

在实验中，存储节点开启Wi-Fi，感知节点和基站连接该Wi-Fi，并在相同的局域网内进行密钥交换和数据传输。在数据上传阶段，感知节点作为客户端，而存储节点作为服务器端，感知节点采集多维数据，并将感知数据上传至存储节点。在数据查询阶段，存储节点则作为客户端，而基站作为服务器端，基站向存储节点发送查询命令，存储节点响应查询请求并将相应数据上传至基站。在数据验证阶段，基站接收存储节点发送的查询结果并进行查询结果完整性验证。

3.2 感知节点程序流程

感知节点采用上海诺行信息技术公司的AliOS Things Developer Kit 开发板，搭载了阿里巴巴公司自主研发的AliOS 系统，并包含有：音频编解码器，8 个传感器，8 位数码相机，LCD 显示屏，sixes LEDs，PCIe模块，USB_OTG_FS模块 和Wi-Fi模块。

开发板先连接存储节点开启的Wi-Fi，确保自己可以正常进行通信，再与基站进行DH 密钥交换，在不被第三方窃取密钥的情况下安全获取相同密钥。在获取相同密钥后，再通过该开发板采集监测区域物理数据，并进行加密运算形成数据密文，同时构建加密索引链和最值比较链，最终将数据密文、加密索引链和最值比较链传输到存储节点。图2 所示为感知节点的程序流程，图3 为AliOS Things Developer Kit 开发板。

图2 感知节点程序流程Fig.2 Program procedure of perception node

图3 AliOS Things Developer Kit 开发板Fig.3 AliOS Things Developer Kit development board

3.3 存储节点程序流程

存储节点采用迅为电子公司的iTOP-4412核心板，使用三星的Exynos 4412 四核处理器，系统为Linux 系统，主频为1.4 GHz，内置了8 GB 存储空间，具有9 路的DC/DC 和28 路LDO 输出电源，在-20～70 ℃范围的高低温测试中运行良好。

在存储节点通电后，先开启Wi-Fi，确保感知节点和基站可以正常通信。如果感知节点和基站没有成功连接Wi-Fi，则循环等待连接。在连接成功后，当存储节点接收到感知节点上传的数据时，判断该数据是密钥交换信息还是隐私数据信息，如果是密钥交换信息则发送给基站，如果是隐私数据信息，则需要进行存储。判断当天的数据表是否已经创建，如果已创建则将数据存入数据表，如果未创建，则先创建数据表再存入相应数据。图4 所示为存储节点程序流程，图5 为iTOP-4412 核心板。

图4 存储节点程序流程Fig.4 Program procedure of storage node

图5 iTOP-4412 核心板Fig.5 iTOP-4412 core board

3.4 基站程序流程

基站用电脑程序模拟，电脑型号为SAMSUNG 500R5H，系统为Windows 8.1，软件环境为Visual Studio 2015，编程语言为Visual Basic.NET。

基站启动后先连接存储节点开启的Wi-Fi。连接Wi-Fi成功后，与感知节点进行DH 密钥交换，获取相同的加密密钥，如果交换密钥失败，则重新连接Wi-Fi。当需要进行范围查询时，加密查询区间，将查询命令发送至存储节点，存储节点接收到查询命令后返回对应的查询结果。基站接收查询结果并进行查询结果完整性验证，如果满足验证，则筛选相应数据并在程序界面进行显示，如果不满足验证，则数据出错，结束查询。图6 为基站的程序流程，图7 为基站程序界面，图8 为DH密钥交换过程，图9为感知节点上传数据，其中，data表示数据密文，index 表示加密索引链，comparer 表示最值比较链，图10 是基站范围查询结果，其中，Illuminance 表示光照度，Temperature 表示温度，Atmos表示大气压，Humidity 表示湿度。

图6 基站程序流程Fig.6 Program procedure of base station

图7 基站程序界面Fig.7 Base station program interface

图8 DH 密钥交换过程Fig.8 Process of DH key exchange

图9 感知节点上传数据过程Fig.9 Process of sensing node uploading data

图10 基站范围查询结果Fig.10 Base station range query results

3.5 能耗分析

在感知节点通信过程中，电流做功使得电能转化成其他形式能量，有多少电能转化成其他形式能量即表明电流做了多少功，也即是电功的大小［22-23］。电子元件的电功大小与跟电流的大小、电压的高低和通电时间长短都有关系，有电功公式W=U•I•t，又因为电功率等于电流和电压的乘积P=U•I，可以推导出W=P•t，使用该公式测算感知节点的通信能量消耗。通过纳普电子科技公司研发的PM9816 高精度功率计测量感知节点的通信功率，该功率计的电压量程为0.5～600 V（AC/DC），电流量程为0.05 mA～40 A（AC/DC），功率量程为0.001 mW～24 KW，再在程序中获取感知节点的通信时间，两者相乘即可得到感知节点的通信能量消耗。

3.6 感知节点通信能耗

为描述方便，将本文提出的隐私保护范围查询方法称为优化HMAC 方法。HMAC 加密算法使用HMAC-MD5 算法，Hash 算法中的参数τ=24。

实验1以单个周期采集数据个数N为自变量，其他参数如表1 所示，优化HMAC 方法和CSRQ 方法的通信时间如表2所示，N对能量消耗的影响如图11所示。

表1 实验1 参数Table 1 Parameters of Experiment 1

表2 实验1 通信时间Table 2 Communication time of Experiment 1 s

图11 N 对能量消耗的影响Fig.11 Effect of N on energy consumption

当N增大时，感知节点所需要进行处理的数据增多。CSRQ 方法需要构建比较项和加密约束链，数据增多后需要构建更长的加密约束链，同时需要构建更多的比较项，使得该方法中的加密约束链的长度逐渐增大，比较项逐渐增多，感知节点的能量消耗也逐渐增大。而对于优化HMAC 方法，数据密文是通过对采集数据进行AES 对称加密运算生成，加密索引链则通过对采集数据的数据最值进行AES 对称加密运算生成，最值比较链是通过对采集数据的数据最值进行反向0-1编码和压缩HMAC 算法生成，N的增大只会增加采集数据总量，而不会增加采集数据中数据最值的个数，因而不影响加密索引链以及最值比较链的长度，只影响数据密文的长度。随着N的增大，数据密文长度逐渐增大，加密索引链和最值比较链长度不变，优化HMAC方法通信能耗相比CSRQ 方法降低4.1 倍。

实验2以感知节点数据位数bit 为自变量，其他参数如表3 所示，优化HMAC 方法和CSRQ 方法的通信时间如表4所示，数据位数对能量消耗的影响如图12所示。

图12 数据位数对能量消耗的影响Fig.12 Effect of data digits on energy consumption

表3 实验2 参数Table 3 Parameters of Experiment 2

表4 实验2 通信时间Table 4 Communication time of Experiment 2 s

当数据位数增大时，在CSRQ 方法中加密约束链长度会缓慢增大，同时需要进行处理的数据位数变多，对加密约束链中的约束因子进行计算生成的比较项也会增多，使得通信能耗逐渐增大。而在优化HMAC 方法中，数据密文以及加密索引链都是使用AES 对称加密算法生成，数据密文和加密索引链不需要逐个比特位进行处理，感知节点数据位数增多后，AES 对称加密算法需要进行加密的数据量增大，使得数据密文以及加密索引链的长度缓慢增大，而最值比较链采用了反向0-1 编码，需要对每一个比特位进行处理获取相应的编码结果，感知节点数据位数增多后，得到的编码结果也会随之增多，同时最值比较链使用了压缩HMAC 算法，其中的元素长度得到有效压缩，使得元素长度较短并能完成相应的大小比较功能，最值比较链的长度会逐渐增大。随着数据位数的增大，优化HMAC 方法通信能耗相比CSRQ 方法降低3.5 倍。

实验3以采集数据维度dim 为自变量，其他参数如表5 所示，优化HMAC 方法和CSRQ 方法的通信时间如表6 所示，数据维度对能量消耗的影响如图13所示。

表5 实验3 参数Table 5 Parameters of Experiment 3

表6 实验3 通信时间Table 6 Communication time of Experiment 3 s

图13 数据维度对能量消耗的影响Fig.13 Effect of data dimensions on energy consumption

当数据维度增大时，在CSRQ 方法中需要为每一维度的数据构建加密约束链，同时构建对应的比较项，比较链以及加密约束链的增多使得CSRQ 方法的通信能量消耗逐渐增大。而对于优化HMAC方法，感知节点需要对新增维度的采集数据进行AES 对称加密算法处理，使得数据密文的长度逐渐增大，而加密索引链和最值比较链中只需要对相应维度采集数据的数据最值进行处理，数据最值自身所占字节数较少，经过AES 对称加密算法加密生成新增的加密索引链以及经过反向0-1 编码和压缩HMAC 算法处理生成新增的最值比较链较短，从而有效减少了发送的数据信息，使得通信的能量消耗较低。随着数据维度的增大，优化HMAC 方法的通信能耗相比CSRQ 方法降低2.8 倍。

4 结束语

本文提出一种多维数据的安全高效范围查询方法。在数据上传阶段，感知节点采集数据后构建数据密文，加密索引链得到最值比较链，加密索引链中的数据用于进行数据的完整性验证，最值比较链则用于进行密文形式的大小比较。采用反向0-1 编码和压缩HMAC 算法，能够缩短最值比较链的长度，降低感知节点通信能量消耗。实验结果表明，相比SafeQBloom、QuerySec、SecRQ 和ESRQ 等方法，优化HMAC 方法通信能耗较低，具有良好的安全性和可行性。但本文方法基于强安全模型，主要针对存储节点被俘获的情况，在预防共谋攻击方面，即感知节点与存储节点同时被俘获时仍有不足，下一步将对此进行研究改进。