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