April 23, 2014

Inspection of Division & Multiplication

Division and multiplication calculations can lead to trigger bugs, and potentially pose as security risks. Here are few things that I believe to be helpful for those who do binary inspection.

Division

Production quality binaries are normally built with optimization enabled which makes the binary to run fast. One of the optimizations technique for the compiler is to emit a series of fast instructions instead of a single slow instruction.

DIV and IDIV instructions are known to be slow. As a part of optimization the compiler emits a series of fast instructions that are functionally equivalent to DIVs. The fast instructions are shift, multiplication, and addition instructions that take magic (constant) values depending on the divisor. Therefore the divisor has to be known at compile-time to apply optimization.

If the optimized binary has any DIVs, that means, the divisor was not known at compile time. Thus it's known at run-time, and so it could be a user-controlled value or a user input taken as it is.

Division can cause exception if the divisor is 0, or if the result is to large to store.

Division by Zero in CLR's Native Code

As an interesting experiment I looked at what happens when an integer is divided by zero in C#.

CLR generates native code with division instruction in it. When the instruction of division by zero is executed, an exception is raised that is handled by CLR's exception handler.

So the generated code with division in it doesn't have a test for the divisor. It's left for the exception handler to handle division by zero situations.

Multiplication

Like division, multiplication can be optimized, too, by using a sequence of fast instructions (sometimes one instruction). Whether or not it's worth optimizing depends on the value of multiplier (or multiplicand).

The multiplication you can see in binary might not be seen on source-code level. And some multiplication cannot be easily spotted in binary code due to optimization. And, multiplications can lead to trigger bugs.

Overflow in Multiplication

Multiplication can lead to integer overflow. Multiplication of two values are more likely to lead to integer overflow than addition of the two values. Multiplication of two word length integers can overflow on 32-bit but addition can't.

Few instances of the IMUL instruction can take immediate value, that is the multiplier. It's easily possible to calculate what multiplicand overflows the multiplication. The challenging part is to determine how the value could be assigned to the multiplicand to trigger overflow.

It's worth searching for MUL and IMUL instructions in the binary using the # (hash mark) Windbg command.

Overflow in Multiplication by Scale Factor

Scale factor is a constant value by which the register in the instruction is multiplied. The scale factor is either 1, 2, 4 or 8.

Use of scale factor could be the result of optimization of multiplication. The example below demonstrates to multiply a value by 4.

lea eax,[edi*4]

Other common use case involves to dereference an element of the array. In the below example the array consists of elements of size 8. On source-level there is no multiplication but on low-level there is.

mov [edi+edx*8],eax

If the value of the register by which the scale factor is multiplied is large enough an integer overflow can occur.

Look at the below instruction. Even the multiplication might not overflow the result can, due to base (esp) and displacement (8000).

mov [esp+ebx*4+8000],eax

Method of Inspection

Generally, it's not feasible to review all the occurrences of certain instructions but on critical areas it might be reasonable to do. Instruction tracing, and tracing like this can be a good start to narrow the area that can be inspected closer.
  This blog is written and maintained by Attila Suszter. Read in Feed Reader.