MAC Aggregation with Message Multiplicity

Abstract. Wireless sensor networks (WSN) collect and report measure-ments, such as temperature, to a central node. Because sensors are usu-ally low-powered devices, data is transmitted hop-by-hop, through neigh-boring nodes, before it reaches the destination. Each nodes ’ messages are authenticated with a MAC (Message Authen-tication Code), keyed with a key known to the generating sensor and the control node. Because transmission channel capacity is often small, MACs represent a significant overhead. Indeed, a typical 128-bit MAC is as much as an order of magnitude larger than the data it authenticates – a temperature or consumption reading, even with a timestamp, can be stored in 10-15 bits. To mitigate these overheads, methods to com-pute aggregate MACs, of length much shorter than the concatenation of constituent MACs, were proposed. Unfortunately, known MAC aggregation techniques require that any mes-sage may not appear twice in the aggregate MAC. This is entrenched both in the definitions and constructions/proofs. This is a significant im-pediment in many typical practical deployments of WSNs. Indeed, one typical message relay strategy, flooding, relies on each node retransmit-ting received packets to all neighbors, almost certainly causing message repetition and inability to aggregate MACs. Further, we are not aware of any WSN protocols that guarantee non-duplication of messages. We propose a simple and very practical new way of MAC aggregation which allows message duplicates, and hence is usable in many more de-ployment scenarios. We derive a new security definition of this type of aggregate MAC, and discuss several variants of our construction and additional benefits such as Denial-of-Service resilience.