follow-me
reversing - Points: 271
I have an execution trace of calc, but I forgot what I inputted.
Can you submit the input (formula) which follows my execution trace to my server?
Challenge server
Server compares branch instructions’ behavior of your input’s and original execution traces, and gives you flag if these are the same.
NOTE: You MUST NOT attack challenge server (including too frequent access).
Location: http://follow-me.chal.seccon.jp/
Sample curl command to submit formula:
curl -q -H 'Content-Type:application/json' -d "{\"input\": \"your formula comes here\"}" http://follow-me.chal.seccon.jp/submit/quals/0Attached files
Executed binary (excluding dynamic libraries): calc
Execution trace generated by tracer: calc.trace
Source code of tracer developed on the top of Pin: branchtrace.cpp
In this challenge you were given an execution trace of a calculator application, where you have to find an input, that produces the same trace on the challenge server to get the flag. The trace only contains the addresses of branch instructions and whether it was taken or not. You observe some unique addresses at the beginning and at the end where you already know they are probably typical ones you would find in any binary but surrounded from others, that appear multiple times and are most likely interesting for the actual execution flow.
To get to know how the binary actually works and what these branches are about, lets open it in Ghidra to find it out.
You will quickly find the function that processes the input with a lot of conditionals, or branches that are present in the trace.
do {
if (*local_40 == '\0') {
FUN_001008c7(puVar2);
return;
}
cVar1 = *local_40;
if (cVar1 == ',') {
if (local_2c == 1) {
FUN_00100922(puVar2);
}
local_2c = 0;
}
else {
if ((cVar1 < '0') || ('9' < cVar1)) {
if (cVar1 == '+') {
uVar4 = FUN_001008c7(puVar2);
uVar5 = FUN_001008c7(puVar2);
FUN_0010098c(uVar5,uVar4,uVar4);
FUN_00100922(puVar2);
local_2c = 2;
}
else {
if (cVar1 == '-') {
uVar4 = FUN_001008c7(puVar2);
uVar5 = FUN_001008c7(puVar2);
FUN_00100a27(uVar5,uVar4,uVar4);
FUN_00100922(puVar2);
local_2c = 2;
}
else {
if (cVar1 == '*') {
uVar4 = FUN_001008c7(puVar2);
uVar5 = FUN_001008c7(puVar2);
FUN_00100a3d(uVar5,uVar4,uVar4);
FUN_00100922(puVar2);
local_2c = 2;
}
else {
if (cVar1 == 'm') {
uVar4 = FUN_001008c7(puVar2);
uVar5 = FUN_001008c7(puVar2);
FUN_00100a94(uVar5,uVar4,uVar4);
FUN_00100922(puVar2);
local_2c = 2;
}
else {
if (cVar1 == 'M') {
uVar4 = FUN_001008c7(puVar2);
uVar5 = FUN_001008c7(puVar2);
FUN_00100aaf(uVar5,uVar4,uVar4);
FUN_00100922(puVar2);
local_2c = 2;
}
else {
if (cVar1 != 'C') {
printf("error: unhandled char \'%c\'\n",(ulong)(uint)(int)cVar1);
/* WARNING: Subroutine does not return */
exit(1);
}
uVar4 = FUN_001008c7(puVar2);
uVar5 = FUN_001008c7(puVar2);
FUN_00100aca(uVar5,uVar4,uVar4);
FUN_00100922(puVar2);
local_2c = 2;
}
}
}
}
}
}
else {
local_2c = 1;
}
}
local_40 = local_40 + 1;
} while( true );
Okay, we can see what operations the calculator supports and find which branches are related to them in the trace, after correcting the base address (simply only look at the least 3 hexdigits):
, @ 0x55f6b4d44be9 # end of number, push to stack
+ @ 0x55f6b4d44c58 # add
- @ 0x55f6b4d44caf # sub
* @ 0x55f6b4d44d06 # mult
m @ 0x55f6b4d44d5d # min
M @ 0x55f6b4d44db4 # max
d @ 0x55f6b4d44c4f # digit
With having resolved only these addresses I wrote a small script that creates the needed input pattern to hit the branches in the order they occurred in the trace and it looks like this:
ddd,ddd,ddd,ddd,ddd,dddd,ddd,mm-mM-ddd,ddd,ddd,mm-ddd,ddd,ddd,ddd,ddd,-+-M+ddd,ddd,ddd,mm*
So far, so good, since the actual numbers are not all depended on branches, we can choose them, BUT when looking how the add and mult operations are implemented, we have to care about some other conditions.
add function:
long FUN_0010098c(long lParm1,long lParm2)
{
long local_20;
int local_c;
local_20 = lParm1 + (lParm2 / 10) * 10;
local_c = 0;
while ((long)local_c < lParm2 % 10) {
local_20 = local_20 + 1;
local_c = local_c + 1;
}
return local_20;
}
To make it a little more tricky, in the add function, the least significant digit of the second summand is added via a loop, that encounters as much branches in the trace, so we have to choose numbers that fulfill these amount of loops. The address for the condition of the while loop is the branch at address 0x55f6b4d44a1f.
In the first addition, the branch is taken three times, so the second summand has to end with 3. It is 8 times for the second addition.
mult function:
long FUN_00100a3d(undefined8 uParm1,long lParm2)
{
int local_10;
int local_c;
local_10 = 0;
local_c = 0;
while ((long)local_c < lParm2) {
local_10 = FUN_0010098c((long)local_10,uParm1,uParm1);
local_c = local_c + 1;
}
return (long)local_10;
}
Similarly this applies for the mult function, where the second multiplier is added (via the add function!) via a loop. So we have to choose the correct multiplier to match the amount of branches and additionally the correct multiplicand. The branch for the condition of the while loop is at address 0x55f6b4d44e08.
For the sole multiplication the branch is taken only once, so the multiplier is 1 and the multiplicand needs to end with 6.
Putting these conditions together, I was able to find the needed numbers for the input pattern, BUT I have to say that I had a small mistake with having a , after an operation that had no influence on the calculation but generated additional traces. I was blind for that, so I ended up with building the provided branchtrace.cpp, what was actually not really necessary. It requires Intel Pin, that can be found here and after tinkering around I looked for the examples here and simply put the branchtrace.cpp in the source/tools/ManualExamples and built with $ make branchtrace.test TARGET=intel64. After diffing the traces, the problem was clear :)
Here is the request with the final input for the flag:
$ curl -q -H 'Content-Type:application/json' -d "{\"input\": \"008,000,000,000,000,0000,000,mm-mM-000,000,000,mm-008,000,000,003,000,-+-M+001,001,001,mm*\"}" http://follow-me.chal.seccon.jp/submit/quals/0
flag: SECCON{Is it easy for you to recovery input from execution trace? Keep hacking:)}