On the Performance and Use of a Space-Efficient Merkle Tree Traversal Algorithm in Real-Time Applications for Wireless and Sensor Networks

With the advance of technology, Public key cryptography (PKC) will be used - sooner or later - in wireless and sensor applications not only to provide security services like authentication, integrity and non-repudiation on the data provided, but also to achieve a perfect connectivity and a perfect resilience in large-scale wireless and sensor networks. One of the weak points of PKC is its performance, and because of this reason several authentication approaches use efficient structures, like the Merkle hash trees (MHT), which are combined with the traditional PKC operations to produce secure but also time-efficient authentication solutions.This paper investigates the performance of a popular algorithm for traversal of large MHTs authored by M. Szydlo and demonstrates that several other parameters (not just the CPU processor) need to be taken into consideration when designing applications that use MHTs, like the signing time, the hash time, the depth of the MHT and the space available, since they impact directly on the performance of the overall application. Moreover, we construct two models to simulate the behaviour of a device that uses Szydlo's algorithm to authenticate large amounts of data, like a real-time data flow. We chose Szydlo's algorithm because it saves more space than other MHT traversal algorithms and we assumed that in our case study the space (and not necessarily the CPU power) is the resource to be considered critical.

I. Introduction

We start our work from the following simple case study: assume to design an application for a device with limited space and (optionally) limited computational capabilities, operating in wireless or sensor environment. The application has to send a real-time data flow to several receivers and the data has to be protected against malicious attacks, like modification of the data flow or sender impersonation. This could be the case of a mobile user doing m-commerce transactions over wireless networks, or of a sensor being part of a sensor network, such as for military sensing and tracking, environment monitoring or patient monitoring and tracking.