(writeupみちゃいました)
調査
ルールは
「コインがN枚が並べてあります。その中に1枚だけ偽物のコインがあるので、一度に何枚でも載せられる天秤をC回だけ使って何番目のコインが偽物か答えてね！
30秒以内でこれを100回解けばフラグをあげるよ」
というゲームです。
上のルールもそうですが、入力や出力の決まりは接続時に表示されるので読んでください。
解法
流れ
人間がやると死ねるのでプログラムに答えてもらいます。
- コイン全体を2等分します
- 片方のグループのコインを全て天秤に載せ、重さを一度に測ります。重さがコインの枚数*10でなければ、このグループに偽物コインがあります。でなければもう一方のグループに偽物コインが含まれています。
- 偽物コインが含まれているグループを基にして、手順1からやり直します。
- 最後に偽物コインが1枚に絞り込めます。
以上！
エクスプロイトコード
# coding: utf-8
import socket
import sys
import re
import time
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_address = ('127.0.0.1', 9007)
sock.connect(server_address)
sock.recv(10024) #接続時のルール説明を読み飛ばす
for i in range(100):
arr = sock.recv(100).strip().split(' ')
count = int(arr[1].split('=')[1])
number = int(arr[0].split('=')[1])
print "c:" + str(count)
print "n:" + str(number)
low = 0
high = number
send_data = " "
#二分探索
for _ in range(count):
mid = (low+high)/2
#2分割したコインの先頭側グループを全て秤に載せる(奇数の場合は先頭グループが常に1枚多くなる)
send_data = " ".join([str(i) for i in range(low, mid+1)])+"n"
sock.sendall(send_data)
time.sleep(0.01) #待たないとダメかも？
data = sock.recv(100)
weight = int(data[:-1])
#ちょうど最後の一枚！
if weight == 9:
pass
#このグループには偽コインは含まれていない場合
elif weight == (mid + 1 - low) * 10:
low = mid + 1
#もう一方のグループが残り1枚なら偽物確定。
if (high - low + 1) == 1:
send_data = str(high) +"n"
#このグループに偽コインが含まれている場合
else:
high = mid
sock.sendall(send_data) #結果送信
time.sleep(0.01)
data = sock.recv(100)
print data
time.sleep(0.01)
data = sock.recv(100)
print data
使い方
普通にやるとサーバの応答が遅いせいでタイムアップになります。
上で接続先にlocalhost(ループバックアドレス127.0.0.1)を指定してることからわかるように、SSHログインしたサーバ内から実行してください。
問題文にも「(if your network response time is too slow, try nc 0 9007 inside pwnable.kr server)」
って書いてありますしね。
具体的には
user1@TTsMacBookPro-2 ~/Desktop -> 10:29 PM 金 9 22$ ssh fd@pwnable.kr -p2222 fd@ubuntu:~$ cd /tmp fd@ubuntu:/tmp$ vim solver11.py ((ここで作成したプログラムをコピペして保存)) fd@ubuntu:/tmp$ python solver11.py
として実行すればよいです
コメント