[pwnable.kr] coin1

skyepodium·2020년 3월 1일

Binary Search coin1 pwnable python time expired! bye!바이너리 서치 보안 워게임 이분탐색 파이썬 해킹

coin1 문제에 대해 알아봅니다.
코드는 정확한데 시간초과가 발생하는 상황을 다룹니다.

문제

바이너리 서치를 사용하는 프로그래밍 문제
문제 링크

1) 내용

당신의 손에 몇개의 황금 코인이 주어졌습니다. 하지만, 그 중 한개의 가짜 코인이 있습니다.

위조코인은 진짜 코인과 똑같이 생겼습니다. 다만, 가짜 코인의 무게는 진짜 코인의 무게와 다릅니다.

진짜 코인의 무게는 10, 가짜 코인의 무게는 9 입니다.

저울을 이용해서 가짜 코인을 찾을 수 있도록 도와주세요.

만약 당신이 100개의 가짜 코인을 찾는다면, 보상을 받을 겁니다 :)

참고, 당신에게는 60초가 주어집니다.

2) 진행 방법

1) N개의 코인 정보와 2) C번의 기회가 주어집니다.
무게를 측정할 코인의 인덱스를 선택합니다.
(0 2 이면, 0~2번 까지 3개의 코인, 3이면 4번 코인 1개)
코인의 무게 정보를 얻습니다.
2~3번 과정을 C번 반복합니다. 그리고 정답을 얻을 수 있습니다.

3) 예시

[Server] N=4 C=2 	# find counterfeit among 4 coins with 2 trial
[Client] 0 1 		# weigh first and second coin
[Server] 20			# scale result : 20
[Client] 3			# weigh fourth coin
[Server] 10			# scale result : 10
[Client] 2 			# counterfeit coin is third!
[Server] Correct!

- Ready? starting in 3 sec... -

N=599 C=10

1. 프로그래밍 문제

보안 취약점을 찾는것이 아닌, 프로그래밍을 통해 주어진 상황을 해결하는 문제입니다.

2. 이분 탐색

바이너리 서치로 찾을 수 있습니다.

3. 코드

from socket import *
clientSock = socket(AF_INET, SOCK_STREAM)
clientSock.connect(('pwnable.kr', 9007))
findCoin = 0
while findCoin < 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]
        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
                findCoin += 1
                print("coin!!! = " + str(findCoin))
                break