lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date:   Mon, 27 Jan 2020 09:20:48 +0100
From:   Pablo Neira Ayuso <>
Subject: [PATCH 0/6] Netfilter updates for net-next


This batch contains Netfilter updates for net-next:

1) Add nft_setelem_parse_key() helper function.

2) Add NFTA_SET_ELEM_KEY_END to specify a range with one single element.

3) Add NFTA_SET_DESC_CONCAT to describe the set element concatenation,
   from Stefano Brivio.

4) Add bitmap_cut() to copy n-bits from source to destination,
   from Stefano Brivio.

5) Add set to match on arbitrary concatenations, from Stefano Brivio.

6) Add selftest for this new set type. An extract of Stefano's
   description follows:

"Existing nftables set implementations allow matching entries with
interval expressions (rbtree), e.g., entries
specifying field concatenation (hash, rhash), e.g.,
but not both.

In other words, none of the set types allows matching on range
expressions for more than one packet field at a time, such as ipset
does with types bitmap:ip,mac, and, to a more limited extent
(netmasks, not arbitrary ranges), with types hash:net,net,
hash:net,port, hash:ip,port,net, and hash:net,port,net.

As a pure hash-based approach is unsuitable for matching on ranges,
and "proxying" the existing red-black tree type looks impractical as
elements would need to be shared and managed across all employed
trees, this new set implementation intends to fill the functionality
gap by employing a relatively novel approach.

The fundamental idea, illustrated in deeper detail in patch 5/9, is to
use lookup tables classifying a small number of grouped bits from each
field, and map the lookup results in a way that yields a verdict for
the full set of specified fields.

The grouping bit aspect is loosely inspired by the Grouper algorithm,
by Jay Ligatti, Josh Kuhn, and Chris Gage (see patch 5/9 for the full

A reference, stand-alone implementation of the algorithm itself is
available at:

Some notes about possible future optimisations are also mentioned
there. This algorithm reduces the matching problem to, essentially,
a repetitive sequence of simple bitwise operations, and is
particularly suitable to be optimised by leveraging SIMD instruction

You can pull these changes from:


Thank you.


The following changes since commit 32efcc06d2a15fa87585614d12d6c2308cc2d3f3:

  tcp: export count for rehash attempts (2020-01-26 15:28:47 +0100)

are available in the git repository at:

  git:// HEAD

for you to fetch changes up to 611973c1e06faef31d034deeb3ae7b7960b1f043:

  selftests: netfilter: Introduce tests for sets with range concatenation (2020-01-27 08:54:30 +0100)

Pablo Neira Ayuso (2):
      netfilter: nf_tables: add nft_setelem_parse_key()
      netfilter: nf_tables: add NFTA_SET_ELEM_KEY_END attribute

Stefano Brivio (4):
      netfilter: nf_tables: Support for sets with multiple ranged fields
      bitmap: Introduce bitmap_cut(): cut bits and shift remaining
      nf_tables: Add set type for arbitrary concatenation of ranges
      selftests: netfilter: Introduce tests for sets with range concatenation

 include/linux/bitmap.h                             |    4 +
 include/net/netfilter/nf_tables.h                  |   22 +-
 include/net/netfilter/nf_tables_core.h             |    1 +
 include/uapi/linux/netfilter/nf_tables.h           |   17 +
 lib/bitmap.c                                       |   66 +
 net/netfilter/Makefile                             |    3 +-
 net/netfilter/nf_tables_api.c                      |  260 ++-
 net/netfilter/nf_tables_set_core.c                 |    2 +
 net/netfilter/nft_dynset.c                         |    2 +-
 net/netfilter/nft_set_pipapo.c                     | 2102 ++++++++++++++++++++
 net/netfilter/nft_set_rbtree.c                     |    3 +
 tools/testing/selftests/netfilter/Makefile         |    3 +-
 .../selftests/netfilter/        | 1481 ++++++++++++++
 13 files changed, 3896 insertions(+), 70 deletions(-)
 create mode 100644 net/netfilter/nft_set_pipapo.c
 create mode 100755 tools/testing/selftests/netfilter/

Powered by blists - more mailing lists