MAC Aggregation with Message Multiplicity

Wireless sensor networks (WSN) collect and report measurements, such as temperature, to a central node. Because sensors are usually low-powered devices, data is transmitted hop-by-hop, through neighboring nodes, before it reaches the destination. Each nodes' messages are authenticated with a MAC (Message Authentication 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 compute {em aggregate} MACs, of length much shorter than the concatenation of constituent MACs, were proposed. Unfortunately, known MAC aggregation techniques require that any message may not appear twice in the aggregate MAC. This is entrenched both in the definitions and constructions/proofs. This is a severe impediment in many typical practical deployments of WSN. Indeed, one typical relay strategy, {em flooding}, relies on each node retransmitting received packets to all neighbors, almost certainly causing message repetition and inability to aggregate. We propose a simple and very practical new way of MAC aggregation which allows message duplicates, and hence is usable in many more deployment scenarios. We derive a new security definition of this type of Aggregate MAC, and discuss several variants of our construction and their additional benefits such as Denial-of-Service resilience.