«CRYPTOGRAPHIC KEY DISTRIBUTION IN WIRELESS SENSOR NETWORKS USING BILINEAR PAIRINGS By Piotr Szczechowiak BEng, MSc THESIS DIRECTED BY: DR. MARTIN ...»
CRYPTOGRAPHIC KEY DISTRIBUTION
IN WIRELESS SENSOR NETWORKS
USING BILINEAR PAIRINGS
THESIS DIRECTED BY:
DR. MARTIN COLLIER AND PROF. MICHAEL SCOTT
A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE
DOCTOR OF PHILOSOPHYDEGREE OF September 2010
FACULTY OF ENGINEERING & COMPUTING
DUBLIN CITY UNIVERSITYI hereby certify that this material, which I now submit for assessment on the programme of study leading to the award of Doctor of Philosophy is entirely my own work, that I have exercised reasonable care to ensure that the work is original, and does not to the best of my knowledge breach any law of copyright, and has not been taken from the work of others save and to the extent that such work has been cited and acknowledged within the text of my work.
ID number: 56124023 Date: 22/09/2010 Abstract t is envisaged that the use of cheap and tiny wireless sensors will soon bring a third I wave of evolution in computing systems. Billions of wireless senor nodes will provide a bridge between information systems and the physical world. Wireless nodes deployed around the globe will monitor the surrounding environment as well as gather information about the people therein. It is clear that this revolution will put security solutions to a great test.
Wireless Sensor Networks (WSNs) are a challenging environment for applying security services. They differ in many aspects from traditional ﬁxed networks, and standard cryptographic solutions cannot be used in this application space. Despite many research efforts, key distribution in WSNs still remains an open problem. Many of the proposed schemes suffer from high communication overhead and storage costs, low scalability and poor resilience against different types of attacks. The exclusive usage of simple and energy efﬁcient symmetric cryptography primitives does not solve the security problem. On the other hand a full public key infrastructure which uses asymmetric techniques, digital signatures and certiﬁcate authorities seems to be far too complex for a constrained WSN environment. This thesis investigates a new approach to WSN security which addresses many of the shortcomings of existing mechanisms. It presents a detailed description on how to provide practical Public Key Cryptography solutions for wireless sensor networks. The contributions to the state-of-the-art are added on all levels of development beginning with the basic arithmetic operations and ﬁnishing with complete security protocols.
This work includes asurvey of different key distribution protocols that have been developed for WSNs, with an evaluation of their limitations. It also proposes IdentityBased Cryptography (IBC) as an ideal technique for key distribution in sensor networks.
It presents the ﬁrst in-depth study of the application and implementation of PairingBased Cryptography (PBC) to WSNs. This is followed by a presentation of the state of the art on the software implementation of Elliptic Curve Cryptography (ECC) on typical WSN platforms. New optimized algorithms for performing multiprecision multiplication on a broad range of low-end CPUs are introduced as well. Three novel protocols for key distribution are proposed in this thesis. Two of these are intended for non-interactive key exchange in ﬂat and clustered networks respectively. A third key distribution protocol uses Identity-Based Encryption (IBE) to secure communication within a heterogeneous sensor network. This thesis includes also a comprehensive security evaluation that shows that proposed schemes are resistant to various attacks that are speciﬁc to WSNs. This work shows that by using the newest achievements in cryptography like pairings and IBC it is possible to deliver affordable public-key cryptographic solutions and to apply a sufﬁcient level of security for the most demanding WSN applications.
• P. SZCZECHOWIAK AND M. SCOTT, Enabling Practical Public Key Cryptography in Wireless Sensor Networks, Research Colloquium on “Wireless as an enabling technology: Innovation for a critical infrastructure”, April 2010, Royal Irish Academy, Committee for Communications and Radio Science
• P. SZCZECHOWIAK, M. SCOTT AND M. COLLIER, Securing Wireless Sensor Networks:
An Identity-Based Cryptography Approach, International Journal of Sensor Networks (IJSNet), Volume 8, Number 4, 2010, Inderscience
• P. SZCZECHOWIAK AND M. COLLIER, TinyIBE: Identity-Based Encryption for Heterogeneous Sensor Networks, in ISSNIP 2009: Proceedings of the 5th International Conference on Intelligent Sensors, Sensor Networks and Information Processing, Melbourne, Australia, December 2009.
• P. SZCZECHOWIAK AND M. COLLIER, Practical Identity-Based Key Agreement for Secure Communication in Sensor Networks, in ICCCN ’09: Proceedings of the 18th International Conference on Computer Communications and Networks, San Francisco, USA, August 2009, pages 1-6, IEEE.
• P. SZCZECHOWIAK, A. KARGL, M. SCOTT AND M. COLLIER, On the Application of Pairing-based Cryptography to Wireless Sensor Networks, in WiSec ’09: Proceedings of the Second ACM Conference on Wireless Network Security, Zürich, Switzerland, March 2009, pages 1-12, ACM.
• P. SZCZECHOWIAK, L.B. OLIVIERA, M. SCOTT, M. COLLIER AND R. DAHAB, NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks, in Wireless Sensor Networks – EWSN 2008, Lecture Notes in Computer Science vol. 4913, pages 305-320, Springer-Verlag, February 2008.
• M. SCOTT AND P. SZCZECHOWIAK, Optimizing Multiprecision Multiplication for Public Key Cryptography, Cryptology ePrint Archive, Report 2007/299, http://eprint.iacr.org/2007/299, August 2007.
CONTENTSList of Publications
4.3 Point multiplication using the ﬁxed-base comb method........... 103
4.4 Elliptic curve Difﬁe-Hellman key exchange protocol in WSNs....... 109
4.5 An example ECDH program based on NanoECC implemented in TinyOS 120
4.6 Voltage levels on Tmote Sky during ECDH protocol............. 122
4.7 Point multiplication timings comparison on MICA2 and Tmote Sky.... 125
4.8 Point multiplication energy comparison on MICA2 and Tmote Sky.... 125
4.9 Point multiplication ROM size comparison on MICA2 and Tmote Sky.. 126
4.10 Point multiplication RAM size comparison on MICA2 and Tmote Sky.. 127
5.1 Pairing timings comparison on MICA2 and Tmote Sky........... 155
5.2 Pairing energy consumption comparison on MICA2 and Tmote Sky.... 156
5.3 Pairing ROM size comparison on MICA2 and Tmote Sky.......... 157
5.4 Pairing RAM size comparison on MICA2 and Tmote Sky.......... 157
A.1 Experimental setup for measuring energy consumption on senor nodes.. 220 A.2 Voltage samples measured on the Tmote Sky node.............. 221
4.1 Operation counts for point addition and doubling.............. 105
4.2 Performance analysis of ECC implementations on sensor motes...... 112
4.3 Cost of point multiplication in basic operations on sensor nodes...... 123
4.4 Performance of point multiplication on the MICA2 mote.......... 123
4.5 Performance of point multiplication on the Tmote Sky node........ 124
5.9 Performance of the Tate pairing on Atmega128 and MSP430........ 152
5.10 Performance of the Tate pairing on the PXA271................ 153
5.11 Performance of the Ate pairing on Atmega128 and MSP430......... 154
5.12 Pairing implementation results on MICA2 and Tmote Sky......... 154
5.13 Pairing implementation results on Imote2................... 155
6.1 ID-based key agreement evaluation on MICAz and Tmote Sky........ 171
6.2 ID-based key agreement evaluation on the Imote2 node........... 171
6.3 Evaluation of the key agreement in cluster-based WSNs........... 178
6.4 Evaluation of the key agreement in cluster-based WSNs........... 178
6.5 TinyIBE evaluation results............................ 186
6.6 Security threats in WSNs and possible defensive measures......... 193
AES Advanced Encryption Standard ALU Arithmetic Logic Unit ANSI American National Standards Institute ARM Advanced RISC Machine ASIC Application Speciﬁc Integrated Circuit BDHP Bilinear Difﬁe-Hellman Problem CCTV Closed Circuit Television CPU Central Processing Unit CRC Cyclic Redundancy Check DES Data Encryption Standard EEPROM Electrically Erasable Programmable Read-Only Memory FPGA Field Programmable Gate Array IEEE Institute of Electrical and Electronics Engineers ISO International Organization for Standardization LEACH Low-Energy Adaptive Clustering Hierarchy LED Light-Emitting Diode LSB Least Signiﬁcant Bit MIRACL Multiprecision Integer and Rational Arithmetic C/C++ Library MSB Most Signiﬁcant Bit NIST National Institute of Standards and Technology
PCB Printed Circuit Board PDA Personal Digital Assistant RAM Random Access Memory RF Radio Frequency RISC Reduced Instruction Set Computer ROM Read Only Memory RSA Rivest-Shamir-Adleman SSL Secure Sockets Layer TDMA Time Division Multiple Access WEP Wired Equivalent Privacy WSN Wireless Sensor Network
oday’s computing systems have evolved much since the 70’s when the ﬁrst perT sonal computers were released. Advances in electronics and circuit miniaturization has brought us to a point where a fully operational computing system can ﬁt on a tip of a ﬁnger. Taking into consideration the size of computers and their numbers, we can easily distinguish three waves in evolution of computing (Fig 1.1). In the beginning computers were very rare and usually operated by few people. The advent of mobile phones and notebook computers has resulted in millions of units sold at the turn of the century. Nowadays, the third wave of evolution is about to happen. Billions of tiny and cheap computing devices deployed around the world will soon gather, analyze and exchange information about the people and the environment they live in. Those pervasive computing devices are not personal computers as we tend to think of them, but very small devices, that will be eventually embedded in almost any type of object imaginable, including cloths, cars, tools, appliances and various consumer goods.
Those tiny devices embed sensors and wireless transceivers to communicate with each other and form distributed networks connected to the Internet. Their main task is to build a bridge between the physical world and the digital world that is displayed on our computer screens. In this way it is possible not only to monitor the physical world but also actuate remotely depending on the measurement data. With advances in this ﬁeld, new intelligent control systems will be available that are completely autonomous and can
act adequately without human supervision.
At the dawn of a new century we are facing new problems that will need deﬁnite solutions in the near future. Our planet’s climate is changing rapidly and we need global and accurate measurement data to better understand what is happening around us. We also need to reduce communication systems costs, and conserve energy and natural resources. Wireless sensors technology brings us a step closer to resolving those (and many more) issues. Sensors can even alert us about incoming natural disasters and help ﬁght against environmental degradation. The emergence of Wireless Sensor Networks (WSNs) is brought about by a convergence of advanced electronic and wireless technologies.
There is no doubt that WSNs will be deployed on a large scale in many different parts of the world. This next generation of computing brings many new challenges not only because we are dealing with very constrained devices, but also because scale really matters here.
The whole WSN paradigm is often described with terms such as “smart dust” , the “internet of things” or “pervasive computing” that will revolutionize the way people live. This revolution, however, can only happen if we ﬁnd the solution to crucial problems of security and privacy in these systems. This is especially important for widespread adoption of WSN technology in many different domains. The range of WSN applications spans from environmental monitoring and home automation to more complex ones like
trafﬁc control and health care. All these applications require various security levels and services. Simple applications like habitat monitoring (e.g ) need only basic security assurances that can be fulﬁlled by using symmetric key systems.
There are also many practical applications, where sensor devices can control the operation of critical equipment, monitor assembly lines and perform condition based monitoring of critical structures. For example, sensor devices are deployed on the Golden Gate Bridge in San Francisco to monitor structure vibrations . The importance of security in such an application justiﬁes the use of a high security level in the network.