- This challenge is a JIT VM
- The VM logic implements modular equations
Challenge Points: 996
No. of solves: 4
Challenge Author: Abhishek Barla, Abhishek Bharadwaj
We made a challenge assuming it would turn out good. But Oh No! The challenge turned out eerie, yes, eerie, not weird but eerie. We are currently on process of figuring out what changed overnight. It is true when people say your code can change overnight. Here is the challenge that we made, let’s work together to figure out why the challenge turned out the way it is.
sobing, in a corner
Oh my poor chall, what have you become ?
We are given a 64-bit stripped ELF. Running the program it prints a prompt after the user input is given. We open the file in IDA and get to main function, we see a flag format check, After the check, we have two functions
The first function takes the user input and converts it into four DWORD’s (excluding flag format) and assigns them globally along with few other constants.
The second function has an array initialized with constants and a switch case inside a while loop, which iterates over a global dump and the last case (
case 0x40) prints the win/fail prompt.
The second function
After initializing the values, each case inside the switch has a function call, if we look at the definition of these functions we can see that a region is mmaped and few bytes are copied to that region and in the end this function is executed (jit).
To find out what each function does we can set a breakpoint at mmap’s function call and look at the jit code and relate them with function arguments.
The functions in cases 0x35,0x36 work in a different way compared to the rest as these functions take in the previous return value as an argument, the vm also has a reset case (case 0x3E) where these return values are stored into memory and the varibale is re-assigned to another value.
The switch cases performs ADD,SUB,MUL,XOR,AND,OR,DIV operations out of which only ADD,SUB,XOR,DIV are used and each function in the respective case would jit the corresponding x86 code, execute it and get the return value.
Now that we have an idea of what’s happening inside the switch case, we can continue with replicating the same in python along with debug statements i.e writing a disassembler, we’ll use Z3’s Bitvectors for flag variables to trace our input
# Z3's BitVec to compute and see the whole equation as it is.
The above disassembly yeilds
[*] Xor (flag_1*6 + flag_0*105 + flag_0*flag_1*5 - flag_0*flag_0*4) % 2130660241, 519498219
If we take a look at the opcodes in the dump the last opcode is 0x40 (responsible to print the prompt) and the ones before that are 0x36 which performs XOR,
Inorder for the program to print
noICE, the return value of the xor case (case 0x36) should be zero in every iteration as the inside the case(case 0x36) takes the previous return value as an argument which takes us to,
(flag_1*6 + flag_0*105 + flag_0*flag_1*5 - flag_0*flag_0*4) mod 2130660241=519498219
Solving modular equations
Let A,B,C,D be the flag variables and
p be the prime number and eq1,eq2,eq3,eq4 be the values that are being compared to
eq1⇒(5*A*B-4*A^2+105*A + 6*B) mod p
Now we have 4 modular equations with 4 unknowns, consider
eq2 and subjecting
b from eq2 we get,
Since these equations are under
mod p it would become
eq1 gives us a polynomial in
a, upon solving yields
a, we can proceed with the other unknowns in a similar way to get the remaining flag variables.
Below is the sage script to solve the equations