[HSCTF 9] vending-machine

1. 개요

프로그래밍 문제

 

2. 분석

item을 사면 coin을 잃어버립니다.

coin 손실을 최소화하면서 item을 모두 구매해야합니다.

Task
You want to buy everything in a vending machine using your limited supply of coins, but the vending machine is broken and it steals your money after every purchase >:(

Interaction Details:
The following commands will be provided:

Display:
Shows the list of remaining coins, items to buy, and your current balance.

Insert <x>:
Insert the xth coin, if it exists, and add its value to your balance.

Buy <x>:
Buy the xth item, if it exists, and you have enough money. Resets balance to zero.

Sample Interaction:
Display
Items: 1: 52716 2: 38793 3: 41085 4: 41725 5: 34276

Coins: 1: 11233 2: 19135

... omitted for brevity, list continues in actual program

19: 5874

Balance: 0
Insert 1
Balance: 11233
Insert 2
Balance: 30368
Buy 5
Not enough money

 

3. exploit

모든 조합을 만들어서 금액 손실이 최소가 되는 조합을 사용했습니다.

from pwn import *
from collections import deque
import re

def refine(m):
    return [int(c.split(": ")[1]) for c in m.split("\n") if c != '']

# 1. 연결
p = remote('vending-machine.hsctf.com', 1337)

p.recvuntil("disabled ==")

# 2. 초기 인풋
p.sendline("Display")
p.recvuntil("Items: \n")
m = p.recvuntil("\n\n").decode("utf-8")

a = refine(m)
sum_items = sum(a)
print("Sum ITEMS", sum_items)
items = [(idx+1, val) for idx, val in enumerate(a)]

p.recvuntil("Coins: \n")
m = p.recvuntil("\n\n").decode("utf-8")
p.recvuntil("Balance: 0")
p.recvline()

a = refine(m)
sum_coins = sum(a)
print("Sum Coins", sum_coins)
coins = [(idx+1, val) for idx, val in enumerate(a)]

items.sort(key=lambda x: -x[1])
coins.sort(key=lambda x: -x[1])

print("items", items)
print("coins", coins)
print("total_diff", sum_coins - sum_items)
print()

items_idx = [0]
res = [100000000]
r_l = [[]]
a_s = set()

def go(idx, l):
    if idx >= len(coins):
        c = [val for idx, val in l]
        sum_val = sum(c)
        cur_diff = sum_val - items[items_idx[0]][1]
        # print(idx)
        if cur_diff >= 0 and res[0] > cur_diff:
            res[0] = cur_diff
            r_l[0] = l[::]
        return

    # if coins[idx][0] not in a_s:
    l.append(coins[idx])
    go(idx + 1, l)
    l.pop()

    go(idx + 1, l)

for _ in range(len(items)):
    print("========", _)
    go(0, [])
    print("diff!!!", res[0])
    print("r_l", r_l[0], len(r_l[0]))
    v = []
    for c in r_l[0]:
        a_s.add(c[0])
        v.append(c[0])

    for val in v:
        p.sendline(f"Insert {val}")
        print("after insert", p.recvline())    
        print()    

    p.sendline(f"Buy {items[items_idx[0]][0]}")
    print("after Buy", p.recvline())

    coins = [(c[0], c[1]) for c in coins if c[0] not in a_s]
    print("coins", len(coins))
    print("a_s", a_s)
    print()
    items_idx[0] += 1
    print(items_idx)
    res = [100000000]
    r_l = [[]]       

message = p.recvall()
print(message)