InCTF2020 - coins write up

 

MISC 분야의 문제이다.

 

 

nc로 접속하면 아래와 같이 문제가 출력이 된다. 문제만 봐도 한눈에 이해가 간다.

 

python으로 4자리를 찾는 코드를 작성하면 아래와 같다.

string 패키지로 문자열을 나열한 다음 for문 4개를 이용해 알맞은 4자리 값을 찾은 후 sendline() 함수로 값을 보낸다.

from pwn import *
import string
import hashlib

context.log_level = "debug"

p = remote("34.74.30.191", "1337")
    
line = p.recvline().replace("\n", "")
line = line.split(" ")
    
length = len(line[0][line[0].find("(")+1 : line[0].find("+")])
salt = line[0][line[0].find("+")+1 : line[0].find(")")]


str_list = string.ascii_lowercase + string.ascii_uppercase + string.digits

flag = 0
for a in str_list:
    for b in str_list:
        for c in str_list:
            for d in str_list:
                plaintext = a + b + c + d + salt
                encrypt = hashlib.sha256(plaintext.encode()).hexdigest()
                
                if encrypt == line[2]:
                    print(a+b+c+d)
                    p.sendlineafter(":", a+b+c+d)
                    flag = 1
                if flag == 1:
                    break
            if flag == 1:
                break
        if flag == 1:
            break
    if flag == 1:
        break
    
p.interactive()

 

 

위 코드를 실행하면 아래와 같이 추가적으로 다른 문제가 나온다.

아래 문제를 요약하면 대충 게임을 하는건데,

1. 15개의 코인이 존재한다. (이 코인의 개수는 풀때 마다 바뀜)
2. 이 코인들 중에서 무게가 다른 1개가 존재한다. 이를 찾는 것이다.
3. 찾는 규칙은 아래와 같다.
	사용자는 [0, 15) 의 인덱스에서 i j 로 입력한다.
    예를들어 0 1 또는 1 5
    이렇게 입력하면 i 부터 j 까지의 코인의 무게를 xor 한다.
    
    만약 무게가 다른 1개의 코인을 찾으면 ! i 라고 입력하면 된다.

 

 

위 규칙을 이해 했다면 아래와 같이 꼼수(?)를 써서 우연치 않게 무게가 다른 코인을 찾을 수 있을 것이다.

0 0, 1 1, 2 2 라고 입력했을때 인덱스가 2인 코인만 무게가 다르기 때문에 ! 2 라고 입력하면 클리어 하게 된다.

하지만 문제를 풀면 코인의 개수가 겁나 많아진다.

똑같은 방법으로 풀면 횟수 제한이 있는지 실패하게 된다.

 

이때 필요한건 역시 바이너리 검색 알고리즘이다.

def get_result():
    p.recvuntil("is ")
    return int(p.recvuntil("\n").replace("\n", ""))

while True:
    # Get coin count
    p.recvuntil("The number of coins in this batch are")
    coin_count = int(p.recvuntil("\n").replace("\n", ""))
    coin = []
    for i in range(coin_count):
        coin.append(i)
    
    # Actual coin's weight
    p.sendline("0 0")
    main_coin = get_result()
    
    
    while True:
        # print("\n\n[*] {}".format(coin))
        p.sendline("{} {}".format(coin[0], coin[int(len(coin)/2)]))
        
        result_weight = get_result()
        
        # right
        if main_coin == result_weight or result_weight == 0:
            coin = coin[int(len(coin)/2)+1:]
        # left
        else:
            coin = coin[:int(len(coin)/2)+1]
        
        if len(coin) == 1:
            p.sendline("! {}".format(str(coin[0])))
            break
        elif len(coin) <= 2:
            p.sendline("{} {}".format(coin[0], coin[0]))
            result = get_result()
            
            if main_coin == result:
                p.sendline("! {}".format(str(coin[1])))
                break
            else:
                p.sendline("! {}".format(str(coin[0])))
                break

위 알고리즘을 통해 몇십만개의 코인 중 무게가 다른 코인을 찾을 수 있게 된다.

 

 

 

Payload

최종적인 payload는 아래와 같다.

from pwn import *
import string
import hashlib

context.log_level = "debug"

p = remote("34.74.30.191", "1337")
    
line = p.recvline().replace("\n", "")
line = line.split(" ")
    
length = len(line[0][line[0].find("(")+1 : line[0].find("+")])
salt = line[0][line[0].find("+")+1 : line[0].find(")")]


str_list = string.ascii_lowercase + string.ascii_uppercase + string.digits

flag = 0
for a in str_list:
    for b in str_list:
        for c in str_list:
            for d in str_list:
                plaintext = a + b + c + d + salt
                encrypt = hashlib.sha256(plaintext.encode()).hexdigest()
                
                if encrypt == line[2]:
                    print(a+b+c+d)
                    p.sendlineafter(":", a+b+c+d)
                    flag = 1
                if flag == 1:
                    break
            if flag == 1:
                break
        if flag == 1:
            break
    if flag == 1:
        break

def get_result():
    p.recvuntil("is ")
    return int(p.recvuntil("\n").replace("\n", ""))

while True:
    # Get coin count
    p.recvuntil("The number of coins in this batch are")
    coin_count = int(p.recvuntil("\n").replace("\n", ""))
    coin = []
    for i in range(coin_count):
        coin.append(i)
    
    # Actual coin's weight
    p.sendline("0 0")
    main_coin = get_result()
    
    
    while True:
        # print("\n\n[*] {}".format(coin))
        p.sendline("{} {}".format(coin[0], coin[int(len(coin)/2)]))
        
        result_weight = get_result()
        
        # right
        if main_coin == result_weight or result_weight == 0:
            coin = coin[int(len(coin)/2)+1:]
        # left
        else:
            coin = coin[:int(len(coin)/2)+1]
        
        if len(coin) == 1:
            p.sendline("! {}".format(str(coin[0])))
            break
        elif len(coin) <= 2:
            p.sendline("{} {}".format(coin[0], coin[0]))
            result = get_result()
            
            if main_coin == result:
                p.sendline("! {}".format(str(coin[1])))
                break
            else:
                p.sendline("! {}".format(str(coin[0])))
                break
p.interactive()