Summarize (rev)

All you have to do is find six numbers. How hard can that be?

14KB
summarize

This challenge is a crackme, which requires us to correctly enter 6 numbers in order for the flag to be shown.

The main function given by Ghidra looks like this: 

undefined8 main(void)
{
  char cVar1;
  long in_FS_OFFSET;
  uint local_60;
  uint local_5c;
  uint local_58;
  uint local_54;
  uint local_50;
  uint local_4c;
  char local_48 [56];
  long local_10;
  
  local_10 = *(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,&local_60);
  printf("b = ");
  __isoc99_scanf(&DAT_0040206c,&local_5c);
  printf("c = ");
  __isoc99_scanf(&DAT_0040206c,&local_58);
  printf("d = ");
  __isoc99_scanf(&DAT_0040206c,&local_54);
  printf("e = ");
  __isoc99_scanf(&DAT_0040206c,&local_50);
  printf("f = ");
  __isoc99_scanf(&DAT_0040206c,&local_4c);
  cVar1 = check(local_60,local_5c,local_58,local_54,local_50,local_4c);
  if (cVar1 == '\0') {
    puts("Wrong.");
  }
  else {
    puts("Correct.");
    sprintf(local_48,"uiuctf{%x%x%x%x%x%x}",(ulong)local_60,(ulong)local_5c,(ulong)local_58,
            (ulong)local_54,(ulong)local_50,(ulong)local_4c);
    puts(local_48);
  }
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

Our 6 inputs are first checked using check(). If it returns 1 we have passed the check, and we obtain the flag. Looking at the check() function:

undefined4 check(uint param_1,uint param_2,uint param_3,uint param_4,uint param_5,uint param_6)
{
  undefined4 uVar1;
  uint uVar2;
  uint uVar3;
  undefined4 uVar4;
  uint uVar5;
  uint uVar6;
  uint uVar7;
  uint uVar8;
  uint uVar9;
  uint uVar10;
  ulong uVar11;
  
  if (((((param_1 < 0x5f5e101) || (param_2 < 0x5f5e101)) || (param_3 < 0x5f5e101)) ||
      ((param_4 < 0x5f5e101 || (param_5 < 0x5f5e101)))) || (param_6 < 0x5f5e101)) {
    uVar1 = 0;
  }
  else if (((param_1 < 1000000000) && (param_2 < 1000000000)) &&
          ((param_3 < 1000000000 &&
           (((param_4 < 1000000000 && (param_5 < 1000000000)) && (param_6 < 1000000000)))))) {
    uVar1 = fun1_2(param_1,param_2);
    uVar2 = fun1(uVar1,param_3);
    uVar3 = fun1(param_1,param_2);
    uVar1 = fun2(2,param_2);
    uVar4 = fun2(3,param_1);
    uVar5 = fun1_2(uVar4,uVar1);
    uVar6 = fun3(param_1,param_4);
    uVar1 = fun1(param_3,param_1);
    uVar7 = fun4(param_2,uVar1);
    uVar11 = fun1(param_2,param_4);
    uVar1 = fun1(param_4,param_6);
    uVar8 = fun3(param_3,uVar1);
    uVar9 = fun1_2(param_5,param_6);
    uVar10 = fun1(param_5,param_6);
    if ((((uVar2 % 0x10ae961 == 0x3f29b9) && (uVar3 % 0x1093a1d == 0x8bdcd2)) &&
        ((uVar5 % uVar6 == 0x212c944d &&
         ((uVar7 % 0x6e22 == 0x31be && ((int)((uVar11 & 0xffffffff) % (ulong)param_1) == 0x2038c4 3c)
          ))))) &&
       ((uVar8 % 0x1ce628 == 0x1386e2 &&
        ((uVar9 % 0x1172502 == 0x103cf4f && (uVar10 % 0x2e16f83 == 0x16ab0d7)))))) {
      uVar1 = 1;
    }
    else {
      uVar1 = 0;
    }
  }
  else {
    uVar1 = 0;
  }
  return uVar1;
}

Let's look at fun1_2 and fun1 first.

void fun1_2(undefined4 param_1,int param_2)
{
  fun1(param_1,-param_2);
  return;
}
long fun1(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));
}

fun1_2 is simply a wrapper for fun1, except that the second parameter is negated before calling fun1.

local_2c and local_30 are initialised to be param_1 and param_2 respectively at first. Then, with each iteration of the for loop, they are each right shifted by 1 bit. bVar1 is also incremented with each iteration. The loop stops if both of them are equivalent to 0. Within the loop, uVar2 is the rightmost bit of local_2c, while uVar3 is the rightmost bit of local_30. Then, local_10 is incremented by (uVar2 ^ uVar3 ^ local_20) << (bVar1 & 0x1f). Notice that (uVar2 ^ uVar3 ^ local_20) only evaluates to 1 if all 3 variables are 1, or only one of them is 1. This looks like how the result bit is obtained from addition of integers!

Let's think about the next line, local_20 = (uVar3 & local_20) | uVar2 & (uVar3 | local_20). In what scenarios would local_20 be set to 1?

  • Case 1: local_20 = 1.(uVar3 & local_20) evaluates to uVar3, and (uVar3 | local_20) evaluates to 1 here, so we are left with uVar3 | uVar2.

  • Case 2: local_20 = 0. (uVar3 & local_20) evaluates to 0 and (uVar3 | local_20) evaluates to uVar3. So we are left with uVar2 & uVar3.

So if local_20 was already 1, as long as either uVar3 or uVar2 is 1, local_20 will be 1. If local_20 was 0, it will become 1 only if both uVar2 and uVar3 are 1. This reminds us of the carry bit during addition of integers! This can be further confirmed by the fact that local_20 is added to local_10 as the most significant bit once the loop exits.

With the above observations, we can deduce that fun1 is essentially doing integer addition of param_1 and param_2 . This means that fun1_2 would be doing subtraction of param_2 from param_1.

Now let's look at fun2. 

int fun2(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;
}

This looks similar to fun1 in that it is performing some bitwise operation, but our carry flag is gone. We are using param_1's bits, but param_2 is used without extracting its bits. Our loop is iterating through the bits in param_1 starting from the rightmost bit. Let's run through an example. Say param_1 = 2 = 0b10 and param_2 = 3 = 0b11.

In the first iteration, local_1c & 1 = 0, so local_14 remains as 0.

In the second iteration, bVar1 = 1. So param_2 is left-shifted by 1 bit, and this time local_1c & 1 = 1. So we get local_14 = local_14 + (3 << 1) * 1).

The result we get is 6. Notice that this is the result of doing 2 * 3!

In general, if bit i of param_1 = 1, then local_14 = local_14 + (param_2 << i), which is equivalent to local_14 = local_14 + param_2 * 2^i.

In another example if param_1 = 3 = 0b11 and param_2 = x, then we would get a result of x * 2^0 + x * 2^1 = x * 1 + x * 2 = param_2 * 3. This should convince you that fun2 is simply a multiplication function!

Now let's look at fun3. 

int fun3(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;
}

fun3 seems very similar to fun1, except that our carry bit is gone and now the bit being added in each iteration is given by (uVar2 ^ local_20 & 1). This is essentially an XOR operation between the bit we obtained from param_1 and the bit we obtained from param_2. So fun3 is an XOR function.

Moving on to fun4:

int fun4(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;
}

It is similar to fun3, except that the bit being added is (uVar2 & local_20 & 1). That is the AND operation between the bit obtained from param_1 and the bit obtained from param_2. So fun4 is performing an AND operation on param_1 and param_2.

Looking back at the restrictions imposed by main(), 

  if (((((param_1 < 0x5f5e101) || (param_2 < 0x5f5e101)) || (param_3 < 0x5f5e101)) ||
      ((param_4 < 0x5f5e101 || (param_5 < 0x5f5e101)))) || (param_6 < 0x5f5e101)) {
    uVar1 = 0;
  }
  else if (((param_1 < 1000000000) && (param_2 < 1000000000)) &&
          ((param_3 < 1000000000 &&
           (((param_4 < 1000000000 && (param_5 < 1000000000)) && (param_6 < 1000000000)))))) {
    uVar1 = fun1_2(param_1,param_2);
    uVar2 = fun1(uVar1,param_3);
    uVar3 = fun1(param_1,param_2);
    uVar1 = fun2(2,param_2);
    uVar4 = fun2(3,param_1);
    uVar5 = fun1_2(uVar4,uVar1);
    uVar6 = fun3(param_1,param_4);
    uVar1 = fun1(param_3,param_1);
    uVar7 = fun4(param_2,uVar1);
    uVar11 = fun1(param_2,param_4);
    uVar1 = fun1(param_4,param_6);
    uVar8 = fun3(param_3,uVar1);
    uVar9 = fun1_2(param_5,param_6);
    uVar10 = fun1(param_5,param_6);
    if ((((uVar2 % 0x10ae961 == 0x3f29b9) && (uVar3 % 0x1093a1d == 0x8bdcd2)) &&
        ((uVar5 % uVar6 == 0x212c944d &&
         ((uVar7 % 0x6e22 == 0x31be && ((int)((uVar11 & 0xffffffff) % (ulong)param_1) == 0x2038c4 3c)
          ))))) &&
       ((uVar8 % 0x1ce628 == 0x1386e2 &&
        ((uVar9 % 0x1172502 == 0x103cf4f && (uVar10 % 0x2e16f83 == 0x16ab0d7)))))) {
      uVar1 = 1;
    }

Our 6 integers are restricted to be within the range (0x5f5e101, 1000000000) (which means they must all be positive and 9-digits long), and further modulo restrictions are imposed on the arithmetic results. Recall that fun1 is addition, fun1_2 is subtraction, fun2 is multiplication, fun3 is XOR, and fun4 is AND. We can use a z3 script to solve these constraints and obtain the 6 integers.

Below is my script:

from z3 import *

i1, i2, i3, i4, i5, i6 = BitVec('i1', 32), BitVec('i2', 32), BitVec('i3', 32), BitVec('i4', 32), BitVec('i5', 32), BitVec('i6', 32)
i1_cpy, i2_cpy, i3_cpy, i4_cpy, i5_cpy, i6_cpy = i1, i2, i3, i4, i5, i6

s = Solver()
s.add(And(i1_cpy >= 0x5f5e101, i2_cpy >= 0x5f5e101,i3_cpy >= 0x5f5e101,i4_cpy >= 0x5f5e101,i5_cpy >= 0x5f5e101))
s.add(And(i1_cpy < 1000000000, i2_cpy < 1000000000,i3_cpy < 1000000000,i4_cpy < 1000000000,i5_cpy < 1000000000))
uVar1 = i1_cpy - i2_cpy
uVar2 = uVar1 + i3_cpy
uVar3 = i1_cpy + i2_cpy
uVar1 = 2 * i2_cpy
uVar4 = 3 * i1_cpy
uVar5 = uVar4 - uVar1
uVar6 = i1_cpy ^ i4_cpy
uVar1 = i3_cpy + i1_cpy
uVar7 = i2_cpy & uVar1
uVar11 = i2_cpy + i4_cpy
uVar1 = i4_cpy + i6_cpy
uVar8 = i3_cpy ^ uVar1
uVar9 = i5_cpy - i6_cpy
uVar10 = i5_cpy + i6_cpy
s.add(uVar2 % 0x10ae961 == 0x3f29b9)
s.add(uVar3 % 0x1093a1d == 0x8bdcd2)
s.add(uVar5 % uVar6 == 0x212c944d)
s.add(uVar7 % 0x6e22 == 0x31be)
s.add(((uVar11 & 0xffffffff) % i1_cpy) == 0x2038c43c)
s.add(uVar8 % 0x1ce628 == 0x1386e2)
s.add(uVar9 % 0x1172502 == 0x103cf4f)
s.add(uVar10 % 0x2e16f83 == 0x16ab0d7)
print(s.check())
print(s.model())
"""
[i2 = 780663452,
 i5 = 966221407,
 i3 = 341222189,
 i6 = 217433792,
 i1 = 705965527,
 i4 = 465893239]
uiuctf{2a142dd72e87fa9c1456a32d1bc4f77739975e5fcf5c6c0}
"""

Last updated