by Václav Matyáš and Petr Švenda
Researchers at Masaryk University, Brno, are working on security issues relating to large-scale, highly distributed and relatively dense wireless sensor networks.
In our work we focus on link key establishment in the memory- and computation-restricted environment of wireless sensor networks (WSNs). We also study how link security behaves under a selected attack and what methods can be used to strengthen the resilience of WSNs against compromise. We base our work on the assumption that a partial compromise in WSNs is inevitable and network architecture should be prepared to cope with related security issues. We work with two basic link key establishment concepts based on symmetric cryptography: memory-efficient probabilistic pre-distributions (Eschenauer & Gligor, 2002) and lightweight key exchange without pre-distributed secrets (Anderson et al, 2004). These two key distribution concepts behave differently when the network is attacked. Analysis of the resulting compromised patterns has led to the proposal of mechanisms for improving the network resiliency based on support from neighbouring nodes.
While the resiliency of probabilistic pre-distribution schemes generally increases when more keys can be put into a key ring on every single node, such an increase is limited by the node storage capacity. Our multiparty protocol creates a large virtual key ring in an efficient and secure way from the key rings of separate nodes. This results in a substantial increase in resilience of the underlying probabilistic key pre-distribution scheme against the threat of node capturing. The protocol performs similarly to the hypercube pre-distribution (Liu & Ning, 2003) but is more suitable for scenarios with random deployment and unknown link compromise status. The proposed protocol itself is also resilient against partial compromise inside a group of supporting neighbours.
Our former work exploited non-uniformity of link compromise patterns in key infection, and led to a secrecy amplification (SA) protocol with a significantly better fraction of secure links than previously published SA protocols, especially for denser networks. We applied SA protocols of partially compromised networks resulting from node capture when probabilistic key pre-distribution are used, and provided analytical and simulation evidence that SA protocols work even better here. On average, SA protocols secure more links for probabilistic pre-distribution than for key infection, when networks with the same percentage of initially compromised links are assumed. When the SA protocols are applied, a network with half of its links compromised can be made reasonably secure with less than 10% of compromised links.
Some combinations of SA protocols that worked for key infection do not increase the number of secure links in probabilistic pre-distribution and thus only impose unnecessary communications overhead. Instead of analysing each separate compromise pattern arising from the combination of a particular key distribution method and attacker strategy, we proposed an automated approach based on the combination of a protocol generator and network simulator. We utilize evolutionary algorithms to facilitate guided searches for high-performance SA protocols created as a series of elementary instructions. Every candidate protocol is evaluated on our network simulator for a particular compromise pattern (see Figure 1).
Using this method, we were able to automatically re-invent all the human-designed SA protocols of which we were aware, and to find a new protocol that outperforms these. Moreover, we proposed an alternative construction of SA protocols that exhibits only a linear (instead of exponential) increase in necessary messages when the number of neighbours in the communication range (network density) is growing, and we achieved comparable performance to protocols with original message-expensive assumptions providing energy-efficient SA protocols. With respect to classical human-made protocols, an increase in the number of secure links was obtained by an efficient combination of the simpler protocols and an unconventional interleaving of elementary instructions. These allow protocols to be executed even when one of the participants is out of radio transmission range.
Our current work focuses on the concept of automatic search for attack strategies with demonstrative applications to link key security for probabilistic pre-distribution and key infection approach. New attacks are generated either as a recombination of existing attacks or as completely novel attacks automatically assembled from elementary attacker actions. They are then evaluated on a network simulator or in a real system. Attacker strategies that increase the number of compromised links with respect to several deterministic algorithms or random cases were found. Initial results for attacks against selected routing protocols show good prospects for an automated search for selective jamming, message dropping and neighbour overloading to achieve a specific attacker goal such as increasing routing path length, message latency or concentrating routed messages.
Due to battery power limits and taking into consideration the high communications overhead exposed by current replication detection, the reputation management mechanisms that have been proposed so far are often not affordable. We are currently designing prevention, detection and reaction techniques for the network. Rather than aiming for perfect security, which is particularly hard to achieve in WSNs, the aim is to force attackers to make disadvantageous trade-offs in terms of computational time, energy or other costs. Due to the diversity of usage scenarios, there is a need to develop an economical/mathematical model that would help to find a near-optimal solution for a particular combination of network usage and available resources.
Link:
A technical report covering some of the issues discussed above: http://www.fi.muni.cz/reports/files/2007/FIMU-RS-2007-05.pdf
Please contact:
Václav Matyáš
Masaryk University, Brno - CRCIM, Czech Republic
Tel: +420 549 49 5165
E-mail: matyas
fi.muni.cz
