Friday, August 29, 2008

Checking Multiple Bits in a Flag Field

Sometimes, it is necessary to check a value in a flag field that is not a power of two (1, 2, 4, 8, etc.) and therefore requires multiple bits to be represented, yet other values in the byte are not part of that flag field. Such is the case for DNS where server status codes are represented as a four-bit value within the fourth byte of the DNS response packet (Reference 1). For the Kaminsky DNS bug (Reference 2), the Sourcefire VRT developed a rule to detect the "back scatter" of the attack in the form of excessive NXDOMAIN packets being sent by a DNS server.

The trouble with detecting NXDOMAIN packets is that the return code field is only four out of the eight bits in the byte. We cannot simply use a byte_test on the value 6 because if any of the other flags in that byte are set the byte_test will fail. Additionally, we cannot do a bit test for 6 in an attempt to ignore the top four bytes because decimal 6 requires two bits to be set in binary form and bitwise AND will return true if either bit is set, not just when both bits are set. For this reason, we must synthesize the value of 6 by checking each individual bit.

The decimal number 6 is represented in the following binary form:

0 1 1 0

This can be determined by using a calculator that will output in binary (Microsoft's XP Calculator in scientific mode will do), or by splitting the number 6 into its component powers of 2, which is 4 + 2. You also can read the binary representation above as (0 * 8) + (1 * 4) + (1 * 2) + (0 * 1). This is important to know, as we must test for each bit individually with its own byte_test.

To make this example line up directly with the DNS bug, we will now split these byte_tests exactly as they would be done for checking for NXDOMAIN packets.

The format of byte_test is the following -- byte_test: , [!], , [,relative] [,] [,] [,string];

  1. Make sure the highest bit is not set:

  2. Make sure the second highest bit is set:

  3. Make sure the third bit is set:

  4. Make sure the lowest bit is not set:

In the above operators, the '&' mean "bitwise AND," which returns true if the bit is set. Preceeding the '&' with '!' means "NOT bitwise AND," and returns true if the bit is not set, as expected.

Note that for the VRT's check for Kaminsky DNS back scatter, we only check the bits that are set, and ignore the most and least significant bits. This was done for performance reasons. It was decided that false positives would be at an acceptable level due to the values of the other rcodes not overlapping those two bits heavily and because the rule uses a threshold so a number of false positives would be required to trigger the alert.

We cannot simply do a single bitwise check for 6 as the bitwise check will return true if either bit in the value 6 is set. Due to the way bitwise AND works, there is no way to distinguish which bit was set or if both bits were set. By checking each individual bit, both the bits that are set and are not set, we have guaranteed the exact value of those four bits. Additionally, we have gotten around the problem where values in the top four bits would make a regular byte_test fail. The Snort rules language allows for the multiple byte tests to work because subsequent tests will only be run if the previous test succeeded. For this reason, it doesn't matter that we are essentially synthesizing the number based upon testing for its binary


  1. DNS, Domain Name System,

AUTHOR: Patrick Mullen, Senior Research Engineer, Sourcefire Vulnerability Research Team

No comments:

Post a Comment