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

문제

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

1) 내용

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

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

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

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

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

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

2) 진행 방법

  1. 1) N개의 코인 정보와 2) C번의 기회가 주어집니다.
  2. 무게를 측정할 코인의 인덱스를 선택합니다.
    (0 2 이면, 0~2번 까지 3개의 코인, 3이면 4번 코인 1개)
  3. 코인의 무게 정보를 얻습니다.
  4. 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

4. 코드는 정확한데 time expired 가 발생한다면

위와 같이 30개 미만의 코인을 찾고 time expired! bye! 로 중단됩니다.

이럴경우, pwnable 서버에 들어가서 직접 코드를 실행해야합니다.

1) pwnable 서버 접속

ssh를 사용해서 서버에 직접 접속합니다. 비밀번호는 guest

ssh fd@pwnable.kr -p2222
# pw: guest

2) python3 셸 실행

파이썬 셸을 실행합니다.

python3

3) 셸에서 코드 실행

작성한 코드를 복사후 붙여넣기 합니다. 그리고 실행합니다.
(단, 줄바꿈이 있으면 인덴트가 잘못된것으로 인식해서, 줄바꿈을 모두 없애주었습니다.)

profile
callmeskye

0개의 댓글