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 table 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