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

Answers


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


Need Your Help

Comparison in reading lines from file

ruby file io

There are multiple ways to read lines from a file. Here are three:

matplotlib plot_date default to 0 for missing dates in Xs

python matplotlib

I have a dataset that defines the time at which events happen. It does not include timestamps for non-events. I want a 0-1 graph showing 0 on days no event occurred and 1 on days at least 1 event

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.