Freshwater

In Cyberthon 2022, 1000 points

Spies have exfiltrated some binary that is important to APOCALYPSE's agent movements.

This binary is codenamed FRESH-WATER and prints out many numbers. When given some random input, it errors out "Wrong" with some strange hash.

Can you find the "Correct" hash?

Please give us the flag in the format: Cyberthon

Challenge files: freshwater

Opening up the binary in IDA or ghidra, we are faced with a pretty daunting main function:

  srand('l\xACP');
  for ( i = 0; i <= 499; ++i )
  {
    for ( j = 0; j <= 499; ++j )
    {
      v3 = rand();
      if ( v3 <= 0 )
        LOBYTE(v3) = -(char)v3;
      output_mat[500 * i + j] = (unsigned __int8)v3;
      std::ostream::operator<<(&std::cout, output_mat[500 * i + j]);
      if ( j != 499 )
        std::operator<<<std::char_traits<char>>(&std::cout, 32LL);
    }
    a2 = (char **)(byte_9 + 1);
    std::operator<<<std::char_traits<char>>(&std::cout, 10LL);
  }
  for ( k = 0; k <= 499; ++k )
  {
    for ( m = 0; m <= 499; ++m )
    {
      for ( n = 0; n <= 499; ++n )
      {
        v11 = output_mat[500 * m + k] + output_mat[500 * k + n];
        a2 = (char **)&v11;
        v4 = (unsigned int *)min(&output_mat[500 * m + n], &v11);
        output_mat[500 * m + n] = *v4;
      }
    }
  }
  for ( ii = 0; ii <= 499; ++ii )
  {
    for ( jj = 0; jj <= 499; ++jj )
    {
      a2 = (char **)&input_mat[500 * ii + jj];
      std::istream::operator>>(&std::cin, a2);
    }
  }
  v16 = 1;
  std::__cxx11::basic_ostringstream<char,std::char_traits<char>,std::allocator<char>>::basic_ostringstream(v10, a2);
  for ( kk = 0; kk <= 499; ++kk )
  {
    for ( mm = 0; mm <= 499; ++mm )
    {
      v16 = v16 && output_mat[500 * kk + mm] == input_mat[500 * kk + mm];
      std::ostream::operator<<(v10, input_mat[500 * kk + mm]);
    }
  }
 std::ostream::operator<<(v10, &std::endl<char,std::char_traits<char>>);
  if ( v16 )
    v5 = std::operator<<<std::char_traits<char>>(&std::cout, "Correct");
  else
    v5 = std::operator<<<std::char_traits<char>>(&std::cout, "Wrong");

Upon further observation, it's clear that the program was written in C++ (the std::ostream::operator<< is a giveaway).

The main function consists of a couple of loops that fill the output_mat with random integers and do some operations on them.

However, the part we are interested in lies in the final for loops which I have reproduced below:

v16 = 1;
 for ( kk = 0; kk <= 499; ++kk )
  {
    for ( mm = 0; mm <= 499; ++mm )
    {
      v16 = v16 && output_mat[500 * kk + mm] == input_mat[500 * kk + mm];
      std::ostream::operator<<(v10, input_mat[500 * kk + mm]);
    }
  }
if ( v16 )
    v5 = std::operator<<<std::char_traits<char>>(&std::cout, "Correct");

For the Correct message to be printed, all the output_mat elements from 0 to 249999 must match the corresponding elements in the input_mat.

Therefore, I decided to use dynamic analysis to solve this challenge. Debugging the binary in gdb and setting a breakpoint on the cmp instruction responsible for comparing the elements in the input and output matrices, we can dump the memory of the output matrix:

dump binary memory result.bin  0x55555555a340 0x55555564e580

The addresses correspond to the start and end of the matrix and can be obtained either through inspecting the instructions in gdb or through IDA/ghidra.

Once we have extracted the memory, I wrote a simple script to feed the integers back to the program. As integers are 4 bytes and stored as little endian, we chunk the memory into 4 byte chunks and use python to parse the bytes as an integer:

from pwn import *
f = open("./result.bin", "rb").read()
y = [int.from_bytes(f[x:x+4],'little') for x in range(0,len(f), 4)]
p = process("./freshwater")
p.clean()
for x in y:
    p.sendline(str(x))
p.interactive()

And the flag is obtained:

[+] Starting local process './freshwater': pid 13812
[*] Switching to interactive mode
Correct
e043849f289bbd548efc73aa1bb085395c82cbcbe1671625dc848df67f213f5e
[*] Process './freshwater' stopped with exit code 0 (pid 13812)