Security protocols in sensor networks: Difference between revisions

From
Jump to navigation Jump to search
No edit summary
No edit summary
Line 32: Line 32:
</tr>
</tr>
</table>
</table>
<br>

Sensors form a self-organizing wireless network with a multihop routing topology. A prototype network consists of a couple of nodes and a more powerful base station.
Sensors form a self-organizing wireless network with a multihop routing topology. A prototype network consists of a couple of nodes and a more powerful base station.
The base station is connected to an outside network. Small batteries work as the energy source for the nodes.
The base station is connected to an outside network. Small batteries work as the energy source for the nodes.
Line 122: Line 122:
This protocol is used to authenticate the origin of received data. &micro;TESLA introduces asymmetry through a delayed (symmetric) key disclosure.
This protocol is used to authenticate the origin of received data. &micro;TESLA introduces asymmetry through a delayed (symmetric) key disclosure.
It requires that base station and nodes are loosely time synchronized and each node knows an upper bound on maximum synchronization error.
It requires that base station and nodes are loosely time synchronized and each node knows an upper bound on maximum synchronization error.
For authenticated packets, the base station computes a mac with a (at this time) secret key. A node can verify that the mac key was not yet disclosed
For authenticated packets, the base station computes a mac with a (at this time) secret key. A node can verify that the mac key was not yet disclosed based on the clock, synchronization error and time schedule) and stores the packet in buffer.
At the time of the key disclosure, the base station broadcasts the verification key to all receivers, which can then verify the correctness of the key and authenticate the packets in buffer.
(based on the clock, synchronization error and time schedule) and stores the packet in buffer.
At the time of the key disclosure, the base station broadcasts the verification key to all receivers, which can then verify the correctness of
the key and authenticate the packets in buffer.


Each mac key is part of a key chain generated by a public one-way function F. The sender chooses the last key of the chain randomly and repeatedly applies F to compute all other keys:
Each mac key is part of a key chain generated by a public one-way function F. The sender chooses the last key of the chain randomly and repeatedly applies F to compute all other keys:
Line 143: Line 141:
current time, a key of the key chain used in a past interval, starting time of interval i, duration of a time interval and the disclosure delay.
current time, a key of the key chain used in a past interval, starting time of interval i, duration of a time interval and the disclosure delay.


*4. Authenticating broadcast packets: The receiver needs to be sure that a packet is safe (not altered), i.e. the sender did not yet disclose
*4. Authenticating broadcast packets: The receiver needs to be sure that a packet is safe (not altered), i.e. the sender did not yet disclose the key used to compute the mac of an incoming packet. Unsafe packets will be dropped. For safe packets, first the newly received keys, then the packets have to be authenticated. The old key will be replaced with the new key.
the key used to compute the mac of an incoming packet. Unsafe packets will be dropped. For safe packets, first the newly received keys,
then the packets have to be authenticated. The old key will be replaced with the new key.


*5. Nodes broadcasting authenticated data:
*5. Nodes broadcasting authenticated data:
Line 155: Line 151:


==Implementation==
==Implementation==
A subset of RC5 from OpenSSL is used for the block cipher (several others were evaluated but not found useful (AES Rijndael, TEA, DES block cipher)).
The mac function is also used as pseudo-random number generator with a secret key X<sub>rand</sub> and counter C, so that the C-th pseudo random block is generated by MAC(X<sub>rand</sub>,C).


==Evaluation==
==Evaluation==
*Code size and performance:
The first table compares the code size of the most important functions for the original, the fastest and
the smallest implementation. The second table compares the computing time for the same function in the fastest
and the smallest implementation.

<table border=1>
<tr>
<td>Version</td><td>Total Size</td><td>MAC</td><td>Encrypt</td><td>Key setup</td>
</tr>
<tr>
<td>Smallest</td><td>1580</td><td>580</td><td>402</td><td>598</td>
</tr>
<tr>
<td>Fastest</td><td>1844</td><td>728</td><td>518</td><td>598</td>
</tr>
<tr>
<td>Original</td><td>2674</td><td>1210</td><td>802</td><td>686</td>
</tr>
</table>
<br>
<table border=1>
<tr>
<td>Operation</td><td>Time in ms (fast impl.)</td><td>Time in ms (small impl.)</td>
</tr>
<tr>
<td>Encrypt</td><td>1.10</td><td>1.69</td>
</tr>
<tr>
<td>MAC</td><td>1.28</td><td>1.63</td>
</tr>
<tr>
<td>Key setup</td><td>3.92</td><td>3.92</td>
</tr>
</table>
<br>
*Performance: At a transmission rate of 10kbps key setup, encryption and MAC can be performed for every message to send.
With a key disclosure after 2 intervals, a maximum of two key setup operations and two CTR encryptions is needed
to check validity of a disclosed key. Additionally two key setup operations, two CTR encryptions and up to four MAC
operations are needed to check the integrity of a message. That gives an upper bound of 17.8ms for checking
buffered messages. This shows that the limiting factor is the amount of buffering. The more messages can be bufferd,
the more computing time is available for the functions.<br>
The base station - being the centre for communication and holding master keys, counter and key chain - is also
the bottleneck for performance and security. Thus it should be placed in a secure location.

*Energy costs: Most costs come from the extra transmission by the protocols (71% data transmission,
20% MAC transmission (8 byte per packet), 7% nonce transmission, 2% MAC and encryption computation).
This shows that the computational overhead is much lower than the transmission overhead.
There are some remaining security issues like DoS attacks (jamming channel with strong signal),
compromised sensors, key agreement, digital signatures (limited resources) and information leakage,
which were not being dealt with in the paper.

==Conclusion==
Security in sensor networks is possible in a limited way, but it requires resources and generates overhead,
which shortens the overall lifetime of the network.


==References==
==References==
*Adrian Perrig, Robert Szewczyk, J.D. Tygar, Victor Wen, David E. Culler: SPINS – Security Protocols for Sensor Networks
*http://de.wikipedia.org

Revision as of 10:39, 22 February 2005

Work in progress!

Applications for sensor networks

Sensor networks can become useful in a variety of applications:

  • Emergency response information: Sensors can collect information about status of buildings, people and transportation pathways.
  • Energy management: We can achieve a better management through optmizied distribution depending on the ambient and immediate temperature of the wire (see California 2001).
  • Medical monitoring: Sensors can monitor health conditions and be used to apply remedies (instant release of medication to the bloodstream).
  • Logistics and inventory management: Sensors can help to manage the worldwide distribution of goods or even the inventory management in a single store.

Limits of sensor networks

Characteristics of a sensor node:

CPU8-bit, 4MHz
Storage8 kbytes instruction flash
512 bytes ram
512 bytes EEPROM
Communication916MHz radio
Bandwith10kbps
Operating SystemTinyOS
OS Code space3500 bytes
Available code space4500 bytes


Sensors form a self-organizing wireless network with a multihop routing topology. A prototype network consists of a couple of nodes and a more powerful base station. The base station is connected to an outside network. Small batteries work as the energy source for the nodes. Since wireless communication is the most energy consuming function we need to minimize communication overhead, while the security has to be limited in the consumption of processing power. Most current secure algorithms are impractical to use since the working memory of a node cannot even hold variables for asymmetric algorithms like RSA with 1024 bits. Furthermore authenticated broadcast with existing protocols generates high communication overhead of 50-1000 bytes per packet. Usual packets in sensor networks are just about 30 bytes long.

System assumptions

  • Communication architecture:

Broadcast is the fundamental primitive. Sensor nodes establish a routing forest with a base station as root of each tree. Routing beacons are used to form a routing topology. Nodes are able to forward messages towards the base station, they can handle the broadcasting of messages, and recognize packets that are adressed to itself. The base station accesses the nodes frequently and has capabilities similar to nodes, but sufficient battery power to surpass the lifetime of all sensor nodes, sufficient memory to store cryptographic keys, and means for communicating with outside networks. There are three communication pattern: node to base station, base station to node, base station to all nodes (beacons, reprogramming etc.).

  • Trust requirements:

We assume that individual sensors are untrusted. Basic wlan communication is not secure (eavesdropping, messageinjection, messagereplaying), so that we do not trust the communication infrastructure. All nodes initially trust the base station and each node trusts itself. Which means it trusts the local clock to be accurate with small drift. The goal is a key setup so that the compromise of a node does not spread in the network.

Design guidelines

Due to the limited program store all cryptographic primitives (encryption, mac, hash, random number generator) will be constructed out of a single block cipher for code reuse.

  • Requirements for sensor network security:

1. Data confidentiality:The message content is not readable for an adversary. The standard approach to keep sensitive data secret is data encryption with a secret key.
2. Data authentication:This allows the receiver to verify that the data was really sent by the claimed sender. Therefore sender and receiver share a secret key to compute a mac (message authentication code). The needed asymmetric mechanism will be introduced by a delayed key disclosure and a one-way-function key chain.
3. Data integrity:This ensures the receiver that the received data was not altered in transit. Data integrity is achieved through data authentication.
4. Data freshness:Freshness implies that data is recent and ensures no replaying of old messages (strong vs. weak freshness).


SPINS

SPINS (security protocols for sensor networks) consist of two building blocks:

  • SNEP: The sensor network encryption protocol, which provides secure point-to-point communication.
  • µTESLA: The micro timed efficient stream loss-tolerant authentication, which provides broadcast authentication.

SNEP

This protocol provides data confidentiality, two-party data authentication, integrity, freshness and semantic security and replay protection. Semantic security means that an eavesdropper has no information about the plaintext even if he is seeing multiple encryptions of the same plaintext. SNEP uses symmetric cryptography with one cryptographic function (RC5) for: encryption, decryption, mac, pseudo random number generation and the hash function.

  • Key generation:

Nodes and base station share a master secret key, which is defined before running the network, and derive independent keys for encryption, mac and pseudo-number generator using a pseudo-random function:

Encryption keys KAB=FX(1) and KBA=FX(3)
MAC keys K'AB=FX(2) and K'BA=FX(4)
PNG key Krand=FX(5)

To minimize energy costs, two counters are shared by node and base station, so that there is no need to send them with messages. If messages get lost try, we can try the next few counter values or else have to synchronize the counter values (counter exchange protocol).

  • Data authentication and data integrity:

For authentication a message authentication code (mac) is used. In this case it is a cbc-mac (cbc == cipher block chaining: each block of plaintext is xored with the previous ciphertext block before encryption). For encrypted messages the counter will be included in the mac. This provides freshness, replay protection and confidentiality. The encrypted data has the following format:

A -> B: {D}KAB, CA, MAC(K'AB, CA||{D}KAB, CA)

where D is the encrypted data (in counter mode), K the encryption key, K' the mac encryption key and C the counter.

With authentication only the message has the following format:

A -> B: D, MAC(K'AB,D)

  • Strong freshness:

This will be achieved through a nonce (number used once), which is included in a request message. The receiver responds and includes the nonce in a mac:

A -> B: NA, RA where N is a nonce and R the request
B -> A: {RB}(KBA, CB), MAC(K'BA, NA||CB||{RB}(KBA, CB))

If the mac verifies correctly, node A knows that node B generated the response after it sent the request.

  • Counter exchange protocol:

This protocol is needed in case of lost messages and an inconsistent state of the shared counters. Getting the counter values initially looks like this:

A -> B: CA B -> A: CB, MAC(K'BA,CA || CB) A -> B: MAC(K'AB,CA || CB)

For synchronization the following messages will be sent:

A -> B: NA B -> A: CB, MAC(K'BA, NA||CB)

Nodes can switch to sending the counter (or another short mac) with each message to avoid potential DoS attacks.

µTESLA

This protocol is used to authenticate the origin of received data. µTESLA introduces asymmetry through a delayed (symmetric) key disclosure. It requires that base station and nodes are loosely time synchronized and each node knows an upper bound on maximum synchronization error. For authenticated packets, the base station computes a mac with a (at this time) secret key. A node can verify that the mac key was not yet disclosed based on the clock, synchronization error and time schedule) and stores the packet in buffer. At the time of the key disclosure, the base station broadcasts the verification key to all receivers, which can then verify the correctness of the key and authenticate the packets in buffer.

Each mac key is part of a key chain generated by a public one-way function F. The sender chooses the last key of the chain randomly and repeatedly applies F to compute all other keys:

Ki=F(Ki+1)

It is assumed that a node knows K0 (this is a commitment to the key chain).

Phases in µTESLA:

  • 1. Sender setup: The sender generates secret keys (one-way key chain) using Function F. Since F is a one-way function, nobody can compute forward

(e.g. K0 to Kj given Kj+1)

  • 2. Broadcasting authenticated packets: Each key is associated with a time interval. The sender computes a mac using the key of the current interval.

The key is revealed in interval i+d, where d is a delay in order of a few time intervals.

  • 3. Bootstrapping a new receiver: The receiver sends a nonce in a request message. The sender replies with a message containing its

current time, a key of the key chain used in a past interval, starting time of interval i, duration of a time interval and the disclosure delay.

  • 4. Authenticating broadcast packets: The receiver needs to be sure that a packet is safe (not altered), i.e. the sender did not yet disclose the key used to compute the mac of an incoming packet. Unsafe packets will be dropped. For safe packets, first the newly received keys, then the packets have to be authenticated. The old key will be replaced with the new key.
  • 5. Nodes broadcasting authenticated data:

Nodes can't store the key chain, and the recomputing of keys is too expensive. Furthermore a node might not share a key with each receiver. Broadcasting the disclosed keys to all receivers also costs more energy. Two possible solutions are:

1) node broadcasts data through base station
2) node broadcasts data, but base station keeps key chain and sends keys to broadcasting node as needed

Implementation

A subset of RC5 from OpenSSL is used for the block cipher (several others were evaluated but not found useful (AES Rijndael, TEA, DES block cipher)). The mac function is also used as pseudo-random number generator with a secret key Xrand and counter C, so that the C-th pseudo random block is generated by MAC(Xrand,C).

Evaluation

  • Code size and performance:

The first table compares the code size of the most important functions for the original, the fastest and the smallest implementation. The second table compares the computing time for the same function in the fastest and the smallest implementation.

VersionTotal SizeMACEncryptKey setup
Smallest1580580402598
Fastest1844728518598
Original26741210802686


OperationTime in ms (fast impl.)Time in ms (small impl.)
Encrypt1.101.69
MAC1.281.63
Key setup3.923.92


  • Performance: At a transmission rate of 10kbps key setup, encryption and MAC can be performed for every message to send.

With a key disclosure after 2 intervals, a maximum of two key setup operations and two CTR encryptions is needed to check validity of a disclosed key. Additionally two key setup operations, two CTR encryptions and up to four MAC operations are needed to check the integrity of a message. That gives an upper bound of 17.8ms for checking buffered messages. This shows that the limiting factor is the amount of buffering. The more messages can be bufferd, the more computing time is available for the functions.
The base station - being the centre for communication and holding master keys, counter and key chain - is also the bottleneck for performance and security. Thus it should be placed in a secure location.

  • Energy costs: Most costs come from the extra transmission by the protocols (71% data transmission,

20% MAC transmission (8 byte per packet), 7% nonce transmission, 2% MAC and encryption computation). This shows that the computational overhead is much lower than the transmission overhead. There are some remaining security issues like DoS attacks (jamming channel with strong signal), compromised sensors, key agreement, digital signatures (limited resources) and information leakage, which were not being dealt with in the paper.

Conclusion

Security in sensor networks is possible in a limited way, but it requires resources and generates overhead, which shortens the overall lifetime of the network.

References

  • Adrian Perrig, Robert Szewczyk, J.D. Tygar, Victor Wen, David E. Culler: SPINS – Security Protocols for Sensor Networks
  • http://de.wikipedia.org