Re: CERT vulnerability note VU# 539363 (fwd)

[Mike Frantzen <frantzen () w4g org>]

> > Hi Carson,
> > State entry lookups don't actually occur in constant time.
> Yes they do, if you have enough memory, and a good enough hash function, 
> such that collisions are low. The paper you mentioned argued that for the 
> hash functions they tried, Khash > log(n)*Ktree, for reasonable values of 
> n. It never said that the hash function time wasn't invariant with n.

The problem with a hashed state table is that hash tables are very easy
to attack.  The use of collision chains (linked lists) would let an
attack totally blow out the D$ and TLB.  I've make a sun U10 440mhz w/
2MB L2 grind to a halt w/ 5 packets a second after a long series of
collisions.

Rehash paths aren't so bad if it is an array of state objects instead of
an array of pointers since you'll get good D$ and TLB performance.  But
that has a much higher initial memory cost (and you may not have space
in the kernel map to accomodate it).


This is why PF uses a state tree.  Optimal case is worse that hash
tables.  But worst case is O(log n) as opposed to O(n).  Alright, it
uses redblack trees so it is technically 2*log n worst case.

.mike
frantzen@(nfr.com | cvs.openbsd.org | w4g.org)
_______________________________________________
firewall-wizards mailing list
firewall-wizards () honor icsalabs com
http://honor.icsalabs.com/mailman/listinfo/firewall-wizards