Optomised Algorithm for keeping track of network packets (replay attack prevention)

I'm implementing a network server that processes udp packets. I want to avoid replay attacks, where an attacker could copy udp packets, and replay them later in time. I way toying with idea that i could hash packet and store this value in a hash table. I can then do the same process everytime a packet is received then look it up in the hash table. If it's already exists then we reject the packet, however if we never seen it (the entry does not exist) we store it for future use.

Now, what hash algorithm would be suitable for this? Do i need something other than hash table? As there are a lot of udp packets being received i want this to work in O(1)!!!!!! ;-), is this possible?

Obviously the longer i 'remember' hashes, the more storage (state) i will need to allocate, can a hash ta开发者_运维技巧ble grow and shrink dynamically over time?

I maybe way off here, i may not need a hash table at all! i'm open to idea's!!

---

Do you have control over the content of the packet? If so, add a hash to the content and use that - which moves the hashing effort to the sender. You could also include a validity period so that a) you know you can discard any record of a packet after that time and b) a packet stored by an attacker becomes useless after that time. You would want to encrypt the time stamp in some way so the attacker can't just update the time stamp.

Other techniques can be found on Wikipedia

---

Using a hash table for packets can be expensive because you will have to rehash your hash table, which is O(n).

In this situation you should negotiate a shared secret between the server and each client. This secret key K is then used to construct a Message Authentication Code. The Message being authenticated should be the data you are transmitting in the UDP packet along with a time stamp. Sequence ID's are unfavorable because there is no guarantee a UDP packet will arrive at all, and its possible for packets to arrive out of order.

It should be noted that this attack is impossible with TCP due to the three way handshake and sequence ids. In this case the security provided by TCP may in fact be lighter than this proposed security system.