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. However, 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 inferring 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. We propose R2-D2, which relies on (i) optimal message dependencies, (ii) parametrizable security guarantees, (iii) randomized bit dependencies, and (iv) optional immediate protection bits to address this problem. 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 even operates more resource-conscious and faster than existing progressive message authentication schemes.