[Dreamhack] hash-browns

1. main

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  unsigned int i; // [rsp+4h] [rbp-21Ch]
  char *v5; // [rsp+8h] [rbp-218h]
  char state_arr[88]; // [rsp+10h] [rbp-210h] BYREF
  __int64 v7; // [rsp+68h] [rbp-1B8h] BYREF
  __int64 v8[18]; // [rsp+80h] [rbp-1A0h] BYREF
  __int64 buf[34]; // [rsp+110h] [rbp-110h] BYREF

  buf[33] = __readfsqword(0x28u);
  v8[0] = 0xFE5D3A093968D02BLL;
  v8[1] = 0xBA0AA367C2862EAELL;
  v8[2] = 0x8BEA2ADA9E26604FLL;
  v8[3] = 0x2E6F41C96DCF5224LL;
  v8[4] = 0x7FD91BD2949B75F3LL;
  v8[5] = 0x5B1ED8E6072F3A6LL;
  v8[6] = 0xC94045C6D4887611LL;
  v8[7] = 0x9D43DF6DF6B94D95LL;
  v8[8] = 0xB9A8A83C8AC08D80LL;
  v8[9] = 0x6D78E80376518464LL;
  v8[10] = 0xE81A20F2023C2D0LL;
  v8[11] = 0x2E41EAE69D89F186LL;
  v8[12] = 0x425C831DD2A3E5FDLL;
  v8[13] = 0x82788DBBDC4100ECLL;
  v8[14] = 0x6D0FEE8D3901DD20LL;
  v8[15] = 0xEBE82A0A41E5D783LL;
  v8[16] = 0x2AFA26414B72E506LL;
  v8[17] = 0xD1848E9C21D114DLL;
  memset(buf, 0, 256);
  printf("Input : ");
  fflush(stdout);
  read(0, buf, 0x100uLL);
  v5 = strchr((const char *)buf, '\n');
  if ( v5 )
    *v5 = 0;
  for ( i = 0; i <= 8; ++i )
  {
    md5_state(state_arr);
    add_block(state_arr, (char *)buf + (int)(3 * i), 3LL);
    hash(state_arr);
    if ( memcmp(&v7, &v8[2 * (int)i], 0x10uLL) )
    {
      puts("Wrong!");
      return 1LL;
    }
  }
  *((_BYTE *)buf + (int)(3 * i)) = 0;
  printf("Correct! Flag is %s\n", (const char *)buf);
  return 0LL;
}

드림핵 사이트에서 참고자료를 열면 암호화 해시 함수가 뜬다.
https://ko.wikipedia.org/wiki/%EC%95%94%ED%98%B8%ED%99%94_%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

참고해서 함수들을 살펴보면 for문 내의 첫 번째 함수(md5_state)가 의심이 된다.
별다른 연산 없이 state_arr 초기화만 진행하기 때문이다.

이에 대해 조사하면 md5 state 값이라는 것을 알 수 있다.

2. MD5 해시함수
   https://ko.wikipedia.org/wiki/MD5
   입력값을 512bit 블록으로 쪼개고 128bit의 출력값을 내놓는 해시 함수

A, B, C, D(각 32bit, 총 128bit)의 초기 state를 가지고 여기에 연산을 거듭하여 최종 결과를 만든다.

이를 바탕으로 코드를 살펴보면 두 번째 함수와 세 번째 함수의 역할 또한 알 수 있다.
두 번째 함수는 각 블록에 buf(입력값)을 추가하는 함수이고
세 번째 함수는 본격적으로 해시를 계산하는 함수다.

마지막으로 계산된 해시를 v8과 비교한다.

이때 buf의 3바이트씩 해시를 각각 계산한다는 점에 주의해야 한다.
또한 이 특징은 brute-force가 가능하게 해준다.

다만, 문제를 풀 때 기존의 해시값들을 어떻게 인식해야 실행 파일에서 memcmp을 활용하는 것과 동일하게 비교할 수 있는지가 헷갈렸던 부분이다.

원래는 기존의 것들을 little endian으로 변환했을 때 16byte로 인식할 경우 어떤 값이 되는지에 주목했는데 잘 생각해보면 md5는 결과값을 little-endian으로 출력한다.
따라서 우리도 저장된 값을 little endian으로 인식하면 된다.

0xFE5D3A093968D02B, 0xBA0AA367C2862EAE
-> 2b d0 68 39 09 3a 5d fe ae 2e 86 c2 67 a3 0a ba

3. exploit.py

import hashlib
from string import printable

whitelist = printable

arr = [
    0xFE5D3A093968D02B, 0xBA0AA367C2862EAE, 0x8BEA2ADA9E26604F, 0x2E6F41C96DCF5224,
    0x7FD91BD2949B75F3, 0x5B1ED8E6072F3A6, 0xC94045C6D4887611, 0x9D43DF6DF6B94D95,
    0xB9A8A83C8AC08D80, 0x6D78E80376518464, 0xE81A20F2023C2D0, 0x2E41EAE69D89F186,
    0x425C831DD2A3E5FD, 0x82788DBBDC4100EC, 0x6D0FEE8D3901DD20, 0xEBE82A0A41E5D783,
    0x2AFA26414B72E506, 0xD1848E9C21D114D
]
arr2 = [0 for i in range(9)]

for i in range(9):
    for j in range(8):
        arr2[i]  = arr2[i] << 8
        arr2[i] = arr2[i] | (arr[2*i] & 0xff)
        arr[2*i] = arr[2*i] >> 8
    for j in range(8):
        arr2[i]  = arr2[i] << 8
        arr2[i] = arr2[i] | (arr[2*i+1] & 0xff)
        arr[2*i+1] = arr[2*i+1] >> 8

flag = ''
for i in range(9):
    for idx1 in range(len(whitelist)):
        for idx2 in range(len(whitelist)):
            for idx3 in range(len(whitelist)):
                temp = whitelist[idx1] + whitelist[idx2] + whitelist[idx3]
                test = int(hashlib.md5(temp.encode('utf-8')).hexdigest(), 16)
                if test == arr2[i]:
                    flag += temp
                    break

    print(flag)

드림핵 2단계까지는 코드 해석 + 역연산만 가능했다면 모두 해결 가능한 문제였다.

하지만 3단계부터는 코드 해석을 통해서 이게 어떤 알고리즘을 뜻하는지를 알아내야 문제를 해결할 수 있다. (코드를 보면 이건 직접 역연산하라고 만든 코드가 아니라고 느껴진다) 즉, 기초 지식이 있어야 해결이 가능한 문제들이다.
또한 코드 해석을 잘 하더라도 사이에 함정이 숨겨져 있어서 이걸 간과하면 문제 알고리즘은 정확히 해석했더라도 해결이 완전 엉뚱한 방향으로 가게 된다.

앞으로 문제 풀면서 이런 것들을 유의하며 풀어갔으면 한다.