To understand what I'm talking about here, I *really* suggest watching
this video titled: "Harder Drive: Hard drives we didn't want or need":

  -> https://www.youtube.com/watch?v=JcJSW7Rprio

which at the 7:46 it says: "and it wouldn't be that hard to embed some
kind of picture or message in here, like how cool would it be to embed
a little qr code in this... right? it'd be a little bit cool... maybe
a little embarrassing too.  Anyway, that's the Internet."

This means that for this blog post we are going to paint the following
picture of me, taken in the Korankei gorge, located in Asuke-chō, Aichi,
Japan.  Yes, I know, the background is not very recognizable.


So, the trivial solution would be to convert each black or white pixel
into a rule in our router's firewall, for example to draw a black pixel:
  iptables -A $some_chain -d $pixel_ip -j DROP

However this would not only require at least 7839 rules for this
small image making our firewall huge and slow, but would completely lack
any fun, and so in the spirit of a Harder Drive it makes sense to find an
overly complicated way to achieve the same result.

Btw, to convert the IP into the coordinates of the image, we can use the
transformation already mentioned on the video, called Hilbert curve:
and so I'm going to steal the implementation written there.


Did you know iptables supports a module called "bpf"?

This bpf module allows us to associate a small program (a small sequence of
byte-codes) to a rule, that will be run for each packet to determine if it
matches or not.  Even though its computation model is not Turing complete,
it give us a great lot of flexibility.

To write bpf programs we have basically two alternatives, one of them is
using the pcap library directly to write the compile it from a pcap
expression, either by using tcpdump on a raw interfaces such as tun*, or
with a script like this one (changing «code» in the first line to specify
the program you would like to compile):

$ luajit -e 'code = "dst"
local ffi = require "ffi"
ffi.cdef [[
  struct bpf_insn { uint16_t code; uint8_t jt; uint8_t jf; uint32_t k; };
  struct bpf_program { unsigned int bf_len; struct bpf_insn *bf_insns; };
  int pcap_compile_nopcap(int, int, struct bpf_program *,
    const char *, int, uint32_t);]]
prog = ffi.new "struct bpf_program[1]"
assert(ffi.load "pcap".pcap_compile_nopcap(-1, 12, prog, code, 1, -1) == 0)
local t = {prog[0].bf_len}
for i = 0, prog[0].bf_len-1 do
  local ins = prog[0].bf_insns[i]      
  t[#t+1] = ("%d %d %d %d"):format(ins.code, ins.jt, ins.jf, ins.k)    
7,48 0 0 0,84 0 0 240,21 0 3 64,32 0 0 16,21 0 1 172425473,6 0 0 4294967295,6 0 0 0

Here is the documentation for pcap/tcpdump expressions:

  -> https://www.tcpdump.org/manpages/pcap-filter.7.html

And so to disassemble bpf byte-code you can use this program:

  -> https://github.com/cloudflare/bpftools/blob/master/linux_tools/bpf_dbg.c

Let's then disassemble the program we just compiled:

$ ./bpf_dbg
> load bpf 7,48 0 0 0,84 0 0 240,21 0 3 64,32 0 0 16,21 0 1 172425473,6 0 0 4294967295,6 0 0 0
> disassemble
l0:     ldb [0]
l1:     and #0xf0
l2:     jeq #0x40, l3, l6
l3:     ld [16]
l4:     jeq #0xa470101, l5, l6
l5:     ret #0xffffffff
l6:     ret #0

It makes sense right?
  * l0 loads the first byte of the IP packet into the register A,
       this byte contains the IP version in the upper nibble.
  * l1 discards the lower nibble: it's doing a bit-wise and: A = A & 0xf0
  * l2 compares the register A with the immediate value 0x40 jumping
       to l3 if it is equal, or l6 otherwise.
  * l3 loads the word (32 bits) at offset 16 which in an IP packet it is
       the destination address, into the register A.
  * l4 compares the register A with the immediate value 0x0A470101 which
       is the IP written in hex, if it matches it jumps to l5,
       if it doesn't, it matches to l6.
  * l5 returns -1, which by being different to 0 it means "match packet"
  * l6 returns 0, meaning "don't match packet".

In other words, as expected the program "dst" matches a given
packet only if it has IP version 4, and if its destination IP address is

The other alternative, which we will be using today, is to write bpf
programs in assembly and compile them using an assembler called "bpfc",
which is included in the netsniff-ng debian package.

In order to do this we need some knowledge about how the BPF model works.

* We have two registers, A and X.  A the accumulator can be used for
  computations, and the X register can be used for indirect addressing.
* There is a scratch memory bank composed of 16 32bit registers M[0] to
  M[15], which doesn't support indexed addressing and can only be used
  on the instructions: ld, ldx, st, stx for transferring to and fro the
  registers A and X.
* Arithmetic and logic operations will always use A as the left operand
  and destination register, while the right operand can either be a 32-bit
  immediate value or the register X:
    a := a «op» #imm
    a := a «op» x
  The following operations are provided: arithmetic: add, sub, mul, div, mod;
  logic: or, and, lsh, rsh, xor; unary: neg (basically A := -A).
* Only jumps forward are allowed, the destination address is always a
  relative immediate unsigned offset: This is important because ensures all
  programs will terminate in at most as many steps as its size; no, there's
  no call stack nor any kind of branch and link BL instruction.  There are no
  functions/subroutines at all.
* Programs can finish by returning a constant (ret #imm) or the value of the
  register A (ret a).  A return value of zero will not match the packet.
* Furthermore the maximum size allowed for BPF programs can be quite small as
  we will see in the following section.

If you want more detail about the classic BPF, here is the paper with a good
introduction to BPF (it's a nice reading material), and the reference manual:

  -> https://www.tcpdump.org/papers/bpf-usenix93.pdf
  -> https://www.freebsd.org/cgi/man.cgi?bpf


So... how much space do we have?: 64, yes only 64 instructions... 😞

  -> https://git.netfilter.org/iptables/tree/include/linux/netfilter/xt_bpf.h?id=18c96821b5901ac5c66dcbc5f299bd07ef5569ef#n8

Let's see, we can at least store 32 bits in a single immediate value, which
we can use by indexing it with the lowest 5 bits of the IP address, in C it
would be: (SOME_CONSTANT >> (address & 0x1f)) & 1.  This in BPF can be
programmed as:
l0: ld [16]     // a := destination ip address
l1: and #0x1f   // a := a & 0x1f, leaving a number between 0 and 31
l2: tax         // x := a, copy into x so that we can shift right by it
l3: ld #BITSET  // a := BITSET, basically the value for 32 pixels
l4: rsh x       // a := a >> x, discards the lowest x bits
l5: and #1      // a := a & 1, leaving only the selected bit.
l6: ret a       // finish the program with either 1 or 0

To see how a right shift «rsh» can be used for indexing a bit, we can see these
two examples: if the IP address in binary ends with 00000, at l2: x will be set
to 0, and then the shift at l4 will not modify the BITSET value at register a,
meaning that l5 will select the lowest bit.

If the IP address on the other hand ends with 11111, at l2: x=31 (11111 in
binary is 31 in decimal), then the shift at l4 will shift the register A 31
bits to the right, and after the «and» at l5, only 0 or 1 will remain, it
being the content of the highest bit of BITSET.

So, how can we use more bits of the IP address to select what constant to use?
In any normal programming language we would normally just provide a table of
constants, like:

const uint32_t MY_TABLE[] = {
  0x7fcbece9, 0xfffff7ff, 0xf7fffdff, 0xff7d777b,
  0xfed7cfff, 0xfdfffbef, 0x639ff99f, 0x600d10f2,
  0x9ffc0021, 0x8800bffc, 0x23858602, 0xffffff47,
  0xefffffff, 0xffffffde, 0xffffffee, 0xebb3dffd };

and that would be the end of the problem, however there's no way to do this
in BPF, yes, we have an array of 16 memory locations, but there's no indexed
loading, and we cannot pre-initialize it.

What we can do is to have a tree of branches!  There's a very useful
instruction called «jset» that does (a & «imm») jumping to a given location
if the value is non-zero and to another given location if it is zero, this
means that we can build a binary tree to jump to a specific «ld #BITSET», so
for 2 bits it can be:

        jset #0x00000040, L1,  L0
L0:     jset #0x00000080, L01, L00
L1:     jset #0x00000080, L11, L10
L00:    ld #BITSET00
        jmp l4
L01:    ld #BITSET01
        jmp l4
L10:    ld #BITSET10
        jmp l4
L11:    ld #BITSET11

And for N additional bits, this code would take 3*(2^N)-1 instructions, meaning
that for N=5 we would have 95 instructions, going over our total limit of 64.
For N=4 instead we have 47 instructions, plus the 6 we had before, we are well
within the margin.  In the end we've managed to check against 9 bits (4 for the
binary tree + 5 by right shifting a 32 bits constant with the lowest 5 bits of
the address), and we still have some additional space to check the remaining
32-9=23 high bits of the IP address against a constant, by starting the
program with, with in the end a grand total of 56 instructions:
        ld [16]
        and #NETMASK
        jeq #NETWORK, ok
        ret #0

To encode a 128*128 pixels image 2^14 pixels, we would then need 2^(14-9)=32
lines of iptables, something completely doable.


I just include the generator for sake of completeness, it's certainly not a
polished piece of code, but it does the job:

#!/usr/bin/env luajit
local bit = require 'bit'

-- I run this program as follows:
--   ./bpfimg.lua yo.pbm | sudo bash
-- and to check the generated assembly:
--   ./bpfimg.lua -d yo.pbm
local function parse_args(arg)
  local i = 1
  local debug = false
  if arg[i] == '-d' then
    debug = true
    i = i + 1
  -- We parse the first argument as the network/mask we are matching:
  local addr_str, cidr_str = arg[i]:match '^(%d+%.%d+%.%d+%.%d+)/(%d+)$'
  local network = 0
  assert(addr_str, 'First arg must be the network/mask, eg:')
  addr_str:gsub('%d+', function(octet)
    local n = tonumber(octet)
    assert(0 <= n and n <= 255)
    network = network * 256 + n
  local cidr = tonumber(cidr_str)
  assert(18 <= cidr and cidr <= 32)
  assert(cidr % 2 == 0, 'Images must have natural aligment')
  local side = 2^((32 - cidr)/2)
  local npixels = side * side

  local netmask = -bit.lshift(1, 32-cidr)
  assert(bit.band(network, netmask) == bit.tobit(network))

  local imgdata
    local fd = assert(io.open(arg[i+1]))
    local rawdata = fd:read '*a':gsub('#.-\n', '')
    local width, height, data = rawdata:match '^P1%s+(%d+)%s+(%d+)%s+(.*)'
    imgdata = data:gsub('%s', '')
    assert(imgdata, 'Image must be in XBM format')
    assert(tonumber(width) == side and tonumber(height) == side,
      'Expected square image of side ' .. side)
    assert(#imgdata == width * height)
  return network, cidr, side, npixels, imgdata, debug

local network, cidr, side, npixels, imgdata, debug = parse_args(arg)

-- This code is basically the C code at Wikipedia's article on Hilbert
-- curve translated to lua, this is why it's so "bit." heavy.
local function d2xy(d)
  -- parameter d and return value are all 0-based.
  local x, y, s = 0, 0, 1
  while s < 65536 do
    local rx = bit.band(1, bit.rshift(d, 1))
    local ry = bit.band(1, bit.bxor(d, rx))
    if ry == 0 then
      if rx == 1 then
        x = s-1 - x
        y = s-1 - y
      x, y = y, x
    x = x + s * rx
    y = y + s * ry
    s = bit.lshift(s, 1)
    d = bit.rshift(d, 2)
  return x, y

-- Find corner with lowest values.  This could be optimized if we were
-- to abuse the fact that d2xy uses the Hilbert curve.
local ox, oy = d2xy(network)
for d = network, network + npixels-1 do
  local x, y = d2xy(d)
  ox, oy = math.min(x, ox), math.min(y, oy)

local function test_d2xy()
  local visited = {}
  local x, y = d2xy(network)
  local px, py = x-1, y
  for d = 0, npixels-1 do
    x, y = d2xy(d + network)
    assert(0 <= x-ox and x-ox < side)
    assert(0 <= y-oy and y-oy < side)
    assert(not visited[y*65536+x])
    visited[y*65536+x] = true
    assert(math.abs(x-px) + math.abs(y-py) == 1)
    px, py = x, y

local genbits_visited = {}
-- Given an IP address as an integer number, calculate the bitset for
-- the 32 IPs block that the BPF code uses for the 5 LSb of the address
local function genbits(base)
  local ret = 0
  if base < 0 then base = base + 0x100000000 end
  for i = 0, 31 do
    local ip = base + i
    local rel = ip - network
    if 0 <= rel and rel < npixels then
      local x, y = d2xy(ip)
      -- we have to obtain the position in the XBM relative to the origin
      local pos = (y - oy) * side + (x - ox) + 1
      -- 49 is ('1'):byte(), representing the black color = DROP
      if imgdata:byte(pos) == 49 then
        -- LSb corresponds to the first IP in the range, since the bpf
        -- code does: (ret >> (IP&31)) & 1
        ret = ret + bit.lshift(1, i)
  -- just to report some statics at the end:
  local visit_count = genbits_visited[ret] or 0
  if visit_count > 0 then
    genbits_visited.duplicates = (genbits_visited.duplicates or 0) + 1
  genbits_visited.total = (genbits_visited.total or 0) + 1
  genbits_visited[ret] = visit_count + 1
  return ret

local function toipstring(ip)
  return ('%d.%d.%d.%d'):format(
    bit.rshift(ip, 24),
    bit.band(bit.rshift(ip, 16), 255),
    bit.band(bit.rshift(ip, 8), 255),
    bit.band(ip, 255))

-- Code generation!

-- If you run: sudo tcpdump -ilo -d 'dst host' you will see that the
-- generated code begins by checking the ETHERTYPE field on the ethernet frame
-- In iptables however the ethernet headers are not provided
-- (man 8 iptables-extensions):
--   > Iptables passes packets from the network layer up, without mac layer.

local chain_name = ('drop_icmp_%s/%d'):format(toipstring(network), cidr)

local function generate_rule(ip, cidr)
  if cidr < 23 then
    generate_rule(ip, cidr+1)
    return generate_rule(ip + bit.lshift(1, 32-cidr-1), cidr+1)
  -- we print the comment in cyan:
  print(('# %srule for %s/%d%s'):format(
    '\27[36m', toipstring(ip), cidr, '\27[0m'))
  local prog = {}
  local function out(s) prog[#prog+1] = s end
  -- We don't really have to check the version, as IPv6 goes through ip6tables
  -- instead, so let's load the destination address located at offset 16:
  local netmask = -bit.lshift(1, 32-cidr)
  out '  ld [16]'

  -- Then we check the top bits to ensure we are in the correct network

  out('  and #0x' .. bit.tohex(netmask))
  out('  jeq #0x' .. bit.tohex(ip) .. ', ok')
  out '  ret #0'

  -- let's load the dst ip again, this time to filter the last 5 bits only
  out 'ok:'
  out '  ld [16]'
  out '  and #31'
  -- and save it in register x
  out '  tax'

  -- Now let's generate the tree for filtering the bits betwen cidr and 26
  -- inclusive.  If there are no bits to test (cidr >= 27) then we just
  -- load the immediate bits for band(network, 0xffffffe0)

  if cidr >= 27 then
    prog[#prog+1] = '  ld #0x' .. bit.tohex(genbits(bit.band(ip, 0xffffffe0)))
    local function dump_tree(label, ip, cidr)
      -- we check against 32-5=27 to interleave the constants with the tree
      -- and so theoretically support a larger jump tree if the number of
      -- maximum instructions would be larger, like 2048, as all jumps would
      -- fall within the 8-bit limit for jump offsets.
      if cidr == 27 then
        out(('  ld #0x%s'):format(bit.tohex(genbits(ip))))
        if not label:find '^L_1+$' then
          out '  jmp finish'
        local b = bit.lshift(1, 32-cidr-1)
        out(('  jset #0x%s, %s1, %s0'):format(bit.tohex(b), label, label))
        dump_tree(label..'0', ip, cidr+1)
        dump_tree(label..'1', ip + b, cidr+1)
    dump_tree('L_', ip, cidr)

  out 'finish:'
  out '  rsh x'  -- a = a >> x, with x being the last 5 bits of dst addr
  out '  and #1'
  out '  ret a'
  io.write('iptables -A ' .. chain_name .. ' -m bpf --bytecode "')
  local fd = assert(io.popen('bpfc -p -f xt_bpf -i -' ..
    (debug and ' -V' or ''), 'w'))
  fd:write(table.concat(prog, '\n'))
  print '" -j DROP'

-- this header makes sure that our chain does not filter anything but pings:
print(('iptables -N %s || iptables -F %s'):format(chain_name, chain_name))
print('iptables -A '..chain_name.." '!' -p icmp -j RETURN")
print('iptables -A '..chain_name.." -p icmp '!' --icmp-type ping -j RETURN")
generate_rule(network, cidr)

-- there was some space for a bit more optimization
print(('# total=%d, duplicated=%d'):format(
  genbits_visited.total, genbits_visited.duplicates))


If for some reason you need to have a dense set of IP addresses, then please
by all means just use ipset with type "bitmap:ip" or "hash:ip" (if the set is
sparse), or any of the additional types for other use cases.

If you need more complex stuff, you probably should use eBPF instead of BPF.

Maybe in the future I could write a second installment with a tutorial for
doing exactly this, but by writing a super efficient eBPF program instead.