Replay Attack Protection with Small State

Consider secure group communication, where a group with many senders transmit packets to a single receiver using a secure channel. Here, the transmitted packets are encrypted using a secret key shared between all the group members. One of the easiest types of attacks that an external adversary can launch, without any knowledge of the secret key, is a replay attack. In this attack, the adversary captures packets from the network and then injects those packets into the network later in the hope that the receiver will accept them. To address the large state space problem with the use of counters, we formulate a randomized hashing mechanism that can probabilistically detect a replay attack with tiny state. For instance, our scheme can detect a replay attack with more than $95%$ probability using just $5$ bits of state per sender; in other words, when there are a million senders, a receiver in our scheme thus needs to store a total of only $5$ million bits of state.