Techniques are presented for optimizing secure communications in a network. A first router receives from a second router an encrypted packet with an unknown security association. The first router examines the packet to determine whether the counter value is in a range of predicted counter values. Additionally, a key server is configured to provision routers that are part of a virtual private network. The key server selects a counter value that is part of a security association and calculates a key value. The key server sends the key value together with the security association to enable routers to exchange encrypted packets with each other in the virtual private network using the key value and the security association. The key server increments the counter value to a value within a range of counter values capable of being predicted by the routers.