  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.
