A mechanism for providing strong anti-replay protection at a security gateway in a network for protection against an attacker duplicating encrypted packets. The mechanism assigns a unique sequence number to each encrypted packet and a time stamp. A receiving security gateway rejects packets that have a duplicative sequence number or that is too old to protect itself against replay attacks. Each security gateway checks off the sequence numbers as they are received knowing that the sending security gateway assigns sequence numbers in an increasing order. The receiving security gateway remembers the value of the highest sequence number that it has already seen as well as up to N additional sequence numbers. Any packet with a duplicative sequence number is discarded. In addition to the sequence number, each packet also has an associated time stamp that corresponds to an epoch during which it should be received. If the packet is received after the epoch has expired, the packet is rejected.