👾
Elijah's CTF Blog
  • 👋Home
  • 🇲🇾Wargames.MY CTF 2024
    • Credentials (crypto)
    • Stones (rev)
    • Rick'S Algorithm (crypto)
    • Rick'S Algorithm 2 (crypto)
    • Hohoho 3 continue (crypto)
  • 🎄Advent of CTF 2024
    • Jingle Bell ROP (pwn)
    • help (pwn)
  • Backdoor CTF 24
    • [rev] Ratatouille
  • 🇭🇰HKCERT CTF 24
    • Shellcode Runner 3 + Revenge (pwn)
    • ISH (1) (pwn)
    • Cyp.ress (rev)
    • Void (rev)
  • 🇮🇹ECSC 2024
    • ➕OffTopic (crypto)
  • 🎩Greyhats WelcomeCTF 24
    • EE2026 (misc)
  • 🚆UIUCTF 24
    • Syscalls (pwn)
    • Summarize (rev)
    • X Marked the Spot (crypto)
    • Without a Trace (crypto)
    • Determined (crypto)
    • Naptime (crypto)
    • Snore Signatures (crypto)
  • 🪼Jelly CTF 24
    • Cherry (crypto)
    • the_brewing_secrets (crypto)
  • 👨‍🦯vsCTF 24
    • Dream (crypto)
    • Cosmic Ray V3 (pwn)
  • 😎AKASEC CTF 24
    • Warmup (pwn)
    • Good_trip (pwn)
    • Sperm Rev (rev)
    • Paranoia (rev)
    • Grip (rev)
    • Risks (rev)
    • Lost (crypto)
  • 😁L3AK CTF 24
    • oorrww (pwn)
    • angry (rev)
    • Related (crypto)
    • BatBot (web-misc)
    • Matrix Magic (crypto)
  • 🥹CDDC Qualifiers 2024
    • WASM (rev)
    • crashMe (pwn)
Powered by GitBook
On this page
  1. UIUCTF 24

Summarize (rev)

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

Last updated 11 months ago

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}
"""
🚆
14KB
summarize