Summary of TinyECC A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks Presented by Maulin Patel Nov 17 09 CSE291 1 WSN Wireless Sensor Networks Operations Monitoring Monitoring continuously check Base Station DWSN HWSN the status of the environment Alerting Alerting a problematic situation is happening going to happen Querying Querying provide information On Demand Reporting Reporting transmit short report of the environment Others Others autonomous self configurable distributed computing decentralized easily deployable inexpensive Shooter localization And by far the most important threat needing secure communications channel Wireless Sensor Network Drawacks Hardware Software Constrained Typical node specs i e MIZAz 8 Mhz 4KB RAM and 128KB ROM Low patter capacity Low power transceiver e g IEEE 802 15 4 And the most important Specific context of WSN Increases likelihood of of attacks Physical Easy access to the network environment nodes Logical Wireless communication Confidentiality Authenticity Integrity How to protect them Symmetric Key Cryptography SKC Low computation cost Smaller key sizes Public Key Cryptography It provides more security than SKC but it requires a nontrivial amount of processing power and memory Past Imposible to use PKC 2004 2007 Doubt in using Possible to use PKC PKC Future Background on ECC Public key asymmetric cryptosystem Based upon a hard number theoretic problem Elliptic Curve Elliptic Curve Discrete Logarithms ECDLP Given an elliptic curve and points P and Q the curve find K such that Q k P The hardness of ECDL defines the security level of all ECC protocols No sub exponential algorithm known which can solve the ECDLP ECC131p 2 million ECC163p 1 trillion 20 years At the base of ECC operations is finite field Galois Field algebra with focus on prime Galois Fields GF p and binary extension Galois Fields GF 2m ECC Performance Security Size is a function of finite field selection elliptic curve type point representation type algorithms used protocol key size hardware software breakdown memory available code and area Elliptic Curves Elliptic curve over prime field Fp is defined by a cubic equation y2 x3 a x b where a b are an element of Fp such that 4 a3 27 b3 0 To encrypt data a point Q on the chosen curve over the finite field The fundamental encryption operation is a point scalar multiplication i e a point P1 added to itself k times Q k P P P P In order to compute Q a double and add method is used and k is represented in binary form and scanned right to left from LSB to MSB performing a Point double each step and an addition if k i is 1 Will require m 1 Point doublings and an averae of m 1 2 Point additions where m is the bit length of the field prime p Elliptic curve over Finite Fields Fields that contain finite number of elements Number of elements of a finite prime field is pn p is prime number and n is a positive integer Finite Fields Point Addition Point Doubling Point Addition Point Doubling 2 multiplications 1 division and 6 addition subtractions 3 multiplications 1 division 7 addition subtractions Division is the critical operation implemented via inversion followed by multiplication ECC Operations Hierarchy First Level Basic Prime Field Operations Point Add Point Double P Q 2 P Third Level Elliptic Curve point operation Point scalar Multiplication a b mod p a d mob p 1 b mod p a b mod p a b mod p Second level Elliptic Curve point operations GF addition GF multiplication GF inversion GF division GF subtraction fundamental and most time consuming operation in ECC Requires multiple Point additions and Point double operations Various optimization algorithms available which are field type and coordinate representation dependent Fourth Level ECC protocol k P P P P k summands ECDSA ECDH ECIES TinyECC Design Objectives Security Provide security based on known PKC primitives ECSDA ECDH ECIES Defined in Standards for Efficient Cryptography Implements Curve Parameters recommended by SECG a b G base point p Portability Runs on TinyOS on the following platforms MicaZ TelosB Tmote Sky and Imote2 Some modules for MICAz TelosB implement Assembly for faster execution causes TOSSIM to break Resource Awareness and Configurability Optimizations are user configurable via compiler supplied parameters Efficiency Adapt almost all existing optimizations for ECC operations Use prime F fields or binary extension fields F m p 2 Binary field operations are better suited when application specific hardware is available ECC Algorithms Digital Signatures ECDSA Elliptic Curve Digital Signature Algorithm Key Agreement ECDH Elliptic Curve Diffie Hellman Scheme for demonstrating the authenticity of a digital message Provides a sign and verfiy operation analogous to DSA Allows two parties each having an elliptic curve public private key pair to establish a shared secret over an insecure channel Shared secret maybe directly used as a key or to derive another key which will be used to encrypt subsequent communication using a symmetric key cipher Diffie Hellman p qG q pG qG pG are public values p and q are private Encryption ECIES Elliptic Curve Integrated Encryption Standard Uses ECDH to derive a shared key which is then used to derive a symmetric key and a message authentication code used for encryption signing Optimizations for Large Integer Operations Barret Reduction Faster than modular division when reducing various numbers modulo the same number the prime value p many times Useful large numbers Can only reduce numbers that at most twice as long in words as the modulus Store off u floor b k p floor 2 w k p Divisions and modular reductions can be replaced by Right Shifts and AND operations if b is a power of 2 Algorithm http www cosic esat kuleuven be publications article 1115 pdf Hybrid Multiplication p is a prime k words long w is bit with of the word i e 8 for an 8 bit processor Assumes that b k is of the form 2 w Maximizes the utilization of registers and reduces the number of memory load operations intended for assembly code since a set size register bank is needed Algorithm http research sun com people eberle CHES 2004 pdf Hybrid Squaring Takes advantage of the fact that partial products of a number where the ith word position not equal the jth word position occur twice ECC Operations Projective Coordinate Systems 1 Point doubling and 2 Point addition scalar multiplication uses 1 2 are on critical path Sliding Window for Scalar
View Full Document
Unlocking...