ipfw divert filter for IPv4 geo-blocking

[Dr. Rolf Jansen]

> Am 31.07.2016 um 15:38 schrieb Ian Smith <smithi at nimnet.asn.au>:
> On Sat, 30 Jul 2016 11:17:13 -0300, Dr. Rolf Jansen wrote:
>> I finished the work on CIDR conformity of the IP ranges tables 
>> generated by the tool geoip. The main constraint is that the start 
>> and end address of an IP block given by the delegation files MUST BE 
>> PRESERVED during the transformation to a set of CIDR records. This 
>> target is achieved by:
>> 
>> 1. Finding the largest common netmask boundary of the start address utilizing
>>    int(log2(addr_count)); then iteration like Euclid's algorithm in computing
>>    a GCD.
>> 
>> 2. Output the CIDR with the given start address and the masklen belonging
>>    to the found netmask.
>> 
>> 3. If the CIDR does not match the whole original IP range then set the start
>>    address of the next CIDR block to the next boundary of the common netmask,
>>    and loop over starting at 1. until the original range has been satisfied.
>> 
>> I carefully tested the algorithm and a table that I pipe by the new 
>> geoip tool into ipfw is 100 % identical to the output of the ipfw 
>> command 'table N list'.
> 
> Great.  I suppose that caters for some of the odd delegations one sees, 
> such as perhaps a /16 then a /15 (ie 3/4 of a /14) followed by maybe a 
> /12, maybw with another /15 tacked on the end .. but I'm unsure if that 
> applies to country allocations as much as it does within countries.
> 
>> It is worth to note, that already the original RIR delegation files 
>> contain 457 non CIDR conforming IPv4 ranges in a total of 165815 
>> original records. I guess that this number will increase in the 
>> future because the RIR's ran empty on new IPv4 ranges and are urged 
>> to subdivide returned old ranges for new delegations. The above 
>> algorithm is ready for this.
> 
> Yes, and just as well.  I'm surprised it's as few as 457 .. I looked 
> into it a bit back when 115.70/17 was first allocated to my ISP, after 
> previously having been, as I recall, in China .. so of course we fell 
> foul of a number of (probably perennially) out-of-date geoip blockers, 
> for months in some cases .. malevolent beasts if not kept well fed :)
> 
>> Generally, CIDR conforming tables are more than twice as large as 
>> optimized (joined adjacencies) IP range tables. All said changes have 
>> been pushed to GitHup already.
> 
> So how many table entries does 'the world' come to, around 400,000?

No, it is not that bad. The total number of original entries in the delegation statistics files of all 5 RIR's is about 166000. The ipdb tool which compiles these ranges into a consolidated sorted binary table, that is suitable for loading it directly into a binary search tree, reduces the number of entries to a bit more than one half, namely ca. 83500.

Consolidation primarily means, resolving of overlaps, because these could not be handled in a meaningful way by a binary search tree. Only as an additional benefit in the same go, that routine combines adjacencies with the same country code, although, skipping the combination is technically not a show stopper for the BST, this is only to increase the performance.

The geoip tool which generates the tables of CIDR ranges per country code out of the consolidated tables would output a count of 167500 entries for all countries. That is a little bit more than the original count, however this table is still optimized, because original ranges that when combined form a new valid CIDR are not broken down again, but the combined CIDR is passed.

>> I am still a little bit amazed how ipfw come to accept incorrect CIDR 
>> ranges and arbitrarily moves the start/end addresses in order to 
>> achieve CIDR conformity, and that without any further notice, and 
>> that given that ipfw can be considered as being quite relevant to 
>> system security. Or, may I assume that ipfw knows always better than 
>> the user what should be allowed or denied. Otherwise, perhaps I am 
>> the only one ever who input incorrect CIDR ranges for processing by 
>> ipfw.
> 
> You've lost me here, Rolf.  Do you mean that ipfw adds incorrect table 
> entries for a given IPv4 address and mask length?  Or that it c/should 
> itself accept IP ranges and generate the needed CIDR entries to match?

Perhaps an example may explain it better. Remember that the first incarnation of geoip passed the incorrect range 201.222.20.0/20 to ipfw. This is an incorrect CIDR because the start address does not match a mask boundary defined by the given masklen. The point now is that this error is caused by EITHER the masklen is incorrect OR the start address is incorrect. ipfw can determine only that the CIDR is incorrect, and does rectify it for further processing:

  # ipfw table 1 add 201.222.20.0/20
  # ipfw table 1 list
  -->  201.222.16.0/20 0

So actually ipfw happily takes an incorrect CIDR and transforms this into a correct one under the arbitrary assumption that the masklen is the correct part and the start address is sort of variable. Technically the addition by ipfw is a correct CIDR, but this is not necessarily the range the user wanted to add.

> If the former, how to reproduce for a bug report?  If the latter, might
> you contemplate adding that functionality to ipfw

Well, in the meantime, I saw that this kind of automatic rectification of incorrect CIDR entries is within ipfw throughout.

  # ipfw add 50000 allow ip from 201.222.20.0/20 to any
  -->  50000 allow ip from 201.222.16.0/20 to any

At least in this case the user is informed directly about the CIDR that has been actually utilized, anyway, it is not exactly the range the user has asked for, and the tiny difference can easily be overseen.

Given that ipfw can't know what the user actually intended - did he mistype the start address or obtained somehow a wrong masklen -, I advocate that ipfw should accept the wrong CIDR and transform it to a correct one exactly as above, but should output a warning, either to the shell or to syslog in case no shell is connected. Ideally this warning would give a useful explanation why the input CIDR is wrong and how it could be made correct by either adjusting the masklen or the start address.

> - or is ipfw better 
> off being driven to generate tables from the output of such as geoip?

Of course, tools like geoip HAVE TO produce by 100 % valid CIDR, otherwise the tool is buggy and the bug must be fixed as in the cse of geoip.

Of course, ipfw must not receive any so called "bug fix" that immediately may break lots of firewall installations around the world, given that it is so easy to inform invalid CIDR, and that ipfw happily accepted these up to now.

I don't want to look more catholic than the pope. My main concern is not that ipfw does a choice for correcting invalid CIDR, my concern is that the choice is sort of arbitrary. I advocate for logging a suitable warning, but keep on processing invalid CIDR's by transforming it to valid ones exactly as before.

Best regards

Rolf