A while ago a member of the RootKit discord server sent a message containing an interesting question containing a math problem. This problem was quite intriguing to me so in this post I’ve wrapped their problem in a fictive scenario to show how knowing modulo math can be useful when reversing binaries.

Reading and understanding the assembly

As shown above, we have our snippet of x86 assembly code before we can actually reverse engineer our encryption function, we first have to understand it. We can’t explain all the assembly registers and operands, so a most basic knowledge of the main registers (ax, dx, bp, sp) and how the stack functions is expected. We will divide this snippet into smaller bits and explain each separately.

This section is responsible for loading our integer parameter into the address rbp - 4. It first decrements the stack pointer and stores the source at the top of the stack. Then it copies the stack pointer to the base pointer. And then finally loads our parameter (edi) into the address of our base pointer minus 4.

First, we move our value into the eax register and then proceed to multiply the value of eax by 123 and store it in eax. Then compute the effective value of rax which is just the 64-bit value of eax plus 18 and store it in edx and then copy the value of edx into eax. So what this section does, is multiply the value of eax with 123 and then adds 18.

Explaining everything in this section is pretty difficult, so this explanation will be very simplified. This pattern of shifts, moves, additions, and subtractions is to my knowledge unique to the GCC compiler and describes a modulus operation (so when looking at assembly from other compilers this operation could look totally different). This one describes the modulus of the value in eax by 256 indicated by both the shr‘s 24 value and the dl value in the movzx operation.

And this last small section just loads the value at the top of the stack into the base pointer and returns our final value.

So, to summarize what we learned from our dissection, our function does the following things:

  • Multiply our value by 123
  • Add 8 to our value
  • Compute the modulus of our value and 256

If we construct a function from what we now know we will get something like this:

Reversing the encryption function

Before we can reverse our encryption function we first have to establish some basics.
The actual mathematical notation for our encryption function function is: E(v) = (123v + 18) \mod 256
If we want to reverse this we will have to use something called the Euclidian algorithm and the Modular multiplicative inverse.
First, we have to use the Euclidian algorithm to find an inverse for 123 modulo 256 that lies between 1 and 256, or find an integer 1\le t \le 256 such that 123\cdot t \equiv1 \mod 256.

256 = 123 \cdot 2 + 10
123 = 10 \cdot 13 + 3
10 = 3 \cdot 3 + 1

Now we can work backward like this.

3 = 123 - (256 - 123 \cdot 2) \cdot 12 = 123 \cdot 25 - 256 \cdot 12
1 = 10 - (123 \cdot 25 - 256 \cdot 12) \cdot 3 = 10 - 123 - 75 + 256 \cdot 36
1 = 256 - 123 \cdot 2 (-123 \cdot 75 + 256 \cdot 36) = 256 \cdot 37 - 123 \cdot 77

From this, we can gather that t = -77.
Because we now have the value of t we can start to construct our decryption function eg. D(v) = −77v + b) \mod 256.
Finally, we have to find the value of b in this function, and then we have our complete decryption function. We can do this by plugging 18 in as our v and setting it equal to 0.

0 = 77 \cdot 18 + b \mod 256
b = 77 \cdot 18 \mod 256
b = 106

So our final function looks like this:

D(v) = -77v + 106 \mod 256

So if we for example would have a blob of data encrypted with this function we can write a small python program to decrypt said blob. Which could look something like this:

And now to test it:

Special thanks to kotae#4872 for the inspiration and help with the assembly, and Earthbound#7194 for the assistance with the math.