DEFCON 19 Final – hiver

This challenge was on logic and understanding of the bloom filter. The binary is for FreeBSD.

binary

Summary: understanding of the bloom filter, bruteforce bloom filter set.

The given program is a forking tcp server which listens to 44366 port.  When connection is established it drops privileges to “hiver” user and forks handler function (0x08049790):

int __cdecl main(int fd)
{
  BLOOM *lpMem; // esi@1
  FILE *hKey; // eax@2
  FILE *hKey2; // edi@2
  int idx; // ecx@3
  int result; // eax@6
  void *receivedData; // eax@8
  const char *receivedData2; // ebx@8
  signed int receivedLength; // eax@9
  int set_of_bits; // eax@15
  _BYTE s[1024]; // [sp+48h] [bp-410h]@3
  size_t size; // [sp+448h] [bp-10h]@5

  lpMem = bloom_create(
            0x140u,
            0xAu,
            hash_func1,
            hash_func2,
            hash_func3,
            hash_func4,
            hash_func5,
            hash_func6,
            hash_func7,
            hash_func8,
            hash_func9,
            hash_funcA);
  if ( lpMem )
  {
    hKey = fopen("key", "r");
    hKey2 = hKey;
    if ( hKey )
    {
      fgets(s, 1024, hKey);
      fclose(hKey2);
      idx = 0;
      do
      {
        lpMem->key[idx] = s[idx];
        ++idx;
      }
      while ( idx != 40 );
      if ( ReadDataFromSocket(fd, &size, 4u) != 4
        || size > 0x400
        || (receivedData = malloc(size), (receivedData2 = (const char *)receivedData) == 0) )
        return 0;
      receivedLength = ReadDataFromSocket(fd, receivedData, size);
      if ( receivedLength == size )
      {
        receivedData2[receivedLength] = 0;
        if ( strstr(receivedData2, "cat key") )
        {
          CheckJury(fd, 0);
          return 0;
        }
        set_of_bits = bloom_check(lpMem, (char *)receivedData2);
        SenDataToSocet_(fd, "%d\n", set_of_bits);
      }
      bloom_destroy(lpMem);
      return 0;
    }
    fwrite("ERROR: Could not open file", 1u, 0x1Au, _stderrp);
    result = 0;
  }
  else
  {
    fwrite("ERROR: Could not create bloom filter\n", 1u, 0x25u, _stderrp);
    result = 0;
  }
  return result;
}

First of all, it creates a Bloom filter with 10 hash functions and set size 140h bits (40 bytes – size of flag).
Then program reads flag from key file and copies it to the Bloom filter set.
When filter is filled information from key file, the program reads data from socket and call bloom_check function (0x0804B990):

int __cdecl bloom_check(BLOOM *bloom, char *input_data)
{
  size_t n; // ebx@2
  unsigned int hash; // eax@3
  unsigned __int8 *v4; // ebx@6
  int result_; // [sp+8h] [bp-10h]@1

  result_ = 0;
  if ( bloom->nfuncs )
  {
    n = 0;
    do
    {
      hash = bloom->funcs[n](input_data);
      if ( ((signed int)bloom->key[hash % bloom->key_size >> 3] >> ((unsigned __int8)hash
            % LOBYTE(bloom->key_size) & 7)) & 1 )
        result_ += 1 << n;
      ++n;
    }
    while ( bloom->nfuncs > n );
  }
  v4 = &bloom->key[rand() % bloom->key_size >> 3];
  *v4 ^= 1 << (rand() % bloom->key_size & 7);
  return result_;
}

That function calculates every hash function from the Bloom filter list for input data and checks whether the data is in the Bloom filter set. Each hash function corresponds to one bit in the answer. Position of bit is determined by number of hash function and hash value, the value of bit (1 or 0) depends on appropriate value in the Bloom filter set (in other words depends on key).

So, to get all bits of the key (of the Bloom filter set) we need to generate set of appropriate input data. Because of the Bloom filter set is very small, it is not so hard to achieve. We did it with a little more than 30 different input strings.

P.S.

Thanks vos for help in solving the task.