BaaaaaaaarkingDog
코딩, 해킹
WCTF 2019 후기

이전 글에 썼듯 WCTF 2019에 참석했습니다.

 

우선 다른 대회와 다르게 이 대회에서는 2문제를 출제해야했기에 준비 과정이 다소 길었습니다. 2문제 중 한 문제는 반드시 Windows 플랫폼에서 돌아야 한다는 제약조건이 있었고, 그래서 한 문제를 Windows에서의 포너블 + 암호 문제로 가닥을 잡았습니다. 맨 처음에는 White box encryption을 가지고 낼까 싶었는데 잘 안되어서 엎어졌고, 대신 Miller Rabin Test에서 base가 난수가 아니라 고정되어 있을 때, Miller Rabin Test를 통과하는 합성수를 만들어 이산 로그(Discrete Logarithm) 문제를 해결하는 문제를 출제했습니다. 어떤식으로 하면 되는지는 다음에 정리해보겠습니다. 아무래도 학기중엔 바빠서 어쩌다보니 제출 기한은 6월 1일까지였는데 무려 20일 정도 늦게 제출을 했습니다ㅎㅎ..

 

이번에는 주최측에서 경비를 주는 대신 비행기표를 직접 끊어줬습니다. 비행기를 타고 대회 장소인 베이징으로 갔습니다. 주최측에서 픽업을 와주어서 호텔까지 차를 타고 한 방에 갈 수 있었습니다. 일단 무엇보다 호텔이 정말 좋았습니다. 비루한 제 자취방과 바꾸고 싶었습니다,,,, 그리고 기념품도 좋았습니다. 제가 원래 노트북에 스티커를 안붙이는데, 처음으로 스티커를 붙이고 싶다는 생각이 들 정도였습니다.

 

대회는 외부의 다른 곳이 아닌, 호텔 연회장에서 진행이 되었습니다. 그래서 이동이 굉장히 편했습니다. 대회는 1일차에 8시간이 진행된 후 서버가 닫히고, 다음날 다시 8시간 동안 진행되어 총 32시간 대회였습니다. 이 대회는 0CTF와 마찬가지로 remote가 허용되는 대회였습니다.

 

대회가 시작되고 뭐라도 할게 없으려나 문제들을 열어보고, 디스코드 방에 채널을 만들고 있는데 30분도 채 되지 않은 시점에 TokyoWesterns 팀이 0daysober가 출제한 kpass 문제를 풀어버렸습니다. 스크린에 각 팀이 문제가 풀 때 마다 휘황찬란한 이펙트가 보여졌는데, 특히나 첫 번째로 그 이펙트가 보여진거라 정말 모두의 이목이 집중되었습니다. 정황상 의도하지 않은 취약점이 있었을거고, 0daysober 팀은 피눈물을 흘렸을 것입니다...ㅠㅠ 그렇게 TokyoWesterns는 기분 좋은 출발을 했습니다.

 

그러나 정작 TokyoWesterns들이 출제한 두 문제 zshforbeginner, Gyotaku The Flag 모두 의도하지 않은, 말도 안되게 간단한 취약점이 있어서 1일차에는 kpass, zshforbeginner, Gyotaku The Flag만 주구장창 풀렸습니다. 저희 팀은 zshforbeginner, kpass를 첫 날 풀어내지는 못했지만 jinmo123님이 The Great Wall이라는 문제를 쓱싹해버리셨습니다.

 

저는 맨 처음에 DragonSector 팀이 출제한 TPM2137이라는 문제가 그나마 할만하다고 생각해보여 TPM2137를 잡았습니다. 이 문제는 베릴로그를 리버싱해야하는 문제였고 저는 베릴로그 노베이스였기 때문에 어거지로 베릴로그를 익히며 해결해보려고 했지만 역부족이었습니다. 결국 고통만 받다가 접었고, 나머지 문제가 다 제가 어떻게 할 수 있는 분야의 문제가 아닌 것 같아 이번 대회는 0솔따리인가 하면서 굉장히 자괴감에 빠져있었는데 다행히 r3kapig 팀에서 출제한 toy라는 문제가 암호문제였습니다. 일단 리버싱이 굉장히 빡셌는데 5unkn0wn님이 리버싱을 해주셔서 문제에서 요구하는 바를 알아차릴 수 있었습니다.

 

toy 문제는 LFSR의 출력을 보고 initial state를 알아내는 문제였습니다. 5unkn0wn님이 python으로 포팅한 코드는 아래와 같습니다.

mat = 0xB64E4D3FA8E7331BD871FA30D46D4DBA
inp = 0x0102030405060708090A0B0C0D0E0F10
res = []

def x(inp):
    l = []

    for i in range(128):
        l.append(inp & 1)
        inp >>= 1

    # x^127+x^125+x^124+x^123+...+x^1+x^0
    add_s = l[127]
    for i in range(126): # not include l[126]...
        add_s ^= l[i]

    # (x^62*x^61*x^60*...*x^0) + (x^53*x^22 + x^22*x^11 + x^59*x^51*x^42*x^41*x^38*x^28*x^26*x^25*x^23*x^20*x^18*x^12*x^9*x^1)
    mul_s = 1
    for i in range(63):
        mul_s &= l[i]
    mul_s ^= ((l[53] & l[33]) & (l[22] & l[11] ^ l[59] & l[51] & l[42] & l[41] & l[38] & l[28] & l[26] & l[25] & l[23] & l[20] & l[18] & l[12] & l[9] & l[1]))

    return add_s ^ mul_s

for i in range(2048):
    r = 0
    if i % 128 == 0:
        print "> Processing......", i / 128, "/", 16
    for j in range(8):
        cur = mat & inp
        s = 0
        while cur:
            s ^= cur & 1
            cur >>= 1
        inp <<= 1
        inp = (inp & 0xfffffffffffffffffffffffffffffffe) | s
        r = (r << 1) ^ x(inp)
    res.append(r)

print res

여기서 파일로 주어진 16376bit의 stream을 만들어내는 초기값 inp를 찾으면 그것이 바로 flag였고 0xB64E4D3FA8E7331BD871FA30D46D4DBA이라는 LFSR의 다항식은 딱히 문제가 없어보였습니다. 새벽 4시쯤 포팅한 코드를 받아 문제가 요구하는 바를 알아차린 이후, 9시간 가까이 굉장히 고통받았습니다. 당연히 안되겠지만 z3 solver에 넣어보기도 하고 simulated annealing 코드를 짜보기도 하고 이런저런 삽질을 하다가, 대회 종료를 5시간 앞두고 갑자기 깨달음을 얻었습니다. 설명은 제 채팅으로 대신합니다.

 

이후 열심히 코딩해 대회 종료 1시간 반 전에 flag를 얻는데 성공했습니다 ^__^ 참가 팀 중에서는 5번째로 문제를 풀어냈습니다.

 

오버워치의 POTG와 같은 영상을 하나 보고 갑시다. 지금까지 인생의 매드무비를 만든다면 이 영상이 꼭 들어가지 않을까 생각을 해봅니다ㅎㅎㅎ...

 

C++로 Gauss elimination을 포함한 코드를 작성했는데 너무 난잡해서 정리를 한 후에 공개를 하고 싶습니다만 언제가 될지는 모르겠네요.

 

이후 대회가 끝날 때 까지 응원단장으로 전향해 열심히 팀원들을 응원했지만 안타깝게도 그 후로 추가적으로 문제를 더 풀어내지는 못하고 5등으로 대회를 마무리 했습니다.

 

다음 날에는 대회를 주최한 Qihoo 360 회사에 가서 세미나를 진행했습니다. 각 팀들은 돌아가면서 자신 팀에서 낸 문제에 대한 풀이를 설명했습니다. 당연히 저희 팀도 발표를 진행했고, 저는 저희가 낸 문제 중 암호가 쓰인 부분에 대한 설명을 진행했습니다. ppt는 만들어갔지만 따로 스크립트는 만들어가지 않았는데, 역시 영어는 굉장히 어려웠습니다. 중간에 512bit이라는 단어를 말해야하는데 512가 영어로 뭔지 갑자기 생각이 안났습니다. 지금 생각하니 좀 어이가 없긴 하네요ㅋㅋㅋ 영어 공부도 하긴 해야하는데 쉽지 않네여

 

한 팀의 발표가 끝난 이후에는 바로 상호 평가가 실시되었습니다. 이 상호 평가 시스템도 정해진 링크에 들어가 스코어를 입력하면 실시간으로 스크린에 뜨는 식으로 꽤 그럴듯하게 만들어두었습니다.

 

보다보면 1점 테러를 해버리거나 심하게는 0.01점씩 주는 경우도 볼 수 있었는데, 아마 문제에 엄청나게 데였던 팀이 엿먹어라하는 생각으로 준게 아니었나 싶습니다. 제가 관여했던 문제는 중간 정도의 점수를 받았습니다. 저는 되게 좋은 문제라고 생각했는데 아니었나봐요ㅠㅠ

 

32시간동안 정말 고통받았지만 풀어낼 때의 쾌감은 정말 뭐라고 설명을 할 수가 없습니다. 함께한 Cykor 팀원들, mathboy07님, 5unkn0wn님 고생 많으셨습니다!! 이 맛에 CTF 한드아아아악

 

마지막으로 찍었던 사진들을 올리고 글을 마무리하겠습니다.

 

로고가 뭔가 쇼미더머니 느낌이 난다는 생각을 많이 했습니다.

 

호텔 좋아요

 

기념품도 정말 좋았습니다. 

 

티셔츠에는 각 팀의 로고가 박혀있었습니다. 앞으로 입을 일은 없겠지만 대회장에서는 열심히 입고 다녔습니다.

 

대회 시작 전, 스크린에는 판다 형님이 서있었습니다. 위의 저 한자는 무슨 뜻일까요..?

 

대회가 시작되고 2분이 지난 시점이었습니다.

 

Budweiser 맥주가 비치되어있었고 술의 힘으로 문제를 해결하자는 생각에 한 잔 걸쳤습니다.

 

간식도 JMT이었습니다.

 

이 깃발은 챙겨왔습니다.

 

끝나기 1시간 전 스코어입니다. 제가 toy를 풀면서 5위에서 4위로 올라섰지만 이후 Nu1L이 다른 문제를 풀며 4위로 올라가며 대회가 종료되었습니다.

 

대회장 입구에는 이런 판넬이 있었고 다른 팀을 따라 저희도 닉네임을 썼습니다.

 

BaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarkingDog

 

최종 스코어보드입니다.

'대회 > 각종 대회 후기' 카테고리의 다른 글

WCTF 2019 후기  (2) 2019.07.12
0CTF/TCTF 2019 후기  (0) 2019.06.19
Codegate 2019 본선 후기  (0) 2019.03.30
Google Hash Code 2019 후기  (3) 2019.03.05
2018 ACM-ICPC Hanoi Regional 후기  (0) 2018.12.04
2018 ACM-ICPC Seoul Regional 후기  (8) 2018.11.07
2018 삼성 육목대회 결선 후기  (1) 2018.09.18
  Comments
댓글 쓰기
WCTF 2019 online competition에 참여해보세요.

Qihoo 360이라는 중국의 보안 회사가 있습니다. 저도 사실 이번에 처음 들어봤긴 한데, 아무튼 이 회사에서 2016년부터 WCTF라는 CTF 대회를 열고 있습니다. 아마 W가 World의 약자인 것 같은데 역시 대륙의 기상은 어마어마합니다.

이 대회는 주최측에서 초대한 10개의 팀이 참가하고 1등 50000달러, 2등 30000달러, 3등 20000달러라는 어마어마한 상금을 뿌리며 자본주의의 막강한 힘을 보여주는 대회인데요, 다른 CTF와는 다르게 Belluminar라는 형식으로 진행이 됩니다.  Belluminar 대회 형식은 한국의 POC2015에서 처음 등장한 해킹 대회 형식으로, 각자 팀이 2문제씩을 출제해 모아진 총 20개의 문제로 ctf를 진행합니다. 이 때 단순히 ctf 점수로만 순위를 가르는 대신 32시간의 대회가 끝난 후 다음날 팀에서 출제한 문제의 풀이를 설명하는 세미나를 진행합니다.

이 세미나에서 각 팀간의 상호평가가 진행되어 얻어지는 점수와 ctf 점수가 합쳐져 순위가 정해집니다. 이 시스템 아래에서 나쁜 마음을 먹는다면 일부러 ctf 점수가 낮은 팀에게 상호평가를 좋게 주고, 점수가 비슷해 순위 경쟁이 발생할 수 있을 것 같은 팀에게 상호평가를 낮게 주는 등의 행동을 할 수 있긴 하지만 애초에 대회의 목적 자체가 경쟁에 있다기 보다는 기존의 Jeopardy 혹은 Capture The Flag에서는 부족했던 팀 간의 교류를 장려하자는 점인 만큼 그런 팀은 아마 없을 것입니다 :p 다만 너무 억지 문제를 내면 세미나 점수가 바닥을 치고, 그렇다고 해서 너무 쉽게 내면 점수를 헌납하게 되니 억지스럽지 않은 수준에서 문제를 굉장히 어렵고 또 최대한 꼬아내는 경향이 있다고 하는데 어떤 문제들이 나올지 감이 안오네요.

전년도에 저는 한게 없는데 동아리원들이 열일을 하셔서 여러 곳에서 실적을 잘 내서 그런지 올해도 WCTF로부터 초청을 받았고, 저희 팀에서 만들어야하는 2문제 중 한 문제를 팀원들과 같이 만들었습니다.

대회는 한국 시간으로 오늘(7월 5일) 오전 10시부터 32시간동안 진행되고, 초청받은 팀이 아니더라도 온라인으로 참여할 수 있습니다. 온라인 대회에 대한 상금도 3000달러, 2000달러, 1000달러로 그럭저럭 나쁘지 않게 있습니다. 아마 문제가 공개될 때 어느 팀이 출제했는지도 보일 것 같은데, 제가 관여한 문제가 완벽하다고는 말할 수 없지만 그래도 나름대로 풀어나가는 과정에서 얻는 것이 있을 것 같은 문제를 내려고 노력했기 때문에 한 번 도전해주시면 감사하겠습니다..!!

대회 링크는 https://ctftime.org/event/833 입니다.

첨부한 사진은 기념품인데, 완전 취향저격입니다. 그런데 캐릭터 디자인은 판다 티모가 연상이 되네요(^오^)

 

  Comments
댓글 쓰기
[BOJ] 13505번: 두 수 XOR

https://github.com/blisstoner/BOJ/blob/master/15940.cpp

 

0, 1을 가지고 Trie로 만들어두고 MSB부터 최대한 일치하지 않는 쪽으로 가는 방식으로 구현을 하면 됩니다.

 

https://github.com/blisstoner/BOJ/blob/master/13505.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 13505번: 두 수 XOR  (0) 2019.07.04
[BOJ] 15940번: 네트워크 해킹  (0) 2019.07.04
[BOJ] 3080번: HERKABE  (0) 2019.07.04
[BOJ] 17261번: 석유가 넘쳐흘러  (0) 2019.07.04
[BOJ] 6101번: Cleaning Up  (0) 2019.07.04
[BOJ] 16436번: 얼룩말 아트  (0) 2019.05.17
[BOJ] 16471번: 작은 수 내기  (0) 2019.05.13
  Comments
댓글 쓰기