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

문제

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

1) 내용

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

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

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

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

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

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

2) 진행 방법

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

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

profile
callmeskye

관심 있을 만한 포스트

0개의 댓글