October 2nd, 2007 at 08:05 UTC by Dan Cvrcek
When we want to check freshness of cryptographically secured messages, we have to use monotonic counters, timestamps or random nonces. Each of these mechanisms increases the complexity of a given system in a different way. Freshness based on counters seems to be the easiest to implement in the context of ad-hoc mesh wireless networks. One does not need to increase power consumption for an extra message for challenge (containing a new random number), nor there is need for precise time synchronisation. It sounds easy but people in the real world are … creative. We have been working with TinyOS, an operating system that was designed for constrained hardware. TinyOS is a quite modular platform and even mesh networking is not part of the system’s core but is just one of the modules that can be easily replaced or not used at all.
TinyOS is a system quite extensively used in current sensor networks based on 802.15.4 networking. It is an open source system that has also been used by several vendors of hardware motes (Crossbow, Ivmote, Intel). The vendors usually just add support for new hardware platforms, tune it a bit, and add new functionality that would sell the products. We (Matt Lewis, Frank Stajano, and myself) have been analysing these systems for a few months and one interesting security issue we found was related to counters.
There is one well known cryptographic library for these systems – TinySec (PDF). TinySec was implemented for MICA2 motes in 2003 and has not been changed since. What a surprise, it does not work with 802.15.4 radio chips. We have closely analysed TinySec, as we needed some cryptographic support for new motes and we have realised in due course that there are counters in frames, but they are used in a weird way.
Each encrypted message in a mesh network contains not fewer than three counters. There is an 8 bit counter (let’s call it counter A) in the MAC header, there is a 16 bit counter (counter B) as part of initialisation vector for CBC cipher mode, and there is another 16 bit message counter (counter C) used by routing algorithms. Each mote in the network replaces counters in received messages with its own counter values before it forwards them on.
So what is wrong? Well, counter A is used by the radio chip driver for ACK frames. The format of the message is changed by the radio chip driver to the original TinyOS format – i.e., counter A is lost. It can not be used for any purpose other than matching the sent frame with the received ACK frame. (Counter A and its 8 bit size comes from 802.15.4 specification so it may be an interesting point to find out how difficult it is to make a mote believe that its message has been successfully received by a neighbour.)
Counter B is incremented with every encrypted message sent by the mote to ensure unique IV. Unfortunately, the receiving mote does not remember previous values of received counter values and can not check whether the value of the counter is monotonically increasing! What does it mean? In a nutshell, there is no freshness ensured by this counter.
Counter C is used for routing, primarily to evaluate quality of links. Each mote stores the last seen value of the counter from all of its neighbours. Let X be the stored value and Xi the counter value in the new message. If Xi>X then everything is fine and we can even detect the number of dropped messages (Xi-X-1). If Xi+K > X than the message is just dropped. K is a predefined constant and it might probably be used to tune stability of the network (reflections?). If Xi+K < X, not only the message would be dropped but all routing information about its sender would be erased. A simplistic view on security could be that using counter B and counter C together could provide some sort of security:
- counter B – providing protection against cryptanalytic attacks
- counter C – providing protection against replay attacks
There is, however, a big problem that lies between the two counters B and C. Counter C would be used to verify freshness of the message but the main goal of the routing (and existence of counter C) is to keep the network connected – not secure. Inconsistency in the counter value does not mean ATTACK but, rather, that there was an ERROR. The routing algorithm will therefore not try to isolate the misbehaving mote but fix the problem and reconnect the mote – by erasing any previous information and pretending that the mote has just appeared.
This fully uncovers the most realistic security issue related to use of a shared key. Replay attacks eavesdropping frames in one place and injecting them in another place within the network. Moreover, the use of TinySec is not able (even if it used pairwise keys and not a common key for the whole network) to guarantee authenticity / freshness of messages and may (well, it does) allow development of further attacks.