On 2004-08-31, Mike Frantzen <frantzen@nfr.com> wrote:
Fixed-sized state tables are absolutely awful when done in software.
Heh, the finite nature of RAM makes them necessary in the end, though.
One way or another, you've got a resource which can't grow beyond a
limit, as you note here:
To be honest, there is only one problem with timing out states too late.
You risk running out of memory.
so this is somewhat a moot point, and certainly orthogonal to the issue
of LRU-necessitated timeouts; such don't mandate a static pool size.
They're trivial to DoS if you can predict the re-hash path or if they
degenerate to a linked list off a hack bucket. My classic example was
That's like saying "it's trivial to DoS Aho-Corasic if you know the
signature set lends itself to a degenerative automata" or, "it's trivial
to turn an IPS into a reverse DoS if you know weaknesses in its
analysis". As designers of security products, everything we write must
take into account the scarcity of resources and the our enemies' wish to
exhaust them. Unfortunately, no pure algorithmic solution exists for
the problem; only adaptation to input and fallback in the face of
overutilization can improve on an essentially futile task. You can't
malloc() forever.
That being said, much of the research in useful, adaptive algorithms
focuses on this problem. The issues involving various Linux kernel
DoS's and improvements via use of the Jenkins hash are most illuminating.
They can be great if done right in hardware (yes, I'd be Intel or AMD's
bestest friend if they put a general purpose CAM table in their
chipsets, and especially for a TCAM). There were some great debates a
I'm not sure I see the difference. Can you elaborate?
culminated in the ideas of random early drop and syn cookies. A LRU
replacement policy gives the worst behavior since an attacker can flood
your state table with new connections and all of the previous valid
connections will be discarded. For beefy state size to bandwidth
numbers, it takes less than 10% of the bandwith to DoS the state table.
... in the face of a truly naive hash, I'm sure this is true. I'd hope
a coder who felt this sufficient wouldn't last long in a security role.
The way we solved this at NFR is to never expire idle TCP states. If we
have the memory to hold fifty bazillion states in a red-black tree, then
we'll hold onto fifty bazillion states even though they have been idle
for months. Then when we run out of memory, we'll pressure the TCP
....ummm. That's LRU, unless I'm critically misunderstanding you.
state table to throw away some connections. It makes it much harder for
an attacker evade the IDS with attacks against the state table when he
doesn't know how much he has to send and can't predict what will get
thrown away.
Why can't they predict it? It sure sounds deterministic to me, simply
deterministic based on network input...as an adaptive hash would be.
Nah. I think my eyes just glazed over after the first few greek letters
wargamesv("sometimes the only winning move is not to play"). I just
started the academic approach recently, and while the minds and ideas
are often exhilirating, I'm often at an uninformed loss when it comes to
appreciating efforts there...
--
nick black "np: the class of dashed hopes and idle dreams."
