InCTF 2020 writeup ~MISC coins~

問題

Toss a coin to your Witcher O' Valley of Plenty O' Valley of Plenty, oh

nc 34.74.30.191 1337

調査

Misc はその名の通り何が問題となっているのかがわからない問題が多いので基本的な戦略としては手を動かして挙動をみて情報を集める。

$ nc 34.74.30.191 1337
sha256(XXXX+TFuI4MRc519fEKgD) == a095a0175ac1ff10b3785a2248812fe11ac46957305669ade6b6cd1cae9eedd6
Give me XXXX: 

アクセスするとSHA256でのハッシュ値から元のtext(先頭4文字以外既知)を要求される。
4桁であるかはあくまでGuessでしかないが、題意のCoinにも関係がなさそうなのでそんな大したことはしなくていいと判断。

4桁なら計算量は(走査対象文字数)^4程度なのでpythonのstring.printableを全探索することにした。
また、続きがある気がしたので対話型のスクリプトを用意する。

from pwn import *
import string
import hashlib

io = remote('34.74.30.191', 1337)
ret = io.recvline().decode('utf-8')

desire_hash = ret.split('=')[2].strip()
# 判定の右辺の部分が入る。アクセスする毎に変動。
# desire_hash = 'a095a0175ac1ff10b3785a2248812fe11ac46957305669ade6b6cd1cae9eedd6'

post_x = ret.split('=')[0].split('+')[1].split(')')[0]
# sha256 でハッシュ化される前のtextの既知の部分。こちらも毎回変動。
# post_x = 'TFuI4MRc519fEKgD'
for x0 in string.printable:
  for x1 in string.printable:
    for x2 in string.printable:
      for x3 in string.printable:
        x = x0 + x1 + x2 + x3
        left_text = x + post_x
        hash = hashlib.sha256(left_text.encode()).hexdigest()
        if hash == desire_hash:
          ret = io.recvline()
          io.sendline(x)

ここまでで数秒でXXXXを34.74.30.191:1337に送りつけてくれるようになった。

本題

以上の過程を踏むとようやくCoinsっぽい話になる。以上への返答を引続き対話型スクリプトをいじりながら読んでいくと以下の文言が返ってくる。

There exists a coin minting machine at Bi0S which is known for its extermely fast minting process. However out of every batch (N coins) it produces one coin is faulty (have a different weight compared to the other N-1 coins). You can get information of the xor of the weight of the coins from index i to index j (both included) by communicating with the minting machine. Find the faulty coin (coin with different weight) with minimum number of queries, as the minting machine has better things to do than answer your questions. Multiple batches are produced by the minting machine and it is gaurenteed that in each batch there is only one defective coin. Your query should be in the format "i j" (without the quotes) where both i and j should lie in the range [0, N). You can report the correct position (Of course after solving it) in the format "! index" (without the quotes) where index lies in the range [0, N). If you correctly identify the faulty coin for a batch, you will continue to the next batch. If a query is given in the wrong format or give a wrong answer you will be rejected.

The number of coins in this batch are 14
Go ahead, ask some queries

ちょっと長いが雑に要約すると

• 与えられるN枚のコインの中に1枚だけfaultyなコインが存在し、他のコインと重さが異なっている
• [i, j] (両端含む)のxorで検査出来る
• 0-index
• 最小の検査回数で不良品を特定したい

query(可能な操作)は2種

• i j
  • 閉区間[i, j]のコインの重量のxor
• ! index
  • indexが不良品であることの指摘

実装方針

• 可能なqueryから最小の検査回数は二分探索でO(logN)で抑えられたら良さそう
• 多入力xorが何を返しているのかはぱっとよくわからなかったが、入力を偶数個にすることで異なる重さのコインが入力に含まれていなければ0, 含まれていたら0以外の数値を返すことが判るのでこれを二分探索の条件式に用いる。
  • シンプルな二分探索より偶数個のrange走査になるようにすることを優先するために少し手を加える。

上記の方針で不良品判定のロジックを組んでその前後の対話型のやりとりやちゃんと期待通りの挙動をしているかの確認を入れたスクリプトが以下になる。

solve.py

from pwn import *
import string
import hashlib
# (r - l) % 2 == 0
def xor_0(l, r):
  i_range = str(l) + ' ' + str(r)
  print(i_range)
  io.sendline(i_range)
  xor = io.recvline().decode('utf-8').strip().split(' ')[11]
  print(xor)
  if r - l != 1:
    return xor == '0'
  else: # last 2
    if xor == '0':
      return True # no faulty
    else: # with faulty
      if l == 0:
        io.sendline('1 2')
        xor = io.recvline().decode('utf-8').strip().split(' ')[11]
        print(xor)
        if xor == '0':
          ans = '! 0'
          io.sendline(ans)
          print(ans)
        else:
          ans = '! 1'
          io.sendline(ans)
          print(ans)
      else:
        i_range = str(l-1) + ' ' + str(l)
        io.sendline(i_range)
        print(i_range)
        xor = io.recvline().decode('utf-8').strip().split(' ')[11]
        print(xor)
        if xor == '0':
          ans = '! ' + str(r)
          io.sendline(ans)
          print(ans)
        else:
          ans = '! ' + str(l)
          io.sendline(ans)
          print(ans)
      ret = io.recvline() # after answer
      print(ret)
      ret = io.recvline()
      print(ret)
      num_coins = ret.decode('utf-8').strip().split(' ')[8]
      print(num_coins)
      if num_coins == 'the':
        last = io.recvline()
        print(last)
        last = io.recvline()
        print(last)
        last = io.recvline()
        print(last)
        last = io.recvline()
        print(last)
      nop = io.recvline() # go ahead...hogehoge
      print(nop)
      solve(0, int(num_coins))


 # N: num of range
def solve(l, N):
  print('see index:' + str(l) + '~' + str(l + N - 1))
  if N == 4:
    if xor_0(l, l + 1):
      solve(l+2,2)
    else:
      solve(l, 2)
  else:
    if xor_0(l, l + (N // 2 + (1 - (N // 2) % 2))):
      # xor_0(l + N - 1 - (N // 2 + (N // 2) % 2), l + N - 1) == false
      solve(l + N - 1 - (N // 2 + (1 - (N // 2) % 2)), (N // 2 + (1 - (N // 2) % 2)) + 1)
    else:
      solve(l,  N // 2 + (1 - (N // 2) % 2) + 1)

io = remote('34.74.30.191', 1337)
ret = io.recvline().decode('utf-8')
print(ret)
print(ret.split('='))
desire_hash = ret.split('=')[2].strip()
# desire_hash = '6ebd36e0d89345820e51ae9f5c07ace698e2bb3a98a8306441af006dd88d4691'
post_x = ret.split('=')[0].split('+')[1].split(')')[0]
# post_x = 'qREf1MWrSB61OxsB'
for x0 in string.printable:
  for x1 in string.printable:
    for x2 in string.printable:
      for x3 in string.printable:
        x = x0 + x1 + x2 + x3
        left_text = x + post_x
        hash = hashlib.sha256(left_text.encode()).hexdigest()
        if hash == desire_hash:
          print(x)
          ret = io.recvline()
          print(ret)
          io.sendline(x)
          ret = io.recvline()
          print(ret) # coin sentense
          ret = io.recvline()
          print(ret) # new line
          num_coins = io.recvline().decode('utf-8').strip().split(' ')[8]
          print(num_coins)
          nop = io.recvline() # go ahead...hogehoge
          print(nop)
          solve(0, int(num_coins))
          break

以上のスクリプトを実行すると

$ python solve.py
[+] Opening connection to 34.74.30.191 on port 1337: Done
sha256(XXXX+bygxj9LpmiWVwSGM) == 23346ff908c336e2560d52b62921bd5d43e5273f2ab933c5fdcb9cba00ae6b16

['sha256(XXXX+bygxj9LpmiWVwSGM) ', '', ' 23346ff908c336e2560d52b62921bd5d43e5273f2ab933c5fdcb9cba00ae6b16\n']
y0gd
b'Give me XXXX: \n'
b'There exists a coin minting machine at Bi0S which is known for its extermely fast minting process. However out of every batch (N coins) it produces one coin is faulty (have a different weight compared to the other N-1 coins). You can get information of the xor of the weight of the coins from index i to index j (both included) by communicating with the minting machine. Find the faulty coin (coin with different weight) with minimum number of queries, as the minting machine has better things to do than answer your questions. Multiple batches are produced by the minting machine and it is gaurenteed that in each batch there is only one defective coin. Your query should be in the format "i j" (without the quotes) where both i and j should lie in the range [0, N). You can report the correct position (Of course after solving it) in the format "! index" (without the quotes) where index lies in the range [0, N). If you correctly identify the faulty coin for a batch, you will continue to the next batch. If a query is given in the wrong format or give a wrong answer you will be rejected.\n'
b'\n'
13
b'Go ahead, ask some queries\n'
see index:0~12
0 7
9
see index:0~7
0 5
9
see index:0~5
0 3
9
see index:0~3
0 1
9
9
! 1
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 384079\n'
384079
b'Go ahead, ask some queries\n'
see index:0~384078
0 192039
0
see index:192039~384078
192039 288060
0
see index:288057~384078
288057 336068
224671
see index:288057~336068
288057 312064
0
see index:312061~336068
312061 324066
0
see index:324063~336068
324063 330066
224671
see index:324063~330066
324063 327066
0
see index:327063~330066
327063 328566
0
see index:328563~330066
328563 329316
0
see index:329313~330066
329313 329690
0
see index:329689~330066
329689 329878
0
see index:329877~330066
329877 329972
0
see index:329971~330066
329971 330020
0
see index:330017~330066
330017 330042
224671
see index:330017~330042
330017 330030
0
see index:330029~330042
330029 330036
224671
see index:330029~330036
330029 330034
0
see index:330031~330036
330031 330034
0
see index:330033~330036
330033 330034
0
see index:330035~330036
330035 330036
224671
330034 330035
224671
! 330035
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 493934\n'
493934
b'Go ahead, ask some queries\n'
see index:0~493933
0 246967
0
see index:246966~493933
246966 370451
738614
see index:246966~370451
246966 308709
0
see index:308708~370451
308708 339581
0
see index:339578~370451
339578 355015
738614
see index:339578~355015
339578 347297
738614
see index:339578~347297
339578 343439
0
see index:343436~347297
343436 345367
738614
see index:343436~345367
343436 344403
738614
see index:343436~344403
343436 343921
738614
see index:343436~343921
343436 343679
738614
see index:343436~343679
343436 343559
738614
see index:343436~343559
343436 343499
738614
see index:343436~343499
343436 343469
0
see index:343466~343499
343466 343483
738614
see index:343466~343483
343466 343475
0
see index:343474~343483
343474 343479
738614
see index:343474~343479
343474 343477
0
see index:343476~343479
343476 343477
0
see index:343478~343479
343478 343479
738614
343477 343478
0
! 343479
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 296781\n'
296781
b'Go ahead, ask some queries\n'
see index:0~296780
0 148391
670269
see index:0~148391
0 74197
670269
see index:0~74197
0 37099
670269
see index:0~37099
0 18551
670269
see index:0~18551
0 9277
0
see index:9274~18551
9274 13913
670269
see index:9274~13913
9274 11595
0
see index:11592~13913
11592 12753
0
see index:12752~13913
12752 13333
0
see index:13332~13913
13332 13623
0
see index:13622~13913
13622 13769
670269
see index:13622~13769
13622 13697
670269
see index:13622~13697
13622 13661
0
see index:13658~13697
13658 13679
0
see index:13676~13697
13676 13687
0
see index:13686~13697
13686 13693
0
see index:13690~13697
13690 13695
0
see index:13692~13697
13692 13695
0
see index:13694~13697
13694 13695
0
see index:13696~13697
13696 13697
670269
13695 13696
0
! 13697
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 766326\n'
766326
b'Go ahead, ask some queries\n'
see index:0~766325
0 383163
840063
see index:0~383163
0 191583
840063
see index:0~191583
0 95793
840063
see index:0~95793
0 47897
840063
see index:0~47897
0 23949
840063
see index:0~23949
0 11975
840063
see index:0~11975
0 5989
0
see index:5986~11975
5986 8981
840063
see index:5986~8981
5986 7485
840063
see index:5986~7485
5986 6737
840063
see index:5986~6737
5986 6363
840063
see index:5986~6363
5986 6175
0
see index:6174~6363
6174 6269
0
see index:6268~6363
6268 6317
840063
see index:6268~6317
6268 6293
0
see index:6292~6317
6292 6305
840063
see index:6292~6305
6292 6299
840063
see index:6292~6299
6292 6297
840063
see index:6292~6297
6292 6295
840063
see index:6292~6295
6292 6293
0
see index:6294~6295
6294 6295
840063
6293 6294
840063
! 6294
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 526445\n'
526445
b'Go ahead, ask some queries\n'
see index:0~526444
0 263223
0
see index:263221~526444
263221 394834
562865
see index:263221~394834
263221 329028
0
see index:329027~394834
329027 361932
562865
see index:329027~361932
329027 345480
562865
see index:329027~345480
329027 337254
0
see index:337253~345480
337253 341368
562865
see index:337253~341368
337253 339312
562865
see index:337253~339312
337253 338284
562865
see index:337253~338284
337253 337770
562865
see index:337253~337770
337253 337512
562865
see index:337253~337512
337253 337384
562865
see index:337253~337384
337253 337320
562865
see index:337253~337320
337253 337288
562865
see index:337253~337288
337253 337272
562865
see index:337253~337272
337253 337264
0
see index:337261~337272
337261 337268
562865
see index:337261~337268
337261 337266
562865
see index:337261~337266
337261 337264
0
see index:337263~337266
337263 337264
0
see index:337265~337266
337265 337266
562865
337264 337265
562865
! 337265
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 381210\n'
381210
b'Go ahead, ask some queries\n'
see index:0~381209
0 190605
164341
see index:0~190605
0 95303
164341
see index:0~95303
0 47653
0
see index:47650~95303
47650 71477
164341
see index:47650~71477
47650 59565
0
see index:59562~71477
59562 65521
164341
see index:59562~65521
59562 62543
0
see index:62540~65521
62540 64031
0
see index:64030~65521
64030 64777
164341
see index:64030~64777
64030 64405
164341
see index:64030~64405
64030 64219
164341
see index:64030~64219
64030 64125
0
see index:64124~64219
64124 64173
0
see index:64170~64219
64170 64195
164341
see index:64170~64195
64170 64183
164341
see index:64170~64183
64170 64177
0
see index:64176~64183
64176 64181
164341
see index:64176~64181
64176 64179
164341
see index:64176~64179
64176 64177
0
see index:64178~64179
64178 64179
164341
64177 64178
0
! 64179
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 372441\n'
372441
b'Go ahead, ask some queries\n'
see index:0~372440
0 186221
315606
see index:0~186221
0 93111
315606
see index:0~93111
0 46557
0
see index:46554~93111
46554 69833
0
see index:69832~93111
69832 81473
0
see index:81470~93111
81470 87291
0
see index:87290~93111
87290 90201
315606
see index:87290~90201
87290 88747
0
see index:88744~90201
88744 89473
315606
see index:88744~89473
88744 89109
0
see index:89108~89473
89108 89291
315606
see index:89108~89291
89108 89201
315606
see index:89108~89201
89108 89155
315606
see index:89108~89155
89108 89133
315606
see index:89108~89133
89108 89121
315606
see index:89108~89121
89108 89115
315606
see index:89108~89115
89108 89113
0
see index:89110~89115
89110 89113
0
see index:89112~89115
89112 89113
0
see index:89114~89115
89114 89115
315606
89113 89114
315606
! 89114
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'The number of coins in this batch are 473931\n'
473931
b'Go ahead, ask some queries\n'
see index:0~473930
0 236965
1021724
see index:0~236965
0 118483
1021724
see index:0~118483
0 59243
1021724
see index:0~59243
0 29623
1021724
see index:0~29623
0 14813
1021724
see index:0~14813
0 7407
0
see index:7406~14813
7406 11111
0
see index:11108~14813
11108 12961
1021724
see index:11108~12961
11108 12035
1021724
see index:11108~12035
11108 11573
1021724
see index:11108~11573
11108 11341
1021724
see index:11108~11341
11108 11225
1021724
see index:11108~11225
11108 11167
0
see index:11166~11225
11166 11197
1021724
see index:11166~11197
11166 11183
0
see index:11180~11197
11180 11189
0
see index:11188~11197
11188 11193
0
see index:11192~11197
11192 11195
0
see index:11194~11197
11194 11195
0
see index:11196~11197
11196 11197
1021724
11195 11196
0
! 11197
b"Correctly identified the faulty coin in this batch, let's keep going!\n"
b'Ahh the winner!! you have earned your reward, the holy piece of text that will lead you to your destination\n'
the
b'\n'
b"b'inctf{1f_y0u_c4n_dr3am_y0u_c4n_s34rch_1n_logn}'\n"

flagはinctf{1f_y0u_c4n_dr3am_y0u_c4n_s34rch_1n_logn} => if you can dream you can search in logn
lognで探索したいと思えば出来る。わかる。割と綺麗に(コードは汚いが)ルートに乗れた。

参加した感想

本当はnetwork pentest系の問題に取り組みたかったが与えられたovpnを利用したVPN内に攻撃対象のマシンが見つけられず断念してMISCに流れた。(network pentestのいい感じのwriteupあったら教えてください)
この問題を解いた前後で自分の中のソフトウェアに対する知識や理解が変わった(向上した)かというと否な気がするのでMISCを敢えて解かないという気概で今後はCTFに参加していきたい。