A tale of a DNS packet (CVE-2016-2776)

Introduction

For a number of years now BIND is the most used DNS server on the internet. It is the standard system for name resolutions on UNIX platforms and is used in 10 of the 13 root servers of the Name Domain System on the internet. Basically, it is one of the main function of the entire Internet.

With this in mind, it isn't everyday that someone finds a vulnerability (CVE-2016-2776) rated HIGH in one of the most used services on the internet (https://kb.isc.org/article/AA-01419/0).

The tests done by ISC (Internet Systems Consortium) discovered a critical error when building a response. Additionally, an advisory in the knowledge base of ISC recognizes that an attack can exploit the vulnerability remotely and probably because of that it receives a HIGH score in terms of severity.

One thing that caught our attention from the ISC Advisory was the following quote:

This assertion can be triggered even if the apparent source address isn't allowed to make queries (i.e. doesn't match 'allow-query')

We decided to dedicate a little bit of time to investigate the main cause of this error with the goal of seeing the root cause of the Denial of Service.

Identifying the modifications

Following the tradition of having errors in the necessary software for the survival of humanity, CVE-2016-2776 came to light. With details of the problem basically nowhere to be found, nor what was the mysterious "Specifically Constructed Request", we decided to see what exactly was modified in the repository of Bind9. 

In the diff of the fix,  the most interesting change is found in dns_message_renderbegin() 

Just by seeing the fix we can guess that there's undefined behaviour when r.length < msg->reserved is FALSE but r.length - DNS_MESSAGE_HEADERLEN < msg->reserved is TRUE. Having noticed this, it's worth investigating the program's context when the following condition validates:

01  not (r.length < msg->reserved) and (r.length - DNS_MESSAGE_HEADERLEN < msg->reserved)

02  (r.length >= msg->reserved) and (r.length - DNS_MESSAGE_HEADERLEN < msg >reserved)

03  r.length - DNS_MESSAGE_HEADERLEN < msg->reserved <= r.length

Now we see what we can do to make that happen. If we see dns_message_renderbegin() we note that r.length describes the space available in isc_buffer_t buffer, that is where the response of the server will be written. This calculates as buffer->length - buffer->used.

Depending on how we craft the query, we can make sure that r.length is a known value given that it is going to be the same as the maximum size a response can have and we didn't do anything to it yet (after all we are in dns_message_render***BEGIN***()).

In our case, we can assure that it is 512, the standard maximum size of a UDP DNS response. Knowing that DNS_MESSAGE_HEADERLEN is the constant value 12, if we are able to make 500 < msg->reserved <= 512, we can create the context that motivated the fix.

So, what is msg->reserved?

In the library  lib/dns/message.c, we can see that it is a variable that indicates how many bytes we wish to reserve in msg->buffer for a later use and only can be manipulated with the functions dns_message_renderreserve() and dns_message_renderrelease(). The interesting thing about this, is what it does to achieve it's purpose. We can see that dns_message_rendersection() modifies the internal state of msg->buffer, or to be precise msg->buffer->length, All of this with a noble intention: make later manipulation attempts over that buffer believe that it's size is smaller than what it actually is.

The famous bufffer.cIf you were able to follow us until here you are probably asking the following:

• What does the the lib implementation do, to manipulate isc_buffer_t ?
• Who is then the famous buffer.c?

Each exposed function has a large quantity of assertions about isc_buffer_t to ensure that things are working properly and avoid potential memory corruption bugs. It's important to carefully consider the rest of the state of isc_buffer_t before changing it. Since the published CVE describes an assertion in buffer.c, clearly there exists a context where msg->reserved leaves the structure of isc_buffer_t invalid and it aborts the process on a posterior call to some function on buffer.c

Doing the POC

Now that we are convinced that msg->reserved is potentially dangerous when 500 < msg->reserved <= 512, it is time to see how we can manipulate this variable. Tracking the use of dns_message_renderreserve() in lib/dns/message.c we find that msg->reserved is used to track how many bytes will be necessary to write the Additional RR (OPT, TSIG y SIG(0)) once the response is finished rendering on dns_message_renderend().


The most direct way we've found of manipulating an Additional RR included on the response is sending a query with a TSIG RR containing an invalid signature. When this happens, the server echoes practically all the record when responding.

The following script sends a query A to the server with a TSIG large enough so as to make the server reserve 501 bytes on msg->reserved when writing the response.

https://github.com/infobyte/CVE-2016-2776/blob/master/namedown.py

Domain Status of Bind9

Running of the exploit namedown.py

We can see that the TSIG RR of the query is 517 bytes long. This is because the TSIG RR included in the server's response is 16 bytes shorter. Because of this, we should add 16 bytes to compensate.

Bind failed

Why did it work?

After parsing the request and failing to validate the signature, the process begins to render the error response. For that, even before calling dns_message_renderbegin() (fundamental for a couple of things not worth detailing... AKA: "exercise for the reader") it already reserves msg->sig_reserved bytes (calculates from the return signature by spacefortsig()) with the function dns_message_renderreserve(). In our case, as we wanted, it reserves 501 bytes.

When it gets to dns_message_renderbegin() we have the context we've looked for:  msg->reserved on 501 and r.length on 512. The if condition which should throw ISC_R_NOSPACE in the patch is not triggered. 

We can see now with the instruction immediatly after the validation why it was so important to consider DNS_MESSAGE_HEADERLEN. Inmediately after validating that the buffer has the sufficient space to store msg->reserved bytes, it allocates DNS_MESSAGE_HEADERLEN (12) bytes in it. In other words it didn't check if after reserving msg->reserved, there is enough space to store 12 bytes more. What happens in the end is that when returning from the function, the available space on buffer is of 500 bytes (buffer->length - buffer->used = 512 - 12 = 500) but we're reserving 501.

When passing through dns_message_rendersection(), msg->reserved  remembers to tell the buffer that it has reserved memory, but it doesn't even ask, it just takes it from him. This leaves the integrity of the isc_buffer_t msg->buffer structure corrupt: now msg->buffer->used is BIGGER than msg->buffer->length. All the ingredients are here, we just need to put them in the oven.

As we expected, when isc_buffer_add() was called further ahead in the same function, the assertions that assure the integrity of the buffer break. For every n, msg->buffer->used + n > msg->buffer->length.

Conclusions

Publishing a fix about a lethal bug where you would have to patch the whole internet, doesn't leave a lot of time to find elegant solutions. So if you review the fix it's possible that a new similar bug appears in dns_message_renderbegin(). while the use of msg->reserved is quite limited. It continues being a complex software. Meanwhile msg->reserved is still being used, the existence of a bug like CVE-2016-2776 is quite probable.

Remediation

Update Bind to these versions:

• BIND 9 version 9.9.9-P3
• BIND 9 version 9.10.4-P3
• BIND 9 version 9.11.0rc3

The majority of the distributions have updated their repositories.

Credits

Martin Rocha, Ezequiel Tavella, Alejandro Parodi (Infobyte Security Research Lab)