<div class="gmail_quote">On Mon, Jan 2, 2012 at 10:58 PM, Heinz N. Gies <span dir="ltr"><<a href="mailto:heinz@licenser.net">heinz@licenser.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Please correct me if I am wrong, I might have misunderstood something entirely.<br>
<br>
* All listed Servers use Prop Lists.<br>
* Prop Lists are liked lists with the elements having the form {key, value}.<br>
* The demonstrated DoS Attack on the Hash tables causes hash tables (usually having a very fast lookup time) to act like linked lists / arrays.<br>
<br>
Doesn't that lead to the conclusion that all listed servers are vulnerable to a even simpler version of the attack since no collisions need to be crafted?<br></blockquote><div><br></div>The attack is only effective if insert is slow. Insert of N keys is worst case O(N) for proplist, which is optimal. Insert of N keys is worst case O(N^2) for hash tables. Remember that you have to traverse the whole list of keys that hash the same to determine if there is a collision or not.<br>
<br><div>-bob</div><div> </div></div>