CTF、pwnable #11 coin1のwriteup

(writeupみちゃいました)

調査

ルールは
「コインがN枚が並べてあります。その中に1枚だけ偽物のコインがあるので、一度に何枚でも載せられる天秤をC回だけ使って何番目のコインが偽物か答えてね!
30秒以内でこれを100回解けばフラグをあげるよ」
というゲームです。

上のルールもそうですが、入力や出力の決まりは接続時に表示されるので読んでください。

解法

流れ

人間がやると死ねるのでプログラムに答えてもらいます。

  1. コイン全体を2等分します
  2. 片方のグループのコインを全て天秤に載せ、重さを一度に測ります。重さがコインの枚数*10でなければ、このグループに偽物コインがあります。でなければもう一方のグループに偽物コインが含まれています。
  3. 偽物コインが含まれているグループを基にして、手順1からやり直します。
  4. 最後に偽物コインが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

として実行すればよいです

コメント