Theori of Relativity

    하얀정령

    문제 설명

    드멍이는 가을학기 중간고사를 위해 열심히 공부 중이에요.
    상대성 이론이 이해가 되지 않아 드냥이에게 물어보니, 이 문제를 풀어오면 도와주겠다고 하네요.
    문제를 풀고 드멍이의 중간고사 점수를 지켜주세요!

    Files

    ubuntu@WSL2:~/CTF/dreamhack.io$ tree Theori\ of\ Relativity
Theori of Relativity
└── relativity

0 directories, 1 file

ubuntu@WSL2:~/CTF/dreamhack.io$ file Theori\ of\ Relativity/relativity
Theori of Relativity/relativity: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=f525968be1ff734ca35e46f700fbc3f84df12440, for GNU/Linux 3.2.0, stripped

    64비트 리눅스용 실행 파일 하나.

    분석

    main

    __int64 __fastcall main(int a1, char **a2, char **a3)
{
  char s[104]; // [rsp+0h] [rbp-70h] BYREF
  unsigned __int64 v5; // [rsp+68h] [rbp-8h]

  v5 = __readfsqword(0x28u);
  printf("Key: ");
  fgets(s, 100, stdin);
  s[strcspn(s, "\n")] = 0;
  if ( sub_55B09C06D298(byte_55B09C070020, (unsigned __int8 *)s) )
    printf("Congrats! Flag is DH{%s} ...if you didn't cheat!\n", s);
  else
    puts("Hmm... :thinking_face:");
  return 0LL;
}
    1. 사용자로부터 \n 개행문자를 포함한 Key값을 100바이트만큼 입력받아 s에 넣는다.
      이때 \n 개행문자는 엔터키를 눌렀을때 자동으로 포함된다.
    2. s에서 \n 개행문자가 들어간 위치에 \n대신 0을 넣는다.
    3. byte_55B09C070020와 s를 매개변수로 지정하여 sub_55B09C06D298 함수를 호출했을 때 참이면, Flag를 출력한다.

    sub_55B09C06D298

    bool __fastcall sub_55B09C06D298(_BYTE *a1, unsigned __int8 *a2)
{
  unsigned __int8 v5; // [rsp+12h] [rbp-2Eh]
  unsigned __int8 v6; // [rsp+13h] [rbp-2Dh]
  char i; // [rsp+18h] [rbp-28h]
  __int128 v8; // [rsp+20h] [rbp-20h]

  v8 = 0uLL;
  for ( i = 0; ; ++i )
  {
    v5 = *a1 + i * i;
    v6 = *a2;
    if ( !__popcnt(v5) )
      break;
    if ( (i & 1) != 0 )
      v8 += (unsigned __int8)(v6 ^ v5);
    else
      v8 += (unsigned __int8)(v5 - v6);
    ++a1;
    ++a2;
  }
  return (int)__popcnt(v6) + v8 == 0;
}

    popcnt?

    “population count”라고도 하는데,
    레지스터나 메모리 위치에 있는 값을 이진수로 변환하여 1의 개수를 세는 어셈블리 명령이다.

    이를 테면 __popcnt(v5)에서 v5가 3이면,
    3을 2진수로 변환했을때 0b11, 즉 1이 2개 있으므로 2가 된다.

    v5가 255라면,
    255를 2진수로 변환했을때 0b11111111, 즉 1이 8개 있으므로 8이 된다.

    따라서 이 함수가 작동되는 원리를 살펴보자면,

    각각 매개변수로 나타내는 a1은 byte_55781E4DA020,
    a2는 사용자가 입력한 flag, 그러니까 main에서 입력받았던 Key인 s를 가리킨다.

    1. 루프문 안에 v5는 (byte_55781E4DA020[i] + i * i) & 255가 된다.
      마지막에 255를 and 연산하는 이유는 unsigned __int8 타입이기 때문이다.
    2. 루프문 안에 v6는 사용자로부터 입력받은 flag[i]가 된다.
    3. __popcnt(v5)가 0일때 루프문에서 빠져나온다. 즉 v5가 0일때 빠져나오게 된다.
    4. 반복 카운트인 i가 홀수이면, v8 += (unsigned __int8)(v6 ^ v5);
      반대로 0 또는 짝수이면, v8 += (unsigned __int8)(v5 – v6);
    5. byte_55781E4DA020와 flag 문자열의 인덱스를 각각 늘리고 루프문으로 돌아간다.
    6. 만약 루프문을 빠져나오게 되면, __popcnt(v6) + v8 값이 0이 되어야 참을 반환한다.

    결론적으로 각각 __popcnt(v6)가 0, v8을 0으로 만족시켜야 되는데,

    4번 과정에서 v6와 v5 값을 서로 같게 만들면 쉽게 해결할 수 있는 문제였다.

    그전에 앞서 byte_55781E4DA020를 추출시켜야할 필요가 있는데,
    이게 실행시킬때마다 무슨 이유에선지 바뀐다.

    —————————————————

    +P.S) ELF RELA Relocation Table을 참고할 것 (0x00055B09C06A628)

    https://github.com/bminor/glibc/blob/4290aed05135ae4c0272006442d147f2155e70d7/sysdeps/x86_64/dl-machine.h#L433

    —————————————————

    gdb 디버깅을 시도하면,

    __int64 sub_55B09C06D189()
{
  if ( ptrace(PTRACE_TRACEME, 0LL, 0LL, 0LL) >= 0 )
    return (unsigned int)(unsigned __int8)byte_55B09C070020[0]-- - 1;
  else
    return (unsigned int)(unsigned __int8)byte_55B09C070020[0]++ + 1;
}

    ptrace 함수를 통해 디버깅을 감지해서 byte_55B09C070020 데이터가 또 바뀌기 때문에
    그냥 후킹 라이브러리를 따로 만들어서 추출하기로 했다.

    //gcc -shared -fPIC -o hook_puts.so hook_puts.c -ldl
//LD_PRELOAD=./hook_puts.so ./relativity

#define _GNU_SOURCE

#include <dlfcn.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

typedef int (*org_puts)(const char *str);

int puts(const char *str) {

    char new_str[1024];
    org_puts original_puts;
    original_puts = (org_puts) dlsym(RTLD_NEXT, "puts");
    printf("hooked str: %s\n", str);

    strcpy(new_str, str);

    uint64_t main_address = 0x555555557384 + 0x2c9c;    
    //main address + (main ~ byte_55B09C070020간 거리)

    size_t num_bytes = 0; 
    uint8_t buffer[1024];

    // 메모리 주소에서 바이트 단위로 읽어오기
    for (size_t i = 0; ; i++) {
        if(*((uint8_t *)(main_address + i)) == 0xFF)
            break;
        buffer[i] = *((uint8_t *)(main_address + i));
        num_bytes++;
    }

    for (size_t i = 0; i < num_bytes; i++) {
        printf("0x%02x ", buffer[i]);
    }
    printf("\n");

    return original_puts(new_str);
}

    위 코드는 Hmm… :thinking_face: 문구를 출력시키는 puts함수에 후킹을 거는 코드를 작성하고
    후킹건 함수에서 byte_55B09C070020에 담긴 데이터를 덤프시킨다.

    ASLR을 비활성화하고, LD_PRELOAD 환경변수를 통해서 위 코드로 만든 라이브러리를 로드시키면 된다.

    ubuntu@WSL2:~/CTF/dreamhack.io/Theori of Relativity$ gcc -shared -fPIC -o hook_puts.so hook_puts.c -ldl
ubuntu@WSL2:~/CTF/dreamhack.io/Theori of Relativity$ sudo sysctl kernel.randomize_va_space=0
kernel.randomize_va_space = 0
ubuntu@WSL2:~/CTF/dreamhack.io/Theori of Relativity$ LD_PRELOAD=./hook_puts.so ./relativity
Key: aaaaaaaaaaaaaaaaa
hooked str: Hmm... :thinking_face:
0x31 0x63 0x30 0x2c 0x29 0x4d 0x3e 0x33 0x24 0xe7 0xd1 0xbf 0xa0 0x8a 0xa1 0x57 0x32 0x11 0xef 0xfa 0xa2 0xa8 0x4d 0x20 0xf6 0xbf 0x90 0x8b 0x51 0x1a 0xb3 0x71 0x38 0x20 0xdf 0x9c 0x51 0x0d 0xc2 0x71 0x23 0xa3 0x51 0xfb 0xd1 0x7c 0x20 0xc2 0x65 0xd4 0x72 0x39 0xa1 0x68 0xd4 0x93 0xf4 0xb4 0x0c 0x9d 0x23 0xaa 0x32 0xaf 0x00 0x7f 0xfc 0x77 0xf0 0x67 0xdc 0x4f 0xc0 0x2f 0x9c 0x07 0x70 0xd7 0x3c 0x9f 0x00 0x5f 0xbc 0x17 0x70 0xc7 0x1c 0x6f 0xc0 0x0f 0x5c 0xa7 0xf0 0x37 0x7c 0xbf 0x00 0x3f 0x7c 0xb7 0x00 0x00 0x00
Hmm... :thinking_face:
    char byte_55B09C070020[104]
31 63 30 2c 29 4d 3e 33 
24 e7 d1 bf a0 8a a1 57
32 11 ef fa a2 a8 4d 20
f6 bf 90 8b 51 1a b3 71
38 20 df 9c 51 0d c2 71
23 a3 51 fb d1 7c 20 c2
65 d4 72 39 a1 68 d4 93
f4 b4 0c 9d 23 aa 32 af
00 7f fc 77 f0 67 dc 4f
c0 2f 9c 07 70 d7 3c 9f
00 5f bc 17 70 c7 1c 6f
c0 0f 5c a7 f0 37 7c bf
00 3f 7c b7 00 00 00 ff

    Python3로 구현시킨 sub_55B09C06D298 함수

    decrypted_byte_55781E4DA020 = [0x31, 0x63, 0x30, 0x2C, 0x29, 0x4D, 0x3E, 0x33,\
                               0x24, 0xE7, 0xD1, 0xBF, 0xA0, 0x8A, 0xA1, 0x57,\
                               0x32, 0x11, 0xEF, 0xFA, 0xA2, 0xA8, 0x4D, 0x20,\
                               0xF6, 0xBF, 0x90, 0x8B, 0x51, 0x1A, 0xB3, 0x71,\
                               0x38, 0x20, 0xDF, 0x9C, 0x51, 0x0D, 0xC2, 0x71,\
                               0x23, 0xA3, 0x51, 0xFB, 0xD1, 0x7C, 0x20, 0xC2,\
                               0x65, 0xD4, 0x72, 0x39, 0xA1, 0x68, 0xD4, 0x93,\
                               0xF4, 0xB4, 0x0C, 0x9D, 0x23, 0xAA, 0x32, 0xAF,\
                               0x00, 0x7F, 0xFC, 0x77, 0xF0, 0x67, 0xDC, 0x4F,\
                               0xC0, 0x2F, 0x9C, 0x07, 0x70, 0xD7, 0x3C, 0x9F,\
                               0x00, 0x5F, 0xBC, 0x17, 0x70, 0xC7, 0x1C, 0x6F,\
                               0xC0, 0x0F, 0x5C, 0xA7, 0xF0, 0x37, 0x7C, 0xBF,\
                               0x00, 0x3F, 0x7C, 0xB7, 0x00, 0x00, 0x00]

def popcnt(n):
    return bin(n).count('1')

# my_flag = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKL"
my_flag = "1d459fbdd85803e8223c2a11604dac728aceaffbc454aedce56b1a8d4e063360"
my_flag = [ord(char) for char in my_flag]
my_flag.append(0)

# print(my_flag)

val = 0
v8 = 0
i = 0
tmp = 0
sum_tmp = 0

guessed_flag = []

while True:
    # print(i)
    v5 = (decrypted_byte_55781E4DA020[i] + i * i) & 255
    v6 = my_flag[i]
    if(popcnt(v5) == 0):
        # print(i) -> 64, always
        # print(decrypted_byte_55781E4DA020[i]) -> 0, always
        # print(v5) -> 0, always
        print(f"[FINAL] v5 = {v5}, v8 = {v8}, v6 = {v6}")
        val = popcnt(v6) + v8
        break
    if i & 1 != 0:
        print(f"[A] v5 = {v5}, v8 = {v8}, v6 = {v6}, tmp = {tmp}")
        tmp = ((v6 ^ v5) & 255)
        v8 = v8 + tmp
        print(f"[a] v5 = {v5}, v8 = {v8}, v6 = {v6}, tmp = {tmp}")
        guessed_flag.append(v5)
    else:
        print(f"[B] v5 = {v5}, v8 = {v8}, v6 = {v6}, tmp = {tmp}")
        tmp = ((v5 - v6) & 255) #tmp + v6 = v5, v6 = v5-tmp
        v8 = v8 + tmp
        print(f"[b] v5 = {v5}, v8 = {v8}, v6 = {v6}, tmp = {tmp}")
        guessed_flag.append(v5)
    i+=1

# print(hex(val))
print(f"val = {hex(val)}, {val}") #should return 0

    Solution

    decrypted_byte_55781E4DA020 = [0x31, 0x63, 0x30, 0x2C, 0x29, 0x4D, 0x3E, 0x33,\
                               0x24, 0xE7, 0xD1, 0xBF, 0xA0, 0x8A, 0xA1, 0x57,\
                               0x32, 0x11, 0xEF, 0xFA, 0xA2, 0xA8, 0x4D, 0x20,\
                               0xF6, 0xBF, 0x90, 0x8B, 0x51, 0x1A, 0xB3, 0x71,\
                               0x38, 0x20, 0xDF, 0x9C, 0x51, 0x0D, 0xC2, 0x71,\
                               0x23, 0xA3, 0x51, 0xFB, 0xD1, 0x7C, 0x20, 0xC2,\
                               0x65, 0xD4, 0x72, 0x39, 0xA1, 0x68, 0xD4, 0x93,\
                               0xF4, 0xB4, 0x0C, 0x9D, 0x23, 0xAA, 0x32, 0xAF,\
                               0x00, 0x7F, 0xFC, 0x77, 0xF0, 0x67, 0xDC, 0x4F,\
                               0xC0, 0x2F, 0x9C, 0x07, 0x70, 0xD7, 0x3C, 0x9F,\
                               0x00, 0x5F, 0xBC, 0x17, 0x70, 0xC7, 0x1C, 0x6F,\
                               0xC0, 0x0F, 0x5C, 0xA7, 0xF0, 0x37, 0x7C, 0xBF,\
                               0x00, 0x3F, 0x7C, 0xB7, 0x00, 0x00, 0x00]

def popcnt(n):
    return bin(n).count('1')

i = 0
flag = []

while True:
    v5 = (decrypted_byte_55781E4DA020[i] + i * i) & 255
    if(popcnt(v5) == 0):
        break
    if i & 1 != 0:
        flag.append(v5)
    else:
        flag.append(v5)
    i+=1

for i in range(len(flag)):
    print(chr(flag[i]), end='')

    FLAG

    ubuntu@WSL2:~/CTF/dreamhack.io/Theori of Relativity$ ./relativity
Key: 1d459fbdd85803e8223c2a11604dac728aceaffbc454aedce56b1a8d4e063360
Congrats! Flag is DH{1d459fbdd85803e8223c2a11604dac728aceaffbc454aedce56b1a8d4e063360} …if you didn't cheat!

    DH{1d459fbdd85803e8223c2a11604dac728aceaffbc454aedce56b1a8d4e063360}

    Related Posts

    답글 남기기

    이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다