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
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
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:
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 such that .
Now we can work backward like this.
From this, we can gather that .
Because we now have the value of we can start to construct our decryption function eg. .
Finally, we have to find the value of in this function, and then we have our complete decryption function. We can do this by plugging 18 in as our and setting it equal to 0.
So our final function looks like this:
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.