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.
Fig.: Structures of TinyOS and TinySec frames with all the counters. TinySec increases length of “data” field to store initialisation vector.
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.
In designing SDP1, a datagram encryption layout, Zooko and I hassled over the IV issue at great length.
The main problem is that all of the classical cryptography suggestions have implementation-side weaknesses. In short, one answer is an implementation-robust solution. We chose to embed into the IV an incrementing counter, a time, and a random. As well, logically, there is a session number in the IV. Then, there is a dosage of advice on how to watch each of these in the implementation in order to get a balance between architectural issues and a decent IV.
The ball is in the implementor’s court: e.g., if keeping an incrementing counter is unlikely because of needs for atomic storage, you can skip it, but keep the time and random elements.
On the issue of replay protection. At a packet level, it is possibly not the right place for it. As the higher layers are at liberty to do their own replays, it is maybe better to kick replay protection upstairs, and cover more forms of replay protection than just an external attacker.
If you read the TinySec paper again, we explicitly omit replay protection as a goal. Our thinking was along the lines of lang’s comment above — we believe replay protection is better handled at the app layer.
Also, I’m confused by your analysis a bit. It seems to implicitly assume TinySec is being used with the TinyOS packet format designed for the 802.15.4 radio. TinySec was designed for Mica2 motes, which used a different packet format. We never proposed using TinySec with the 802.15.4 radio stack or the newer packet format. See the paper for the Mica2 TinyOS packet format.
Please let me know if I’ve misinterpreted any of your work.
[:to ckarlof] I should start with a basic statement that I wanted to demonstrate difficulties one encounters when security depends on more than one independent modules of a complex system.
Let me make a few points and please, do dispute them. I am very interested in your opinion.
1. One thing is your paper and completely different is how people understand security in sensor networks based on TinyOS. TinySec is the only widely known mechanism / library that may provide cryptographic protection. My analysis is not that much about theory but about security engineering.
2. I believe that many people do not realise that there may be a problem once TinySec is used. I tried to show some problems that are related to the use of a single common key – assuming that the attacker does not get hold of that key! (Something quite unusual for research in sensor networks.)
3. You did not try to solve key management – quite understandably – but the problem does not disappear and one has to deal with it somehow. Your paper says “…implementation is included in the current TinyOS public release and is available for routine use as well.” (what key management will be deployed in “routine use”?). I cannot see a way how pairwise keys could be used in dynamic multi-hop networks at all – more realistic solution is to use end-to-end keys.
4. You rightly say that your library was for Mica2 motes but even there, I’m missing support for replay protection and for multi-hop routing in general. It seems to me that decision not to check IV of incoming frames and not to use counter for unencrypted frames was done in favour of lower overhead and not security and I’m not sure it was the right decision. TinySec does check MAC and offers result of this test to the application. Could this be done with IV/counters? I think that yes. I am also tempted to say, given 2. and 3., that “routine use” has been let down a bit.
5. Let the application do the difficult stuff? I do not see a strong reason for this because TinySec brings in serious limitations for crypto protection in the form of short IVs and MACs. Beside that, TinySec does not allow replays as the counter value in the IV is incremented with each new sent message. Iang also says about SDP1 “[there is] dosage of advice on how to watch each of these [freshness indicators]…” but the same cannot be done with TinySec because the IV is not exported with the message out of the module – application can not do anything even if it wanted to.
6. I do think that TinySec has been a great think – as an academic work at least. The problem is that it has become a commonly used mechanism and as such, the engineering issues became even more important than ideas – the weakest link was not only shifted somewhere else but also blurred a bit.
It is odd that TinySec mandates a (predictable) counter for the IV used in CBC-mode encryption; it is known (and easy to see) that this is not semantically secure.
One can argue whether this leads to a vulnerability in practice, but the TinySec paper specifically lists semantic security as a goal, and also (mistakenly) claims that CBC is semantically secure as long as IV-reuse does not occur.
Oops — my bad. Looking at the TinySec paper, the authors take care of the issue I raised above by using a variant of standard CBC mode where the IV is passed through the cipher before being XORed with the first message block.