# Summarize (rev)

{% file src="<https://243380073-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBIa0PcXGYuP6chd3J1Ry%2Fuploads%2Fa12iRYfSNu5LNi4iGAzT%2Fsummarize?alt=media&token=1d22ba41-e672-4328-99e7-bc1a875d60c0>" %}

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

The main function given by Ghidra looks like this:<br>

```c
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:

```c
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.

```c
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`.&#x20;

`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`.&#x20;

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`.&#x20;

```c
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`.&#x20;

In the first iteration, `local_1c & 1 = 0`, so `local_14` remains as `0`.&#x20;

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)`.&#x20;

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`.&#x20;

```c
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`:

```c
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()`,&#x20;

```c
  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:

```python
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}
"""
```