[Preview]

CTF 문제를 풀기 시작한 최근, 여러 분야의 문제들을 보고 있습니다. 이번에 도전해 본 분야는 PPC(Professional Programming Challenges)입니다. 문과출신의 저에게 약한 분야인 수학에 대한 내용이기에 지레 겁먹고 손대지 않았었지만 이번엔 왠지 할만하다는 느낌적인 느낌(?) 덕택에 도전하게 되었습니다. 포기하고 자려고 마음먹고 침대에 누운 순간 솔루션이 생각나서 그대로 밤을 샜던 좋은 경험(?)을 할 수 있었습니다 ㅋㅋ..


[Summary]

이번 문제는 엄청 큰 수 n보다 작으며 x**y를 만족하는 n에 가장 가까운 수 'r'을 찾아내는 문제였습니다. 문제풀이의 핵심은 시간 내에 효율적으로 계산이 되게끔 코드를 구성할 수 있는가 입니다. 저는 3가지 방법을 써서 코드의 효율성을 높일 수 있었습니다.

 

 1. n에 가장 가까운 2**y 에서 y를 구함

 2. [1]번에서 구한 y값을 줄여나가며 'n - (x**y) < 0' 을 처음으로 만족하는 x값을 구함

 3. [2]번에서 구한 'n - ((x-1)**y)' 값이 이전에 구한 최소값보다 작은지 비교

 4. [2]번의 조건을 만족하기 위한 x의 증가폭을 처음에 크게 설정 후 증가폭을 조절

 5. 수의 크기에 따라서 y가 2가 되는 순간까지 x값을 구하지 않고 중간에 포기하도록 함


어찌보면 난잡할 수도 있지만 로그와 극한도 잘 모르는 저는 여러가지 시행착오 끝에 위와 같은 솔루션을 구할 수 있었습니다.


[Code]

import socket import hashlib #read data - get hash_num def read_hash(): data="" data2="" while "[-6:] = " not in data: data += s.recv(1) data2=s.recv(6) #hash_num print data+data2 return data2 #PoW def do_PoW(hash_num): pow_result="" print ("[*] I'm doing PoW...") for i in xrange(1000000000): if hash_num in str(hashlib.sha256(str(i)).hexdigest())[-6:]: pow_result=str(i) break print "[!] pow result = %s" % pow_result s.send(pow_result+"\n") #read data - get big number data1=recvuntil("n = ") data2=recvuntil("To") data3=recvuntil(":)") s.recv(1) print data1+data2+data3 return data2 #get y on 2**y def get_num_x_2(a): for i in range(100, 1000000): if (a-(2**i)<0): print ("[*] start y - %s" % str(i-1)) return i-1 #get x by decreasing y(get_num_x_2(a)) def get_num_y_2(num, num_cnt): x=3 y=num yt=0 tmp=a cnt=num_cnt tmp2=0 while(1): if(a-(x**y)<0): #give-up point if(num>3000): if(y<17): print ("[*] Gotya! %s" % str(tmp)) return str(tmp) elif(num>2000): if(y<15): print ("[*] Gotya! %s" % str(tmp)) return str(tmp) elif(num>1000): if(y<11): print ("[*] Gotya! %s" % str(tmp)) return str(tmp) elif(num>700): if(y<8): print ("[*] Gotya! %s" % str(tmp)) return str(tmp) else: if(y==2): print ("[*] Gotya! %s" % str(tmp)) return str(tmp) #is smaller r? if(a-((x-1)**y)<tmp): #set increasing range of x if(y<=190 and cnt!=1): x-=cnt cnt = cnt/2 continue tmp=a-((x-1)**y) y-=1 yt=y cnt=num_cnt else: y-=1 yt=y cnt=num_cnt else: #set increasing range of x if(y>190): x+=1 elif(y<=190): x+=cnt #check clear def isNext(): dt="" dt+=recvuntil("\x0a") if "next stage" in dt: data1=recvuntil("n = ") data2=recvuntil("To") data3=recvuntil(":)") s.recv(1) print data1+data2+data3 return data2 else: print dt while 1: print recvuntil("\x0a") #custom recvuntil def recvuntil(str): data="" while str not in data: data += s.recv(1) return data ######main###### num_y=0 num_cnt=2**250 s = socket.socket() ip = '37.139.22.174' port = 11740 s.connect((ip,port)) #pow a=do_PoW(read_hash()) a=a[0:len(a)-3] a=long(a) #get r while(1): num_y = get_num_x_2(a) result = get_num_y_2(num_y, num_cnt) print ("[!] r=\'%s\'" % str(result)) s.send(result+"\n") a=isNext() a=a[0:len(a)-3] a=long(a)

[그림 1] 문제 풀이 코드(Python)



 

[그림 2] 솔루션 실행 화면
















'CTF > asis ctf 2018' 카테고리의 다른 글

[PPC] Neighbour - ASIS CTF 2018  (0) 2018.05.08
var net = require('net');

flag='fake_flag';

var server = net.createServer(function(socket) {
    socket.on('data', (data) => { 
        //m = data.toString().replace(/[\n\r]*$/, '');
        ok = true;
        arr = data.toString().split(' ');
        arr = arr.map(Number);
        if (arr.length != 5) 
            ok = false;
        arr1 = arr.slice(0);
        arr1.sort();
        for (var i=0; i<4; i++)
            if (arr1[i+1] == arr1[i] || arr[i] < 0 || arr1[i+1] > 127)
                ok = false;
        arr2 = []
        for (var i=0; i<4; i++)
            arr2.push(arr1[i] + arr1[i+1]);
        val = 0;
        for (var i=0; i<4; i++)
            val = val * 0x100 + arr2[i];
        if (val != 0x23332333)
            ok = false;
        if (ok)
            socket.write(flag+'\n');
        else
            socket.write('nope\n');
    });
    //socket.write('Echo server\r\n');
    //socket.pipe(socket);
});

HOST = '0.0.0.0'
PORT = 23333

server.listen(PORT, HOST);

[그림1] 문제 전체 소스코드



[그림1] 문제의 전체 소스코드를 살펴보면 var형 변수를 쓰는 것과 nodejs에서의 TCP 소켓을 구현하는 방식임을 보고 미루어 보았을 때 nodejs로 구현된 TCP 소켓 서버임을 알 수 있다. 유저가 보낸 data를 받아와 ' '(공백)을 기준으로 split 한 후 배열에 넣어 여러 검증과정과 처리과정을 거친 후 나오는 결과값이 '0x23332333' 인지 확인한 후 맞다면 플래그를 띄운다.



        arr = data.toString().split(' ');
        arr = arr.map(Number);
        if (arr.length != 5) 
            ok = false;
        arr1 = arr.slice(0);
        arr1.sort();

[그림2] 데이터 초기 처리과정




[그림3] Javascript 에서의 split(), map(), slice(), sort() 동작 과정


[그림2]의 초기 데이터 처리과정은 [그림3]과 같이 진행된다. 여기서 주의해야 할 점은 유저의 데이터가 ' data.toString().split(' ') ' 을 통해 'String' 으로 형변환이 되며 arr 배열로 들어가기 때문에 뒤의 ' arr1.sort() ' 코드에서 정렬할 때 'int' 형이 아닌 'string' 형으로 정렬이 된다. 이 말은 곧, 숫자의 크기와 상관 없이 맨 앞글자부터 크기를 비교하기 때문에, [그림3]과 같이 [8, 21, 4, 57, 6]이 배열에 들어갔다면 [21, 4, 57, 6, 8]로 정렬이 되는 것이다. 저는 이걸 헷갈려서 한참을 헤맸다는...



if (arr.length != 5) ok = false; ... for (var i=0; i<4; i++) if (arr1[i+1] == arr1[i] || arr[i] < 0 || arr1[i+1] > 127) ok = false;

[그림4] 유저의 input data 검증 과정


이후 [그림4]와 같이 배열의 크기가 5가 아니면 ok 플래그 변수에 false를 넣고(유저의 인풋값이 스페이스를 기준으로 나누어 5개의 값만을 넣어야 한다), 인풋값 중 같은 값이 있는 지, 혹은 0보다 작거나 127보다 큰 수가 있는 지를 검사한다(sort() 이후 검증을 하기 때문에 arr1[i+1]==arr1[i] 만으로도 같은 값이 있는 지 검사할 수 있다).



        arr2 = []
        for (var i=0; i<4; i++)
            arr2.push(arr1[i] + arr1[i+1]);
        val = 0;
        for (var i=0; i<4; i++)
            val = val * 0x100 + arr2[i];
        if (val != 0x23332333)
            ok = false;
        if (ok)
            socket.write(flag+'\n');
        else
            socket.write('nope\n');

[그림5] 데이터 처리 및 계산, 인증 과정


검증 후 arr2 배열을 새로 만들어 arr2에 arr1의 원소를 앞에서부터 두개씩 더하여 넣는다(총 4개의 원소 발생). 이 arr2 배열에 초기값이 0인 상태로 0x100씩 곱하여 원소를 더하고 이를 다시 이용하고 반복하며 이 과정이 끝났을 때 '0x23332333' 이 맞는 지 검사하고 맞다면 플래그를 띄워준다.




for a in range(0, 124): for b in range(a+1, 125): for c in range(b+1, 126): for d in range(c+1, 127): for e in range(d+1, 128): arr1 = [] arr1.append(str(a)) arr1.append(str(b)) arr1.append(str(c)) arr1.append(str(d)) arr1.append(str(e)) arr1.sort() arr2 =[] arr2.append(str(int(arr1[0])+int(arr1[1]))) arr2.append(str(int(arr1[1])+int(arr1[2]))) arr2.append(str(int(arr1[2])+int(arr1[3]))) arr2.append(str(int(arr1[3])+int(arr1[4]))) val = 0 for x in range (0, 4): val = val * 0x100 + int(arr2[x]) if(val==590553907): break if(val==590553907): break if(val==590553907): break if(val==590553907): break if(val==590553907): break else: print ("[%s] I'm doing.." % str(a+1)) print ("[*] I Found It!!!") print (a, b, c, d, e) print (arr2) print (val)

[그림6] 문제 조건에 부합하는 배열을 찾기 위한 Python 스크립트



문제 코드에서 나타난 과정을 Python으로 똑같이 구현하여 조건에 부합하는 배열을 찾아낸다. 같은 수가 나오면 안되므로 맨 뒤부터 순차적으로 숫자를 증가시키며 값을 찾아낸다.



[그림7] Python 스크립트 실행 결과




[그림8] 인증 결과


Flag Get!!!

'CTF > *ctf (star ctf - xctf) 2018' 카테고리의 다른 글

[Web] 2018 starctf - simpleweb  (0) 2018.04.23

+ Recent posts