[CVE-2023-4408] Parsing large DNS messages may cause excessive CPU load

Quick Links	🔗
Incident Manager:	@matthijs
Deputy Incident Manager:	@michal
Public Disclosure Date:	2024-02-13
CVSS Score:	7.5
Security Advisory:	isc-private/printing-press!76
Mattermost Channel:	CVE-2023-4408: O(n²) complexity in DNS message parsing logic
Support Ticket:	N/A
Release Checklist:	#4515 (closed) & #4555 (closed)

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

Earlier Than T-5

• 🔗 (IM) Pick a Deputy Incident Manager
• 🔗 (IM) Respond to the bug reporter
• 🔗 (SwEng) Ensure there are no public merge requests which inadvertently disclose the issue
• 🔗 (IM) Assign a CVE identifier
• 🔗 (SwEng) Update this issue with the assigned CVE identifier and the CVSS score
• 🔗 (SwEng) Determine the range of product versions affected (including the Subscription Edition)
• 🔗 (SwEng) Determine whether workarounds for the problem exist
• 🔗 (SwEng) If necessary, coordinate with other parties
• 🔗 (Support) Prepare "earliest" notification text and hand it off to Marketing
• 🔗 (Marketing) Update "earliest" notification document in SF portal and send bulk email to earliest customers
• 🔗 (Support) Create a merge request for the Security Advisory and include all readily available information in it
• 🔗 (SwEng) Prepare a private merge request containing a system test reproducing the problem
• 🔗 (SwEng) Notify Support when a reproducer is ready
• 🔗 (SwEng) Prepare a detailed explanation of the code flow triggering the problem
• 🔗 (SwEng) Prepare a private merge request with the fix
• 🔗 (SwEng) Ensure the merge request with the fix is reviewed and has no outstanding discussions
• 🔗 (Support) Review the documentation changes introduced by the merge request with the fix
• 🔗 (SwEng) Prepare backports of the merge request addressing the problem for all affected (and still maintained) branches of a given product
• 🔗 (Support) Finish preparing the Security Advisory
• 🔗 (QA) Create (or update) the private issue containing links to fixes & reproducers for all CVEs fixed in a given release cycle
• 🔗 (QA) (BIND 9 only) Reserve a block of CHANGES placeholders once the complete set of vulnerabilities fixed in a given release cycle is determined
• 🔗 (QA) Merge the CVE fixes in CVE identifier order
• 🔗 (QA) Prepare a standalone patch for the last stable release of each affected (and still maintained) product branch
• 🔗 (QA) Prepare ASN releases (as outlined in the Release Checklist)

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

• 🔗 (IM) Grant QA & Marketing clearance to proceed with public release
• 🔗 (QA/Marketing) Publish the releases (as outlined in the release checklist)
• 🔗 (Support) (BIND 9 only) Add the new CVEs to the vulnerability matrix in the Knowledge Base
• 🔗 (Support) Bump Document Version for the Security Advisory and publish it in the Knowledge Base
• 🔗 (First IM) Send notification emails to third parties
• 🔗 (First IM) Advise MITRE about the disclosed CVEs
• 🔗 (First IM) Merge the Security Advisory merge request
• 🔗 (IM) Inform original reporter (if external) that the security disclosure process is complete
• 🔗 (Marketing) Update the SF portal to clear the ASN
• 🔗 (Marketing) Email ASN recipients that the embargo is lifted

After Public Disclosure

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

---

Hi, Continuing our research, regarding CVE 2023-2828 (issue/4055) we discovered yet another possible vulnerability in BIND9 resolvers where one malicious CNAME query can cause over 27,000,000 calls to the dns_name_equal function and over 1,000,000,000 CPU instructions.

In the getsection function in message.c file there is a check if a name is already present in the section before appending the new name to the section.

...
if (!dns_name_equal(dns_rootname, name) ||
sectionid != DNS_SECTION_ADDITIONAL ||
msg->opt != NULL)
{
DO_ERROR(DNS_R_FORMERR);
}
...
for (count = 0; count < msg->counts[sectionid]; count++) {
...

The function checks whether each name is already present in the section by sending all the previous names with the new name to dns_name_equal function - which causes a quadratic function call.

For CNAME queries, the BIND resolver has a resolution limit of 17, so for each malicious CNAME query the resolver executes 17 queries to the authoritative name server.

I tested an answer with 1800 RRsets long CNAME chain, and as a result, the dns_name_equal function is called i-1 times for RRset i for i = n to n-17.

In the experiment, I observed 27,304,801 calls for dns_name_equal function, and my calculation indeed predicts:

∑ n^2 / 2. n from 1800 to 1784 = 27,295,948

I used Valgrind and Kcachegrind for checking that. Here is the valgind file: callgrind.out.cname_shoham1.shoham.fun

You can see here the number of function calls and the CPU instructions:

And here is an example of the answer section I respond:

How to reproduce the vulnerability and additional technical information:

For this experiment, I used my Azure environment:

I used 3 machines: a client, resolver and authoritative name server

All my machines are Intel(R) Xeon(R) CPU E5-2673 v4 @ 2.30GHz x64 with 2 vCPUs 8 GiB RAM and Linux (Ubuntu 20.04) OS.

I used BIND 9.16.42 version with no configuration changes. Here is the config.log file: config.log

and the conf.named.option file: named.conf.options

In the authoritative, I have a CNAME chain with 1800 RRsets (from shoham1.shoham.fun to shoham1800.shoham.fun). Attaching the zonfile here: shoham.fun.forward

The client issued a single query using this command: dig shoham1.shoham.fun. @<my_resolver_ip>

To reproduce the attack:

Turn on the resolver with the Valgrind tool using the following command: valgrind --tool=callgrind named -g -c /etc/named.conf.

From the client, query shoham1.shoham.fun using this command: dig shoham1.shoham.fun. @<your_resolver_ip>

Close the Valgrind resolve (Ctrl c will work)

Open the Callgrind file using Qcachegrind: qcachegrind ./callgrind.out.

You can also create your authoritative with the zonefile attached or with any long CNAME chain, here is a script for that:

with open('zonfile.txt', 'w') as f:
 for i in range(1, 1801):
  if i % 1800 != 0:
   print(f'shoham{i} 86400 IN CNAME shoham{i + 1}',file=f)
  else:
   print(f'shoham{i} 86400 IN A 1.1.1.1',file=f)

Please don't hesitate to ask any question or any additional information.

Thanks,

Shoham Danino, Anat Bremler-Barr, Yehuda Afek and Yuval Shavitt