Description

Analysis

As always let’s open the binary in Ghidra, and see what we could find.

The `main` function

Opening the binary in Ghidra, the first thing we observe is that it has been stripped. This means the function names are missing, making our initial analysis slightly more challenging. However, the main function is usually easy to identify, as it’s the entry point of our program. After locating and examining the main function, and renaming some of the variables and functions based on context clues (like puts messages), we have:

 
undefined8 main(void)
 
{
  bool isCorrect;
  long in_FS_OFFSET;
  uint a;
  uint b;
  uint c;
  uint d;
  uint e;
  uint f;
  char buffer [56];
  long canary;
  
  canary = *(long *)(in_FS_OFFSET + 0x28);
  puts(
      "To get the flag, you must correctly enter six 9-digit positive integers: a, b, c, d, e, and f ."
      );
  putchar(10);
  printf("a = ");
  __isoc99_scanf(&DAT_0040206c,&a);
  printf("b = ");
  __isoc99_scanf(&DAT_0040206c,&b);
  printf("c = ");
  __isoc99_scanf(&DAT_0040206c,&c);
  printf("d = ");
  __isoc99_scanf(&DAT_0040206c,&d);
  printf("e = ");
  __isoc99_scanf(&DAT_0040206c,&e);
  printf("f = ");
  __isoc99_scanf(&DAT_0040206c,&f);
  isCorrect = checkIntegers(a,b,c,d,e,f);
  if (isCorrect) {
    puts("Correct.");
    sprintf(buffer,"uiuctf{%x%x%x%x%x%x}",a,b,c,d,e,f);
    puts(buffer);
  }
  else {
    puts("Wrong.");
  }
  if (canary != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

`checkIntegers` function

Now here’s the function that interests us in this whole binary, this is the function that checks if the given integers are correct or not:

 
bool checkIntegers(uint a,uint b,uint c,uint d,uint e,uint f)
 
{
  bool bVar1;
  undefined4 uVar2;
  uint uVar3;
  uint uVar4;
  undefined4 uVar5;
  uint uVar6;
  uint uVar7;
  uint uVar8;
  uint uVar9;
  uint uVar10;
  uint uVar11;
  ulong uVar12;
  
  if (((((a < 0x5f5e101) || (b < 0x5f5e101)) || (c < 0x5f5e101)) ||
      ((d < 0x5f5e101 || (e < 0x5f5e101)))) || (f < 0x5f5e101)) {
    bVar1 = false;
  }
  else if (((a < 1000000000) && (b < 1000000000)) &&
          ((c < 1000000000 && (((d < 1000000000 && (e < 1000000000)) && (f < 1000000000)))))) {
    uVar2 = FUN_004016d8(a,b);
    uVar3 = FUN_0040163d(uVar2,c);
    uVar4 = FUN_0040163d(a,b);
    uVar2 = FUN_004016fe(2,b);
    uVar5 = FUN_004016fe(3,a);
    uVar6 = FUN_004016d8(uVar5,uVar2);
    uVar7 = FUN_0040174a(a,d);
    uVar2 = FUN_0040163d(c,a);
    uVar8 = FUN_004017a9(b,uVar2);
    uVar12 = FUN_0040163d(b,d);
    uVar2 = FUN_0040163d(d,f);
    uVar9 = FUN_0040174a(c,uVar2);
    uVar10 = FUN_004016d8(e,f);
    uVar11 = FUN_0040163d(e,f);
    if ((((uVar3 % 0x10ae961 == 0x3f29b9) && (uVar4 % 0x1093a1d == 0x8bdcd2)) &&
        ((uVar6 % uVar7 == 0x212c944d &&
         ((uVar8 % 0x6e22 == 0x31be && ((int)((uVar12 & 0xffffffff) % (ulong)a) == 0x2038c43c))))))
       && ((uVar9 % 0x1ce628 == 0x1386e2 &&
           ((uVar10 % 0x1172502 == 0x103cf4f && (uVar11 % 0x2e16f83 == 0x16ab0d7)))))) {
      bVar1 = true;
    }
    else {
      bVar1 = false;
    }
  }
  else {
    bVar1 = false;
  }
  return bVar1;
}

Demystifying functions

We have this block that calls a bunch of functions, as a first guess it must be doing some kind of operations to it’s arguments, as it’s arguments and results are all integers:

uVar2 = FUN_004016d8(a,b);
uVar3 = FUN_0040163d(uVar2,c);
uVar4 = FUN_0040163d(a,b);
uVar2 = FUN_004016fe(2,b);
uVar5 = FUN_004016fe(3,a);
uVar6 = FUN_004016d8(uVar5,uVar2);
uVar7 = FUN_0040174a(a,d);
uVar2 = FUN_0040163d(c,a);
uVar8 = FUN_004017a9(b,uVar2);
uVar12 = FUN_0040163d(b,d);
uVar2 = FUN_0040163d(d,f);
uVar9 = FUN_0040174a(c,uVar2);
uVar10 = FUN_004016d8(e,f);
uVar11 = FUN_0040163d(e,f);

We have five functions in here, which are:

FUN_0040163d
FUN_004016d8
FUN_004016fe
FUN_0040174a
FUN_004017a9

Demystifying `FUN_0040163d`

As we can see this function takes two integer inputs and returns an integer:

 
long FUN_0040163d(uint param_1,uint param_2) {
  byte bVar1;
  uint uVar2;
  uint uVar3;
  uint local_30;
  uint local_2c;
  uint local_20;
  long local_10;
  
  local_10 = 0;
  local_20 = 0;
  bVar1 = 0;
  local_2c = param_1;
  for (local_30 = param_2; (local_2c != 0 || (local_30 != 0)); local_30 = local_30 >> 1) {
    uVar2 = local_2c & 1;
    uVar3 = local_30 & 1;
    local_2c = local_2c >> 1;
    local_10 = local_10 + (ulong)((uVar2 ^ uVar3 ^ local_20) << (bVar1 & 0x1f));
    local_20 = uVar3 & local_20 | uVar2 & (uVar3 | local_20);
    bVar1 = bVar1 + 1;
  }
  return local_10 + ((ulong)local_20 << (bVar1 & 0x3f));
}

The for loop seems to be treating bit per bit from both inputs of the function, uVar2 and uVar3 stores the bit at which the loop is at currently, then it does a bitwise XOR of those two bits with a third bit local_20, after that it shifts everything by bVar1, the (bVar1 & 0x1f) is solely to make sure that bVar1 is always in the 32 bit range, it then adds the result of these operations to local_10 and stores them in the same variable, I can guess that this is doing addition, and the third bit was the canary, as we can see from the line local_20 = uVar3 & local_20 | uVar2 & (uVar3 | local_20); it checks if the first bit and the second bit are 1, or if one of those bits are 1 and the canary also is 1, this means that this is a full adder, so let’s rename the function and the variables for clarity:

 
long add(uint in1,uint in2) {
  uint in1_bit;
  uint in2_bit;
  uint i;
  uint k;
  uint carry;
  long sum;
  byte j;
  
  sum = 0;
  carry = 0;
  j = 0;
  k = in1;
  for (i = in2; (k != 0 || (i != 0)); i = i >> 1) {
    in1_bit = k & 1;
    in2_bit = i & 1;
    k = k >> 1;
    sum = sum + (ulong)((in1_bit ^ in2_bit ^ carry) << (j & 0b00011111));
    carry = in2_bit & carry | in1_bit & (in2_bit | carry);
    j = j + 1;
  }
  return sum + ((ulong)carry << (j & 0b00111111));
}

Essentially, this function implements a bitwise addition algorithm, mimicking how addition is performed at the hardware level.

Demystifying `FUN_004016d8`

Following our analysis of the add function, we have FUN_004016d8. This function is more straightforward: it takes two integer parameters but only passes them to FUN_0040163d (our renamed add function) after inverting the sign of the second parameter. This clearly indicates that FUN_004016d8 implements subtraction.

void FUN_004016d8(undefined4 param_1,int param_2) {
  FUN_0040163d(param_1,-param_2);
  return;
}

Here it is renamed:

void sub(undefined4 param_1,int param_2) {
  add(param_1,-param_2);
  return;
}

This highlights a common optimization technique in programming where more complex operations are built upon simpler ones.

Demystifying `FUN_004016fe`

Moving on, we have FUN_004016fe, another function that takes two integer inputs (param_1 and param_2) and returns an integer result. Examining the decompiled code, we can see that it iterates through the bits of the first parameter (param_1) and selectively adds a shifted version of the second parameter (param_2) to an accumulator variable (local_14) based on the current bit value. This pattern strongly suggests a multiplication operation.

int FUN_004016fe(uint param_1,int param_2)
 
{
  byte bVar1;
  uint local_1c;
  int local_14;
  
  local_14 = 0;
  bVar1 = 0;
  for (local_1c = param_1; local_1c != 0; local_1c = local_1c >> 1) {
    local_14 = local_14 + (param_2 << (bVar1 & 0x1f)) * (local_1c & 1);
    bVar1 = bVar1 + 1;
  }
  return local_14;
}

Let’s rename the function to mul and clarify the variable names to make the logic more apparent:

 
int mul(uint in1,int in2)
 
{
  uint in1_bits;
  int res;
  byte i;
  
  res = 0;
  i = 0;
  for (in1_bits = in1; in1_bytes != 0; in1_bits = in1_bits >> 1) {
    res = res + (in2 << (i & 0x1f)) * (in1_bits & 1);
    i = i + 1;
  }
  return res;
}

The code iterates through each bit of in1. If the current bit of in1 is set (equal to 1), a left-shifted version of in2 is added to the res variable. The amount of the left shift is determined by the position of the current bit being processed. This process multiplies in1 and in2 at the bit level, accumulating the partial products in res. This approach to multiplication is known as shift-and-add.

Demystifying `FUN_0040174a`

Now with the function FUN_0040174a. Similar to the previous functions we’ve encountered, it accepts two unsigned integer parameters (param_1 and param_2) and returns an integer. Looking closer at the decompiled output, we see a familiar pattern: the function iterates through the bits of both input integers. However, instead of addition or multiplication, this function utilizes the bitwise XOR operator (^) on the individual bits of the inputs, storing the resulting bits into an accumulator variable (local_18). This behavior strongly suggests a bitwise XOR operation.

 
int FUN_0040174a(uint param_1,uint param_2)
 
{
  byte bVar1;
  uint uVar2;
  uint local_20;
  uint local_1c;
  int local_18;
  
  local_18 = 0;
  bVar1 = 0;
  local_1c = param_1;
  for (local_20 = param_2; (local_1c != 0 || (local_20 != 0)); local_20 = local_20 >> 1) {
    uVar2 = local_1c & 1;
    local_1c = local_1c >> 1;
    local_18 = local_18 + ((uVar2 ^ local_20 & 1) << (bVar1 & 0x1f));
    bVar1 = bVar1 + 1;
  }
  return local_18;
}

To better reflect its functionality, we’ll rename the function to xor and clarify the variable names:

 
int xor(uint in1,uint in2)
 
{
  uint in1_bit;
  uint in2_bits;
  uint in1_bits;
  int res;
  byte i;
  
  res = 0;
  i = 0;
  in1_bits = in1;
  for (in2_bits = in2; (in1_bits != 0 || (in2_bits != 0)); in2_bits = in2_bits >> 1) {
    in1_bit = in1_bits & 1;
    in1_bits = in1_bits >> 1;
    res = res + ((in1_bit ^ in2_bits & 1) << (i & 0x1f));
    i = i + 1;
  }
  return res;
}

Demystifying `FUN_004017a9`

The last function we need to understand is FUN_004017a9. Like its predecessors, it receives two unsigned integers as input (param_1 and param_2) and returns an integer result. Analyzing the decompiled code reveals a familiar structure: the function iterates through each bit of the input integers. However, in this case, it applies the bitwise AND operator (&) to the corresponding bits of the inputs and accumulates the resulting bits into a variable (local_18). This pattern clearly indicates that the function implements a bitwise AND operation.

 
int FUN_004017a9(uint param_1,uint param_2)
 
{
  byte bVar1;
  uint uVar2;
  uint local_20;
  uint local_1c;
  int local_18;
  
  local_18 = 0;
  bVar1 = 0;
  local_1c = param_1;
  for (local_20 = param_2; (local_1c != 0 || (local_20 != 0)); local_20 = local_20 >> 1) {
    uVar2 = local_1c & 1;
    local_1c = local_1c >> 1;
    local_18 = local_18 + ((uVar2 & local_20 & 1) << (bVar1 & 0x1f));
    bVar1 = bVar1 + 1;
  }
  return local_18;
}

To make its purpose explicit, let’s rename the function and give the variables more meaningful names:

 
int and(uint in1,uint in2)
 
{
  uint in1_bit;
  uint in2_bits;
  uint in1_bits;
  int res;
  byte i;
  
  res = 0;
  i = 0;
  in1_bits = in1;
  for (in2_bits = in2; (in1_bits != 0 || (in2_bits != 0)); in2_bits = in2_bits >> 1) {
    in1_bit = in1_bits & 1;
    in1_bits = in1_bits >> 1;
    res = res + ((in1_bit & in2_bits & 1) << (i & 0x1f));
    i = i + 1;
  }
  return res;
}

Solution

Having successfully demystified the individual functions within the binary, we can now piece together the logic of the checkIntegers function and formulate our solution.

 
bool checkIntegers(uint a,uint b,uint c,uint d,uint e,uint f)
 
{
  bool isCorrect;
  undefined4 uVar1;
  uint uVar2;
  uint uVar3;
  undefined4 uVar4;
  uint uVar5;
  uint uVar6;
  uint uVar7;
  uint uVar8;
  uint uVar9;
  uint uVar10;
  ulong uVar11;
  
  if (((((a < 0x5f5e101) || (b < 0x5f5e101)) || (c < 0x5f5e101)) ||
      ((d < 0x5f5e101 || (e < 0x5f5e101)))) || (f < 0x5f5e101)) {
    isCorrect = false;
  }
  else if (((a < 1000000000) && (b < 1000000000)) &&
          ((c < 1000000000 && (((d < 1000000000 && (e < 1000000000)) && (f < 1000000000)))))) {
    uVar1 = sub(a,b);
    uVar2 = add(uVar1,c);
    uVar3 = add(a,b);
    uVar1 = mul(2,b);
    uVar4 = mul(3,a);
    uVar5 = sub(uVar4,uVar1);
    uVar6 = xor(a,d);
    uVar1 = add(c,a);
    uVar7 = and(b,uVar1);
    uVar11 = add(b,d);
    uVar1 = add(d,f);
    uVar8 = xor(c,uVar1);
    uVar9 = sub(e,f);
    uVar10 = add(e,f);
    if ((((uVar2 % 0x10ae961 == 0x3f29b9) && (uVar3 % 0x1093a1d == 0x8bdcd2)) &&
        ((uVar5 % uVar6 == 0x212c944d &&
         ((uVar7 % 0x6e22 == 0x31be && ((int)((uVar11 & 0xffffffff) % (ulong)a) == 0x2038c43c))))))
       && ((uVar8 % 0x1ce628 == 0x1386e2 &&
           ((uVar9 % 0x1172502 == 0x103cf4f && (uVar10 % 0x2e16f83 == 0x16ab0d7)))))) {
      isCorrect = true;
    }
    else {
      isCorrect = false;
    }
  }
  else {
    isCorrect = false;
  }
  return isCorrect;
}

For the following line, we can see that the numbers should be bigger than or equal to 100000000.

  if (((((a < 0x5f5e101) || (b < 0x5f5e101)) || (c < 0x5f5e101)) ||
      ((d < 0x5f5e101 || (e < 0x5f5e101)))) || (f < 0x5f5e101)) {
    isCorrect = false;
  }

After checking that, it checks if the numbers are smaller than 1000000000

else if (((a < 1000000000) && (b < 1000000000)) &&
          ((c < 1000000000 && (((d < 1000000000 && (e < 1000000000)) && (f < 1000000000))))))

This is basically checking a if the numbers are 9-digits long.

Once those checks are done, it starts doing the following operations:

uVar1 = sub(a,b);
uVar2 = add(uVar1,c);
uVar3 = add(a,b);
uVar1 = mul(2,b);
uVar4 = mul(3,a);
uVar5 = sub(uVar4,uVar1);
uVar6 = xor(a,d);
uVar1 = add(c,a);
uVar7 = and(b,uVar1);
uVar11 = add(b,d);
uVar1 = add(d,f);
uVar8 = xor(c,uVar1);
uVar9 = sub(e,f);
uVar10 = add(e,f);

We can simplify these even more:

uVar1 = a - b;
uVar2 = uVar1 - c;
uVar3 = a + b;
uVar1 = 2 * b;
uVar4 = 3 * a;
uVar5 = uVar4 - uVar1;
uVar6 = a ^ d;
uVar1 = c + a;
uVar7 = b & uVar1;
uVar11 = b + d;
uVar1 = d + f;
uVar8 = c ^ uVar1;
uVar9 = e - f;
uVar10 = e + f;

After doing those calculations, the program then checks for the final conditions:

if ((((uVar2 % 0x10ae961 == 0x3f29b9) && (uVar3 % 0x1093a1d == 0x8bdcd2)) &&
	((uVar5 % uVar6 == 0x212c944d &&
	 ((uVar7 % 0x6e22 == 0x31be && ((int)((uVar11 & 0xffffffff) % (ulong)a) == 0x2038c43c))))))
   && ((uVar8 % 0x1ce628 == 0x1386e2 &&
	   ((uVar9 % 0x1172502 == 0x103cf4f && (uVar10 % 0x2e16f83 == 0x16ab0d7)))))) {
  isCorrect = true;
}

So basically to solve this we’ll use z3, for that let’s define our symbols, as the integers are 9 digits long, that means it’s 32 bits vectors:

solver = Solver()
 
A = BitVec('A', 32)
B = BitVec('B', 32)
C = BitVec('C', 32)
D = BitVec('D', 32)
E = BitVec('E', 32)
F = BitVec('F', 32)

Then let’s prepare the initial conditions:

solver.add(A < 1000000000)
solver.add(B < 1000000000)
solver.add(C < 1000000000)
solver.add(D < 1000000000)
solver.add(E < 1000000000)
solver.add(F < 1000000000)
 
solver.add(A > 100000000)
solver.add(B > 100000000)
solver.add(C > 100000000)
solver.add(D > 100000000)
solver.add(E > 100000000)
solver.add(F > 100000000)

After that, let’s define the calculations that the program does:

uVar1 = A - B;
uVar2 = uVar1 + C;
uVar3 = A + B;
uVar1 = B * 2;
uVar4 = A * 3;
uVar5 = uVar4 - uVar1;
uVar6 = A ^ D;
uVar1 = C + A;
uVar7 = B & uVar1;
uVar11 = B + D;
uVar1 = D + F;
uVar8 = C ^ uVar1;
uVar9 = E - F;
uVar10 = E + F;

Next let’s add the constraints:

solver.add(uVar2 % 0x10ae961 == 0x3f29b9)
solver.add(uVar3 % 0x1093a1d == 0x8bdcd2)
solver.add(uVar5 % uVar6 == 0x212c944d)
solver.add(uVar7 % 0x6e22 == 0x31be)
solver.add(((uVar11 & 0xffffffff) % A) == 0x2038c43c)
solver.add(uVar8 % 0x1ce628 == 0x1386e2)
solver.add(uVar9 % 0x1172502 == 0x103cf4f)
solver.add(uVar10 % 0x2e16f83 == 0x16ab0d7)

Then the rest is easy, we’ll simply call solver.check() and see if we got a sat, if so we got the flag:

if solver.check() == sat:
    log.success('Found a solution')
 
    model = solver.model()
    a = model.eval(A)
    b = model.eval(B)
    c = model.eval(C)
    d = model.eval(D)
    e = model.eval(E)
    f = model.eval(F)
 
    log.info(f'Results:\n')
    log.info(f'\ta = {a}')
    log.info(f'\tb = {b}')
    log.info(f'\tc = {c}')
    log.info(f'\td = {d}')
    log.info(f'\te = {e}')
    log.info(f'\tf = {f}')

And here’s our fancy script that does all of that:

from z3 import *
from pwn import *
from IPython import embed
 
solver = Solver()
 
A = BitVec('A', 32)
B = BitVec('B', 32)
C = BitVec('C', 32)
D = BitVec('D', 32)
E = BitVec('E', 32)
F = BitVec('F', 32)
 
solver.add(A < 1000000000)
solver.add(B < 1000000000)
solver.add(C < 1000000000)
solver.add(D < 1000000000)
solver.add(E < 1000000000)
solver.add(F < 1000000000)
 
solver.add(A > 100000000)
solver.add(B > 100000000)
solver.add(C > 100000000)
solver.add(D > 100000000)
solver.add(E > 100000000)
solver.add(F > 100000000)
 
uVar1 = A - B;
uVar2 = uVar1 + C;
uVar3 = A + B;
uVar1 = B * 2;
uVar4 = A * 3;
uVar5 = uVar4 - uVar1;
uVar6 = A ^ D;
uVar1 = C + A;
uVar7 = B & uVar1;
uVar11 = B + D;
uVar1 = D + F;
uVar8 = C ^ uVar1;
uVar9 = E - F;
uVar10 = E + F;
 
solver.add(uVar2 % 0x10ae961 == 0x3f29b9)
solver.add(uVar3 % 0x1093a1d == 0x8bdcd2)
solver.add(uVar5 % uVar6 == 0x212c944d)
solver.add(uVar7 % 0x6e22 == 0x31be)
solver.add(((uVar11 & 0xffffffff) % A) == 0x2038c43c)
solver.add(uVar8 % 0x1ce628 == 0x1386e2)
solver.add(uVar9 % 0x1172502 == 0x103cf4f)
solver.add(uVar10 % 0x2e16f83 == 0x16ab0d7)
 
log.info('Searching for solutions ...')
if solver.check() == sat:
    log.success('Found a solution')
 
    model = solver.model()
    a = model.eval(A)
    b = model.eval(B)
    c = model.eval(C)
    d = model.eval(D)
    e = model.eval(E)
    f = model.eval(F)
 
    log.info(f'Results:\n')
    log.info(f'\ta = {a}')
    log.info(f'\tb = {b}')
    log.info(f'\tc = {c}')
    log.info(f'\td = {d}')
    log.info(f'\te = {e}')
    log.info(f'\tf = {f}')
 
    io = process("./summarize")
 
    io.recvline()
 
    io.sendline(f'{a}'.encode())
    io.sendline(f'{b}'.encode())
    io.sendline(f'{c}'.encode())
    io.sendline(f'{d}'.encode())
    io.sendline(f'{e}'.encode())
    io.sendline(f'{f}'.encode())
 
    io.recvuntil(b'Correct.')
 
    flag = io.recvuntil(b'}').decode().strip()
 
    log.success(f'Flag: {flag}')

The flag: uiuctf{2a142dd72e87fa9c1456a32d1bc4f77739975e5fcf5c6c0}

🔻 ihuomtia's blog

UIUCTF [REV] summarize

Description

Analysis

The `main` function

`checkIntegers` function

Demystifying functions

Demystifying `FUN_0040163d`

Demystifying `FUN_004016d8`

Demystifying `FUN_004016fe`

Demystifying `FUN_0040174a`

Demystifying `FUN_004017a9`

Solution

Table of Contents

🔻 ihuomtia's blog

UIUCTF [REV] summarize

Description

Analysis

The main function

checkIntegers function

Demystifying functions

Demystifying FUN_0040163d

Demystifying FUN_004016d8

Demystifying FUN_004016fe

Demystifying FUN_0040174a

Demystifying FUN_004017a9

Solution

Table of Contents

The `main` function

`checkIntegers` function

Demystifying `FUN_0040163d`

Demystifying `FUN_004016d8`

Demystifying `FUN_004016fe`

Demystifying `FUN_0040174a`

Demystifying `FUN_004017a9`