Despite years of open source fans claiming that “many eyes make all bugs shallow” there are far too few security researchers actually auditing these projects. And even fewer making their work public. That’s why it’s nice to see a post like this that describes an interesting bug. On June 26th Lab Mouse Security published a nice write up of a 20 year old integer overflow vulnerability in a widely used LZO implementation written by Markus Oberhumer.

When I see something like this and a patch is released, I like to investigate the code to look for additional issues. Auditing source code for vulnerabilitis is hard and bugs like to travel in groups. Even professional auditors miss vulnerabilities and trying to prove that there are no security vulnerabilities in a certain piece of code is essentially impossible.

First: The patched Linux version is still vulnerable to integer overflows. The bug(s) still require that about 16Mb is decompressed at once, which is hopefully is uncommon. As a result of the integer overflow it is possible to write data beyond the output buffer.

We will use the source code of the current (as of this blog post) version in the Linux tree. This is the version that was patched for the reported integer overflows.

We are only focusing on out of bound writes into out. And only on issues that allow us to write behind the buffer. Lab Mouse Security detailed how the overflow can be used to write before out, but I’ll only look at writing beyond out. In the following code op is the current output pointer end op_end is the end of the output buffer.

When reading the code it becomes clear that the HAVE_OP macro on line 26 is the primary defense against writing outside of the output buffer out.

26  #define HAVE_OP(t, x)                                   \
27          (((size_t)(op_end - op) >= (size_t)(t + x)) &&  \
28          (((t + x) >= t) && ((t + x) >= x)))

Analyzing this macro one can see several ways this check can be bypassed.

1. If op is ever higher than op_end (size_t)(op_end - op) will be a big value effectively negating any further bounds checks and allowing writing beyond the out buffer.
2. There are no checks to check that op does not point before the output buffer out. This post will not investigate this part further.
3. The checks for overflow on line 28 are, depending on the compiler and settings, incorrect, C standard compliant compilers are free to remove both checks. This post however is also not about this 3rd issue. If you are interested there is some info from LLVM and GCC. Linus Torvalds indicated that the Linux kernel is compiled with -fno-strict-overflow which prevents the optimization.

Lets focus on just the first issue. Are there any places in the code where op can be increased beyond op_end?

First example at line 103:

103             {
104                 NEED_OP(t, 0);
105                 NEED_IP(t, 3);
106                 do {
107                     *op++ = *ip++;
108                 } while (--t > 0);
109             }

NEED_OP is a simple wrapper around HAVE_OP:

36  #define NEED_OP(t, x)                                   \
37          do {                                            \
38                  if (!HAVE_OP(t, x))                     \
39                          goto output_overrun;            \
40          } while (0)

As we can see from the macros above NEED_OP(t, 0) will succeed without error when t = 0 even if op_end and op point to the same location. Once this check is passed op will be increased inside the while loop. After the increase op points past op_end bypassing further checks in HAVE_OP.

The question then becomes, can we get t to be 0. If we look a little above this code, at the while loop at line 78 we see:

77                      if (unlikely(t == 0)) {
78                                  while (unlikely(*ip == 0)) {
79                                          t += 255;
80                                          ip++;
81                                          NEED_IP(1, 0);
82                                  }
83                                  t += 15 + *ip++;
84                          }
85                          t + 3;

We find a familiar sight. A nice integer overflow. By having a lot of 0’s inside the input t keep being increased. We can now increase t to 0xfffffffd. The addition of 3 in line 85 will increase the value of t to 0x100000000, which requires 33 bits to store. On 32bit systems t only has room for 32bit and the extra bit is simply ignored and not stored. As a result by having around 16 million 0 bytes it is possible to raise t sufficiently high that the addition of 3 can wrap t around to 0.

If we go back to the actual while loop in line 103 we see that this example is not very usefull. The while loop will ‘decrease’ t to 0xffffffff and keep looping and writing memory for a very long time, likely triggering all sorts of traps or segfaults, making exploitation inconvenient and depending on the actual target impossible.

Let’s continue auditing.

Second example is at line 207 in the middle of the following code:

203                 unsigned char *oe = op + t;
204                 NEED_OP(t, 0);
205                 op[0] = m_pos[0];
206                 op[1] = m_pos[1];
207                 op += 2;
208                 m_pos += 2;
209                 do {
210                         *op++ = *m_pos++;
211                 } while (op < oe);

Once again this operation is protected by a NEED_OP(t, 0). But in this case op is increased by at least 3. Once by 2 on line 207 and once by 1 on line 210. As long as op points at most 2 bytes before op_end this will increased op beyond op_end allowing writing beyond the out buffer. For this scenario to happen we need to pass the NEED_OP check at line 204. Given that op_end - op has be at most 2 t has to either 2, 1, or 0.

t can be controlled in many location in the code. Tracing where t comes from and checking if it can be 0, 1 or 2 is a short auditing exercise. Most of the code ensures that t will be at least 3. At line 139 however we find a familiar while loop:

138                 if (unlikely(t == 2)) {
139                         while (unlikely(*ip == 0)) {
140                                 t += 255;
141                                 ip++;
142                                 NEED_IP(1, 0);
143                         }
144                         t += 31 + *ip++;
145                         NEED_IP(2, 0);
146                 }

An integer overflow can once again occur while parsing t, once again requiring at least around 16Mb of data inside the input buffer in.

Now that we have found a path that allows increase op beyond op_end we can see what is required:

1. Fill out with out_len - 1 bytes, ensuring that op_end - op is 1.
2. Using the integer wrap in the while loop at line 139 to set t to 0, 1 or 2.
3. Trigger the increase of op beyond op_end.
4. op will now point beyond op_end bypassing all the checks in HAVE_OP and allowing writing beyond out.

At this point the limit of data we can write beyond the end of out is limited by the room in the input buffer. Since LZO is a compression algorithm few bytes inside the input buffer can result in many output bytes.

Lesson we can learn from this:

• Though developers find and fix a lot of security vulnerabilities during development, some tricky vulnerabilities can stick around for a long time without a dedicated auditing effort.
• Just because the code is included in a lot of projects and in a lot of code bases does not imply that it has had sufficient (if any) code audits to assure a level of security.
• And just because an auditor has audited the code and found some bugs, doesn’t mean they found all of them.

• Auditing is hard and it takes time to do well. Finding one bug is only a warning. Based on these bugs I doubt anyone interested in disclosing bugs ever audited this code for security vulnerabilities before Lab Mouse Security did.

• Without hiring skilled auditor working on the defense side, we can be sure many security bugs will never be patched. We cannot rely on the free evenings of professional auditors and haphazard audits by volunteers of varying skill levels to secure critical infrastructure like the Linux kernel or OpenSSL.

• Not fixing the root cause, in this case the integer overflow options for t, means that you have to very carefully audit the code to make sure the root cause does not lead to other unwanted behaviour.
• With that said, the LZO code is relatively small so if you have an afternoon, take a look and let us know what you find.

I do not have enough free time to go over all the different version of LZO out there, but a quick look at the minilzo implementation from Markus Oberhumer indicates that it added a proper check to prevent t from overflowing. If you would like to further limit my free time I can be reached at info@lekkertech.net

Patch suggestions:

1. Fix the incorrect overflow checks in HAVE_OP and HAVE_IP, code that is used in this many locations will likely be used with optimizing compilers that just remove those checks.
2. Fix the integer overflows when calculating t.
3. Have the code reviewed by code auditors trained in finding security vulnerabilities.

Simple patch for the Linux Kernel.

As an exercise:

Spot the other places op can be increased beyond op_buf in the Linux LZO version.

There is another check in the code NEED_IP which tries to make sure that no data is read from beyond the input buffer. This check too can be bypassed if ip ever passes beyond ip_end determining whether this is possible in the Linux LZO code is another good exercise.