[pwnable.kr] coin1(6 pts) :: Write-Up

 

 

 

 

 

Mommy, I wanna play a game!

(if your network reponse time is too slow, try nc 0 9007 inside pwnable.kr server)

 

Running at : nc pwnable.kr 9007

 

 

 

 

 

 

보니까 진짜 동전은 무게가 10이고, 가짜 동전은 무게가 9인데, 무게의 합을 통해 가짜 동전을 찾아달라는 게임이네요. 두개씩 비교를 한다면 N/2번 비교를 해야하지만, 주어지는 C는 N/2보다 터무니없이 값이 작습니다. 따라서 이원탐색, Binary Search를 사용하면 좋을 것 같네요. Binary Search에 대한 기본적인 내용은 다음과 같습니다: https://dokhakdubini.tistory.com/175?category=847037

[자료구조] 이원/이진 탐색(binary search)에 대하여

 

기본적인 내용은 전체 집합을 반으로 나누어서 찾는 방식으로 탐색을 좁혀나가는 자료구조의 일종입니다. 시간복잡도가 O(logn)이므로 효율적인 알고리즘이라고 할 수 있겠네요.

 

 

그러면 이를 기반으로 코딩을 해줍시다.

 

     1	from pwn import*
       
     2	p = remote("pwnable.kr", 9007)
       
     3	sleep(3)						#starting in 3 sec...
     4	p.recv()
       
     5	for j in range(0, 100):
     6		p.recvuntil("N=")
     7		N = int(p.recvuntil(" "))
     8		p.recvuntil("C=")
     9		C = int(p.recvuntil("\n"))
    10		print(N, C)       
    11		left = 0
    12		right = N
    13		cnt = 0
    14		while cnt != C:
    15			pay = ""
    16			cnt = cnt + 1
    17			mid = (left+right)/2
    18			for i in range(left, mid):
    19				pay = pay + str(i)
    20				pay = pay + " "
    21			pay = pay + str(mid)
    22			print pay
    23			p.sendline(pay)
    24			res = int(p.recv())
    25			print res
    26			if((res % 10) == 9):
    27				right = mid
    28			else:
    29				left = mid + 1
    30		
    31		mid = (left+right)/2
    32		print mid
    33		p.sendline(str(mid))
    34		print p.recv()       
    35	print p.recv()
    36	p.interactive()

 

 

잘 짜긴 짰는데 time expired!라면서 중간에 멈춰버린다.. 이거보다 더 빠른 알고리즘을 찾아야 한다니...?

아니 이거보다 어떻게 더 효율적이게 짜라는거지???!?!?!?! 하면서 몇시간을 붙잡고있다가

서버가 느려서 그런거라는걸 깨달았다.........후.............

 

 

그래서 pwnable.kr에 아무 서버나 들어가서 이 코드를 한 번 더 돌려주면 플래그가 나온다. 이거때문에 몇시간을 삽질한건지....

 

그리고 pwnable.kr 내에 있는 서버에 직접 연결하여 코드를 실행시켜야하기때문에 폰툴따위 쓸 수 없다. 즉 소켓프로그래밍을 해야한다는 뜻인데... 하 접속이 잘 되게끔 해놓던가 이건 좀 아니라고 생각한다.

 

from socket import *
clientSock = socket(AF_INET, SOCK_STREAM)
clientSock.connect(('pwnable.kr', 9007))
cnt = 0
while cnt < 101:
    data = clientSock.recv(2048).decode('utf-8')
    print(data)
    size = len(data)
    if size != 0 and size != 1102 and size != 13 and size != 14:
        data = data.split(" ")
        data[0] = data[0].split("=")
        data[1] = data[1].split("=")
        n = data[0][1]
        c = data[1][1]
        print(n, c)
        n = int(n)
        c = int(c)
        start = 0
        end = n-1
        while 1:
            mid = (start + end) // 2
            if start != end and end != mid:
                message = ""
                sumValue = (mid - start + 1) * 10
                for i in range(start, mid + 1):
                    message = message + " " + str(i)
                message += "\n"
                c -= 1
                clientSock.send(message.encode('utf-8'))
                resultValue = clientSock.recv(2048).decode('utf-8')
                resultValue = int(resultValue)
                if sumValue > resultValue:
                    end = mid
                else:
                    start = mid + 1
            else:
                result = str(start) + "\n"
                clientSock.send(result.encode('utf-8'))
                c -= 1
                if c != -1:
                    data = clientSock.recv(2048).decode('utf-8')
                    clientSock.send(result.encode('utf-8'))
                    c -= 1
                break

Wa 개같은 소켓프로그래밍!

솔직히 다른블로그 참고했음... 소켓프로그래밍 도대체 언제쓴다고

https://velog.io/@skyepodium/pwnable-coin1

 

 

한참을 헤맸네........

해킹문제가 아니라 코딩문제였네요... 끝!