[Dreamhack] similar

1. main

__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  unsigned int buf; // [rsp+8h] [rbp-218h] BYREF
  unsigned int i; // [rsp+Ch] [rbp-214h]
  int j; // [rsp+10h] [rbp-210h]
  int fd; // [rsp+14h] [rbp-20Ch]
  char *lineptr; // [rsp+18h] [rbp-208h] BYREF
  size_t n; // [rsp+20h] [rbp-200h] BYREF
  FILE *stream; // [rsp+28h] [rbp-1F8h]
  unsigned int base[122]; // [rsp+30h] [rbp-1F0h] BYREF
  unsigned __int64 v12; // [rsp+218h] [rbp-8h]

  v12 = __readfsqword(0x28u);
  sub_18A2(a1, a2, a3);
  fd = open("/dev/urandom", 0);
  read(fd, &buf, 4uLL);
  srand(buf);
  puts("Values:");
  for ( i = 0; (int)i <= 29; ++i )
  {
    base[4 * i] = rand() % 200 - 100;
    base[4 * i + 1] = rand() % 200 - 100;
    base[4 * i + 2] = rand() % 200 - 100;
    base[4 * i + 3] = i;
    printf("%d: %d %d %d\n", i, base[4 * i], base[4 * i + 1], base[4 * i + 2]);
  }
  qsort(base, 0x1EuLL, 0x10uLL, compar);
  puts("Result?");
  for ( j = 0; j <= 29; ++j )
  {
    __isoc99_scanf("%d", &n);
    if ( base[4 * j + 3] != (_DWORD)n )
    {
      puts("Wrong...");
      return 0LL;
    }
  }
  lineptr = 0LL;
  n = 0LL;
  stream = fopen("./flag", "r");
  getline(&lineptr, &n, stream);
  printf("Bingo! Flag: %s", lineptr);
  free(lineptr);
  fclose(stream);
  return 0LL;
}

base 배열을 랜덤으로 만들고 compar 함수에 따라서 정렬한 다음에 해당 결과값을 똑같이 입력해주면 된다.

2. compar

__int64 __fastcall compar(_QWORD *a1, __int64 *a2)
{
  double v3; // [rsp+18h] [rbp-38h]
  double v4; // [rsp+20h] [rbp-30h]
  __int64 v5; // [rsp+40h] [rbp-10h]
  __int64 v6; // [rsp+48h] [rbp-8h]

  v5 = *a2;
  v6 = a2[1];
  v3 = sub_16A3(*a1, a1[1]);
  v4 = sub_16A3(v5, v6);
  if ( v3 - v4 < 0.0000001 )
    return 0LL;
  if ( v4 <= v3 )
    return 1LL;
  return 0xFFFFFFFFLL;
}

3. sub_16A3

double __fastcall sub_16A3(__int64 a1, int a2)
{
  double v3; // [rsp+18h] [rbp-28h]

  v3 = sqrt((double)3);
  return 1.0
       - (double)(HIDWORD(a1) + (int)a1 + a2)
       / (sqrt((double)(HIDWORD(a1) * HIDWORD(a1) + (int)a1 * (int)a1 + a2 * a2))
        * v3);
}

벡터 v = (x,y,z)
벡터 u = (a,b,c)
둘의 내적값을 벡터 v, u의 크기로 나눈 것과 같다. 즉, 두 벡터 사이의 코사인 값을 뜻한다.

이번 문제는 C로 다시 구현하는게 나을 것 같다. 라고 하기에는 vm을 열어야 되는구나.

찾아보니 python 내에서도 내가 원하는 방식대로 정렬할 수 있는 모듈이 있다. lambda보다 더 구체적으로 함수를 지정할 수 있다.

https://wikidocs.net/24603

64비트, 32비트, signed, unsigned 모두 확인하다가 진짜 모르겠어서 그냥 내적 코사인 값 구하는 방법을 쳐보니 바로 나온다...

(1, 1, 1)과의 유사도를 1에서 뺀 것. 유사도가 높을 수록 값이 작아진다. 그래도 0.0000001의 비교치가 있기 때문에 이것만 수정해보자.

이렇게 해도 TypeError: loop of ufunc does not support argument 0 of type int which has no callable sqrt method 에러가 나서 이것저것 시도해보다가 다시 어셈블리를 살펴보았다.

그러던 중 내가 엄청난 삽질을 하고 있었다는 걸 깨달았다...
base에 각각의 값을 넣고 sort는 64bit 기준으로 하길래 64bit로 저장하고 연산을 더 해야 하는 줄 알았다. 그런데 어셈블리로 살펴보니 이상하게 다 eax였다. 메모리를 그리고 인덱스를 정리해보니 결국에는 base[4*i], base[4*i+1], base[4*i+2]에 대한 벡터를 만들면 끝이었다.

이렇게 푸니까 바로 풀린다...ㅋㅋㅋㅋㅋ

p.sendline으로 바로 보내니까 마지막에 에러 나서 수동으로 입력하니 해결됐다.

4. exploit.py

from pwn import *
from functools import cmp_to_key
import numpy as np
from numpy import dot
from numpy.linalg import norm

def cos_sim(a,b,c):

    doc1 = np.array([a, b, c])
    doc2 = np.array([1, 1, 1])
    return 1.0 - (dot(doc1, doc2) / (norm(doc1) * norm(doc2)))

def compare(arr):
    n = len(arr)

    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j][0]-arr[j+1][0] >= 0.0000001:
                arr[j], arr[j+1] = arr[j+1], arr[j]


#p = process('./similar')
p = remote('host1.dreamhack.games', 9035)
base = []
p.recvline()

for i in range(30):
    data = p.recvline().split()
    base.append([cos_sim(int(data[1]), int(data[2]), int(data[3])), i])

compare(base)
p.recvline()
print(base)

'''
for i in range(30):
    idx = base[i][1]
    print(idx)
    p.send(p64(idx))
'''
p.interactive()