[CVE-2024-1737] BIND's database will be slow if a very large number of RRs exist at the same name

Quick Links	🔗
Incident Manager:	@mnowak
Deputy Incident Manager:	@greg
Public Disclosure Date:	2024-07-23
CVSS Score:	7.5
Security Advisory:	isc-private/printing-press!110
Mattermost Channel:	CVE-2024-1737
Support Ticket:	N/A
Release Checklist:	#4735 (closed)

💡 Click here (internal resource) for general information about the security incident handling process.

Earlier Than T-5

At T-5

🔗 (Marketing) Update the text on the T-5 (from the Printing Press project) and "earliest" ASN documents in the SF portal
🔗 (Marketing) (BIND 9 only) Update the BIND -S information document in SF with download links to the new versions
🔗 (Marketing) Bulk email eligible customers to check the SF portal
🔗 (Marketing) (BIND 9 only) Send a pre-announcement email to the bind-announce mailing list to alert users that the upcoming release will include security fixes

At T-1

🔗 (First IM) Send notifications to OS packagers

On the Day of Public Disclosure

After Public Disclosure

🚫 🔗 (QA) Merge a regression test reproducing the bug into all affected (and still maintained) branches

Summary

RBTDB handling of nodes with many RRs of the same type seems to be inefficient. This causes significant performance drop if a node has LOTS of RRs on it.
RBTDB handling of nodes with many RR types seems to be inefficient. (This is speculation based on my accidentally passing through rbtdb.c.) This causes significant performance drop if a node has LOTS of types on it.

It seems like an attack vector:

for secondaries or systems exposed to updates from not-really-trusted parties
for resolvers which can be queried by an attacker

BIND version used

~"Affects v9.16": 5c327f20
Affects v9.18: v9_18_3
~"Affects v9.19": b18b0e41

Steps to reproduce

TL;DR Start authoritative server with a zone which has lots of RRs of the same type.

"slow" variant with many RRs on one node

dig example.com SOA example.com NS > many.db
for I3 in $(seq 0 255); do for I2 in $(seq 0 128); do echo "big 0 IN A 0.0.$I3.$I2"; done; done >> many.db
time named-checkzone example.com many.db

$ time named-checkzone example.com example.com.db 
zone example.com/IN: loaded serial 2022040444
OK

real	0m39.496s
user	0m39.407s
sys	0m0.030s

named.conf
named -g -c named.conf -n1

yes 'big.example.com A' | dnsperf -l 5

Statistics:

  Queries sent:         1666
  Queries completed:    1666 (100.00%)
  Queries lost:         0 (0.00%)

  Response codes:       NOERROR 1666 (100.00%)
  Average packet size:  request 33, response 497
  Run time (s):         5.246397
  Queries per second:   317.551264

  Average Latency (s):  0.307935 (min 0.003612, max 0.373912)
  Latency StdDev (s):   0.063756

fast variant

Same configuration, different zone file content.

dig example.com SOA example.com NS > example.com.db
for I3 in $(seq 0 255); do for I2 in $(seq 0 128); do echo "big$I2$I3 0 IN A 0.0.$I3.$I2"; done; done >> many.db
time named-checkzone example.com many.db

zone example.com/IN: loaded serial 2022040444
OK

real	0m0.327s
user	0m0.317s
sys	0m0.010s

while true; do for I3 in $(seq 0 255); do for I2 in $(seq 0 128); do echo "big$I2$I3 A"; done; done; done | dnsperf -l 5

Statistics:

  Queries sent:         163332
  Queries completed:    163332 (100.00%)
  Queries lost:         0 (0.00%)

  Response codes:       NXDOMAIN 163332 (100.00%)
  Average packet size:  request 25, response 100
  Run time (s):         5.002245
  Queries per second:   32651.739369

  Average Latency (s):  0.002966 (min 0.000034, max 0.005476)
  Latency StdDev (s):   0.000589

See #3403 for the second reproducer, but there's no magic sauce - just add many RRTYPEs under a single name.