coin1

1. intro

2. code 및 분석

2.1.  code

별도 코드 없음.

2.2. 분석

        ---------------------------------------------------
        -              Shall we play a game?              -
        ---------------------------------------------------

        You have given some gold coins in your hand
        however, there is one counterfeit coin among them
        counterfeit coin looks exactly same as real coin
        however, its weight is different from real one
        real coin weighs 10, counterfeit coin weighes 9
        help me to find the counterfeit coin with a scale
        if you find 100 counterfeit coins, you will get reward :)
        FYI, you have 60 seconds.

        - How to play -
        1. you get a number of coins (N) and number of chances (C)
        2. then you specify a set of index numbers of coins to be weighed
        3. you get the weight information
        4. 2~3 repeats C time, then you give the answer

        - Example -
        [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=289 C=9

 

3. 취약점 확인 및 공격 준비

3.1. 취약점

단순한 알고리즘 문제이다.

3.2. 공격 준비

문제에서 보듯 무게를 10으로 나눴을때 나머지가 9이면 그 안에 위조 코인이 있는 것이기에 찾을때까지 절반씩 잘라서 계속 던져주면 된다.

다만 로컬에서 서버로 메시지를 주고 받을때 시간이 걸리기에 타임 아웃이 발생하기에

서버에 접속하여 다시 서버의 localhost로 접속하여 풀면 빠르다.

 

4. exploit

from pwn import *

p = remote('localhost',9007)
p.recvuntil("- Ready? starting in 3 sec... -")

for i in range(100):

    p.recvuntil('N=')
    n = int(p.recvuntil(' '))  
    p.recvuntil('C=')
    c = int(p.recvuntil('\n'))

    start = 0
    end = n-1
    mid = 0

    for k in range(c):
        mid = (start+end)//2
        in_str = ''
        
        for k in range(start, mid+1):
            in_str += (str(k)+' ')

        p.sendline(in_str)
        ans = int(p.recvline())

        if (ans%10)==9:
            end = mid
        else:
            start = mid+1
    
    p.sendline(str(end))
    p.recvline()

p.interactive()

알고리즘 공부 좀 해야될 듯...