Re: Max iptables rules?

From: henry (info_at_intellitree.com)
Date: 01/13/05 

Date: Wed, 12 Jan 2005 21:34:00 -0500

Here is my understanding of how Iptables processes firewall rules,
please someone correct if where this is wrong:

Lets say we have a table like the following dummy example

# Target prot source destination
===============================================
1 ACCEPT all 0.0.0.0/0 0.0.0.0/0 state: est/connected
2 ACCEPT all 10.0.0.0/24 0.0.0.0/0
3 ACCEPT all 0.0.0.0/0 0.0.0.0/0 tcp dpt: 80
4 ACCEPT all 30.30.0.0/16 0.0.0.0/0 tcp dpt: 22
5 ACCEPT all 31.31.0.0/16 0.0.0.0/0 tcp dpt: 22
6 ACCEPT all 32.32.0.0/16 0.0.0.0/0 tcp dpt: 22
        ...
        ...
        ...
20 ACCEPT all 60.60.0.0/16 0.0.0.0/0 tcp dpt: 22
21 REJECT all 66.1.0.0/16 0.0.0.0/0
22 REJECT all 66.2.0.0/16 0.0.0.0/0
23 REJECT all 66.3.0.0/16 0.0.0.0/0
24 REJECT all 66.4.0.0/16 0.0.0.0/0
        ...
        ...
        ...
        ...
1000 REJECT all 70.30.0.0/16 0.0.0.0/0

Lets say the above is our firewall with 1000 rules in it. Now this isn't
a very good firewall configuration, but bear with me. Lets say that a
packet come through on port 80. The packet will be compared to the list.
On the 3rd rule, iptables will find a match and will allow the packet,
and will ignore all the rest of the 997 rules as if they weren't even
there. Lets say a packet from ip 70.30.1.2 comes in on port 80. It is in
the list and should clearly be rejected, right? (number 1000). Well, it
would indeed match that reject rule, but it would also match the ACCEPT
rule number 3, and since 3 comes first, the packet will be allowed. If
our default policy is to REJECT, then all of our reject rules that come
at the end of our list effectively do nothing--and also shouldn't impact
performance... Here is a more senseable config:

# Target prot source destination
===============================================
1 ACCEPT all 0.0.0.0/0 0.0.0.0/0 state: est/connected
2 ACCEPT all 10.0.0.0/24 0.0.0.0/0
3 ACCEPT all 30.30.0.0/16 0.0.0.0/0 tcp dpt: 22
4 ACCEPT all 31.31.0.0/16 0.0.0.0/0 tcp dpt: 22
5 ACCEPT all 32.32.0.0/16 0.0.0.0/0 tcp dpt: 22
        ...
        ...
        ...
19 ACCEPT all 60.60.0.0/16 0.0.0.0/0 tcp dpt: 22
20 REJECT all 66.1.0.0/16 0.0.0.0/0
21 REJECT all 66.2.0.0/16 0.0.0.0/0
22 REJECT all 66.3.0.0/16 0.0.0.0/0
23 REJECT all 66.4.0.0/16 0.0.0.0/0
        ...
        ...
        ...
        ...
999 REJECT all 70.30.0.0/16 0.0.0.0/0
1000 ACCEPT all 0.0.0.0/0 0.0.0.0/0 tcp dpt: 80

Now this firewall actually does something. In this firewall, we say that
everyone should be able to connect to port 80, EXCEPT those hosts that
we are rejecting. The question is, how much will this impact performance?

Lets say that machine 10.0.0.4 wants to browse out to the net (assuming
we also have a snat rule). Those packets match on rule 2, so there is
virtually no extra processing happening there, it doesn't matter if
there are 10,000 rules below it, rule 2 matches, the packet is allowed,
and iptables doesn't look at the rest of the list.

Ok, but now lets say that a random machine, say 90.100.100.9, wants to
connect on port 80. Iptables will begin comparing the packet line by
line until it finds a match. Lets say we have no reject rules that match
this host. Iptables will have to go all the way through the entire list
until it gets to rule 1000, that says the packet should be allowed.
Thats hefty processing right? Especially for every single packet that
goes through the firewall, right? Well lets look. 90.100.100.9 wants to
connect on port 80. Before the firewall allows the packet, it runs
through all 1000 rules for allowing the packet to pass through he
filter. The packet reaches the web server, which responds (since the web
server is probably on 10.0.0.0/24, it will match rule 2 and be allowed
right away) and goes back to 90.100.100.9, which in turn sends a packet
back as the 2 hosts begin to communicate. Now when the following packets
come from host 90.100.100.9, the firewall again has to compare them, as
with every packet, to the firewall rules. This time however, the packets
from 90.100.100.9 have a state of established/connected, related to the
session it has established it the web server. The firewall compares the
packet to its firewall rules and matches on the very first rule of
connected/established, and allows the packet.

As we see, even with connections from hosts that have to match rules all
the way at the bottom of the list, in reality only a fraction of the
packets that pass the filter will have to undergo such scrutiny. And,
with a powerful box, shouldn't it be able to effectively handle a list
of a few hundred thousand entries?

The example you described of the "tree" is not my understanding of how
Iptables processes rules. The rules are perfectly linear. Every packet
is compared to every rule in the list until a match is found. Thats why
I think the key is to make it so that as many of the packets as possible
match as high on the list as possible.

Maybe I have it all wrong... That's why I am posting the question.

In any case, I think it is worth an experiment. I am going to setup a
box with 100,000 rules that will be randomly generated from a perl
script. Most of the rules will be reject rules for small blocks of IPs.
I will then put the rule that will match to my test box at the top of
the list, test performance and load, and then at the bottom the list,
and test performance and load. I will do the same for the rule of
allowing established/connected packets at the top and bottom as well,
testing both cases. I'll be sure to post my results.

Wolfgang Kueter wrote:
> henry wrote:
>
>
>>Thanks for your response Wolfgang. My firewalling approach is the
>>following: [...]
>
>
> In general your approach is correct.
>
>
>>If the order of the rules is done in an intelligent manner, then
>>shouldn't packets that match rules near the top not be bogged down? [...]
>
>
> Right. Concerning ordering of rules think of a tree structure of user
> defined chains:
>
> rule_1aa
> /
> rule_1a
> / \
> / rule_1ab
> rule_1
> |
> |
> | rule_2aa
> | /
> | rule_2a
> | / \
> | / rule_2ab
> rule_2
>
>
> In this small example we have a total of eight rules but after a maximum of
> 3 decisions every packet reaches its final destination. When we have the
> standard ordering the rules (one rule after the other in a stack) a packet
> might have to travel through the whole stack.
>
> Well, compare a tree structure of lets say a thousand rules to a stack of
> 1000 rules and you got my point.
>
> Wolfgang

Relevant Pages

  • Re: securing Ubuntu and firewall
    ... implement a firewall, it's a packet filter. ... The one place where it might seem iptables would be ...
    (Ubuntu)
  • Re: Potential crafted packets vulnerability in firewalls
    ... Does iptables need some additional rules to ... In other words, a packet with ... SYN,RST flags set, and ACK flag clear, will be interpreted by firewall as ... Many use Linux as a firewall to ...
    (comp.os.linux.security)
  • Re: Kerio PFW 2.14 - Safe?
    ... >> down user interface. ... Then consider the fact that most packet ... If Kerio 'X' says it's stateful it most ... >> way to know for sure would be to stand between the firewall and the ...
    (comp.security.firewalls)
  • Re: Firewall questions -- what is ...?
    ... packet payload inspection. ... IDS is not a firewall and does not necessarily protect you. ... port number for a well known service and the destination port is above 1023, ... Firewalls and IDS are prone to frequent false alarms. ...
    (microsoft.public.security)
  • Re: Max iptables rules?
    ... Here is my understanding of how Iptables processes firewall rules, ... Lets say the above is our firewall with 1000 rules in it. ... The packet will be compared to the list. ... On the 3rd rule, iptables will find a match and will allow the packet, ...
    (comp.security.firewalls)