ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

Can-CWIC CTF2017 [Write-up]

Can-CWIC CTF2017にHarekazeとして参加し, 2127pで4位でした.
僕は2問解いて210p取得しました.
Write-upです.


[Prog] Tri it 0 (60)
nc 159.203.38.169 5672
早速やってみましょう.
表示されるのは Read https://en.wikipedia.org/wiki/Balanced_ternary と 何やら怪しげな数式.
適当に入力すると Wrong answer. と言われ終了, とりあえず上記のURLにアクセスします.

Balanced Ternary, 平衡三進数でした.
普通の三進法とは異なり, 0と1と-1を表すシンボル(T)で表現されます.
BTからDecへの変換は, 3n * [0 or 1 or -1] するだけですが, decimalからBalanced Ternaryにどうやって変換しようかとずっと悩んでいました..
下記のサイトが参考になりました.
http://www5e.biglobe.ne.jp/~emm386/2015/numeration/nb01.html

10進数 a に対して, a+1したものに通常の3進数を求める方法を適用します.
このとき, 商から-1して [-1, 0, 1] に揃えます. これを絶対値最小剰余と呼ぶそうです.

a, R =  floor( (a + 1) / 3),  (a + 1)%3 -1  

これをaが0になるまで繰り返し, Rを表示すればTBが得られます.
例えば a = 50 とすると

1 : a, R = floor(51 / 3), (51 mod 3) -1   # a = 17, R = -1
2 : a, R = floor(18 / 3), (18 mod 3) -1 # a = 6, R = -1
3 : a, R = floor(7 / 3), (7 mod 3) -1 # a = 2, R = 0
4 : a, R = floor(3 / 3), (3 mod 3) -1 # a = 1, R = -1
5 : a, R = floor(2 / 3), (2 mod 3) -1 # a = 0, R = 1

よって 50 は 1T0TT となります



以下solverです.

from pwn import *

rep = {'0':0, '1':1, 'T':-1, }
rep_de = { 0 : '0', 1 : '1',  -1 : 'T' }

def gen_decimal_num(balance):
  for _pow, ch in enumerate(balance[::-1]):
    yield ( (3**_pow) * (rep[ch]) )

def convert_to_balanced(num):
  bal = ""
  while num != 0:
    num, R = (num+1) / 3, ((num+1) % 3-1)
    bal += rep_de[R]
  return bal[::-1]

r = remote('159.203.38.169', 5672)
r.recvuntil('Read https://en.wikipedia.org/wiki/Balanced_ternary\n')

while True:
  fomula = r.recvuntil('\n')
  print(fomula)
  fomula = fomula.strip()
  polys = fomula.split(' + ')
  bal1, bal2 = polys[0], polys[1]
  #print(bal1, bal2)
  _sum = sum(gen_decimal_num(bal1)) + sum(gen_decimal_num(bal2))
  ans = convert_to_balanced(_sum)
  print(ans)
  r.sendline(ans)

数十回繰り返すのかと思ってたら2回で終わりました.
socket使うべきなんですがpwntools使いました. よくない


[Prog] Tri it 1 (150)
先ほどの問題, 続きがありました.
先ほどのFLAG{}以降を読み込むと, パワーアップした式が出てきます.
何度か読み込んでみると pol1 + (pol2 + pol3) * pol4 といった形式で出力されていたので, これはもう単純に部分抽出して計算するだけだなと思いsolver書いて実行してみると, なんと偶然連続で同じフォーマットで表示されていただけで, 括弧が増えたり位置が変わったりするようです. クリアしていくと項も増えます..

項の数も変化するとなれば正規表現で取り出すしかありませんね.
ということでsolverです. Tri it 0 の続きなので重要な部分のみ記述します.

pattern = r'[1|0|T]+'
while True:
    formula = r.recvuntil('\n')
    print(formula)

    reped = re.findall(pattern, formula)
    rep = [sum(gen_decimal_num(bal)) for bal in reped]
    for _rep, _reped in zip(rep, reped):
       ormula = re.sub(_reped, str(_rep), formula, 1)


    ans = convert_to_balanced(eval(formula))

    print(ans)
    r.sendline(ans)

項数がわからないので, '[1|0|T]+'に一致するパターンを全て抜き出し, それをdecimalに直して取得した数式に置換という方法になります. 数式さえ判れば eval(formula) で答え出せるので, フラグ出るまで繰り返しました. たまにWrong answerが出てましたがよくわからないです.
Tri it 0 は計算2回でFLAG出るので手計算でできなくもないですが, 今回は項がかなり増えてくるので難しいです.
確か17, 18回でフラグ出るんですが,

-(1011000 + T0T0TTT0 + (1001 + (1 + T1) * T0T1 * 1T101) * (1T0T11T + TT100100)) + (TT0 + (T + T0) * T10 * T1T01 + (1 + T1) * T * 1 * (T110 + 1TT10) * (T + 1T) * T1T01 * (10T1 + (1 + T1) * TT10 * 11111)) * (1TT01000 + T01000T01 + (1110 + (T + 0) * T10T1 * 11TT0) * (111100TT + T10TTTTT01))

を解かなきゃいけないので正規表現とeval()が正攻法だと思います.
そしてこの問題, さらに続きがあるのですが, 問題の意味がよくわからなかったのでやってません..


Cryptoも解きたかったのですが力及ばずでした..