A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing. <s> BIB001 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> We introduce a new class of public-key functions involving a number n = pq having two large prime factors. As usual, the key n is public, while p and q are the private key used by the issuer for production of signatures and function inversion. These functions can be used for all the applications involving public-key functions proposed by Diffie and Hellman, including digitalized signatures. We prove that for any given n, if we can invert the function y = E (x1) for even a small percentage of the values y then we can factor n. Thus, as long as factorization of large numbers remains practically intractable, for appropriate chosen keys not even a small percentage of signatures are forgeable. Breaking the RSA function is at most hard as factorization, but is not known to be equivalent to factorization even in the weak sense that ability to invert all function values entails ability to factor the key. Computation time for these functions, i.e. signature verification, is several hundred times faster than for the RSA scheme. Inversion time, using the private key, is comparable. The almost-everywhere intractability of signature-forgery for our functions (on the assumption that factoring is intractable) is of great practical significance and seems to be the first proved result of this kind. <s> BIB002 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n . <s> BIB003 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> We discuss the use of elliptic curves in cryptography. In particular, we propose an analogue of the Diffie-Hellmann key exchange protocol which appears to be immune from attacks of the style of Western, Miller, and Adleman. With the current bounds for infeasible attack, it appears to be about 20% faster than the Diffie-Hellmann scheme over GF(p). As computational power grows, this disparity should get rapidly bigger. <s> BIB004 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> We discuss analogs based on elliptic curves over finite fields of public key cryptosystems which use the multiplicative group of a finite field. These elliptic curve cryptosystems may be more secure, because the analog of the discrete logarithm problem on elliptic curves is likely to be harder than the classical discrete logarithm problem, especially over GF(2'). We discuss the question of primitive points on an elliptic curve modulo p, and give a theorem on nonsmoothness of the order of the cyclic subgroup generated by a global point. <s> BIB005 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> The market for Personal Digital Assistants (PDAs) is growing at a rapid pace. An increasing number of products, such as the PalmPilot, are adding wireless communications capabilities. PDA users are now able to send and receive email just as they would from their networked desktop machines. Because of the inherent insecurity of wireless environments, a system is needed for secure email communications. The requirements for the security system will likely be influenced by the constraints of the PDA, including limited memory, limited processing power, limited bandwidth, and a limited user interface. ::: ::: This paper describes our experience with porting PGP to the Research in Motion (RIM) two-way pager, and incorporating elliptic curve cryptography into PGP's suite of public-key ciphers. Our main conclusion is that PGP is a viable solution for providing secure and interoperable email communications between constrained wireless devices and desktop machines. <s> BIB006 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> Strong public-key cryptography is often considered to be too computationally expensive for small devices if not accelerated by cryptographic hardware. We revisited this statement and implemented elliptic curve point multiplication for 160-bit, 192-bit, and 224-bit NIST/SECG curves over GF(p) and RSA-1024 and RSA-2048 on two 8-bit microcontrollers. To accelerate multiple-precision multiplication, we propose a new algorithm to reduce the number of memory accesses. <s> BIB007 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> The common perception of public key cryptography is that it is complex, slow and power hungry, and as such not at all suitable for use in ultra-low power environments like wireless sensor networks. It is therefore common practice to emulate the asymmetry of traditional public key based cryptographic services through a set of protocols [1] using symmetric key based message authentication codes (MACs). Although the low computational complexity of MACs is advantageous, the protocol layer requires time synchronization between devices on the network and a significant amount of overhead for communication and temporary storage. The requirement for a general purpose CPU to implement these protocols as well as their complexity makes them prone to vulnerabilities and practically eliminates all the advantages of using symmetric key techniques in the first place. In this paper we challenge the basic assumptions about public key cryptography in sensor networks which are based on a traditional software based approach. We propose a custom hardware assisted approach for which we claim that it makes public key cryptography feasible in such environments, provided we use the right selection of algorithms and associated parameters, careful optimization, and low-power design techniques. In order to validate our claim we present proof of concept implementations of two different algorithms—Rabin’s Scheme and NtruEncrypt—and analyze their architecture and performance according to various established metrics like power consumption, area, delay, throughput, level of security and energy per bit. Our implementation of NtruEncrypt in ASIC standard cell logic uses no more than 3,000 gates with an average power consumption of less than 20 μW. We envision that our public key core would be embedded into a light-weight sensor node architecture. <s> BIB008 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> Elliptic curves also figured prominently in the recent proof of Fermat's Last Theorem by Andrew Wiles. Originally pursued for purely aesthetic reasons, elliptic curves have recently been utilized in devising algorithms for factoring integers, primality proving, and in public-key cryptography. In this article, we aim to give the reader an introduction to elliptic curve cryptosystems, and to demonstrate why these systems provide relatively small block sizes, high-speed software and hardware implementations, and offer the highest strength-per-key-bit of any known public-key scheme. <s> BIB009 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> Wireless networks of miniaturized, low-power sensor/actuator devices are poised to become widely used in commercial and military environments. The communication security problems for these networks are exacerbated by the limited power and energy of the sensor devices. In this paper, we describe the design and implementation of public-key-(PK)-based protocols that allow authentication and key agreement between a sensor network and a third party as well as between two sensor networks. Our work is novel in that PK technology was commonly believed to be too inefficient for use on low-power devices. As part of our solution, we exploit the efficiency of public operations in the RSA cryptosystem and design protocols that place the computationally expensive operations on the parties external to the sensor network, when possible. Our protocols have been implemented on UC Berkeley MICA2 motes using the TinyOS development environment. <s> BIB010 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> We present the first known implementation of elliptic curve cryptography over F/sub 2p/ for sensor networks based on the 8-bit, 7.3828-MHz MICA2 mote. Through instrumentation of UC Berkeley's TinySec module, we argue that, although secret-key cryptography has been tractable in this domain for some time, there has remained a need for an efficient, secure mechanism for distribution of secret keys among nodes. Although public-key infrastructure has been thought impractical, we argue, through analysis of our own implementation for TinyOS of multiplication of points on elliptic curves, that public-key infrastructure is, in fact, viable for TinySec keys' distribution, even on the MICA2. We demonstrate that public keys can be generated within 34 seconds, and that shared secrets can be distributed among nodes in a sensor network within the same, using just over 1 kilobyte of SRAM and 34 kilobytes of ROM. <s> BIB011 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> We introduce TinySec, the first fully-implemented link layer security architecture for wireless sensor networks. In our design, we leverage recent lessons learned from design vulnerabilities in security protocols for other wireless networks such as 802.11b and GSM. Conventional security protocols tend to be conservative in their security guarantees, typically adding 16--32 bytes of overhead. With small memories, weak processors, limited energy, and 30 byte packets, sensor networks cannot afford this luxury. TinySec addresses these extreme resource constraints with careful design; we explore the tradeoffs among different cryptographic primitives and use the inherent sensor network limitations to our advantage when choosing parameters to find a sweet spot for security, packet overhead, and resource requirements. TinySec is portable to a variety of hardware and radio platforms. Our experimental results on a 36 node distributed sensor network application clearly demonstrate that software based link layer protocols are feasible and efficient, adding less than 10% energy, latency, and bandwidth overhead. <s> BIB012 </s> A survey of security issues in wireless sensor networks <s> PUBLIC KEY CRYPTOGRAPHY IN WSNS <s> In this paper, we quantify the energy cost of authentication and key exchange based on public-key cryptography on an 8-bit microcontroller platform. We present a comparison of two public-key algorithms, RSA and elliptic curve cryptography (ECC), and consider mutual authentication and key exchange between two untrusted parties such as two nodes in a wireless sensor network. Our measurements on an Atmel ATmega128L low-power microcontroller indicate that public-key cryptography is very viable on 8-bit energy-constrained platforms even if implemented in software. We found ECC to have a significant advantage over RSA as it reduces computation time and also the amount of data transmitted and stored. <s> BIB013
Many researchers believe that the code size, data size, processing time, and power consumption make it undesirable for public key algorithm techniques, such as the Diffie-Hellman key agreement protocol BIB001 or RSA signatures BIB003 Public key algorithms such as RSA are computationally intensive and usually execute thousands or even millions of multiplication instructions to perform a single security operation. Further, a microprocessor's public key algorithm efficiency is primarily determined by the number of clock cycles required to perform a multiply instruction  . Brown et al. found that public key algorithms such as RSA usually require on the order of tens of seconds and up to minutes to perform encryption and decryption operations in constrained wireless devices which exposes a vulnerability to DoS attacks BIB006 . On the other hand, Carman et al. found that it usually takes a microprocessor thousands of nano-joules to do a simple multiply function with a 128 bit result  . In contrast, symmetric key cryptography algorithms and hash functions consume much less computational energy than public key algorithms. For example, the encryption of a 1024-bit block consumes approximately 42 mJ on the MC68328 DragonBall processor using RSA, while the estimated energy consumption for a 128 bit AES block is a much lower at 0.104 mJ  . Recent studies have shown that it is feasible to apply public key cryptography to sensor networks by using the right selection of algorithms and associated parameters, optimization, and low-power techniques BIB007 BIB013 BIB008 . The investigated public key algorithms include Rabin's Scheme BIB002 , NtruEncrypt  , RSA BIB003 , and Elliptic Curve Cryptography (ECC) BIB004 BIB005 . Most studies in literature focus on RSA and ECC algorithms. The attraction of ECC is that it appears to offer equal security for a far smaller key size, thereby reducing processing and communication overhead. For example, RSA with 1024 bit keys (RSA-1024) provides a currently accepted level of security for many applications and is equivalent in strength to ECC with 160 bit keys (ECC-160) [38] . To protect data beyond the year 2010, RSA Security recommends RSA-2048 as the new minimum key size which is equivalent to ECC with 224 bit keys (ECC-224)  . Table  3 summarizes the execution time of ECC and RSA implementations on an Atmel ATmega128 processor (used by Mica2 mote) BIB007 . The execution time is measured on average for a point multiplication in ECC and a modular exponential operation in RSA. ECC secp160r1 and secp224r1 are two standardized elliptic curves defined in [40] . As shown in Table 3 , by using the small integer e = 2 16 + 1 as the public key, RSA public key operation is slightly faster than ECC point multiplication. However, ECC point multiplication outperforms RSA private key operation by an order of magnitude. The RSA private key operation, which is too slow, limits its use in a sensor node. ECC has no such issues since both the public key operation and private key operation use the same point multiplication operations. Wander et al. investigated the energy cost of authentication and key exchange based on RSA and ECC cryptography on an Atmel ATmega128 processor BIB013 . The result is shown in Table 4 . The ECC-based signature is generated and verified using the Elliptic Curve Digital Signature Algorithm (ECDSA) BIB009 . The key exchange protocol is a simplified version of the SSL handshake, which involves two parties: a client initiating the communication and a server responding to the initiation  . The WSN is assumed to be administered by a central point with each sensor having a certificate signed by the central point's private key using a RSA or ECC signature. In the handshake process, the two parties verify each other's certificate and negotiate the session key to be used in the communication. As Table 4 shows, in comparison with RSA cryptography at the same security level, ECDSA signatures are significantly cheaper than RSA signatures and ECDSA verifications are within reasonable range of RSA verifications. Further, the ECC-based key exchange protocol outperforms the RSA-based key exchange protocol at the server side, and there is almost no difference in the energy cost for these two key exchange protocols at the client side. In addition, the relative performance advantage of ECC over RSA increases as the key size increases in terms of the execution time and energy cost. Tables 3 and 4 indicate that ECC is more appropriate than RSA for use in sensor networks. The implementation of RSA and ECC cryptography on Mica2 motes further proved that a public key based protocol is viable for WSNs. Two modules, TinyPK BIB010 , based on RSA, and TinyECC  , based on ECC, have been designed and implemented on Mica2 motes using the TinyOS development environment. Similar work was also conducted by Malan et al. on ECC cryptography using a Mica2 mote BIB011 . In their work, ECC was used to distribute a single symmetric key for the link-layer encryption provided by the TinySec module BIB012 . While public key cryptography may be possible in sensor nodes, the public key operations are still expensive. The assumptions in BIB008 BIB011 may not be satisfied in some applications. For example, the work in BIB008 BIB011 concentrated on the public key operations only, assuming the private key operations will be performed by a base station or a third party. By selecting appropriate parameters, for example, using the small integer e = 2 16 + 1 as the public key, the public key operation time can be extremely fast while the private key operation time does not change. The limitation of private key operation nTable 3. Public key cryptography: average ECC and RSA execution times (Source: BIB007 occurring only at a base station makes many security services using public key algorithms not available under these schemes. Such services include peer-to-peer authentication and secure data aggregation. In contrast, Tables 5 and 6 show the execution time and energy cost of two symmetric cryptography protocols on an Atmel ATmega128 processor. In Table 5 , the execution time was measured on a 64 bit block using a 80 bit key. From the table we can see that symmetric key cryptography is faster and consumes less energy as compared to public key cryptography. In the next section we focus on symmetric key cryptography.