Hash tables revisted March 17, 2010 | 05:38 pm

Just a quick note, I wanted to point this paper out to everyone here. Basically, the author demonstrates a denial of service attack using engineered hash collisions to force the programs into worst case behavior situations, just like I commented way back then.

And I’m not sure how much faith I’d put into a new hash algorithm being the savior here. The security of the system now relies on the cryptographic robustness of the hashing algorithm- remember, the attacker only has to find a sequence which demonstrates worst case, or near worst case, behavior in order to launch the denial of service attack. So if there is a cryptographic flaw in the algorithm which allows a malicious attacker to discover collisions much cheaper than brute force, then it becomes computationally feasible for the attacker to compute the worst case sequence, especially once they put their botnet on to it.

  • Mike G.

    Your “Way back When” is still 5 years after that paper was published in 2003.

    That paper did cause quite a stir, though. Among other things, the implementation of perl was changed to avoid this issue after the paper was published.