# mt77's based

In this crackme brought to us by mt77 we are tasked with reversing a Linux binary for `x86-64`

.

## An interesting note on divisions in `x86`

When analyzing the x86 instructions, we ran into interesting assembly code:

```
# Division by 4
shr rax, 2
# Somehow division by 25
mov rdx, 2951479051793528259
mul rdx
mov rax, rdx
shr rax, 2
```

We are able to perform a division by a literal using a `mul`

instruction.

### How `mul`

works

`mul`

is quite an unexpectedly complex instruction. At a glance it multiplies a register with `rax`

and stores the result in `rax`

.

However, to handle overflow `mul`

can write to `rdx`

. The least significant bytes of the multiplication are written to `rax`

while the most significant bytes are written to `rdx`

.

### Finding the magic number

We are in a 64bit program and performing a division by 4. We will therefore be using $2^{66}$ in our calculations.

Let $q, r$ be the quotient and reminder of $2^{66}$ by $25$.

We noticed that the constant of our program can be written as $2951479051793528259 = q + 1$.

Let’s now prove that our assembly program gives us a division.

Let $x < q$, we can take the quotient $q_x$ and reminder $r_x$ of $x$ by $25$.

\[\begin{align*} x \times 2951479051793528259 &= 25 \times q_x \times 2951479051793528259 + r_x \times 2951479051793528259 \\ &= q_x \times (25 \times (q + 1)) + r_x \times (q + 1) \\ &= q_x \times 2^{66} + q_x \times (25 - r) + r_x \times (q + 1) \end{align*}\]- $q_x \times (25 - r) < q_x \times 25$ by definition of the reminder
- $r_x \times (q + 1) = q \times r_x + r_x \le q \times (25 - 1) + r_x = 2^{66} - q - r + r_x$ by definition of the reminder

Using both inequalities we can now write \(\begin{align*} R &= q_x \times (25 - r) + r_x \times (q + 1) \\ &\le q_x \times 25 + 2^{66} - q - r + r_x \\ & = 2^{66} + x - q - r \qquad\qquad\qquad (x < q)\\ &< 2^{66} \\ \end{align*}\)

\[x \times 2951479051793528259 = q_x \times 2^{66} + R \implies \lfloor x \times 2951479051793528259 / 2^{66} \rfloor = q_x\]We are able to retrieve the quotient we wanted!

## The code

Let’s solve this challenge. Using IDA Free we were able to disassemble then decompile the binary. We studied the `luna`

function:

```
_BOOL8 __fastcall luna(unsigned __int64 a1)
{
int v2; // [rsp+18h] [rbp-10h]
int v3; // [rsp+1Ch] [rbp-Ch]
v3 = 0;
while ( a1 )
{
v2 = 2 * (a1 / 0xA % 0xA);
if ( v2 > 9 )
v2 -= 9;
v3 += v2 + a1 % 0xA;
a1 /= 100uLL;
}
return v3 % 10 == 0;
}
```

We need to try to find an integer that satisfies this property.

The digits are selected 2 by 2 and added together. In `v2`

we take twice the first digit of the two and multiply it by 2. Later we add this result with the second digit.

The digit pair `11`

adds 3 to `v3`

, so `1111`

brings us up to 6. We can add `12`

to reach 10.

## Solution

`111112`