티스토리 뷰
최종 수정: 2015-10-27
hackability@TenDollar
안녕하세요. Hackability 입니다.
이번 포스팅은 2015 TrendMicro 에서 BlackJack 다음으로 저를 빡(?)치게 했던 Maze 라는 문제 입니다.... -_-;; 왜 해킹 대회에 이런 문제들이 나오는지 ....
Maze (미로찾기)
먼저 맵 파일이랑 자동으로 돌려서 푼 답에 대한 코드는 다음과 같습니다. 재미로 확인해보세요 :-)
먼저 문제자체는 간단합니다.
5 3 0
#####
#G.S#
#####
와 같이 주어 집니다.
첫 줄의 5는 row, 3은 col, 0은 check point의 수 입니다.
G는 Goal 이고 S는 시작 지점입니다. 이 문제의 정답은 LL 입니다 (왼쪽, 왼쪽 이동)
다른 문제를 보면
7 7 0
#######
# . . . . . #
##### . #
# . . S . . #
# . #####
# . . G . . #
#######
이러면 정답으로 LLDDRR (왼쪽 두번, 아래 두번, 오른쪽 두번)
뭐 이런식으로 풀면 됩니다. 이런식의 류는 인터넷에 찾아 보면 뭐 알고리즘이나 자료구조 공부 할때 많은 예제들이 있는데 이번 CTF에서는 2가지 룰이 더 추가 됩니다.
한 가지는 check point입니다.
11 11 1
###########
# .# .# .# . . . #
# .# .# .# .###
# . . . . . . . # .#
### .#####.#
# . . G#.# . . .#
### .# .# .# .#
# .# . . .# .# S#
# .# .# .# .###
#C . .# . . . . .#
###########
이런 문제의 경우 바로 G로 가면 되는게 아니라 반드시 맵에 있는 C (Checkpoint)를 모두 먹고 G로 가야지 인정이 됩니다. 따라서 이런 문제는 정답이 UULLDDDDLLUULLDDLLRRUURUU 이 되겠네요
하지막 룰은 Energy 입니다. 맵 중간 중간에 E 라는 것도 있는데 이는 에너지 로써 움직일때마다 에너지가 깍입니다. 초반에 주어지는 에너지는 13000 이며 에너지를 하나 먹을 때 마다 20씩 증가 합니다. 사실 저는 Check point이후, Energy를 먹는 로직도 추가 했어야 했는데 이 로직을 넣지 않아도 에너지가 130인가 남고 깨졌습니다.
일단 이걸로 문제 설명은 대충 끝내고 ... 먼저 한 가지 중요한개 이 맵이 1001개 입니다... 후 ....
초기 230개 까지는 체크 포인트가 없어서 230개 정도 까지는 금방 마무리 했는데 그 다음 부터는 모든 맵에 체크 포인트가 존재 합니다.
그리고 후반부 맵 보시면 ... -_-
15 17 2
###############
# E . . . . . . # . . G# .#
##### .### .# . # .#
# . # . . . . . . . # . . . #
# . #######.#####
# . . C . . . S #. . . . . #
### . # .# .# .#####
# . . . # . # . . . . . . . #
# .# . ####### .###
# . . . # . # .# . . . . . #
### .# . # .#######
# . . . . . # . # . . . . C#
### .# .# .##### . #
# . . . # . . . # .# .# . #
# .# .# . # .# .# .# . #
# .# .# E# . . . . . . . #
###############
맵 파일은 파일 첨부에 올렷으니 확인하시면 됩니다.
마지막으로 소스에 고려된 사항은 다음과 같습니다.
1. 길 찾기는 Recursive 로 코딩
2. 방금 온길은 다시 돌아 가지 않도록 코딩
3. 만약 내가 오른쪽으로 갓는데 도착지에 도착하지 않고 다시 내가 온길 밖에 없게 된다면 아까 오른쪽으로 결정했던 곳부터 다시 결정을해 왼쪽으로 갈 수 있도록 코딩
4. 체크 포인트를 모두 먹고 Goal 로 가도록 코딩
5. 그리고 답이 나오면 답을 검증 하는 프로그램도 추가
maze.py
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 | import sys energy = 13000 wall = '#' start = 'S' goal = 'G' checks = 'C' drink = 'E' nothing = '.' maps = [] check = {} def verify(maps, answer, s_x, s_y, e_x, e_y): for i in range(0, len(answer)): ch = answer[i] if ch == 'L': s_x = s_x - 1 elif ch == 'R': s_x = s_x + 1 elif ch == 'U': s_y = s_y - 1 elif ch == 'D': s_y = s_y + 1 if maps[s_y][s_x] == '#': return False if i == (len(answer) - 1): if s_y != e_y or s_x != e_x: #if maps[s_y][s_x] != 'G': return False return True def search(maps, s_x, s_y, e_x, e_y, m_x, m_y, opt, check): #print "\t( %d , %d ) -> " % (s_y, s_x), if s_y == e_y and s_x == e_x: return '' check_str = "%d_%d" % (s_y, s_x) if check.has_key(check_str): #print ' [!] ALREADY WALKED (opt = %d)' % (opt) return False check[check_str] = 1 if opt == 0: if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y): return 'R' + res if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y): return 'L' + res if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y): return 'D' + res if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y): return 'U' + res elif opt == 1: if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y): return 'L' + res if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y): return 'D' + res if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y): return 'U' + res if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y): return 'R' + res elif opt == 2: if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y): return 'D' + res if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y): return 'U' + res if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y): return 'R' + res if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y): return 'L' + res elif opt == 3: if (s_y - 1 >= 0) and maps[s_y-1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y-1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y-1, e_x, e_y): return 'U' + res if (s_x + 1 < m_x) and maps[s_y][s_x+1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x+1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x+1, s_y, e_x, e_y): return 'R' + res if (s_x - 1 >= 0) and maps[s_y][s_x-1] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x-1, s_y, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x-1, s_y, e_x, e_y): return 'L' + res if (s_y + 1 < m_y) and maps[s_y+1][s_x] != '#': tmp_check = check for opt in range(0, 4): res = search(maps, s_x, s_y+1, e_x, e_y, m_x, m_y, opt, tmp_check) if res != False and verify(maps, res, s_x, s_y+1, e_x, e_y): return 'D' + res return False for i in range(0, 1001): print name = './maze/%04d.map' % (i) fd = open(name, 'r') data = fd.read().splitlines() fd.close() info = data[0].split(" ") x = int(info[0]) y = int(info[1]) c = info[2] for j in range(1, len(data)): ind_s = data[j].find('S') if ind_s > -1: s_y = j-1 s_x = ind_s ind_e = data[j].find('G') if ind_e > -1: e_y = j-1 e_x = ind_e maps.append(data[j]) check_point = [] for j in range(1, len(data)): for k in range(0, len(data[j])): if data[j][k] == 'C': check_point.append([j-1, k]) if len(check_point) != 0: ''' LOG CHECK POINTS fd = open("maze_check_point.txt", "a") fd.write("%05d\n" % (i)) fd.close() ''' pass print "LEVEL : %4d" % (i) for m in maps: print m answer = '' check = {} if len(check_point) == 0: print '( %d , %d ) -> ( %d , %d )' % (s_x, s_y, e_x, e_y) answer = search(maps, s_x, s_y, e_x, e_y, x, y, 0, {}) print print "ANSWER : %s" % (answer) else: print "SHOULD HAVE CHECK POINTS !!!" skip = [] check = {} for j in range(0, len(check_point)): if j in skip: continue #print "( %d , %d ) -> ( %d , %d )" % (s_y, s_x, check_point[j][0], check_point[j][1]) check = {} for opt in range(0, 4): res = search(maps, s_x, s_y, check_point[j][1], check_point[j][0], x, y, opt, {}) if res != False: break print if res == False: print "( %d , %d ) -> ( %d , %d )" % (s_y, s_x, check_point[j][0], check_point[j][1]) print "[WARNING] : %05d" % (i) sys.exit(-1) break for k in check: tmp = k.split("_") tmp_y = tmp[0] tmp_x = tmp[1] for l in range(j+1, len(check_point)): if check_point[l][1] == tmp_x and check_point[l][0] == tmp_y: print 'Check point : ( %d , %d )' % (tmp_y, tmp_x) skip.append(l) answer = answer + res s_y = check_point[j][0] s_x = check_point[j][1] check = {} for opt in range(0, 4): res = search(maps, s_x, s_y, e_x, e_y, x, y, opt, {}) if res != False: break answer = answer + res print print "ANSWER : %s" % (answer) if answer == '': print "EMPTY ANSWER : %04d" % (i) ### ANSWER fd = open("maze_answer.txt", "a") fd.write("%05d : %s\n" % (i, answer)) fd.close() fd = open("maze_submit.txt", "a") fd.write("%s\n" % (answer)) fd.close() maps = [] check = {} | cs |
maze_verify.py
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | # READ ANSWER fd = open("maze_answer.txt", "r") data = fd.read().splitlines() fd.close() answer = [] for d in data: path = d.split(':')[1].strip() answer.append(path) for i in range(0, 1000): fd = open("./maze/%04d.map" % (i), "r") data = fd.read().splitlines() fd.close() maps = [] s_x = 0 s_y = 0 e_x = 0 e_y = 0 for j in range(1, len(data)): ind_s = data[j].find('S') if ind_s > -1: s_y = j-1 s_x = ind_s ind_e = data[j].find('G') if ind_e > -1: e_y = j-1 e_x = ind_e maps.append(data[j]) check_point = [] for j in range(0, len(maps)): for k in range(0, len(maps[j])): if maps[j][k] == 'C': check_point.append([j, k]) walked = [] print "( %d , %d )" % (s_y, s_x) verified = 0 walked.append([s_y, s_x]) for j in range(0, len(answer[i])): ch = answer[i][j] if ch == 'L': s_x = s_x - 1 elif ch == 'R': s_x = s_x + 1 elif ch == 'U': s_y = s_y - 1 elif ch == 'D': s_y = s_y + 1 print "( %d, %d ) = %c" % (s_y, s_x, maps[s_y][s_x]) walked.append([s_y, s_x]) if maps[s_y][s_x] == '#': print '(%d , %d)' % (s_y, s_x) verified = 1 break if j == len(answer[i])-1: print maps[s_y][s_x] if maps[s_y][s_x] != 'G': verified = 2 break # CHECK THE CHECK POINTS for ch in range(0, len(check_point)): if check_point[ch] not in walked: verified = 3 break if verified != 0: print '[%05d] is (** not **) verified (X) :' % (i), if verified == 1: print " bricks ..." elif verified == 2: print " not reached to the [G]oal" elif verified == 3: print " not consumed the check points" continue print '[%05d] is verified (O)' % (i) | cs |
-_-;; 흠냐;;; 이런 시간 잡아 먹는 문제는 좋지 않음 ... ;;
'CTF_WriteUps > 2015_CTF' 카테고리의 다른 글
[2015_School_CTF] (Crypto 200) Master of guesswork (0) | 2015.11.08 |
---|---|
[2015_School_CTF] (Admin 200) Cipollino, little onion (0) | 2015.11.08 |
[2015_TrendMicro_CTF] (Programming 200) 사칙연산 풀기 (0) | 2015.10.27 |
[2015_TrendMicro_CTF] (Programming 100) click on the different color (0) | 2015.10.27 |
[2015_CSAW_CTF] (Reversing 300) FTP (0) | 2015.10.27 |
댓글
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- UAF
- Mona 2
- 쉘 코드
- IE 10 익스플로잇
- 데이터 마이닝
- 윈도우즈 익스플로잇 개발
- CTF Write up
- expdev 번역
- TenDollar
- shellcode
- IE 10 God Mode
- WinDbg
- IE 11 UAF
- 2015 School CTF
- IE 11 exploit
- School CTF Write up
- 쉘 코드 작성
- Use after free
- data mining
- 힙 스프레잉
- shellcode writing
- IE 10 리버싱
- heap spraying
- IE 11 exploit development
- School CTF Writeup
- TenDollar CTF
- 2014 SU CTF Write UP
- IE UAF
- Windows Exploit Development
- IE 10 Exploit Development
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함