Take a Bite of the Reality Sandwich: Revisiting the Security of Progressive Message Authentication Codes

Message authentication guarantees the integrity of messages exchanged over untrusted channels. Yet, the required per-message authentication tags considerably expand packet sizes, which is especially problematic in constrained environments. To address this issue, progressive message authentication aggregates and distributes integrity protection over multiple messages, promising to reduce overheads while upholding strong security of traditional integrity protection. However, as we show in this paper, existing progressive message authentication schemes are susceptible to packet drops: By interfering with just two selected packets, an attacker can remove integrity protection from a complete sequence of messages. Revisiting the security of progressive message authentication, we consider it imperative to thwart such attacks by rethinking how authentication tags depend on the successful reception of packets. To this end, we propose R2-D2, which relies on randomized dependencies with parameterized security guarantees to mitigate network-level attacks inherent to current progressive authentication schemes. To deploy our approach to resource-constrained devices, we introduce SP-MAC, which implements R2-D2 using efficient XOR operations. Our evaluation shows that SP-MAC protects against sophisticated network-layer attacks, and still operates as resources-conscious and fast as existing insecure schemes.