Low-overhead authentication method for
reprogramming protocol based on rateless codes in
wireless sensor networks
Lina Yang
1,2
, Shining Li
1
, Yu Zhang
1
and Gang Liu
3
1
School of Computer Science and Technology
2
School of Cryptographic Engineering
3
School of Information Science and Engineering
Northwestern Polytechnical University Information Engineering University Henan University of Technology
Xi’an, China Zhengzhou, China Zhengzhou, China
Email: yanglina@mail.nwpu.edu.cn, {lishining, zhangyu}@nwpu.edu.cn, liu2002gang@163.com
Abstract—Over-the-air reprogramming is a key service in
wireless sensor networks. The service can disseminate a new
code image to every sensor node in the network. For security
reasons, every code image must be authenticated to prevent
an attacker from installing its code to the network. In this
paper, an authentication method named Hierarchical Hash Tree
(HHT) is proposed to reduce the overheads of Sreluge, which
is a reprogramming protocol based on rateless codes. HHT is
a composed structure including two layers of Merkle Tree. The
pages from code image are used to construct small hash trees
in bottom. For reducing communication overhead, the roots of
bottom trees are aggregated into root fingerprints, which are used
to build top tree. Then, the security is analysed for proposed
method and mathematical analysis are provided for the HHT
overheads. Furthermore, we implement pages authentication
using HHT in Sreluge. Experimental results show that our method
can cut pages authentication overhead by at least half that of
Sreluge for more than 3-KByte code image. And dissemination
completion time of our method is about 60% that of Sreluge.
Keywords—over-the-air reprogramming; wireless sensor net-
works; Hierarchical Hash Tree; root fingerprints; authentication
overhead
I. INTRODUCTION
Many applications exploit wireless sensor networks
(WSNs) for long term data gathering, ranging from environ-
mental sensing, industry monitoring to military operations, etc.
In fact, the requirements for the network may change in time,
or existing applications need to be modified or patched. Given
the difficulty of physically redeploying sensor nodes, this
requires new code image (a binary file obtained from newly
compiled program) to be securely and remotely disseminated
to all the nodes in the network, which is referred to as over-
the-air reprogramming (OAP).
Recently, rateless codes are used in OAP because they have
no limitation on the rate and are simultaneously near optimal
for every erasure channel, such as Rateless Deluge [1] and
Synapse [2]. The advantage of the reprogramming protocols
using rateless codes is that they are resilient to packet loss. But
an attacker still can pollute encoded packets, thereby executing
the kind of denial-of-service attack known as pollution attack.
Several security schemes [3]–[6] can provide authentication
services to prevent an attacker from installing its code in WSN,
but they work on original data packets. So, these schemes
cannot ensure the security of the reprogramming protocols
based on rateless codes as data packets are transmitted as
encoded packets in the protocols.
For reprogramming protocols based on rateless codes,
several security schemes [7]–[10] have been proposed to resist
pollution attack. One of these schemes referred to as Sreluge
[10] is a secure extension to Rateless Deluge. Sreluge employs
a neighbor classification approach with time series forecasting
and digital signature scheme based on Merkle Tree (MT) to
resist pollution attack. This combinatorial technique can detect
polluters with zero false negative rate and a negligible false
positive rate. In this technique, nodes need to authenticate
obtained pages after decoding encoded packets. When code
image has more pages, the depth of MT is so long that
pages authentication overhead would get very large, where the
overhead is O (N log
2
N). The goal of this paper is to propose
a method to reduce pages authentication overhead for Sreluge
and its implementation is able to ensure the security of OAP.
Our contributions are as follows.
(a) We propose an authentication method referred to
as Hierarchical Hash Tree that is a data structure
composed of two layers of MT to reduce pages
authentication overhead for Sreluge protocol.
(b) We analyse the security of proposed method to
ensure code image securely disseminated to all the
nodes in WSNs.
(c) We analyse theoretically the overheads of HHT.
Analysis results show that HHT authentication over-
head can be reduced to O(N ), in which N is the
number of divided pages from code image.
(d) We implement pages authentication using HHT in
Sreluge. Experimental results show that our method
can cut pages authentication overhead by at least half
that of Sreluge for more than 3-KByte code image.
The remainder of this paper is organized as follows. Section
II discusses related work. Section III gives system model
which this proposal is based on. Section IV describes our
method in detail. Section V analyse the security of code image.
978-1-4799-0959-9/14/$31.00 ©2014 IEEE 881