We analyze a small binary that asks to satisfy a seemingly unsolvable equation.

Taking a Look at the Executable

The challenge consists of one 32-bit binary named impossible with a size of about 4k. Putting it into hex rays decompiles the program smoothly. The relevant parts (with slight adjustments to improve readability) are shown below:

#include <stdio.h>

unsigned int nums[21];


int is_in_range(int a1)
{
  int result;

  if ( a1 <= 1 || a1 > 1000000 )
    result = -1;
  else
    result = a1;

  return result;
}

int main(int argc, const char **argv, const char **envp)
{
  long long tmp1;
  int tmp2;
  unsigned long long tmp3;
  unsigned long long product;
  unsigned long long sum;
  int i, j, last_idx;

  alarm(15);
  last_idx = 0;
  nums[0] = 1;
  for (i = 1; i < 21; i++) {
    scanf("%d", &nums[i]);
    nums[i] = nums[i - 1] < nums[i] ? is_in_range(nums[i]) : -1;
    last_idx = i;
    if (nums[i] == -1)
      break;
  }

  sum = 0;
  product = 1;

  for (j = 1; j < last_idx; j++) {
    sum += nums[j];
    tmp1 = nums[j];
    tmp2 = tmp1 * HIDWORD(product) + HIDWORD(tmp1) * product;
    tmp3 = (unsigned int)product * (unsigned long long)(unsigned int)tmp1;
    LODWORD(product) = tmp3;
    HIDWORD(product) = HIDWORD(tmp3) + tmp2;
  }

  if (last_idx <= 1 || product != sum) {
    puts("Wrong...");
  } else {
    puts("Correct!");
  }

  return 0;
}

The program reads in up to 20 distinct numbers in ascending order, checks whether they are in the range $[2,10^6]$, computes the sum and the product of the numbers and checks if the sum equals the product. Don’t let yourself be confused by the HIDWORD and LODWORD macros, that’s just IDA’s way of telling us that 64bit arithmetic is being done on 32 bit numbers. If the values of sum and product match and we gave the program more than one number, we win.

The Math behind the Problem

So, remember are looking for $m\in[2,20]$ distinct $n_i\in[2,10^6]$ such that \[ \sum_{i=0}^{m-1} n_i = \prod_{i=0}^{m-1} n_i \text. \]

Mathematicians proved that the only solutions to the problem above ${(0, 0), (1, 1), (2, 2)}$ do not meet our requirements, so solving the problem above is provably impossible.

… well, then, how the heck could the solve counter for the challenge be $>0$ at the time we started working on the task? Fair enough: The above equation omits the fact we’re not working on numbers of arbitrary precision. What we’re actually looking for is a solution to the congruence

\[ \sum_{i=0}^m n_i \equiv \prod_{i=0}^m n_i \pmod{2^{64}} \text. \]

So the integer wrap-around is right there to rescue us. At this point, a long and cruel session of mindtorturing emerged and many ideas turned out to be totally useless until we had the final inspiration. Some observations:

• The product always grows faster than the sum, so probably the only possibility to satisfy the equation is abusing the wrap-around
• The sum will never wrap as even the largest constructable number ($\sum_{i=0}^{20}10^6-i)$ is still magnitudes below $2^{64}$.
• The product is invariant under moving a prime factor from one number to another, whereas the sum changes under this operation. Clearly, numbers with many small prime factors give us some flexibility.

The following idea finally led to a solution: Once the wrap-around occurs, we want the resulting number to be as small as possible (see observation 1 above). This means that we need to construct a number with a very large gap between the first and the second 1 bits. Clearly, all numbers $2^x+2^y$ with $x$ large (as close as possible to and below of $64$) and $y$ small (as close as possible to and above $0$) satisfy this requirement. We thus started looking at numbers $2^n + 1$ with $n\in[0,63]$ to find the largest one consisting of prime factors all below $10^6$:

(n, prime factors of 2^n+1)
(0, 2)
(1, 3)
(2, 5)
(3, 3^2)
(4, 17)
(5, 3 * 11)
(6, 5 * 13)
(7, 3 * 43)
(8, 257)
(9, 3^3 * 19)
(10, 5^2 * 41)
(11, 3 * 683)
(12, 17 * 241)
(13, 3 * 2731)
(14, 5 * 29 * 113)
(15, 3^2 * 11 * 331)
(16, 65537)
(17, 3 * 43691)
(18, 5 * 13 * 37 * 109)
(19, 3 * 174763)
(20, 17 * 61681)
(21, 3^2 * 43 * 5419)
(22, 5 * 397 * 2113)
(23, 3 * 2796203)
(24, 97 * 257 * 673)
(25, 3 * 11 * 251 * 4051)
(26, 5 * 53 * 157 * 1613)
(27, 3^4 * 19 * 87211)
(28, 17 * 15790321)
(29, 3 * 59 * 3033169)
(30, 5^2 * 13 * 41 * 61 * 1321)
(31, 3 * 715827883)
(32, 641 * 6700417)
(33, 3^2 * 67 * 683 * 20857)
(34, 5 * 137 * 953 * 26317)
(35, 3 * 11 * 43 * 281 * 86171)
(36, 17 * 241 * 433 * 38737)
(37, 3 * 1777 * 25781083)
(38, 5 * 229 * 457 * 525313)
(39, 3^2 * 2731 * 22366891)
(40, 257 * 4278255361)
(41, 3 * 83 * 8831418697)
(42, 5 * 13 * 29 * 113 * 1429 * 14449)
(43, 3 * 2932031007403)
(44, 17 * 353 * 2931542417)
(45, 3^3 * 11 * 19 * 331 * 18837001)
(46, 5 * 277 * 1013 * 1657 * 30269)
(47, 3 * 283 * 165768537521)
(48, 193 * 65537 * 22253377)
(49, 3 * 43 * 4363953127297)
(50, 5^3 * 41 * 101 * 8101 * 268501)
(51, 3^2 * 307 * 2857 * 6529 * 43691)
(52, 17 * 858001 * 308761441)
(53, 3 * 107 * 28059810762433)
(54, 5 * 13 * 37 * 109 * 246241 * 279073)
(55, 3 * 11^2 * 683 * 2971 * 48912491)
(56, 257 * 5153 * 54410972897)
(57, 3^2 * 571 * 174763 * 160465489)
(58, 5 * 107367629 * 536903681)
(59, 3 * 2833 * 37171 * 1824726041)
(60, 17 * 241 * 61681 * 4562284561)
(61, 3 * 768614336404564651)
(62, 5 * 5581 * 8681 * 49477 * 384773)
(63, 3^3 * 19 * 43 * 5419 * 77158673929)

Gotcha! $2^{62}+1 = 5 \cdot 5581 \cdot 8681 \cdot 49477 \cdot 384773$, all well below $10^6$. To trigger the integer wrap-around, we also need to include a factor of $4$ (left shift by two bit positions) to get $4 \cdot 5 \cdot 5581 \cdot 8681 \cdot 49477 \cdot 384773 \equiv 4 \pmod{2^{64}}$. Now the (quickly growing, see observation 2) product is significantly smaller than the sum $4 + 5 + 5581 + 8681 + 49477 + 384773 = 448521$. Awesome!

The last step is pretty lame: We wrote a small python script that quickly brute-forced a last number $z$ such that the sum would match the product and found $149507$. And indeed:

% python3 -q
>>> print(4 + 5 + 5581 + 8681 + 49477 + 149507 + 384773)
598028
>>> print(4 * 5 * 5581 * 8681 * 49477 * 149507 * 384773 % 2**64)
598028
>>>